A Declarative Debugging Scheme

Lee Naish

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

Technical Report 95/1

Department of Computer Science University of Melbourne Parkville, Victoria 3052 Australia

We present a very simple but flexible declarative debugging scheme. A declarative debugger can be defined in Prolog with a single clause and relies on the definition of just two additional predicates. With suitable definitions of these predicates the debugger can diagnose several classes of bugs in many languages. We give examples of diagnosis of wrong answers in functional, relational and object oriented languages as well as missing answers in relational languages and calls which are not well-defined in functional languages. By using declarative semantics of programs, the debugger is able to hide complex execution mechanisms such as unification, backtracking, coroutining, parallelism, higher order functions, lazy evaluation, message passing and inheritance.

Keywords: declarative algorithmic debugging, Prolog, lazy higher order function, object oriented.

1 Introduction

One of the major advantages of many modern high level programming languages is their support for the separation of concerns of correctness and efficiency. Understanding what a program computes can be separated from understanding how it is computed. In lazy functional languages we can use infinite data structures on our finite memory machines. In logic languages we can reason about truth, in our interpretation, rather than construction of proofs. In constraint languages we can specify constraints without knowing how they are satisfied. In object oriented languages we can specify inheritance without knowing what compilation or runtime mechanisms are used to implement it. A language can be implemented in parallel without our conceptual model of the language changing.

Traditional debugging methods such as diagnostic writes, tracing, break points et cetera are based on how programs execute, that is, their procedural meaning. There are two important drawbacks of this. First, separating the concerns of correctness and efficiency cannot be done during program development. Second, with languages that support complex execution mechanisms debugging becomes very difficult. For example, lazy evaluation, backtracking, coroutining and parallelism all result in complex interleaved execution of conceptually simple programs.

These problems can be largely overcome by basing the debugging method on the declarative meaning of programs rather than the procedural meaning. Programs can often be written without detailed knowledge of how they execute and declarative debugging techniques can be used to diagnose bugs while hiding the complexities of the execution from the programmer. Declarative debugging algorithms were first developed for diagnosing wrong and missing answers in Prolog [Sha83], a relational language. More recently the ideas have been adapted to diagnosing errors in lazy functional languages [NF92] [Nai93] and combined relational and functional languages [NB94].

In this paper we view declarative debugging more abstractly than previous presentations and give a simple but very general scheme for declarative debugging. The scheme can be applied to multiple classes of bugs in a variety of languages. As an example, we describe what we believe is the first declarative debugger for an object oriented language. The scheme has also clarified exactly what classes of bugs are found and simplifies the proof of correctness of the debugger.

The rest of this paper is structured as follows. We first discuss wrong answer diagnosis for Prolog. Next we present our scheme which a generalization of wrong answer diagnosis for Prolog and give a very simple top-down debugger. Several instances of the scheme are then described, including several languages and classes of bugs. We conclude by summarising the advantages of our scheme.

2 Wrong answers in Prolog

We will illustrate declarative wrong answer diagnosis of Prolog programs with the following version of insertion sort. The insert procedure bas a bug which leads to elements of the input list sometimes not appearing in the output list. For example the query isort([3,1,2],X) results in the answer X=[1,3].

    % insertion sort
isort([], []).
isort(N.Ns, Ss) :-
    isort(Ns, Ss1),
    insert(N, Ss1, Ss).
    % insert number into sorted list
insert(N, [], [N]).
% insert(N, S.Ss, N.S.Ss) :- % correct
insert(N, S.Ss, N.Ss) :-    % bug
    N =< S.
insert(N, S.Ss0, S.Ss) :-
    N > S,
    insert(N, Ss0, Ss).

The computation of the wrong answer can be described using a proof tree [Llo84]. Each node in the tree contains an atom which was proved in the computation. If an atom H in a node is derived using the clause instance H : −B_{1}, B_{2}, ... then the children of the node contain the atoms B_{1}, B_{2}, .... The leaves of a proof tree contain atoms which are instances of facts in the program or system predicates. Note that proof trees are independent of the computation rule and search strategy and so wrong answer diagnosis algorithms based on proof trees can work with any combination of chronological or intelligent backtracking, or-parallelism, coroutining, and-parallelism, memoization and bottom-up evaluation. The following is the

proof tree for isort([3,1,2],[1,3]).

isort([3,1,2],[1,3]) insert(2,[],[2])  1=<2 insert(1,[2],[1]) isort([1,2],[1]) isort([2],[2])  3>1  insert(3,[],[3]) insert(3,[1],[1,3]) isort([],[])

It can be seen that the atom at the root of the tree was derived using the clause instance:

isort([3,1,2],[1,3]) :- isort([1,2],[1]), insert(3,[1],[1,3]).

Declarative debugging relies on the programmer having an intended interpretation of the program. That is, some ground atoms are considered true and the rest are considered false. The atoms in the tree printed in bold are false in the intended interpretation of the program and correspond to wrong answers. We refer to these nodes as erroneous nodes. Atoms in proof trees can contain variables. Such nodes are considered erroneous if the atoms are not valid (true for all instances) in the intended interpretation. Declarative debugging can be formalised with the help of the following definition.

Definition A node in a tree is buggy if it is erroneous but has no erroneous children.

For wrong answer diagnosis of Prolog, the atom in a buggy node is the head of an incorrect clause instance. Each atom in the body of the clause (the children) is valid but the head is not. This implies that the clause (interpreted as a universally quantified implication) is not true in the intended interpretation. In the example above there is one buggy node and the corresponding incorrect clause instance is:

insert(1,[2],[1]) :- 1 =< 2.

Declarative debugging can be thought of as searching a tree for a buggy node. To determine if an node is erroneous an oracle is used. Often the oracle is the programmer, who is asked questions about the validity of atoms, though a runnable specification of the program can also be used [ET83] [DL87] [DNTM89] [KKMH89]. This is particularly useful when the size of data structures makes questions difficult to comprehend.

To illustrate a typical declarative debugging session we use the NU-Prolog Debugging Environment (NUDE) [NDZ89]. NUDE uses a top-down search of the tree and (optionally) prints the clause instance used at each stage. The oracle is the programmer.

  1% nude isort.nl
  NU-Prolog 1.6.4
  1?- isort([3, 1, 2], X).
  X = [1, 3] w
  wrong isort([3, 1, 2], [1, 3]).
  Do static analysis? n
  Do dynamic wrong answer analysis?
  isort([3, 1, 2], [1, 3])    Valid? n
  Clause instance used:
  isort([3, 1, 2], [1, 3]) :-
      isort([1, 2], [1]),
      insert(3, [1], [1, 3]).
  isort([1, 2], [1])    Valid? n
  Clause instance used:
  isort([1, 2], [1]) :-
      isort([2], [2]),
      insert(1, [2], [1]).

                                       isort([2], [2])    Valid?
                                       insert(1, [2], [1])    Valid? n
                                       Clause instance used:
                                       insert(1, [2], [1]) :-
                                           1 =< 2.

                                       Incorrect Clause Instance:
                                       insert(1, [2], [1]) :-
                                           1 =< 2.
                                       Matching Clauses:
                                       insert(N, [S|Ss], [N|Ss]) :-
                                           N =< S.
                                       Do you want to edit insert/3 ?

3 The debugging scheme

The scheme we propose is a simple generalization of diagnosing wrong answers in Prolog programs by searching the proof tree for a buggy node. We assume the computation can be represented by some finite of tree (not necessarily a Prolog proof tree) and there is some suitable definition of a node being erroneous (not necessarily the atom in the node not being valid).

Essentially the scheme assumes that a computation can be decomposed hierarchically into subcomputations (represented as a tree) and the correctness of the result of each subcomputation can be determined. The tree definition is formalized by the predicate child(N, Child), where the depth and branching factor of the tree are finite. The definition of erroneous is formalized by the predicate erroneous(N). Buggy nodes can be defined in terms of these predicates (we use NU-Prolog syntax [Nai86]).

buggy(N) :-
    erroneous(N),
    not some [N1] (child(N, N1), erroneous(N1)).

A declarative debugging algorithm is simply a tree search. It is sound if the node(s) returned are buggy. Any algorithm which uses exhaustive search can be proved complete using the following proposition.

Proposition A finite tree in which the the root is erroneous has at least one buggy node.

Proof Trivial □

The search order may be determined by heuristics [Sha83] [PC88] [Nic88]. Usually the search terminates when the first buggy node is found, so changing the search order may have a dramatic affect on the number (and complexity) of queries to the user. This is normally the main criterion on which declarative debugging algorithms are based.

Many debuggers use a top-down search which only visits nodes whose parents are erroneous. The following code implements a very simple but effective top-down debugger. The procedure debug is called with the root of the tree and it returns a buggy node (multiple buggy nodes can be returned on backtracking). Finer points related to implementation are discussed in the next section.

debug(Root, Bug) :-
    erroneous(Root),
    (if some [Child, Bug1] (
        child(Root, Child),
        debug(Child, Bug1))
    then
        Bug = Bug1
    else
        Bug = Root
    ).

This debugger is not guaranteed to find all buggy nodes in a tree. In particular, buggy nodes which are descendants of nodes which are not erroneous will not be found (this situation occurs when a sub-computation has errors internally but still returns the correct result). However, if the root of the tree is erroneous the top-down debugger will find at least one buggy node.

Definition A tree node is a topmost buggy node if it is buggy and all its ancestors are erroneous.

Proposition A finite tree has at least one topmost buggy node if and only if the root is erroneous.

Proof Trivial □

Proposition (Soundness and completeness of the top-down debugger) If the child relation defines a finite tree the top-down debugger returns all top-most buggy nodes and only topmost buggy nodes.

Proof We use induction on the maximum depth of recursion (which is bounded by the depth of the tree). For a depth of one, if the root is not erroneous there is no top-most buggy node and debug fails immediately. Otherwise there are no children of the node so the root is buggy and is returned (via the else branch).

For a depth of k > 1 the root node must be erroneous and each recursive call to debug has depth at most k − 1. If a recursive call succeeds then Bug1 must be a topmost buggy node of a subtree and therefore a topmost buggy node of the whole tree and it is returned (note that NU-Prolog if-then-else allows the condition to return multiple answers). If all recursive calls fail then no children are erroneous so the root node is a topmost buggy node and it is returned. □

The top-down debugger can also be coded very simply in a functional language. Lazy evaluation of the functional program below is equivalent to a backtracking search using the NU-Prolog program above.

>debug A
>    = [],    if ~erroneous(A)
>    = Bs,    if  erroneous(A) & Bs ~= []
>    = [A],   otherwise
>      where Bs = concat (map debug (children A))

4 Instances of the scheme

We now present concrete instances of the debugging scheme for diagnosing several kinds of bugs in several languages. This illustrates the flexibility of the scheme and may provide some useful ideas for constructing other instances of the scheme.

4.1 Prolog

4.1.1 Wrong answers

We have already presented how the scheme applies to diagnosing wrong answers in Prolog code. Here we discuss some related work, an improved definition of the class of bugs found and some implementation details. The top-down debugger we have presented is very similar to the debugger described in [Nai93]. That debugger is a more abstract version of previous wrong answer diagnosers and is able to diagnose several kinds of errors in relational (Prolog) and functional code [NB94]. It relies on three predicates, valid, successful clause and c member. The debugger presented here is even more abstract: valid is a special case of (not) erroneous and the other two predicates combined are a special case of child. By using more abstraction the debugger can be even more general and proved correct more easily.

By using this instance of the debugging scheme and our general definition of buggy nodes, we can arrive at the following definition.

buggy(A) :-
    not valid(A),
    successful_clause(A, B),
    valid(B).

This is a weaker version of the definition of an incorrect clause instance A:-B given in [Llo87] and [Nai92] which insists that A must be unsatisfiable. Unsatisfiability is overly restrictive and causes problems for debugging goals with non-ground answers. NUDE has some unfortunate hacks for precisely this reason.

The main implementation decision to be made in a debugger based on our scheme is the representation of the tree. For reasons which will become obvious, the representation of nodes in a Prolog proof tree we suggest has a tag, wp, and a Prolog atom with a computed answer substitution applied. We will write this as wp(Atom). The implementation of erroneous must check that the atom is not valid in the intended interpretation. This can be done by asking the user (preferably storing the answer in a database so questions need not be repeated) or using a runnable specification.

There are two main ways in which child can be implemented. The first is using an explicit representation of the proof tree. The tree can be represented as a pair: wp(Atom)

- Children, where Children is a list of subtrees. The proof tree can be constructed by a meta interpreter [SS86] or by transforming the program [BN94]. Children of a node can be found by simply matching members of the list. The second implementation technique is to use the atom to implicitly represent its own proof tree. In order to find the children the atom must be re-executed to find a matching clause with a successful body. The children can then be extracted from the body of the clause instance. The time/space tradeoff of these two techniques is analysed in [Pla84].

For the purposes of debugging, the proof tree can be slightly simplified. It is not necessary to store any nodes corresponding to system predicates as these presumably cannot be erroneous. Similarly, constructs such as disjunction need not represented. If an atom A succeeds using clause containing a disjunction then the atoms in the disjunct which succeeded should be children of A in the proof tree.

If the representation of the proof tree is not ground then the code we have given for the debugger may flounder. Due to this and efficiency considerations it is more practical to use the non-logical Prolog conditional -> rather than the NU-Prolog if-then-else. The debugger is then guaranteed to return a top-most buggy node if one exists but may not return all such nodes.

4.1.2 Missing answers

Missing answer diagnosis in Prolog is more difficult than wrong answer diagnosis, especially when there may be coroutining (see [Nai92]). However, our scheme can be used for diagnosing missing answers in Prolog as follows. Each node in the tree contains a tag, mp, a Prolog atom and the set of computed answers for the atom. The implementation of erroneous checks to see if all correct answers were computed. This can be done by asking the user incompleteness questions [Nai92][DNTM89][Per86]. An incomplete call has a valid instance which fails. If the call itself failed then the user can simply be asked if the atom is valid (if it is ground) or satisfiable. Assuming a left to right computation rule, the children of a node containing atom A are the atoms: {B_{i}θ | H : −B_{1}, B_{2}, ..., B_{i}, ... is a clause and θ is a computed answer substitution for A = H, B_{1}, B_{2}, ..., B_{i−1}} with tags mp and the appropriate sets of answers. The top-down debugger using these definitions is equivalent to debugger N.5 in [Nai92]. It can be extended to handle coroutining by using partial answers and asking more questions (having more children in the tree in our framework).

Missing answer diagnosers return uncovered atoms [Llo87] [Nai92] [NB94] or not completely covered atoms [DNTM89]. The original definition of an uncovered atom was a valid atom for which there is no matching clause with a valid body. Atoms returned by the debugger presented here have an instance which is an uncovered atom, as defined below. Again, this is an improvement over previous definitions of the class of bugs returned.

buggy(A) :-
    instance(A, AI),
    valid(AI),
    not some [B] (is_clause(AI, B), valid(B)).

The better missing answer debuggers have enhancements which can also be supported by our scheme. First, wrong answer diagnosis can be used for sub-computations. Missing answers at the top level are often caused by wrong answers in sub-computations and wrong answers diagnosis typically uses simpler questions and results in a simpler explanation of the bug. It can also be implemented in our scheme by adding the following children to each mp node: {wp(B_{i−1}θ) | B_{i−1} and θ defined as above}. For nodes with tag wp, child and erroneous are as defined in the section on wrong answer diagnosis. Thus we have a tree with two kinds of nodes and some subtrees are proof trees. Second, negation can be supported using the same technique. A node wp(A) where A succeeded using a clause containing not(B) should have mp(B,[]) as a child and mp nodes should have wp children for failed negations. Enhancements such as these have been added to debuggers in an ad hoc way in the past. By defining the tree separately, reasoning about the correctness of debuggers and developing improved strategies for searching the tree should be significantly easier.

We conclude this section with a brief example of debugging isort([3,1,2],[1,2,3]). The first two questions correspond to mp nodes. Both calls fail but only the first is erroneous. The third question corresponds to a wp node, and the debugger then continues in the same way as for wrong answer diagnosis. The same bug is returned.

isort([3, 1, 2], [1, 2, 3])  valid ? y
insert(3, [1], [1, 2, 3])  valid ? n
isort([1, 2], [1])  valid? n
isort([2], [2])  valid? y
insert(1, [2], [1])  valid? n

4.2 Functional code

NUE-Prolog [Nai91] is an extension of NU-Prolog which supports evaluable functions, including lazy evaluation and higher order functions. It is implemented by transformation into NU-Prolog: a function f(A_{1}, A_{2}, ..., A_{N}) is flattened into a predicate f(A_{1}, A_{2}, ..., A_{N}, A_{N+1}), where the extra argument is result returned by the function. NUE-Prolog has been a convenient vehicle for experimenting with debuggers for functional languages due to the ease of meta-level programming in Prolog. The buggy version of insertion sort could be written as follows in NUE-Prolog.

isort([]) = [].
isort(N.Ns) = insert(N, isort(Ns)).
insert(N, []) = [N].
insert(N, S.Ss0) =
    ( N > S ? S.insert(N, Ss0)
            : N.Ss0).    % should be N.S.Ss0

4.2.1 Wrong answers

A wrong answer diagnosis algorithm for the functional subset of NUE-Prolog is given in [Nai93]. Here we describe how the algorithm can be seen as an instance of the top-down debugger using our debugging scheme.

A strict functional computation can be represented as a tree in the following way. Each node contains a tag, wf, a call to an evaluable function with all the arguments evaluated and the result returned by the function. A node has a child for each evaluable function which was called in the right hand side of the matching equation. For example, the root node of the tree could be represented as wf(isort([3,1,2])=[1,3]) and the children could be

represented as wf(isort([1,2])=[1]) and wf(insert(3,[1])=[1,3]). The representation

of the computation used in [Nai93] is much more obscure but contains this information implicitly. Erroneous simply asks if the call equals the result returned in the intended interpretation, as follows.

isort([3, 1, 2]) = [1, 3] valid? n
isort([1, 2]) = [1] valid? n
isort([2]) = [2] valid? y
insert(1, [2]) = [1] valid? n
Incorrect equation instance:
insert(1, [2]) = (1 > 2 ? [2|insert(1, [])]
                        : [1]).

By flattening each question and the call and result in each node we obtain the same questions and the same tree as would result from the running the flattened (Prolog) version of the program. Thus debugging first order strict functional code is very similar to debugging Prolog code. Our scheme also supports debugging higher order and lazy code, as we discuss next.

The explicit recursion in the definition of isort can be avoided by using a higher order function as follows.

isort(Ns) = foldr(insert, [], Ns).

Computations using the higher order program could be represented in a very similar way to those using the recursive program. An extra root with a call to isort, for example, wf(isort([3,1,2]) = [1,3]) can be added and each call of the form isort(Xs) in the rest of the tree can be replaced by foldr(insert,[],Xs). If foldr was a user-defined function then questions about the correctness of these nodes could then be asked. If foldr is a builtin function such questions should be avoided. Like builtin predicates in the Prolog case, these nodes can simply be deleted from the tree. In the resulting tree the root has three children, containing calls to insert. If the children were examined from left to right then the top-down debugger would ask the following questions before returning the same bug as before.

isort([3, 1, 2]) = [1, 3] valid? n
insert(2, []) = [2] valid? y
insert(1, [2]) = [1] valid? n

The same tree structure can be used with lazy evaluation but the arguments to calls and results of calls will only be evaluated to the extent they were in the computation. Consider the following function, which incorrectly returns the value 3.

two = second(isort([4,3,1,2])).
second(Xs) = hd(tl(Xs)).

With lazy evaluation isort([4,3,1,2]) is only evaluated up the the point where the second element of the result is known. The last call to insert, insert(4,[]), is not evaluated. A simple implementation of erroneous would ask questions as follows, continuing with the same questions as before to debug the sub-computation which (completely) evaluates

isort([3,1,2]).
two = 3 valid? n
second([1, 3|insert(4, [])] = 3 valid? y
isort([4, 3, 1, 2]) = [1, 3|insert(4, [])] valid? n
isort([3, 1, 2]) = [1, 3] valid? n
...

In [Nai93] it is suggested that questions be simplified by replacing unevaluated expressions by suitably quantified variables. This can be seen as an alternative implementation of erroneous which results the following questions:

two = 3 valid? n
second([1, 3|X] = 3 valid? y
some [X] isort([4, 3, 1, 2]) = [1, 3|X] valid? n
isort([3, 1, 2]) = [1, 3] valid? n
...

4.2.2 Undefined calls

A class of runtime errors in functional programs can also be diagnosed using a declarative debugger [NB94] [BN94]. These errors result from calls to functions which are not total (well defined for all inputs). For example, the evaluation of the function three below results in hd([]) being called, which typically causes a runtime error.

three = third(isort([3,1,2])).
third(Xs) = hd(tl(tl(Xs))).

Function calls which are undefined can be thought of as returning a special value, bottom. A computation tree can be defined in the same way as before, using bottom as the result of all function calls which were undefined. Expressions which are not evaluated due because of the error should be treated in the same way as other unevaluated expressions. The implementation of erroneous must also be modified to handle bottom and ask appropriate questions (which can be simplified using variables as before [NB94]). In the example above, the following questions may be asked.

three well-defined? y
third([1, 3]) well-defined? n
isort([3, 1, 2]) = [1, 3] valid? n
...

4.3 Relational+functional code

The trees for functional and Prolog computations can be combined in a similar way to the trees for wrong and missing answers in Prolog to obtain a declarative debugger for full NUE-Prolog. The result is a tree with several kinds of nodes. The insights obtained with our scheme can lead to several improvements over the original debugger for NUE-Prolog:

• Simpler code for the core of the debugger.

• The same code for wrong and missing answers.

• A simpler representation for Prolog computations, for builtins.

• A simpler representation for functional computations, including the basic tree structure and higher order builtin functions.

• A better understanding of the classes of bugs returned for wrong and missing answers in Prolog code.

4.4 Object oriented code

The final instance of the debugging scheme we discuss in detail is for diagnosing wrong answers in an object oriented relational language. We believe this is the first declarative debugger for an object oriented language. The language was first implemented as an extension to Quintus Prolog [BJN92]. More recently it has been improved and ported to NU-Prolog, giving rise to “NUOO-Prolog”. A survey of related languages can be found in [Dav93].

NUOO-Prolog is an extension of NU-Prolog which supports objects, nondeterministic messages or methods and inheritance. Multiple inheritance and mutable state are not supported but NUOO-Prolog is still an attractive alternative to NU-Prolog for many knowledge representation applications. A simple example of a NUOO-Prolog program and session appears below.

       % a typical/generic bird
   def_object bird.
   goes(chirp).
   weight(300).           % weight = 300g
   can_swim :- fail.      % can't swim
   can_fly :-             % birds can fly if
       self :: weight(W), % their weight is
       W < 4000.          % less than 4kg
   end_def bird.
       % the famous tweety
   def_object tweety isa bird.
   goes(tweet).
   end_def tweety.
       % emus are flightless Australian birds
   def_object emu isa bird.
   goes(hiss).
   goes(squawk).
   weight(12).            % should be 12000
   end_def emu.

                                                     % tweety's cousin
                                                 def_object brucey isa emu.
                                                 end_def brucey.

                                                 ?- tweety :: goes(X).
                                                 X = tweet ;
                                                 fail.
                                                 ?- brucey :: goes(X).
                                                 X = hiss ;
                                                 X = squawk ;
                                                 fail.
                                                 ?- tweety :: can_fly.
                                                 true.
                                                 ?- brucey :: can_fly.
                                                 true.

The last goal succeeds incorrectly, the computation proceeding as follows. The object brucey has no definition of the method can fly so the parent object, emu, is examined. No definition is found in emu so the parent, bird, is examined and the definition can fly :- self::weight(W), W < 4000 is found. The special constant self is replaced by the original object the method is being applied to, brucey, and the goal brucey::weight(W) is invoked. Inheritance is used again and the definition of weight in emu binds W to 12 (this is incorrect – the weight being given in kilogram instead of gram). The goal 12 < 4000 is then called and the computation succeeds.

The debugging scheme can be applied as follows. The tree is the same as the proof tree for diagnosing wrong answers in Prolog except for goals of the form Object::Message. These nodes contain a tag wom, and Object and Message with the answer substitution applied. The children of wom nodes are of two types. The first type are associated with the method definition which was used. These are the same as in a Prolog proof tree except that goals of the form O::M are treated as described above and the constant self is replaced by Object. The second type are associated with the inheritance mechanism. For each step up the isa hierarchy which was needed to find the method definition there is a child with tag woi and objects Obj and ParentObj. These nodes have no children. For example, the computation described above can be represented with the following tree.

woi(brucey isa emu)  wom(brucey :: can fly) wom(brucey :: weight(12))  wp(12 < 4000) woi(brucey isa emu)  woi(emu isa bird)

In the intended interpretation of a NUOO-Prolog program ::/2 and isa/2 can be treated as relations and erroneous can query the user about the validity of such goals. An example of a debugging session follows:

brucey :: can_fly  valid? n
brucey :: weight(12)  valid? n
brucey isa emu  valid? y

Incorrect clause instance:
brucey ::
weight(12).
Relevant clauses:
brucey isa emu.
emu ::
weight(12).

The “incorrect clause instance” displayed is not an explicit clause in the program. However, it is an implicit clause in the program because brucey inherits weight from emu. Similarly, the clause brucey isa emu is not an explicit clause in the program but it is implied by the definition of the object brucey. Comparing the debugging session with the description of the computation given earlier shows how details of yet another complex execution mechanism (inheritance) can be hidden by a declarative debugger.

4.5 Other instances of the scheme

A missing answer debugger for NUOO-Prolog should be straightforward to implement using our scheme. It should also be possible to diagnose “undefined method” runtime errors in a similar way to undefined calls in functional languages. Other object oriented logic programming languages, such as those based on concurrent logic programming (see [Dav91], for example), should also be amenable to debugging using our scheme.

Constraint logic programming languages seem an obvious target for declarative debugging. A prototype debugger for CLP(R) [JL87] based on our scheme has recently been implemented. A prototype wrong answer declarative debugger for AKL [HJ90] based on the debugger described in [Nai93] was previously implemented by the author. The computational model of AKL is much more complicated than Prolog but a successful computation can still be represented as a proof tree so the same debugging algorithm can be used. The implementation, in AKL, was somewhat more complicated. By using the scheme presented here it should be possible to simplify the debugger.

It is also conceptually possible to apply declarative debugging to imperative languages, though there are some important practical problems to overcome. The decomposition of a computation into subcomputations is simple for procedure and function calls, sequencing and conditionals. Iteration is more complicated and may be best treated like calls to tail recursive procedures. Checking if a sub-computation is erroneous can be very difficult because potentially all data structures in the program need to be displayed (which is especially difficult if pointers are used). If a subcomputation uses many global data structures, explicit pointers and iteration (with destructive assignment) then declarative debugging will not magically make debugging easy. Declarative debugging is better suited to programming languages where features such as these may be used in the implementation of the language but are not directly accessable to the programmer.

5 Conclusion

For languages in which programs can be viewed declaratively, declarative debugging is an effective way of hiding execution details from the programmer. This is particularly useful for modern languages which have very complex execution models. The scheme we have presented relies on two things. First, a computation must be represented as a tree. Second, there must be a way of determining the correctness of the result of each subcomputation (subtree). The scheme has resulted in many improvements over existing declarative debugging work including: simpler correctness proofs for debuggers; a better understanding of the classes of bugs found; improved behaviour for non-ground Prolog derivations; a more unified approach to diagnosing wrong and missing answers in Prolog; more efficient handling of system predicates and functions; and simplified data structures for debugging lazy functional code. It has also proved to be a very convenient basis for new applications of declarative debugging to languages such as NUOO-Prolog and CLP(R).

References

[BJN92] Fevzi Belli, Oliver Jack, and Lee Naish. Object-oriented programming in Prolog: rationale and a case study. Technical Report 92/2, Department of electrical and electronics engineering, University of Paderborn, Paderborn, Germany, 1992.

[BN94] Timothy Barbour and Lee Naish. Declarative debugging of a logical-functional language (honours thesis). Technical Report 94/28, Department of Computer Science, University of Melbourne, Melbourne, Australia, December 1994.

[Dav91] Andrew Davison. From Parlog to Polka in two easy steps. Proceedings of The Third International Symposium on Programming Language Implementation and Logic Programming, pages 171–182, August, 1991.

[Dav93] Andrew Davison. A survey of LP-based object-oriented languages. In Peter Wegner, Akinori Yonezawa, and Gul Agha, editors, Research Directions in Concurrent Object Oriented Programming. MIT Press, 1993.

[DL87] Nachum Dershowitz and Yuh-Jeng Lee. Deductive debugging. In Proceedings of the Fourth IEEE Symposium on Logic Programming, pages 298–306, San Francisco, California, August 1987.

[DNTM89] Wlodek Drabent, Simin Nadjim-Tehrani, and Jan Maluszynski. Algorithmic debugging with assertions. In John W. Lloyd, editor, Meta-programming in Logic Programming, page MIT Press. 1989.

[ET83] A. Edman and Sten-Åke Tärnlund. Mechanization of an oracle in a debugging system. In Proceedings of Eighth IJCAI, pages 553–555, Karlsruhe, Germany, August, 1983.

[HJ90] Seif Haridi and Sverker Janson. Kernel Andorra Prolog and its computation model. In Proceedings of the Seventh International Conference on Logic Programming, Jerusalem, Israel, June 1990.

[JL87] Joxan Jaffar and Jean-Louis Lassez. From unification to constraints. In K. Furukawa, H. Tanaka, and T. Fujisaki, editors, Proceedings of the Sixth Logic Programming Conference, pages 1–18, Tokyo, Japan, June 1987. published as Lecture Notes in Computer Science 315 by Springer-Verlag.

[KKMH89] T. Kanamori, T. Kawamura, M. Maeji, and K Horiuchi. Logic program diagnosis from specification. ICOT Technical report TR-447, Institute for New Generation Computer Technology, Tokyo, Japan, March, 1989.

[Llo84] John W. Lloyd. Foundations of logic programming. Springer series in symbolic computation. Springer-Verlag, New York, 1984.

[Llo87] J.W. Lloyd. Declarative error diagnosis. New Generation Computing, 5(2):133– 154, 1987.

[Nai86] Lee Naish. Negation and quantifiers in NU-prolog. In Ehud Shapiro, editor, Proceedings of the Third International Conference on Logic Programming, pages 624–634, Imperial College of Science and Technology, London, England, July 1986. published as Lecture Notes in Computer Science 225 by Springer-Verlag.

[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.

[NB94] Lee Naish and Timothy Barbour. A declarative debugger for a logical-functional language. Technical Report 94/30, Department of Computer Science, University of Melbourne, Melbourne, Australia, December 1994.

[NDZ89] L. Naish, P. W. Dart, and J. Zobel. The NU-prolog debugging environment. In Antonio Porto, editor, Proceedings of the Sixth International Conference on Logic Programming, Lisboa, Portugal, June 1989.

[NF92] Henrik Nilsson and Peter Fritzson. Algorithmic debugging of lazy functional languages. Proceedings of The Fourth International Symposium on Programming Language Implementation and Logic Programming, to appear, August, 1992.

[Nic88] A.E. Nicholson. Declarative debugging of the parallel logic programming language GHC. In Proceedings of the Eleventh Australian Computer Science Conference, pages 225–236, Brisbane, Australia, February 1988.

[PC88] Luis Moniz Pereira and Miguel Calejo. A framework for prolog debugging. In Kenneth A. Bowen and Robert A. Kowalski, editors, Proceedings of the Fifth International Conference/Symposium on Logic Programming, pages 481–495, Seattle, Washington, August 1988.

[Per86] Luis Moniz Pereira. Rational debugging in logic programming. In Ehud Shapiro, editor, Proceedings of the Third International Conference on Logic Programming, pages 203–210, London, England, July 1986. published as Lecture Notes in Computer Science 225 by Springer-Verlag.

[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.

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

[SS86] Leon Sterling and Ehud Shapiro. The art of Prolog: advanced programming techniques. Logic Programming series. MIT Press, Cambridge, Massachusetts, 1986.