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

2.8 More about Backtracking

The example in section 2.7 contained a coding mistake and the backtracking was inadvertent. As we saw with the example from section 1.1 demonstrating Goldbach’s conjecture, backtracking can be intended and useful. Let us see how that worked.

Goldbach’s Conjecture Example

Here is the rule:

IF      ?X = 3 OR ?X = 5 OR ?X = 7 OR ?X = 11 OR ?X = 13
AND     ?Y = 3 OR ?Y = 5 OR ?Y = 7 OR ?Y = 11 OR ?Y = 13
AND     ?A = ?X + ?Y
AND     ?A EQ ?Z
THEN    SUM_OF ?X ?Y ?Z

SYN renders this as

1 IF       ?X = 3
            OR ?X = 5
            OR ?X = 7
            OR ?X = 11
            OR ?X = 13
2      AND ?Y = 3
            OR ?Y = 5
            OR ?Y = 7
            OR ?Y = 11
            OR ?Y = 13
3      AND ?A = ?X + ?Y
4      AND ?A EQ ?Z
5 THEN     SUM_OF ?X ?Y ?Z

This translates as:

PROCEDURE SUM_OF(?X,?Y,?Z)

?X = 3
ELSE  ?X = 5
ELSE  ?X = 7
ELSE  ?X = 11
ELSE  ?X = 13
END IF

?Y = 3
ELSE  ?Y = 5
ELSE  ?Y = 7
ELSE  ?Y = 11
ELSE  ?Y = 13
END IF

?A = ?X + ?Y

IF    ?A EQ ?Z
END IF

END PROCEDURE

Here we have two series of ELSE statements without an introductory IF. This is because the first clause is an assignment ?X = 3 which isn’t a test. We also have the final test ?A EQ ?Z which translates to a Block IF with a null action.

Execution of the Rule

Let us consider what happens when this is called with ?Z = 12. The interpreter starts by setting ?X = 3. As there hasn’t been a test, none of the ELSE statements is executed and it proceeds to the statement ?Y = 3. Again there is a series of ELSE statements without an introductory test, so the interpreter proceeds to the statement ?A = ?X + ?Y where it sets ?A = 3 + 3 = 6.

Next it executes the test IF ?A EQ ?Z, which isn’t true. As there is no ELSE in this Block IF, the interpreter now backtracks. It goes back through the execution tree to the last statement which has an ELSE clause which hasn’t yet been tried. This is the ELSE immediately after the statement ?Y = 3. As a result, it now sets ?Y = 5 and goes forward again.

This time ?A = ?X + ?Y resolves as ?A = 3 + 5 = 8. It then executes the test IF ?A EQ ?Z, which is again False. It therefore backtracks to ?Y = 3 and thence to the as-yet-untried ELSE ?Y = 7. Once again it goes forwards, setting ?A = 3 + 7 = 10 and then testing IF ?A EQ ?Z, which again fails.

This process continues until all the ELSE clauses which reset ?Y have been tried and the test IF ?A EQ ?Z has failed in each case.

When the test fails for ?X = 3 and ?Y = 13 the backtracking now goes back beyond the block of ELSE statements which reset ?Y to the statement ?X = 3. It then tries the next ELSE clause, which sets ?X = 5. It goes forward again. As the interpreter has now gone back beyond the block of ELSE statements which reset ?Y, it “forgets” that it has previously explored all these possibilities and starts afresh, setting ?Y = 3 and then jumping to the statement ?A = ?X + ?Y. This sets ?A = 8 so the test IF ?A EQ ?Z fails.

As was done when ?X = 3, the interpreter backtracks repeatedly to ?Y = 3 and tries the various ELSE clauses. With ?Y = 7 it finds a value for which ?A EQ ?Z . It is then able to reach the END PROCEDURE statement and return to the calling procedure with the values ?X = 5, ?Y = 7, ?Z = 12.

This illustrates that backtracking can be useful provided you understand how it works, i.e. the sequence in which statements will be executed.

How to Avoid Backtracking

Conversely, if you lack confidence in how backtracking works, you should try to ensure that backtracking never happens and the code remains entirely procedural. The cardinal rules to prevent backtracking are:

  • ensure that statements which may behave as tests appear immediately after

  • a keyword in the Code;

  • an opening bracket; or

  • an OR in the Description;

  • ensure that each statement which may behave as a test has its corresponding OR clause which will always resolve TRUE;

  • make sure that brackets are balanced.

SYN can help you with this by showing you the logical structure of your code that the interpreter sees, not what you think it is.

Laying Out Rules to Show Logical Structure

You may find it helpful to write rules using a system of indenting similar to that used by SYN:

  • align each OR clause within a Block IF so that it is indented by 1 character from the first statement in the Block IF;

  • align each AND statement within a Block IF so that it is indented by 4 characters from the first statement of its block;

  • align closing brackets immediately below or one character to the right of the corresponding opening bracket.

Unfortunately, the maximum length of 64 characters for Descriptions makes it hard to maintain good layout. Compromises are often necessary.

Using this system of indenting we might rewrite the MAXOF rule as follows:

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

IF      ?X GE ?Y
            AND ( ?X GE ?Z
                      AND ?A = ?X + 0
                   OR ?A = ?Z + 0
                 )
         OR ?Y GE ?Z
            AND ?A = ?Y + 0
         OR ?A = ?Z + 0

THEN    MAX_OF ?X ?Y ?Z ?A

This has the advantage that it never resets ?A and so would work correctly without the “+ 0” to force statements such as ?A = ?X + 0 to be assignments. On the other hand, it is longer than the original MAXOF1 and arguably harder to understand and therefore to maintain.

With practice you will get used to reading such code as easily as its procedural equivalent. You will also avoid making mistakes which would cause backtracking. See also section 3.1 for details of how to prevent and detect backtracking.


Back                                Next
Comments