3.1 Preventing Backtracking

Using Complete Block IF Constructs

We can avoid backtracking entirely if we write our code as the translation of complete block IF constructs, i.e. where there is an ELSE clause for each test:

IF (test 1) THEN
    (action 1)
ELSEIF (test 2) THEN
    (action 2)
    (default action)

This translates to

IF <test 1>
    AND <action 1>
OR <test 2>
    AND <action 2>
    AND <default action>

Why Complete Block IFs are Sometimes Impracticable

Unfortunately it is not practicable to write code so that everything which can resolve FALSE is encased in a complete block IF. This is because it is not just tests which can resolve FALSE. We can divide Aspen SCM Expert System statements into three classes:

  • those which either resolve TRUE or cause an error, thereby stopping the interpreter: assignments; arithmetic statements; Aspen SCM commands;

  • statements which resolve TRUE or FALSE (or cause an error): tests; functions; macros; etc

  • predicates and rules, which resolve TRUE, FALSE or UNKNOWN.

In practice one tends to encase only tests in complete block IFs. Sometimes predicates are encased with an OR TRUE to protect them against returning UNKNOWN. If any other statement resolves FALSE it causes backtracking.

How to Trap Backtracking

Backtracking can be detected by including extra lines of code such as

AND     ( TRUE OR CRASH "Middle of MYRULE" )

where CRASH is a predicate which does just that, e.g. by dividing by zero. As this traps a back-track we shall call it a backtrap. When the interpreter stops at an error it reports the rule and the interpreted source code of the statement where it has stopped, thereby showing immediately where backtracking has occurred.

Clearly it is better to prevent backtracking where it is not wanted by writing code which is properly structured with complete block IFs than to detect it by including backtraps. But backtraps can be included in code with minimal effort. They can best be considered as the coding equivalent of antibodies. You can inoculate procedural code against backtracking by including a sprinkling of them: they then stand guard ready to spring into action should backtracking occur.

A backtrap which is placed at the top of a rule protects the rule against ending FALSE (because if the rule is about to end FALSE the interpreter would backtrack to the top, fall in the trap and crash). Alternatively this may be achieved by having an OR CRASH clause just before the predicate with the OR in the Code

THEN     <Predicate>

Note that neither of these offers protection if the code contains loops where the outermost loop is a WHILE or where it is stopped by a BREAK statement.

Another method of detecting predicates which end FALSE is the UNTRUE rule described in section 2.d. This procedure also detects predicates which return UNKNOWN and non-existent predicates.

Back                                Next