TEC: Implementing Backtracking Predicates Using repeat/0

Backtracking is a subject that often drives TEC rule writers to distraction, especially those whose only programming experience is in procedural languages.

To them it's hard to understand how one can get anything done without looping control structures or grasp the power of a language that falls back to an earlier point of execution and resets all the variables changed since that point. As confusing as it can be, backtracking is perhaps the single most important feature that makes Prolog ideal for event correlation. With backtracking TEC rules can work through multiple solutions to problems, testing every alternative with efficient and concise code.

Most TEC rule programmers already use backtracking without thinking about it all. For example the all_duplicates and all_instances TEC predicates backtrack to find each event that matches the specified attributes. Also, hidden from the TEC rule programmers is Prolog backtracking to process each action, each rule, and each rule set. Many built-ins such as member/3 use backtracking to process lists and when programmers utilize backtracking to process facts asserted into the knowledge base, but there are many cases where Prolog does not provide backtracking predicates. For such cases there is repeat/0. This special built-in does nothing but create a choice points that Prolog uses in order to initiate backtracking.

A good illustration of this is reading a file. BIM Prolog provides a number of file I/O predicates (fopen/3, fclose/2, the various read*, etc.) but unfortunately none of them create choice points so programmers must turn to repeat/0 to create a choice point from which Prolog will backtrack. The normal procedure is to open the file using fopen/3 then backtrack on successful calls to a read predicate by utilizing not/1 to generate a failure when the read succeeds and a success when it fails so that a ! (cut/0) can be invoked that has the effect of ending the backtracking. Consider the code listed below:

fopen(_fh,'/etc/hosts','r'),
repeat,
not((readln(_fh,_line),do_something_with_line)),!,
fclose(_fh)

There are several difficulties with working with this algorithm. First off, all actions that are performed on each line must be encapsulated within a not/1 call so that successes become failures that trigger backtracking to the repeat and a failure becomes a success to permit a call to ! (cut) which clears the repeat choice point. The ! must be invoked at some point, otherwise prolog would backtrack infinitely. The second problem is the cut itself, when used in a rule it has the effect of a commit_set call. To get around this problem the above code must be a part of a custom predicate or the repeat and line processing code encapsulated within a findall/3 call:

fopen(_fh,'/etc/hosts','r'),
findall(_,(repeat,
not((readln(_fh,_line),do_something_with_line)),!),_),
fclose(_fh)

While this implementation can safely used in TEC rules, it is often not very helpful as the lines read in are only matched to _line within the context of the findall/3 call.

There is a way using repeat to generate backtracking predicates using repeat and are TEC rule safe. This is possible using the BIM Prolog built-in predicates mark/1 and cut/1. The mark/1 predicate marks a position in the Prolog execution sequence and when this position is passed to cut/1 all defined choice points defined after the mark/1 call are cleared. Consider the following code:

read_file_get_line(_fh,_line) :-
mark(_mark),
repeat,
read_file_readln(_fh,_mark,_line).

read_file_readln(_fh,_mark,_line) :-
re_read_file_readln(_fh,_mark,_line),!.

re_read_file_readln(_fh,_,_line) :- readln(_fh,_line).
re_read_file_readln(_fh,_mark,_) :- eof(_fh), cut(_mark), fclose(_fh).
re_read_file_readln(_fh,_mark,_) :- cut(_mark).

The important predicates are the re_read_file_readln/3 calls called from read_file_readln/3. The ! call limits each call to the fist successful call to re_read_file_readln/3 and since it is contained within a Prolog predicate body it is TEC rule safe. Once the readln/2 call fails cut/1 is invoked clearing the repeat/0 choice point. If for some reason the readln/2 failed and the file handle was not at the end of file mark, the final predicate cuts away repeat/0 choice point to prevent infinite backtracking.

To use this code from within a TEC rule simply consult, assert, or use the user_predicates file to load the above predicates into the Prolog knowledge base then call:

fopen(_fh,'/tmp/test.txt','r'),
read_file_get_line(_fh,_line)

Now Prolog will backtrack, matching _line with each line in the file as seen in this trace:

[3] 7:27:28 call reception_action tec_start
[4] call fopen( _1235 ,'/tmp/test.txt',r)
[5] exit fopen(0x835dda8,'/tmp/test.txt',r)
[6] call read_file_get_line(0x835dda8, _1864 )
[7] exit read_file_get_line(0x835dda8,'This a simple test of using repeat/0, mark/1, and cut/1 to read a file.')
[8] 7:27:28 exit reception_action tec_start
[9] 7:27:28 redo reception_action tec_start
[10] redo read_file_get_line
[11] exit read_file_get_line(0x835dda8,'Each line will be matched with a Prolog variable.')
[12] 7:27:28 exit reception_action tec_start
[13] 7:27:28 redo reception_action tec_start
[14] redo read_file_get_line
[15] exit read_file_get_line(0x835dda8,'Then the Prolog runtime engine will backtrack to the next line.')
[16] 7:27:28 exit reception_action tec_start
[17] 7:27:28 redo reception_action tec_start
[18] redo read_file_get_line
[19] exit read_file_get_line(0x835dda8,'When there are no more lines the call stops backtracking.')
[20] 7:27:28 exit reception_action tec_start
[21] 7:27:28 redo reception_action tec_start
[22] redo read_file_get_line
[23] exit read_file_get_line(0x835dda8, _1864 )
[24] 7:27:28 exit reception_action tec_start

With careful use of repeat/0, mark/1, and cut/1 a TEC rule programmer can create powerful Prolog backtracking predicates for use within TEC rules.

If there are any questions about the content of this article, please feel free to contact me at iv_blankenship@gulfsoft.com