4.8 Recursion

Writing Recursive Rules

The Aspen SCM Expert System language has been designed to support recursion and does so efficiently. When writing recursive rules you need to be very disciplined as to the scope of the various resources which you are using and the values which they will have each time the rule is called.

Local variables are the safest and easiest entities to use as they are local to each call to the rule. There is therefore no possibility of values being confounded between calls.

Sets, tables and global variables are clearly resources which are shared by all calls to a recursive rule. However, whereas global variables are static and therefore of limited use in recursive rules, sets and tables are dynamic. In particular the APPEND command adds elements to the end of a set and therefore provides a stack-like data structure.

Note, however, that it is inefficient to use the APPEND command on its own to manage the growth of a set. If a set is full, i.e. has as many elements as the maximum count, the APPEND command increases the maximum count by 10. It copies the set and all the tables which are indexed by the set to new areas of memory which are dimensioned by the new maximum count. It does this each time the set fills up, i.e. every tenth APPEND command.

The REPEAT command is even worse. If a set is full, each time a REPEAT command is executed the interpreter copies the set and all tables indexed by it to new areas of memory indexed by the new maximum set count, which is 1 greater than the last maximum set count.

It is much more efficient to increase the maximum count of the set in larger increments by using the command:


Use Rule Arguments in Preference to Globals

A problem which arises with recursive code is that one often wants to use a “blank common” global variable to keep track of some quantity in a loop (a local variable cannot be used as local variables are freed each time the loop iterates). As a global variable is a single resource which is shared by all calls to the recursive rule, this appears to be impossible.

One solution is to test on entry to the rule whether the global variable is already set. If it is, the value is saved in a local variable and then the global is reset to the value of the local immediately before returning to the called rule. Because local variables are local to the call to the rule, this enables the values of the global variable to be saved simultaneously for each call in the hierarchy.

Better still is to avoid the use of globals entirely by having the erstwhile global as an argument to the recursion. This can be seen in the following example:

EUDMSG81 Tokenise ?ARG from ?ARGIPOS putting ?ARGNUM in Desc
        /* Quit if ?ARG is empty */
AND     ( ?LEN EQ 0

        /* Quit if ?ARGIPOS isn’t in the string */

           OR ?ARGIPOS EQ 0
           OR ?ARGIPOS GT ?LEN
        /* Otherwise get the next token */

           OR ?NEWIPOS = ?ARGIPOS + 0
              AND ?TOKEN = SUBSTR(?ARG,?NEWIPOS,0)

        /* See if it’s a special token for which we must recurse */

              AND ( NOT ?TOKEN IN EUDLIST

        /* It’s not; APPEND token to EUDTOKEN */
                        AND APPEND EUDTOKEN ?TOKEN

        /* Test whether any more tokens; if there are, recurse */
                        AND ( ?NEWIPOS EQ 0
                               OR EUDMSG81 ?ARG ?NEWIPOS ?NEWNUM

        /* It’s a special token ; get list and recurse on it */

                    OR ?LIST = EUDLIST(?TOKEN,D)
                       AND EUDMSG81 ?LIST 1

Debugging Recursive Rules

Recursive rules are harder to debug than ordinary ones because of the possibility of “infinite recursion”, i.e. the rule calls itself infinitely. Once this happens, the only escape is to kill the process from the Task Manager, thereby losing the work, including any trace which may have been written to ETRACE. You can avoid this by writing the trace to a file, by setting CNTLE(TRTAB,1) = FILE and CNTLE(TRFILE,1) = FILE.LIS (or whatever). As the writing to the file is buffered, you are likely to lose the end of it, but what remains should help to identify what was going on.

You can avoid the need to kill the process by including a TIMEOUT statement in the procedure which calls the recursive rule. This enables a time limit to be specified after which the Aspen SCM Expert System interpreter will interrupt processing. The timer continues to run until you turn it off, so remember to include a TIMEOUT OFF statement at the top of your program; otherwise next time you start the program the old TIMEOUT limit will fire and your program will be interrupted.

Back                                Next