Towards a portable lazy functional declarative debugger

Lee Naish Tim Barbour

(lee@cs.mu.OZ.AU, http://www.cs.mu.oz.au/˜ lee, trb@cs.mu.OZ.AU, http://www.cs.mu.oz.au/˜ trb)

Technical Report 95/27 Department of Computer Science University of Melbourne Parkville, Victoria 3052, Australia

Abstract

Declarative (or algorithmic) debugging is a promising technique for debugging lazy functional programs. This paper addresses two important reasons why it is not more widespread: the difficulty of writing a declarative debugger for a lazy functional language in the language itself and the efficiency of the debugger. Using the source language to implement the debugger is desirable for portability and we discuss the reasons why this is very difficult to do. We propose a system in which nearly all the code is in the source language but there is one function which must be written at lower level. We also show how this function can be the key to significantly improving the efficiency of declarative debuggers for such languages. Keywords: algorithmic debugging, referential transparency, i/o, monads, types, trace, transformation

1 Introduction

Traditional debugging methods such as diagnostic writes, tracing, break points et cetera are very difficult to apply to modern lazy functional programming languages. To obtain diagnostic output substantial parts of the program may have to be rewritten due to the i/o model of these languages. Traces are very difficult to understand due to the unintuitive execution order produced by lazy evaluation. Traditional break points are of little use since at the time a function is called its arguments are typically not evaluated. A promising solution to these problems is to use declarative debugging, which uses the declarative meaning of programs rather than the sequence of steps in the execution to locate bugs. Declarative debugging algorithms were first developed for diagnosing wrong and missing answers in Prolog [Sha83]. More recently the ideas have been adapted to diagnosing errors in lazy functional languages [NF94] [Nai93] and related languages [NB95] [Nai95]. These debuggers have two important disadvantages: they are not portable and they are unacceptably inefficient, especially in terms of space.

Most declarative debuggers for Prolog have been implemented in Prolog. This is easy to do and results in relatively portable debuggers. Declarative debuggers for lazy functional languages have so far been implemented at a lower level. In the case of Nilsson et al. the lazy functional language is implemented in C and the debugger is implemented in C. In the case of Naish et al. the lazy functional language, NUE-Prolog [Nai91], is implemented on top of Prolog and the debugger is implemented in Prolog. For portability, a debugger for a language should be implemented in the language itself. In this paper we discuss several reasons why this ideal is difficult, if not impossible to achieve efficiently with modern lazy functional languages. However, we propose a system in which nearly all of the code is written in the source language but a key function must be written at a lower level. We also show how this function can be used to make debuggers for lazy functional languages much more efficient.

The paper is structured as follows. We first give a high level overview of declarative debugging of lazy functional programs. Then we present the difficulties involved in implementing a declarative debugger for a lazy functional language in a lazy functional language. Next we describe our general approach, including a specification of the main low level primitive. We also discuss how this primitive can be used to solve the most important efficiency problem in existing debuggers. Finally we summarize our proposal and how it differs from other approaches.

2 Declarative Debugging

A general scheme for declarative debugging is proposed in [Nai95]. Here we describe how it is applied to diagnosing wrong answers in lazy functional languages. The evaluation of an expression is represented by a tree (called an evaluation dependence tree in [SN95]). To simplify the presentation we will assume that the top level expression which is evaluated is simply mainbug. Each node in the tree contains two expressions. The root node contains the expression mainbug and the result returned by mainbug. In general, a node contains a call to a function f a_{1} a_{2} … and the result computed. The arguments a_{1} a_{2} … and result are in the form they were eventually reduced to in the evaluation of mainbug. Each node has a child for each function call in the right hand side of the equation it was matched with (if any). Certain functions, for example arithmetic, may be considered primitive and do not result in tree nodes. Consider the following program (we will use Haskell syntax throughout).

mainbug = take 2 ones
-- returns first n elements of a list
take _as | as == []
  = []
take n _| unity n    -- should be: zero n
  = []
take n as
  = hd as : take (n-1) (tl as))
-- infinite list of ones
ones = 1 : ones
unity n = (n == 1)
hd (a:_) = a
tl (_:as) = as

The evaluation of mainbug incorrectly returns [1] due to the bug in the second base case of take. The value of ones is an infinite list of ones but due to laziness it is only partially evaluated. The tree for this computation is as follows:

take 2 (1:ones) = [1]

\underline{mainbug = [1]}

take 1 ones = []

ones = 1:ones

hd (1:ones) = 1  tl (1:ones) = ones  ones = ones

unity 1 = true

The underlined nodes in the tree are erroneous — the result of the function call is incorrect, indicating a bug in a function called in that subtree. A node is buggy if it is erroneous but has no erroneous children, indicating a bug in the definition of the function called at that node. The essence of declarative debugging is the search for buggy nodes. A simple top-down debugger can be defined as follows. It can return a list of all “topmost” buggy nodes but lazy evaluation leads to a top-down left to right search for the first such node [Nai95].

debug :: Node -> [Node]
debug n | not (erroneous n)
  = []
debug n | erroneous n && bs /= []
  = bs
    where bs = concat (map debug (children n))
debug n | otherwise
  = [n]
erroneous :: Node -> Bool
children :: Node -> [Node]

The definition of erroneous requires an oracle which knows the intended behaviour of each function. Normally the oracle is implemented by querying the user. The definition of children will depend on the representation of the tree. This very simple debugger can be enhanced to provide better search strategies (to reduce the number of questions to the user) or to allow browsing etc.

3 The problems

Implementing a declarative debugger for Prolog in Prolog is easy. Similarly, implementing a declarative debugger for a strict functional language in that language can be easy. However, there are several obstacles to writing declarative debuggers for and in modern lazy functional languages. The first difficulty is building the tree, particularly representation of unevaluated expressions. So far this has been done at the language implementation level (C or Prolog), resulting in unportable debuggers. Another possibility is to use a meta interpreter but this results in an order of magnitude slowdown and greatly increased memory consumption. An attractive alternative to both these methods is to use a source to source transformation of the program so functions return the original value plus a representation of the tree. We now outline the key difficulty with this approach and several other problems which must be overcome.

3.1 Laziness and referential transparency

Modern lazy functional languages are referentially transparent: equals can be replaced by equals and an expression denotes the same value wherever it occurs. For example, the occurrence of ones in take 1 ones denotes the same value as the occurrence of ones in take 2 ones. However, in a lazy language the evaluation of the two occurrences of ones is different. The information required to debug an expression depends on the evaluation, which depends on the context in which the expression is evaluated, not just on the value of the expression. Thus a simple source to source transformation which preserves referential transparency cannot produce the desired results. The original declarative debugger for NUE-Prolog was almost entirely “pure” but had a single occurrence of the non-logical var/1 at a key point for precisely this reason. The approach we propose uses a transformation which relies on a new primitive which is not referentially transparent and therefore cannot be defined in the source language. The primitive must not force further evaluation of an expression and hence returns different results depending on how much the expression has been evaluated previously.

3.2 Strong typing

Unevaluated expressions can appear in arbitrary parts of user-defined data types. In order to display questions to the user, representations of partially evaluated expressions must be analysed by the debugger. For example, the debugger may need to ask if tl 1:1: ones correctly evaluated to 1: ones , where ones is some representation of an unevaluated call to ones. At the implementation level this is not a problem and such data structures were used in the original NUE-Prolog debugger. However, at the source level 1:1: ones is not of type [Int]. We would prefer to avoid complicated type analysis of the program and construction of new types for the transformed program. The transformation proposed in [SN95] uses existential types which are not widely supported and hence should also be avoided. Also, for the debugger to be written without knowledge of the program, the representation of terms in the program must be independent of the types used in the program. This leads us to a representation of terms which has a fixed set of constructors and ultimately relies on strings. For efficiency, the transformed program should use the types of the original program for computing results and use the string-based type only for passing information to the debugger.

3.3 Laziness and multiple representations

There is a potential problem with separating the original return values from the representation which is passed to the debugger. With the original program, the computation is driven by the need to fully evaluate the top level expression. In the transformed program the computation must be driven by evaluation of an equivalent expression. However, this evaluation does not need the data structures which are to be passed to the debugger and so those data structures will not be constructed. We must be careful with the way this behaviour interacts with the behaviour of the new primitive which does not further evaluate expressions!

3.4 Input/Output

Various mechanisms have been proposed for i/o in lazy functional languages. Due to the evaluation order it is important that the i/o mechanism is referentially transparent. I/o information must be passed implicitly or explicity to all parts of the program which do i/o. One consequence of this is that the simple elegant coding of the top-down debugger must be changed totally if erroneous uses i/o. Conceptually, erroneous is simply a function which “knows” the intended behaviour of all functions in the program. In practice it produces output (questions to the user) and requires input (the answers) in order to operate (it also has state, which leads to very similar problems). It is also essential that a declarative debugger be able to debug programs that use i/o. Producing output is what drives the evaluation of lazy functional program; a program which does no output is likely to terminate immediately. For practical reasons, the ability to debug programs which use input, possibly interactively, is also important.

One often used approach to debugging is to run the program and dump a trace (the tree in this case) into a file. This requires a mechanism to ensure the tree is only output after the rest of the execution terminates, but simplifies i/o handling since the program and the debugger executions are separated. However, the tree can be huge and simple textual representations of the tree are especially inefficient. If a large data structure is used in many function calls it may be printed to the file many times. Even if the representation is optimised, the whole tree must be printed even though only a small part of it may be searched in order to find the bug.

A more flexible and efficient alternative is to run the program and the debugger together. With some care the tree can be generated lazily or possibly even incrementally (see below). In general, the program and the debugger are both interactive and so some way of separating the i/o of the program from the i/o of the debugger is necessary. The “top level” of the program being debugged is no longer the top level of the system and it does not have exclusive use of the i/o streams. If it was able to close the output stream or consume all of the input stream the debugger could not operate.

3.5 Single threading

Many functional programs manipulate some data structures in a single threaded way. After the initial creation of the data structure there may be several new versions, each computed from the previous version. The code is such that creation of version i+1 uses the only reference to version i. Programming constructs such as monads can be used to enforce singled threading of data structures. Functional programming systems can then use such things as imperativestyle destructive assignment of the data structure in a referentially transparent way [PW93] [LP94]. For debugging it is generally necessary to inspect the intermediate versions of data structures since that is where bugs may be manifest. Thus debugging and single threading are in direct conflict. If single threading was used just to improve efficiency then it could be sacrificed for debugging purposes. However, in languages such as Haskell the monadic (single threaded) style is essential for i/o and other features — it is not just a matter of efficiency.

3.6 Memory consumption

Memory consumption of the debugger does not make writing the debugger difficult but it does impact on practical application of the debugger. The most obvious additional space usage is for the construction of he tree, especially if it uses a relatively inefficient representation of the program data structures to stay within the type system. To quote from the conclusion of [NF94]: “… (the debugger) cannot be considered to be a practically usable system, mainly due to the prohibitively large trace size… ”. Lazy evaluation can actually help us here if we are able to construct the tree lazily. The debugger typically searches only a small percentage of the tree in order to find the bug so the actual space required for the tree may not be unreasonable. The tree size can also be reduced by simply not building nodes for calls to “trusted” functions (such as library functions), as described in [Nai95]. However, even ignoring the size of the tree the debugger can result in a huge increase in memory consumption because it introduces a “space leak”. Garbage collection of intermediate data structures is not posible since the debugger may be required to display these data structures. A program that normally runs in constant space due to garbage collection may run in O(N) space for debugging purposes.

The normal solution to this problem in declarative debuggers for languages such as Prolog is to incrementally construct the tree. Initially only the top level(s) of the tree are built and the lower levels of the computation use the original code which does not build a tree. A further advantage of this method is that the initial execution is faster so the programmer does not have to wait so long for the first question from the debugger. If the debugger reaches a leaf of the (partial) tree then the sub-computation at that point is re-executed to build (the top levels of) the subtree. Space-time tradeoffs are analysed in [Pla84]. Re-execution in Prolog or strict functional languages is easy because the execution is usually independent of the context. Failure of sub-computations in Prolog with coroutining is dependent on the context, making declarative debugging of such programs difficult [Nai92]. Similarly, in lazy functional languages the extent to which an expression in a subtree is evaluated depends on what values are needed to evaluate the top level expression. It may be unacceptably inefficient to re-execute the whole program each time we need to incrementally extend the tree, as suggested in [NF94].

4 Our proposal

We now present our approach to solving (most of) the problems presented above. We first describe a source to source transformation and the primitive function it relies on. Then we discuss how currying and higher order functions interact with the transformation. Next we describe our (partial) solution to the problems of i/o, including the top level of the debugging system. Finally we discuss two ways in which memory consumption can be greatly reduced.

4.1 The transformation

As mentioned in Section 3, functions are transformed so that they return a tuple comprising the original function result and a tree representing the computation of that result. The computation of a function application is represented by a string naming the function, a list of representations of the arguments the function was applied to, a representation of the function result, the number of the matching equation (for reporting bugs), and a list of subtrees, one for each call in the equation. The representation of an argument or result of a function is of type Term. It is produced by calling the primitive dirt, desribed in the next section. A Haskell definition of the tree type is:

data Tree = Node String [Term] Term Int [Tree]

When transforming an equation we initially introduce two new variables to denote the value of the right-hand side and the tree. For each function call in the right-hand side we introduce a further two variables, denoting the return value and computation tree for that call. Since each call is now returning a pair, of which only one member is the original function result, a where clause is used to separate the values from the computation trees. The return value is used in place of the call and the tree is used to build the tree of the calling function.

We now describe the transformation precisely. Given an equation (number k) of the form f a_{1} a_{2} … a_{n} = r the transformation has three stages:

1. Rewrite the equation as

f a_{1} a_{2} … a_{n} = (v, t)

       where

v = r

2. Apply the following step as many times as possible. Let g be a function of m arguments. If g b_{1} b_{2} … b_{m} is an innermost function application in r replace it by v_{i} and add the following equation to the where clause (where v_{i} and t_{i} are new variables)

(v_{i}, t_{i}) = g b_{1} b_{2} … b_{m}

3. Add the following equation to the where clause (where t_{1}, …, t_{p} are the t_{i} introduced above)

t = Node "f" [dirt a_{1}, dirt a_{2}, …, dirt a_{n}] (dirt v) k [t_{1}, …, t_{p}]

For example, the last equation in the definition of take given earlier would be transformed into the following:

take n as = (v, t)
  where
    v = v_hd : v_take
    (v_hd, t_hd) = hd as
    (v_tl, t_tl) = tl as
    (v_take, t_take) = take (n-1) v_tl
    t = Node "take" [dirt n, dirt as] (dirt v) 4 [t_hd, t_tl, t_take]

The transformation is very similar to the flattening transformation used in NUE-Prolog and its debuggers. The transformation described in [SN95] is also similar though the “plumbing” (extra variables) is hidden by higher order functions. The key difference is our use of dirt. Dirt always returns a Term, avoiding problems with strong typing, and also solves the problem of referential transparency, as we describe later. The transformation of [SN95] relies on existential types and uses only referentially transparent functions. The resulting tree is used by the debugger to construct another tree and this requires functions that are not referentially transparent. Our transformation avoids having two trees and also allows the debugger code to be “pure”, so declarative debugging can be applied to (new versions of) the debugger.

4.2 The primitive function

The primitive function, dirt^{1}, takes an expression which may be partially evaluated and returns a representation of the expression. The representation is of type Term and there is some flexibility in the way it is defined. There are three fundamental requirements for dirt:

1. It must only be evaluated on demand. The structure of the debugger will ensure that the value of a call to dirt is only demanded after the normal execution of the program has finished. If dirt is called eagerly its argument may be insufficiently evaluated.

2. It must not further evaluate its argument. If dirt caused further evaluation of its argument the computation of the transformed program would not be equivalent to the computation of the original program. For example, the transformed program may loop where the original program terminated.

3. It must return a representation of its argument that contains sufficient information for erroneous to determine if the function call corresponding to a tree node behaved correctly. One mimimal representation is simply a string with unevaluated parts shown as underscores. String concatenation could be used in erroneous to costruct a suitable question for the user. For example, a node containing "tl", [dirt (1:1: ones )] and

     dirt (1: ones ) could result in the question "Is tl (1:1:_) = 1:_correct?".

There are advantages in Term being a data type which better reflects the structure of the expression (a tree). This makes it easier to implement user-defined methods of displaying expressions in questions and should make the other use we have for dirt (see later) easier to implement. For example, we could use the representation for expressions suggested in [SN95] which uses strings to represent constructor names and a different constructor for unevaluated expressions. The questions used in [Nai93] explicitly quantify variables and would require additional information so (representations of) unevaluated calls could be compared for equality. At the implementation level there should be a unique address associated with each unevaluated call and this could be mapped to an integer.

4.3 Higher order functions and currying

The transformation defined earlier can be used for many common uses of higher order functions. For example, if map is defined in the normal way then an expression such as map (take 2) [[...],...] will yield an appropriate tree. Nodes containing a call to map will have two children: one for the call to take and one for the recursive call to map. One difficulty is that dirt must return an appropriate representation for the function which is argument to map.

1Display Intermediate Reduced Term

This is trivial in NUE-Prolog since functions are represented as Prolog terms. However, it may require additional support in some systems. An alternative is to have a more complex (and less efficient) transformation such as that discussed in [SN95].

Our transformation (and also that of [SN95]) generally cannot be used if function definitions are curried. The transformed definition of take expects hd to be of type [a]->(a,Tree), which is the type of the transformed version of the normal definition of hd. However, suppose hd was defined as follows:

    hd = hd1
    hd1 (a:_) = a

The transformed version of hd would be as follows; its type ([a]->(a,Tree),Tree).

    hd = (val, tree)
      where
        val = hd1
        tree = Node "hd" [] (dirt val) 6 []

It is possible to solve this problem by applying a more complex transformation. Functions of type a->b->c in the source would be of type (a->(b->(c,Tree),Tree),Tree) in the transformed program (rather than type a->b->(c,Tree) as in the transformation we have described). This makes the resulting program significantly larger and less efficient and typically results in many useless nodes in the tree. An intermediate transformation which only handles currying when necessary is desirable. Whether this can be done without detailed analysis of the program is under investigation.

4.4 Input/Output

For simplicity, and because some lazy functional languages have no more sophisticated i/o mechanism, we are currently using stream i/o. The top level of the program is assumed to be a function from the list of characters in the input to the list of characters in the output. The lazy evaluation is driven by the desire to print the output and input is read lazily, allowing interactive programs. We plan to investigate other i/o models in the future.

The object program i/o and debugger i/o are separated as follows. The output of the debugging session is the output of the object program concatenated with the output of the debugger. Thus, by the time the output of the debugger is needed, the object program output has been completely evaluated, though the tree has not. The output of the debugger is the sequence of questions asked by the oracle followed by a description of the bug. The output of these questions drives the construction of the tree.

The input stream is split into two parts. The first part is used as the input to the object program and the second part is used as the input to the debugger. To determine where to split the input stream we require the user to enter a special escape sequence. To input the escape character to the object program it must be typed twice but in all other respects the interactive i/o behavior of the program will be unchanged. If the object program does not read until the end of the input stream then the extra escape sequence seems unnecessary. However, there is no clean portable way of “taking control” of the unused portion of the input stream when a function terminates. This problem is normally solved by the function itself returning the unused input. However, we cannot expect every function we want to debug to be written in this way. The top level of the debugging system could be coded as follows:

main I =
    PrgO ++ debugger DebI Tree
    where (PrgI, DebI) = split I
          (PrgO, Tree) = mainbug PrgI

The original code for the debugger had to be substantially rewritten in order for erroneous to use stream i/o. Most functions must return a string (the list of questions followed by the bug description) and have a string (the list of answers the user types) as one of the inputs. Substantial care must be taken in order to get the correct interleaving of interactive input and output, as is typical with lazy functional languages. It is simplest to explicitly only search for one bug rather than rely on laziness.

At this stage we have no solution to the problem of debugging code which uses monads or similar techniques. The most severe problem is monadic i/o. The bulk of the code in most programs doesn’t use i/o and this can be debugged without problems if the way in which it is called can be reproduced without using explicit i/o. However, at least an ad hoc solution to the problem monadic i/o is highly desirable.

4.5 Memory consumption

Our debugger evaluates the tree lazily, thus minimising that particular space problem. We have also found that dirt is the key to solving the space leak problem. Consider the (buggy) evaluation of take 3 (take 5 ones). One of the nodes in the tree will correspond to take 5 (1:1: ones ) evaluating to 1:1: ones . The tree node will contain the representations of these two expressions, as returned by dirt. This is enough information to precisely reconstruct the subtree — it is not necessary to re-execute the whole computation to provide the correct context. The only context information which is important is that the first two elements of the output list were demanded and the tail of the list was not. The subtree can be reconstructed by comparing the function call, with unevaluated parts replaced by arbitrary expressions, with the evaluated parts of the result. In this case we compare take 5 (1:1:expr) with 1:1:anything. The comparison will drive the evaluation exactly the required amount.

To incrementally construct the tree we can use a slightly different program transformation. Transformed functions accept an additional argument which specifies how much of the tree to generate (the depth, for example). When a depth of zero is reached a special tree node is returned and the original (untransformed) versions of the functions are called. These will execute efficiently without space leaks. An added advantage of this method is that we do not have to be too careful about the efficiency of the transformed code since it is only used at the top levels of the computation. The top levels of the computation could even be interpreted, avoiding program transformation entirely. When the debugger reaches one of the special nodes in the tree it re-evaluates the expression to build the subtree as described above. A special node can be seen as an implicit representation of the subtree and the re-evaluation can be done transparently inside the children function [Nai95]. We are currently investigating the details of this scheme further, particularly ways of encapsulating the re-execution mechanism in strongly typed languages.

5 Implementation status

We are currently experimenting with prototype debuggers for the lazy functional subset of NUE-Prolog. Because NUE-Prolog is untyped, has a simple interface to (impure) Prolog and is implemented in NU-Prolog, it is an ideal system for rapid prototyping. For example, in our first prototype dirt was defined in one line and erroneous used imperative IO by calling Prolog. In subsequent versions the implementation of dirt has been changed so it returns terms that would be acceptable in typical strongly typed languages. The rest of the debugger is written in a very simple portable style. Stream IO has been implemented using the coroutining facilities of NU-Prolog [TZ886]. The debugger has been used to find bugs in small programs, including buggy versions of the debugger itself. We have also implemented a version of the debugging system which uses a different transformation and incrementqlly constructs the tree. This will be described in more detail in a future report. Ultimately we hope to port the system to the Glasgow Haskell Compiler, with the help of the functional programming group at Glasgow.

6 Conclusion

Laziness and referential transparency are two language features which make declarative debugging very attractive. Unfortunately, they also make implementation of declarative debuggers very difficult. Other difficulties arise due to strong typing and i/o, particularly monadic i/o, and efficiency is also a major practical concern. Our approach to solving these problems is based on a familiar style of program transformation which results in functions returning a representation of the computation as well as the normal result. The new aspect of our transformation is the use of the function dirt which is not referentially transparent. The debugger architecture proposed in [SN95] is closely related to ours. Advantages of our approach include: the transformation does not need existential types, no intermediate tree is constructed and the code for the debugger does not contain any “impure” features (allowing it to be debugged more easily). We have addressed the efficiency issues, using laziness to minimize the space taken by the tree and showing how dirt can be used to help build the tree incrementally. We also have a partial solution to the i/o problems, using stream i/o. There is still much work to be done, but we have made significant progress towards a (reasonably) portable practical declarative debugger for strongly typed lazy functional languages.

References

[LP94] John Launchbury and Simpon L Peyton Jones. Lazy functional state threads. ACM SIGPLAN Notices, 29(6):24–35, Jun 1994.

[Nai91] Lee Naish. Adding equations to NU-Prolog. Proceedings of The Third International Symposium on Programming Language Implementation and Logic Programming, pages 15–26, August, 1991.

[Nai92] Lee Naish. Declarative diagnosis of missing answers. New Generation Computing, 10(3):255–285, 1992.

[Nai93] Lee Naish. Declarative debugging of lazy functional programs. Australian Computer Science Communications, 15(1):287–294, 1993.

[Nai95] Lee Naish. A declarative debugging scheme. Technical Report 95/1, Department of Computer Science, University of Melbourne, Melbourne, Australia, February 1995.

[NB95] Lee Naish and Timothy Barbour. A declarative debugger for a logical-functional language. In Graham Forsyth and Moonis Ali, editors, Eighth International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems — Invited and Additional Papers, volume 2, pages 91–99, Melbourne, June 1995. DSTO General Document 51.

[NF94] Henrik Nilsson and Peter Fritzson. Algorithmic debugging of lazy functional languages. Journal of functional programming, 4(3):337–370, 1994.

[Pla84] David A. Plaisted. An efficient bug location algorithm. In Sten-Åke Tärnlund, editor, Proceedings of the Second International Logic Programming Conference, pages 151– 157, Uppsala, Sweden, July 1984.

[PW93] Simon L Peyton Jones and Philip Wadler. Imperative functional programming. In Proceedings of the Twentieth Annual ACM Symposium on Principles of Programming Languages, pages 71–84, Jan 1993.

[Sha83] Ehud Y. Shapiro. Algorithmic program debugging. MIT Press, Cambridge, Massachusetts, 1983.

[SN95] Jan Sparud and Hendrik Nilsson. The architecture of a debugger for lazy functional languages. In Mireille Ducassé, editor, Proceedings of AADEBUG’95, Saint-Malo, France, May, 1995.

[TZ886] NU-Prolog reference manual, version 1.0. Technical Report 86/10, Department of Computer Science, University of Melbourne, Melbourne, Australia, 1986.