Aspen SCM‎ > ‎Expert System‎ > ‎2. Flow of Control‎ > ‎

2.7 Backtracking

So far, Aspen SCM Expert System has appeared to behave just as a procedural language does. But this is only because our example has been written correctly as quasi-procedural code.

Example of Unintended Backtracking

Consider our example MAXOF2 and suppose that we forgot (or did not know) that the statement ?A = ?X was interpreted as a test if ?A and ?X both had values. Our rule for this is:

MAXOF3  Returns ?A as greatest of ?X ?Y ?Z

IF      ?X GE ?Y AND ?A = ?X OR ?A = ?Y
AND     ?A GE ?Z OR ?A = ?Z
THEN    MAXOF3 ?X ?Y ?Z ?A

How will this work? The first line is fine because ?A starts FREE and is assigned the value ?X or the value ?Y depending on whichever is the greater. The second line will also work fine provided that the resulting ?A is greater than or equal to ?Z, i.e. provided ?Z is not the largest number among ?X, ?Y and ?Z.

But what if ?Z is the largest number? Suppose that we have ?X = 2, ?Y = 1, ?Z = 3. In this case the statement ?A = ?Z will resolve FALSE. What happens next is something which does not happen in a procedural language: the interpreter backtracks.

What Happens and Why

Backtracking is a process in which the interpreter backs up the logical tree which it has been following and then follows down the first branch which it has not already explored. To understand why it does this, we shall show explicitly the brackets which are implicit in the statement of the rule. To the right, we show the truth status of the clauses which we have already evaluated:

IF   ( ( ?X GE ?Y             IF   ( ( TRUE
             AND ?A = ?X )                 AND TRUE )
          OR ( ?A = ?Y )                OR ( UNKNOWN )
      )                             )
AND  ( ( ?A GE ?Z )           AND  ( ( FALSE )
          OR ( ?A = ?Z )                OR ( FALSE )
      )                             )
THEN ( MAXOF3 ?X ?Y ?Z ?A )   THEN ( MAXOF3 2 1 3 ?A )

This simplifies to the proposition:

IF     ( TRUE OR UNKNOWN )
AND    ( FALSE )
THEN   ( MAXOF3 2 1 3 ?A )

Now although this may appear to mean that the proposition MAXOF3 2 1 3 ?A must be FALSE, there is another possibility. This is because the truth of the clause on the second line prefixed by AND in the Code is not fixed. Its truth or falsity depends on how the preceding clauses were evaluated.

The interpreter backtracks from the statement ?A = ?Z towards the initial IF to see if there is a clause which it has not evaluated which might enable it to prove the predicate. It finds the statement ?A = ?Y whose status is currently UNKNOWN. It evaluates this, setting ?A = 1. This works as an assignment rather than a test because during back-tracking the interpreter frees local variables whose values were assigned in the back-tracked code.

Going Forward Again after Backtracking

The interpreter then moves forward again and tests whether ?A GE ?Z, i.e. 1 GE 3. As it isn’t, it then evaluates the statement ?A = ?Z, i.e. 1 = 3. This resolves FALSE. There are now no UNKNOWN clauses in the tree, so the interpreter declares the entire rule to be FALSE. This can be seen in the trace of the rule (which was called from a rule called TESTMAX and which has been annotated with comments):

TRUE         RULE: MAXOF3     IF: [?X=]2 GE [?Y=]1
TRUE         RULE: MAXOF3     IF: ?A = 2 = [?X=]2
FALSE        RULE: MAXOF3     IF: [?A=]2 GE [?Z=]3
FALSE        RULE: MAXOF3     IF: ?A = 2 = [?Z=]3  ! N.B. Test
TRUE         RULE: MAXOF3     IF: ?A = 1 = [?Y=]1  ! Backtracked!
FALSE        RULE: MAXOF3     IF: [?A=]1 GE [?Z=]3 ! Forward again
FALSE        RULE: MAXOF3     IF: ?A = 1 = [?Z=]3  ! Test fails
                                                   ! again; search
                                                   ! tree exhausted
FALSE  RULE: TESTMAX    IF: MAXOF3 2 1 3 [?A=]****


Back                                Next
Comments