Domain Specific Debugging Aids for Novice Programmers

1. The student may have invented a 2-digit subtraction table

He may have chosen among a wide variety of table representations. We represent these as a class hierarchy, which for each class has the associated rule for rewriting the user's effect description into diff, <DIFF> is an arbitrary symbol invented by the user.

If we take account of argument reversals, there are 10 possible ways of organizing subtrac­ tion tables. Each indirect-table subclass has two triples as parts which are mutually constrained (the outer and the inner get) by the difference predicate. We hypothesize a particular table-class, and seek confirmation until we can decide on the actual class used by the student. Then we look for all the entries of the table and create an object DIFF which has associated with it the code to recognize (diff a b), e.g. as (get (get a SUB) b). Data base analysis reveals the frequent error-type of missing or inconsistent entries in the data base. Triples which belong to no pre-defined c!ass, but "partially" match eome class (i.e. because they contain a known link-name) are categorized as inconsistent and the user is informed about them.

2. The student may have represented 'diff' procedurally

Using add1 and sub1, he may have written a recursive procedure to implement 'diff'. Since a SOLO procedure can only have an effect by side­ effecting the data base, the DSLP for a procedural implementation has to change slightly. Any function f, which is represented procedurally as f-proc will be transformed in the library plan as follows:

where N is the node to be side-effected.

The following example shows a typical student implementation of 'diff' together with the effect description produced by the debugging assistant:

TO DIFF-REC /X/ /Y/ /ANS/

1 CHECK EQUALS /X/ /Y/ 1A If Present: NOTE /ANS/ VAL .O; EXIT 1B If absent: CONTINUE 2 CHECK /X/ SUB1 ?x1 2A If present: DIFF-REC *x1 /Y/ /ANS/; CONTINUE 2B If absent: EXIT 3 CHECK /ANS/ VAL ?v 3A If present: CONTINUE 3B If absent: ERROR; EXIT 4 CHECK *v ADD1 ?v1 4A If present: NOTE /ANS/ VAL *v1 4B If absent: ERROR; EXIT

Symbolic evaluation first produces:

di ff-rec (x y ana db-in) · (cases [(· (get EQUALS x) ~) l[bind (ana VAL) OJ · db-in}] [(fresent (get x SUB1)) l bind (ana VAL) (get (get ana VAL) ADD1))] · (self (get x SUB1) y ans db-in)}])

This matches a recursion pattern for which there is a DSLP. The binding being affected in the terminating case (ana VAL) is identical to that of the post-recursive step, which means that (ana VAL) is successively rebound. The DSLP simplifies this to an instance of a prototypical data base entry:

It says that the value is an (ana VAL) binding whose target can be computed by substituting for g007 the init value and then stepping through the rec-rel a-list substituting for g007 until term-if is true. This representation has the advantage that other recursive implementations (i.e. a tail-recur­ sive one) can be mapped to an equivalent db-entry. The DSLP for diff-proc will match this db-entry instance modulo renaming and substituting (sub1 x) for (get x SUB1).

IV COMPARING EFFECT DESCRIPTIONS OF USER PLANS WITH LIBRARY PLANS -

A variety of user programs for a given task can be recognized as having the same effect desc­ ription as a pre-stored plan. The reduction to a canonical form allows the user to (1) invent arbi­ trary names, (2) order steps arbitrarily, (3) break up procedures arbitrarily into sub-procedures, (4) pass values through intermediate nodes of the data base, and (5) invent his own data representation.

What happens if the user's program does not match a library plan?

Our goal is to give the student as much help as possible in detecting the underlying cause of an error. Here, the effect descriptions are useful too: By using the library plan to generate the get­ compositions corresponding to his data-represen­ tation, we can compare the terminal nodes of both his and the DSLP's effect description for each condition. (The assistant takes care of situations in which nested cases must be reordered for both trees to match.)

A very frequent error which can be detected by comparing effects at terminal nodes is 'name­ substitution' (e.g. the student writes v and means v). The assistant compares the bindings added or deleted at each terminal branch of DSLP (goal bindings, · gi) with those of the user program (actual bindings, ai). Assume it finds a mismatch of two bindings at some terminal branch:

actual-binding: a · [bind (a1 a2) a3] For example if in line 3 of DIFF-IND (Fig. 2) the code were NOTE /ANS/ VAL *T, then lines 4-6 of its effect description (Fig. 3) would be: j(bind (ans VAL) (a SUBTBL)) · e} l a instead of j(bind (ana VAL) (get (get a SUBTBL) b)] · e} l g

as suggested by 2-COL-SUB (lines 5-8 of Fig. 4).

We go up in the symbolic evaluation tree to the place where a vas achieved using variable v (i.e . line 3 of DIFF-IND using variable T). If the mismatch vas in pair lai,gi}, and in the local environment some other variable vas bound to gi, we can propose substituting it for the one used in the code. In our example the mismatch was in !a3,g3l with a3 being T, and g3 being R, eo a substitution of R for T at line 3 is suggested to the student.

If gi is not bound locally, we look at the CHECK (or procedure call) where w was bound and recursively search for the goal of binding w to gi. In case of success, we ask the student whether he wants to accept the proposed renaming.

If this fails, we try step insertion, because another typical source of errors in SOLO is students forgetting a level of indirectness (i.e. using the source of a triple, instead of the target along some link). Lines 1 and 3 in SUBTRACT (Fig. 5) manifest this error, given the implementation of DIFF-IND (Fig. 2).

A CHECK step can be inserted to correct that, if by. substituting (get e K) for some subexpression e in ai (where K is some constant link), ai can be made equal to gi. In SUBTRACT the actual effect is:

(diff-ind B D F)

l a

whereas the goal in 2-COL-SUB (lines 7-9 of Fig. 4) gives

(diff-ind (get B VAL) (get D VAL) F) J g

and thus K · VAL. The insertion of two CHECK statements of the form CHECK B VAL ?B-VAL and modification of the calls of DIFF-IND in lines and 3 (Fig. 5) is suggested.

If step insertion fails also, we look at the possibility of reversed present and absent branches (cf. [8]). This manifests itself in the effect description such that the correct data base change has occurred, but at the wrong branch of the tree. In such cases, the user is queried about whether the clauses of the CHECK statement should be reversed.

If this fails also, our last resort is to look for a branch of the tree where the conditione are correct, but there is a disagreement in the effect. The assistant chooses a counterexample that would run through this branch of the tree, and asks the student to try that example on hie program. Consider line 2B in DIFF-IND (Fig. 2). The student did not consider the case where (geq a b) does not hold. The effect description for SUBTRACT (Fig. 5) has no effect where it should match lines 11-16 of 2-COL-SUB. We collect the case predicates that lead to this leaf of the symbolic evaluation tree, and see that under the condition

SUBTRACT would fail. Since the assistant knows that (val-of B) and (val-of D) are digits, it generates values which fulfill this condition and asks the student to try his program with those.

V CONCLUSIONS AND FURTHER WORK

Our work demonstrates how a combination of domain-specific knowledge and symbolic evaluation techniques can be applied to building a help facility for novice programmers. Writing programs in an elementary assertional data base language like SOLO is experienced by our students as a simple and natural entry point into programming. However, automatically coping with the sorts of bugs which arise through programming by side-effect requires extensions to earlier work on program understanding and debugging. The techniques we have employed give the students a fair amount of freedom in choosing their own representations, a fact which reflects one of the main goals of the course they are taking, i.e. understanding computer modelling and knowledge representation.

We are currently extending the plan library in accordance with empirical observations, in order for the debugging assistant to be capable of handling a wider range of programming tasks.