Programming Corner from Icon Newsletter 4

June 3, 1980; Icon Version 3


One aspect of Icon that distinguishes it from other languages with goal-directed evaluation (notably AI languages) is the limited scope of backtracking in Icon. In Icon, backtracking is strictly limited by syntactic constructions, as opposed to being determined by the computational history of the program. An advantage of this limitation is that the extent of backtracking can be determined from the program structure and undesired backtracking, one of the banes of goal-directed evaluation, can be avoided easily. There are also significant efficiencies that can be obtained by limiting backtracking.

Unfortunately, the early Icon documentation is not explicit about which syntactic constructions limit backtracking (this omission is corrected in the Version 3 documentation). Briefly stated, backtracking is limited by semicolons separating expressions, braces surrounding expressions, and by all control-structure reserved words except every-do. Thus in 
e1; e2
once evaluation of el is complete, no failure in e2 can cause backtracking into e1. Similarly, in 
if e1 then e2 else e3
once evaluation of el is complete, failure in e2 or e3 cannot cause backtracking into e1.

Within expressions, however, backtracking is unlimited. Thus in 
e1 || e2
if e1 succeeds, but e2 fails, backtracking into e1 occurs. If e1 produces an alternative, e2 is evaluated again.

This mode of evaluation is very general. For example, in 
f(x | y)
f(x) is called first. Should this call fail, backtracking to the argument expression occurs, and f(y) is called .

Note that there is nothing special about the conjunction operator: e1 & e2 is simply an operation that returns its right operand (as opposed to performing some computation).

This evaluation mechanism introduces all kinds of programming possibilities -- and also may lead to unexpected results and errors if it is not understood and used properly.

Consider the problem of writing a procedure to compress repeated, successive occurrences of a character to a single instance of that character. There are, or course, many ways of doing this. One method, using string scanning, is illustrated by the following procedure. 
procedure compress(s,c)
   local x

   s ? {
      while tab(upto(c)) do
         x : = move(1)
         tab(many(x)) := ""
         }
      return &subject
      }
end

Editor's Note, 2/25/96: Assignment to tab() is no longer legal in Icon.

Note that c may be a set of characters. (You might speculate on the wisdom and possible consequences of returning from within a scanning expression -- this style is used here to be compatible with both Versions 2 and 3.)

One question that you might ask about this solution is why the local identifier x cannot be removed as follows: 
s ? {
   while tab(upto(c) do {
      tab(many(move(1))) := ""
      }
   return &subject
   }
Consider the case in which there is just a single instance of a character in c. In the first solution 
tab(many(x)) := ""
fails and no replacement is performed. This failure is of no consequence, since 
x := move(1)
has already moved &pos past this character. (There is an implicit semicolon after the move expression.) Note that the compound expression in the do clause fails, but this again is of no consequence. (What would happen if backtracking was not limited by while and backtracking occurred into the control expression tab(upto(c)?) However, in 
tab(many(move(1)))

the failure of many results in backtracking into move. Although move has no alternatives, it does restore &pos to its previous value. (What are the consequences of this?)

It might seem that the auxiliary identifier and the division of the computation into two expressions are necessary to avoid unwanted backtracking. Not so -- consider 
s ? {
   while tab(upto(c)) do {
      tab(many({move(1})}) := ""
      }
   return &subject
   }
Here the braces provide an explicit barrier to backtracking, preventing &pos from being restored in case many fails.

Tricky? Perhaps, but the issues raised by goal-directed programming and the limitation of backtracking are worth study.
Icon home page