Language facilities for programmable backtracking

Most languages intended for artificial intelligence applications include a search and backtracking facility. While built-in backtracking facilities are convenient, they are often too inflexible for use beyond a limited range of applicability. Other mechanisms, such as those based on explicit manipulations of bindings or stack frames, tend to be very unstructured, and give the programmer little control over the backtracking process. This paper describes the SL5 programming language and its use for “programmable backtracking.” SL5 includes a general procedure mechanism that permits procedures to be used as recursive functions or as coroutines. Using this mechanism, the programmer can construct control hierarchies that are tailored to the specific application. A string pattern-matching facility is given as an example of the use of the SL5 facilities.