3.8 Breaking a Loop at the Predicate

“Expert System”  Approach

Our Goldbach example from section 2.b continued looping even after it had found a solution. We can stop this by putting a BREAK statement onto the THEN clause:

IF      ?X IN ODDPRIME
AND     ?Y = ?Z - ?X
AND     ?Y IN ODDPRIME
THEN    SUM_OF ?X ?Y ?Z AND BREAK ?X

This could be described as the “Expert System” way of finishing a loop. More generally we might have:

IF      ?ITEM IN SET
            AND <intermediate code without ORs>
            AND <test on ?ITEM>
            AND <further code for successful ?ITEM>
THEN    <predicate ?ITEM> AND BREAK ?ITEM

This is very elegant. It loops through SET until it finds the item where the test succeeds, executes the further code and then the predicate, after which the loop is stopped by the BREAK. But it is dangerous because it involves having the <test on ?ITEM> after intermediate code. When this test fails it causes backtracking which is only halted by the loop statement itself. So this technique is really only usable if the intermediate code does not include any tests which evaluate TRUE which have OR statements associated with them.

Finding the Position of a Substring in a String

The following example shows how the “Expert System” approach can be used to implement a standard problem, finding the position of a substring in a string, or returning 0 if it cannot be found. In this case we have a WHILE loop with two tests applied in succession. The rule always reaches the predicate and ends TRUE. Note also the dummy WHILE loop which is started when ?MAXLOOP is 0; this is required in order to ensure that the BREAK ?ILOOP statement in the conclusion will work in all cases.

INDEX   Returns position ?IPOS of ?SUBSTR in ?STRING after ?START
   
/* Get the length of the string and the substring */
       
IF      ?STRLEN = STRLEN ?STRING
AND     ?SUBLEN = STRLEN ?SUBSTR
       
        /* Work out the maximum number of times to loop */
       
AND     ?MAXLOOP = ?STRLEN + 1
AND     ?MAXLOOP = ?MAXLOOP - ?START
AND     ?MAXLOOP = ?MAXLOOP - ?SUBLEN
       
        /* If ?MAXLOOP is less than 0, set ?IPOS = 0 and start */
        /* dummy loop so that we can BREAK out of it on the */
        /* THEN clause     */
       
AND     ( ?MAXLOOP LT 0
              AND ?IPOS = 0
              AND WHILE ?ILOOP
       
        /* ?MAXLOOP is 0 or more; start a genuine loop  */
       
           OR WHILE ?ILOOP
       
        /* Get the substring starting at ?ILOOP'th position */
       
                  AND ?IPOS = ?START + ?ILOOP
                  AND ?STRIPOS = SUBSTR(?STRING,?IPOS,?SUBLEN)
       
        /* Test whether found it: if so, will go forward to */
        /* THEN clause and BREAK, proving rule with the */
        /* correct ?IPOS */
       
                  AND ( ?STRIPOS EQ ?SUBSTR
       
        /* Haven't found the substring; see whether finished */
        /* looping. If we haven't, interpreter will backtrack */
        /* to WHILE clause and then iterate forward again; */
        /* if we have finished, set ?IPOS to 0 and go forward */
        /* to the THEN clause and BREAK */
       
                         OR ?ILOOP EQ ?MAXLOOP
                            AND ?IPOS = 0
                       )
         )

        /* Reach the predicate once only and BREAK out of loop */
       
THEN   INDEX ?STRING ?SUBSTR ?START ?IPOS AND BREAK ?ILOOP


Back                                Next
Comments