Debugging SICStus Prolog

This is a debugging session using SICStus prolog. The initial version of the file foo.pl is here. It defines predicates member and union, but there are some bugs....

 Things with underlines are things I typed. ® indicates that I simply typed a return. Things in bold are comments added later. The rest was printed by prolog.


SICStus 3.7: Tue Sep 08 19:55:50 MET DST 1998
Licensed to cs.rutgers.edu
| ?- [foo].  This loads file foo. Note the period after the ].
{consulting /fac/u42/lou/440/prolog/foo.pl...}
{SYNTAX ERROR: in line 24 (within 22-25)}
** , or ) expected in arguments **
member ( E , [ _ | Rest ] ) :- member ( E , Rest
** here **
] .
{/fac/u42/lou/440/prolog/foo.pl consulted, 0 msec -88 bytes}
yes
                     Oops - there was a ] where I needed a ).
                     I changed the last line of the file to
                     member(E, Rest).
                     and SAVED THE FILE (ctl-x ctl-s)
| ?- [foo].           Now reload into prolog
{consulting /fac/u42/lou/440/prolog/foo.pl...}
{/fac/u42/lou/440/prolog/foo.pl consulted, 0 msec 88 bytes}

yes
| ?- union([a, b], [c, a ], X).           A test call to union.

no                   No?? Something is wrong ...
| ?- trace.           This causes prolog to step through the program one clause at a time
{The debugger will first creep -- showing everything (trace)}

yes
{trace}
| ?- union([a, b], [c, a ], X).               Try the test call again
1 1 Call: union([a,b],[c,a],_314) ? ®         Prolog is calling the initial goal I just
                                         typed. _314 is a new variable in place of X.
                                         This is actually my goal unified with the head of the
                                         second clause for union.  (The goal did not unify with
                                         the head of the first clause, so prolog skipped down
                                          to the second clause.)
  2 2 Call: member(a,[c,a]) ? s           First subgoal of the second clause of union. The s I typed
                                     means skip - run until this goal succeeds or fails.
? 2 2 Exit: member(a,[c,a]) ? ®          Exit means the call succeeded.  The ? means this is a
                                    backtrack point - there is another alternative we could have taken
                                    and if we later fail we will come back here and try that
                                    alternative.
  3 2 Call: union([b],[c,a],_314) ? ®    Second subgoal of second clause - a recursive call
  4 3 Call: member(b,[c,a]) ? s          First subgoal of recursive call - Skip over this call
  4 3 Fail: member(b,[c,a]) ? ®          Call fails
  4 3 Call: member(b,[c,a]) ? g          Hmm.. why are we calling it again?  The g command prints the
                                     ancestors of this goal, i.e. the goals this is a subgoal of, a
                                     subsubgoal of, etc.
Ancestors:
0 0 Call: break
1 1 Call: union([a,b],[c,a],[b|_2110])
3 2 Call: union([b],[c,a],[b|_2110])     Aha - the last argument is already bound to [b | ...] so we
                                    must be doing the third clause of union
4 3 Call: member(b,[c,a]) ? s

4 3 Fail: member(b,[c,a]) ? ®
3 2 Fail: union([b],[c,a],_314) ? a     And now I saw the bug - the 3rd clause of union was supposed to
                                    handle the case where First is NOT a member of S2.  So I fixed
                                    the 3rd clause to be
                                      union([First | Rest], S2, [First | U]):-
                                           union(Rest, S2, U).
                                    the 'a' I typed means abort - stop running my code and return
                                    to the ?- prompt

{Execution aborted}
| ?- [foo].
{consulting /fac/u42/lou/440/prolog/foo.pl...}
{/fac/u42/lou/440/prolog/foo.pl consulted, 0 msec -24 bytes}

yes
| ?- trace.                               The abort turned off trace, so here I turned it back on
{The debugger will first creep -- showing everything (trace)}

yes
{trace}
| ?- union([a, b], [c, a ], X).
  1 1 Call: union([a,b],[c,a],_314) ? ®
  2 2 Call: member(a,[c,a]) ? s
  ? 2 2 Exit: member(a,[c,a]) ? ®
  3 2 Call: union([b],[c,a],_314) ? ®
  4 3 Call: member(b,[c,a]) ? s
  4 3 Fail: member(b,[c,a]) ? ®
  4 3 Call: union([],[c,a],_2104) ? ®
  4 3 Exit: union([],[c,a],[c,a]) ? ®
  3 2 Exit: union([b],[c,a],[b,c,a]) ? ®
? 1 1 Exit: union([a,b],[c,a],[b,c,a]) ? ®

X = [b,c,a] ? ;                          Correct answer.  Now I checked to make sure there were
                                    no more answers
1 1 Redo: union([a,b],[c,a],[b,c,a]) ? l  The l means leap - run until you hit a spy point or an answer

X = [a,b,c,a] ? ;                        Wrong... hmm - member had a choice point, maybe that's the problem

no
{trace}
| ?- spy(member).                        spy places a breakpoint on a predicate
{Spypoint placed on user:member/2}

yes
{trace}
| ?- union([a, b], [c, a], X).
        1      1 Call: union([a,b],[c,a],_314) ? l
 +      2      2 Call: member(a,[c,a]) ? ®
 +      3      3 Call: member(a,[a]) ? ®
?+      3      3 Exit: member(a,[a]) ? ®
?+      2      2 Exit: member(a,[c,a]) ? ®
        4      2 Call: union([b],[c,a],_314) ? ®
 +      5      3 Call: member(b,[c,a]) ? ®
 +      6      4 Call: member(b,[a]) ? ®
 +      7      5 Call: member(b,[]) ? ®
 +      7      5 Fail: member(b,[]) ? ®
 +      6      4 Fail: member(b,[a]) ? ®
 +      5      3 Fail: member(b,[c,a]) ? ®
        5      3 Call: union([],[c,a],_2890) ? ®
        5      3 Exit: union([],[c,a],[c,a]) ? l

X = [b,c,a] ? ;
 +      2      2 Redo: member(a,[c,a]) ? l
 +      3      3 Redo: member(a,[a]) ? ®
 +      4      4 Call: member(a,[]) ? ®
 +      4      4 Fail: member(a,[]) ? ®
 +      3      3 Fail: member(a,[a]) ? ®
 +      2      2 Fail: member(a,[c,a]) ? ®       No, the choice point in member failed so it did not lead to
                                           the wrong extra answer
        2      2 Call: union([b],[c,a],_858) ? g
Ancestors:
        0      0 Call: break
        1      1 Call: union([a,b],[c,a],[a|_858])  This is the THIRD clause of union - a is a member of [c, a]
                                             which should be handled by the second clause - aha, we need
                                             a cut.

        2      2 Call: union([b],[c,a],_858) ? a     I edited the second clause to be
                                                 union([First | Rest], S2, U):-
                                                    member(First, S2),
                                                    !,
                                                    union(Rest, S2, U).
                                              I saved the file.
| ?- [foo].                                           reload it into prolog
{consulting /fac/u42/lou/440/prolog/foo.pl...}
{/fac/u42/lou/440/prolog/foo.pl consulted, 0 msec 16 bytes}

yes
| ?- union([a, b], [c, a], X).

X = [b,c,a] ? ;

no                                                   Correct. Here is the final program.
| ?-