Explaining Prolog Based Expert Systems Using a Layered Meta-Interpreter

1 Constructs for Explanation

In recent years, several systems have been developed for explaining the execution of Prolog. Applications of these systems have ranged from teaching Prolog [Brayshaw and Eisenstadt, 1988], debugging Prolog [Pereira, 1986, Shapiro, 1983], to presenting the results of Prolog­ based expert systems, [Clark and McCabe, 1982, Ham­ mond, 1984, Niblett, 1984, Sterling and Lalee, 1986, Walker eta/. 1987, Yal~inalp and Sterling, 1988]. In each case extra ~echanisms were added to make explicit the rele~ant features of Prolog's backward chaining behav­ ior .

For example, the following constructs are needed to give MYCIN-like explanations of expert systems writ­ ten as collections of simple Prolog clauses . Proof trees represent successful branches of the search tree which is implicitly generated and traversed during a Prolog com­ putation . After completion of the computation, a proof tree is presented in a suitable format to answer ques­ tions about how a solution is computed. History lists represent the current branch of the search tree bei.ng traversed and are implemented as a stack of success1ve goals investigated up to the current goal. Whenever the user is consulted for information, for example to find a missing fact, which might be used to prove or refute the particular goal in question, she is allowed to inquire why with a different abstraction of the control flow than the standard meta-interpreter. The new meta-interpreter al­ lows proper explanations of extra-logical predicates such as the cut. Further, by introducing the concept of par­ tial proof trees, it treats explanations given both during and after the computation uniformly, and faithfully to Prolog's computation model.

·This research was supported under NSF Grant No. 1R187-03911, and Equipment Grant No. DMC 8703210.

2 A Two-Layer Meta-Interpreter

A good explanation depends on a good representation of the computation at an appropriate level of abstraction. The major limitation of current explanations of Prolog­ based systems stems from handling failure too implicitly. Failure in Prolog is composed of two different events. First, a failure occurs when a particular goal fails to unify with any of the existing clauses in the program. This fail­ ure causes backtracking to generate alternative solutions. Second, if all backtracking efforts result in failure for all clause definitions of a goal, Prolog answers "no".

The inability to unify, and the exhaustion of al­ ternatives for a goal are implicitly used in most re­ ported work, but not explicitly represented. The stan­ dard meta-interpreter can be augmented with a result variable to make it fail-safe [Levi and Sardu, 1987, Sterling and Lakhotia, 1988] . This makes failure infor­ mation available but changes the behaviour of Prolog.

Prolog's behaviour can be kept while maintaining ex­ plicit failures by building a meta-interpreter in two lay­ ers. We call the first layer of the interpreter the goal layer, while the second layer is called the branch layer. The goal layer uses the predicate solve_branch to gener­ ate each possible computation of the goal being solved. The result of the computation, either yes or no, is re­ turned by the second argument of solve_branch. Note that the solve_branch layer is fail-safe. This result is then filtered by the goal layer to recover Prolog's behaviour. Its essence is captured in the predicate, solve_goal, de­ fined as follows.

The branch layer is similar to the standard meta­ interpreter at the clause reduction level. The complete code for the two-layer interpreter is given in Figure 1. The scope of the interpreter is given by the clauses for solve_branch. In particular, it covers conjunctive goals , system goals, negated goals, single goals (namely rules), conditionals, set predicates, such as Jindal/ and askable goals.

Note that the two events involved in Prolog's failure mechanism have been made explicit. Failure to unify is indicated by a solve_branch clause, which returns a "no". This occurs when none of the clauses in the database are unifiab le with the current goal. This is recognized by using the negation of the built-in clause{Goal,Body} in Prolog. Backtracking is initiated by the failure of filter _failure. This explicit representation offailure will be used in extending the interpreter later.

This two-layer interpreter follows the computation model of Prolog faithfully. Failure can be controlled and used to represent the result of a computation. Further, all computation is handled by a single interpreter. There is no reason to wait for the result of computation for a goal to detect failures, as in other systems [Bruffaerts and Renin, 1988, Sterling and Lalee, 1986]. The com­ putation, as in Prolog, is performed only once, which allows the interpreter to correctly handle programs with side-effects.

The presence of two layers makes it straightforward to handle negation-as-failure correctly, as follows:

We next demonstrate how the two layer approach facil­ itates the handling of cuts. A third result is used, namely commit, which represents a special type of failure due to commitment in the body of a clause. In the branch layer, Prolog's clause ordering is exploited to achieve the de­ sired result.

Obtaining a commit result at a branch can affect the program in two ways, depending on the type of the goal.

• For a series of conjunctive goals, ...,_ P1, P2, ... , P;, ... , Pn, a cut can be any of these goals in the body. We retain the value of the computation, namely commit, as a failure occuring due to a commitment for the entire conjunction and inform the parent goal. If the cut is the final goal, Pn, then the result of the computation will be com­ mit by the solve_branch clause above. If this goal is P; and the result of the computation of Pi+b ... , Pn is "no", then the result of the computation in the branch layer is commit. This is then handled in the goal layer of the interpreter, as seen in Figure 1.
• For a single goal, a commitment at the branches means an immediate failure as it is the parent goal. That means a commit result for a branch of the sin­ gle goal actually indicates a no result in the goal layer, and the goal should no longer investigate other possibilities via different clause definitions in the branch layer.

Handling cuts correctly is achieved by modifying fil­ ter-fail'ure and solve_goal. Now, filter_Jailure acts as an­ other "port" for indicating overall failure upon com­ mitment by returning a "no" result for a single goal. Solve_goal is altered to make the interpreter actually commit itself by placing a cut in the goa.! layer . This prevents backtracking of the interpreter back to the branches which generate alternative solutions. The mod­ ified goal layer is represented in Figure 1.

% GOAL LAYER solve...goai(Goai,Result) +­ copy( Goa I, Copy). solve..branch( Copy, Branch_Result), (Branch_Result = commit- !;true), filter _failure(Branch_Resu lt,Resu It , Goal, Copy) . solve...goal( Goal,no ). %BRANCH LAYER solve..branch( true,yes )+--! . solve..branch((A.B).Result) +-- !, %A and B solve...goai(A,RA), solve..branch_and(RA.A,Result,B) . solve..branch((A- 8; (),Result) +- solve...goai(A, ResultA), !, solve..branch_if(ResultA, Result, B. C) . solve..branch((A - B),Result) +­ solve...goai(A,ResultA), !, solve..branch_iLone(ResultA,Result, B) . solve..branch((A;B) .Result) +-- !, %A orB solve...goal( RA.A), solve..branch_or( RA, Result, B) . solve..branch(not Goai,Result) +­ solve...goai(Goai,ResuiLNot) , !, invert( Resu ILNot , Result). solve..branch( findaii(X.P,l), Result) +- findaii(X-R,solve...goal( R. P),Alist ), eliminate(Result,Alist,l). %HANDLING CONJUNCTION solve..branch_and(yes,!,Result,B) +-- !, so1ve...goal( B. Result B), ((ResultS = no ; ResultS = commit) - Result= commit ; Result = yes) . solve..branch_and(yes,A,Result,B) +-- !, % when A is not a cut solve...goai(B.Result). solve..branch_and(no,A,no,B). % HANDLING IF BRANCHES solve..branch_if_one(yes.Result, B) +-- !, solve...goal( B. Result) . solve..branch_if_one(NoResult, NoResult, B) +­ (NoResult = commit ; NoResult = no), !. solve_branch_if(yes, Result , B. C) +-- !. solve...goal( B. Result) . solve..branch_if(no, Result, B. C)+-- !, solve...goal( C. Result) . solve..branch_if(commit, commit, B. C)~!.

filter _fa ilu re(yes .yes , Goa I. Goa I). filter _failure( commit ,commit . Goal , Copy) +­ non_singular(Goal) . !. filtedailure(commit ,no,Goai ,Copy) . % for single goals filtedailure(no,_,_, _) +--fail. solve_branch( !,yes). solve_branch(! ,commit) +-- !. solve_branch(A.Result) +- sys(A). A, Result = yes . solve_branch(A.Result) +­ sys(A). Result= no, !. solve_branch(A,no) +- not clause(A.Body),! . solve_branch(A,Result) +­ clause(A.Body ). solve...goal( Body, Result) . solve_branch(A.Result) +­ askable(A) , investigate_goal( A, Result) . invert(yes,no ). invert(no,yes). %HANDLING DISJUNCTION solve_branch_or(yes,yes,B) +-- !. solve..branch_or(no,Result ,B) +-- ! solve....goal( B. Result). solve_branch_or( commit,commit, B) +-- ! .

To handle the effect of cuts on instantiating variables correctly, a copy of the goal is needed. Since the com­ mitment would instantiate the actual goal, the bindings will be propagated within the tree. In order to be faith­ ful to the execution process, the actual goal should be uninstantiated upon failure. To have a uniform struc­ ture, the copy of-the actual goal is used for creating the branches and explicit unification with this goal happens upon success.

Other control predicates can be handled in our frame­ work. For example, the extension for the if-then-else con­ struct, P --+ Q; R, is immediate. The interpeter uses the Result of the goal defining the conditional part, if, to de­ fine and control the result of the branch defining the the construct. It is shown in the full interpreter in Figure 1.

3 Explanations Generated by the Layered Meta-Interpreter

An extra argument, Proof, is used for collecting proofs in the branch layer of the interpreter. This is a standard technique discussed in [Sterling and Shapiro, 1986] and used in [llruffaerts and Henin, 1988, Sterling and Lalee, 1986, Yal<sinalp and Sterling, 1988], etc. The proofs, both of successes and failures, are transmitted to the goal layer at this layer's exit points.

The exit points of the goal layer are jilter_failure, upon success or failure due to commitment, and the second clause of solve_goal upon ultimate failure of the goal. Since this interpreter does not know in advance whether a goal will ultimately fail or not, the proof is kept by the goal layer when a "no" result occurs in the branch layer . If there is no commitment, the alternative solutions are generated by imposing failure. Upon generating a suc­ cess, a "yes" result by the branch layer, all the previously encountered failures are discarded since they are not rel­ evant. However a failure , which occurs by commitment or ultimate failure of all branches, enables the interpreter to collect the proofs of all the failure branches that are previously stored. The method is shown below:

solve..goal( Goai,Result,Proof) +- copy(Goai,Copy), solve_branch( Copy, BResult, BProof), (BResult =commit--+ !;true), filter _failu re(BResult,Result,Copy, Goai,BProof, Proof). solve..goal( Goal,no,fail( Goal , Failures)) +- geLproof( Goai,Failures ). filter _failu re(yes,yes, Copy, Goai,Proof, Proof) +­ geLproof( Goal, Failures) , Goal= Copy. filter _failure( no,_, Copy, _, BProof._) +­ store(Copy,BProof). !, fail. filtedailure( commit,commit,Copy,Goai,Proof, Proof) +­ non ...singular( Goal),! . filter _failure( commit,no, Copy, Goai,Proof, fail( Goal, Failures))+- %for single goals geLproof(Goal, Prev_Failures), append( Prev_Failures,commit( Copy, Proof). Failures) . There are two reasons for using a copy of the goal.

First, we are interested in keeping the actual unin­ stantiated goal and instantiate it as necessary. This is to handle the effect of cut on committing to bindings as explained above. Second, for failures, the structure fail( Goal, Failures) is used to collect the proofs offail­ ures for the actual goal Goal, where Failures is a list of failures of this goal. Later, during explanation, the ac­ tual goal in this structure is used to resolve the variable differences in the tree by the scope information in the proofs of failure.

The non_singular predicate checks whether the given goal is a construct, such as a disjunction, conjunction, if­ then-else or the cut, in fact anything other than a single goal defined as a set of clauses in the program. Since com­ mitment is propagated in Prolog in these constructs, the interpreter must also adopt this behaviour. Upon check­ ing the goal, jilter_failure either propagates commitment or decides that a single goal ultimately fails and collects all the failures.

As mentioned earlier, generation of explanations ac­ tually depends on a good representation of the com­ putation . With an appropriate representation such as a proof tree, stilted English statements can be formed using straightforward techniques, described for example in [Sterling and Shapiro, 1986]. Similar techniques are used to make the proofs of computation collected by the two-layer interpreter more understandable.

Instead of providing a full "trace" of the entire pro­ gram, any of the subgoals within the body of the cur­ rently investigated clause can be chosen for further ex­ planation. This method allows the user to navigate the tree as desired and the explanation for each clause is given upon demand. In addition, it is possible in our ex­ planation system to reinvestigate the computation pro­ cess by starting from the top goal at any point, or go back to the previous rule which has been investigated.

Let us illustrate the form of explanation generated with an example. Consider the simple program below that defines hypothetical rules for Ph.D. candidacy. A student is required either to take the qualifying test and pass, or to take advanced courses and achieve a suffi­ ciently high grade point average.

candidacy(X) +- phd_student(X). qua lified_in_math(X) . qualified_in_math(X) +­ has_taken_test(X,math ). ! , passed_test(X,math ). qualified_in_math(X) +­ has_advanced_courses(X,Y). !, satisfies_gpa(X,Y). has_taken_test(Person ,Subject) +- exam( Person ,Subject, Date) . passed_test( Person ,Subject) +­ result( Person ,Subject, Date,pass ). phd_student(jim). exam(jim,math jan 1988). result(jim,math jan 1988,fail).

The query '1-candidacy(jim} gives a "no" answer. The explanation provided from the system is as below. User responses are italicized.

candidacyUim) fails because in the clause definition

1. phd_studentUim) succeeds.

2. qualified_in_mathUim) fails. >? 2. qualified_in_mathUim) fails because in the clause definition 1. has_taken_testU im, math) succeeds. 2. passed_testUim,math) fails. and the goal qualified_in_mathUim) is committed to this clause because there is a cut after has_taken_test. > ? applicable_rules. 2 rules in the database match the current goal. The computation is committed to the 1st (current clause). Therefore, the clause below is not reachable: qualified_in_mathUim) +- >? 2. has_advanced_coursesUim,Y), !, satisfies_gpaUim,Y) . passed_testUim,math) fails because in the clause definition 1. resultGim,math ,Date,pass) fails. >? 1. This goal does not match with the clause(s) of result/4.

There is 1 fact in the database for result/4: resultGim,math jan 1988,fail). > ? quit.

As can be seen from the example, the user can further investigate the reasons of success or failure for each goal. It ~s possible to request further explanation regarding which clauses for the goal qualified_in_math{jim} are not considered as alternative choices due to the presence of the cut. Further meta-knowledge about facts, such as result/4, will enhance the explanation capabilities.

The interpreter has been extended to generate detailed explanations for arbitrary Prolog programs. Other fea­ tures can be easily integrated to this shell, as in a pre­ vious version [Yal~inalp and Sterling, 1988], to provide history and depth information.

4 Explaining Partial Computations

The answer a user provides to a request for information may depend on what has transpired in the computation so far. Alternatively, as in an expert system for motor selection being developed at Case Western Reserve Uni­ versity [Discenzo et al., 1988], the user may demand to see the history of the computation when answering a why question. In either case, a "global picture" of the computation must be provided.

Recall that a full description of the computation after it terminates is contained in a proof tree. A fully instan­ tiated proof tree is not available for explanations during the computation. However, a partially instantiated tree which has full branches for completed portions of the computation and uninstantiated nodes for incomplete portions can be made available. 'Ve call this structure a partial proof tree . It is similar to the partially specified tree described in [Pereira and Shieber, 1987] for repre­ senting DCG parse trees during the parsing process.

A partial proof tree is easily generated by adding two extra arguments to the interpreter in Figure 1. The first argument represents the partial proof tree. It is dif­ ferent from the Proof argument described in the pre­ viou~ section and used in [Sterling and Lalee, 1986, Yal~malp and Sterling, 1988] because it can be accessed at any time during the computation. The branches are generated as a structure by using the second argument which shows the current node of the partial proof tree. The tree is instantiated at its leaves, when computation finitely succeeds or fails. In the beginning of the com­ putation, these two additional arguments represent the same entity, the uninstantiated tree, by the query :

?- solve_goal(Goal, Tree, Tree, Result}.

The nodes are generated in the branch layer during the computation by the second extra argument and the full partial proof tree is passed to all layers of the compu­ tation. For example, the partial proof tree is generated as follows for a conjunctive goal in the branch layer:

When additional information is required by the in­ terpreter, the user interacts with the system during the computation, by the last clause of solve_branch that rep­ resents askable goals. A how explanation of the partial proof tree can be presented during the computation. This is handled by passing the argument that represents the partial proof tree to investigate_goal which provides the how explanation. However, the explanation incorporates the partial instantiations for clauses and informs the user which goals which have not yet been solved.

5 Conclusions

The expressive power of the two-layer interpreter has been illustrated in the previous sections. The execution of the interpreter is faithful to Prolog's execution, al­ lowing the collection of information about the reasons for failure, including branches having been pruned due to cuts. The execution does not require prior knowledge of success and failure as in [Bruffaerts and Renin 1988 Sterling and Lalee, 1986] and all the computation is han~ dled by a single interpreter. We have also shown the util­ ity of generating partial proof trees. This allows explana­ tions to the user about the full computation both during and at the termination of computation.

The two-layer interpreter can be modified we believe to handle debugging systems in the style ~f Shapiro'~ algorithmic debugging [Shapiro, 1983] as well as expla­ nation systems. At the moment, the clauses that are not defined in the database are reported to the user as well as the clauses defined but do not match with the current goal. In addition, inaccesible clauses due to commitment are also noted. Hence, deguggers can benefit from this knowledge.

Our work can further be extended to explain Prolog programming cliches which have primarily a procedural reading. For example, a failure-driven loop, defined as follows, is a common construct.

The success of the last clause is meaningful only in relation to the repeated failure of the previous clause. By recognizing this construct as a special case, the proof tree kept for explaining the final clause will also contain information about the previous failures. Other cliches in this category are repeat loops, and cut-fail combinations.

More generally, we plan to investigate the interaction between programming style and explanation generation. A good way of using Prolog to construct expert systems is to design and implement an embedded language. Ex­ planations should be in terms of the constructs of the embedded language rather than Prolog structures. How­ ever Prolog constructs cannot be ignored entirely.

We conclude with a brief discussion of the signifi­ cance of our work to meta-level programming. Certain aspects of the object level computation are explicitly rep­ resented in a meta-interpreter while others are kept im­ plicit . Those explicit aspects are said to be reified while the implicit ones are absorbed. Reification and absorp­ tion were originally discussed for the Lisp community by Smith [des Rivieres and Smith, 1984], and have been used informally in logic programming by Ken Kahn and Ehud Shapiro. Standard Prolog meta-interpreters reify clause reduction and absorb unification, except for the decomposition of constructs, such as conjunction and disjunction. Failure is also absorbed in the standard four­ clause meta-interpreters hence we have no access to when it occurs or how backtracking affects the computation. In contrast, our layered abstraction reifies Prolog's control flow, where the communication between the goals and the state of the computation, namely success, failure or commitment, is explicit. Prolog's unification mechanism is absorbed in our model.

Other research in meta-level programming has pon­ dered the issue of reflection. We believe our work can be discussed within this terminology, but to do so is be­ yond the scope of this paper . For an overview of current meta-level programming and applications, see [Maes and Nardi, 1988, Lloyd, 1988].