Programming Corner from Icon Newsletter 6

May 1, 1981; Icon Version 2

An Idiom

Every programming language has a number of particularly apt idioms. Consider the expression 
x <- x
At first sight, this expression appears to be a curiosity. However, when used in a conjunction expression, it serves as a stack with automatic pushing of the value of x when it is evaluated and automatic popping of the value of x during backtracking. Thus, in 
expr1 & (x <- x) & expr2
if expr1 succeeds, the value of x is pushed and expr2 is evaluated. If expr2 fails, the value of x is popped and expr1 is reactivated.

In situations in which several expressions are connected by conjunction to obtain the first-in, last-out sequencing provided by goal-directed evaluation, this reversible-assignment idiom is both concise and (once it is understood) clearly indicates its purpose.

Solutions to Questions Posed in Newsletter 5

In the programming corner of Newsletter 5, several programming questions were posed. These questions are restated below with their answers.

Problem 1: Q: What is the output produced by each of the following expressions? 
(a) every write((0 | 0) to 7)
(b) every write(0 to 3,0 to 7,0 to 7)
(c) every write(1 | 2 to 3 | 4 by 1 | 2)
(d) every 1 to 3 do every write(1 to 3)
A: These expressions illustrate the use of every to force generators through all their results. The left-to-right, last-in first-out order of results is shown by the output below. Ellipses are used to compress long sequences where the output follows an obvious pattern. 
(a) 0     (b) 000      (c) 1     (d) 1
    1         001          2         2
    2          .           3         3
    3          .           1         1
    4          .           3         2
    5         076          1         3
    6         077          2         1
    7         100          3         2
    0         101          4         3
    1          .           1
    2          .           3
    3          .           2
    4         176          3
    5         177          2
    6         200          2
    7         201          3
               .           4
               .           2
               .           4
              276
              277
              300
              301
               .
               .
               .
              376
              377
Problem 2: Q: For arbitrary procedures f(x,y) and g(x,y), what is the sequence of calls produced by 
every (f | g)(1 to 3, 4 | 5)
A: 
f(1,4)
f(1,5)
f(2,4)
f(2,5)
f(3,4)
f(3,5)
g(1,4)
g(1,5)
g(2,4)
g(2,5)
g(3,4)
g(3,5)
Problem 3: Q: Given 
s1 := "aeiou"
s2 := "abecaeioud"
what are the outcomes of 
(a) (find | upto)(s1,s2)
(b) (find | upto)(s2,s1)
(c) (if size(s1) > size(s2) then upto else find)(s1,s2)
A: The answer to this question illustrates that functions are data objects and that function application involves applying the value of a (function-valued) expression, such as (find | upto). In addition, goal-directed evaluation applies to such expressions themselves. In fact, an expression such as expr(expr1, ..., exprn) involves the mutual goal-directed evaluation of expr, expr1, ..., exprn in which the value of expr is applied to expr1, ..., exprn. The outcomes for the expressions above are 
(a) 5
(b) 1
(c) 5
Problem 4: Q: What are the outcomes of the following expressions? (Note any that produce errors.) 
(a) (x | y) := 3
(b) (x & y) := 3
(c) (1 & x) := 3
(d) (x & 1) := 3
(e) (x + 1) := 3
A: The term outcome is used in the technical sense here. As indicated, the outcomes of the first three expressions are variables, since assignment returns its left operand as a variable. 
(a) x (assigned the value 3)
(b) y (assigned the value 3)
(c) x (assigned the value 3)
(d) error (variable expected)
(e) error (variable expected)
Problem 5: Q: Given the procedure 
procedure drive(x)
   fail
end
What is the output produced by 
(a) drive(write(1 to 7))
(b) drive(write(0 to 7,0 to 7))
A: This problem illustrates the relationship between goal-directed evaluation and the control structure every, which forces generators to produce all their results. The same effect can be produced by a procedure that only fails, hence forcing goal-directed evaluation to produce all the results of its argument. 
(a) 1    (b) 00
    2        01
    3        02
    4         .
    5         .
    6         .
    7        06
             07
             10 
             11
             12 
              .
              .
              .
             66
             67
             70
             71
             72
              .
              .
              .
             76
             77
Problem 6: Q: What does the execution of the following program do? 
procedure main()
   f(f := write)
end
A: This one is tricky. Since the program has no procedure declaration for f, one might suppose the execution of the program is an error. Recall Problem 3 above, however, noting that function and procedure applications are evaluated the same way. Furthermore variables are not dereferenced until all the arguments are evaluated. This applies to the "zeroth" argument, which is the function or procedure to be applied. Evaluation of the first argument assigns a function value to f (i.e., the value of write). Hence this expression is equivalent to write(write) and produces the output 
function write
(The form of the output is a consequence of "imaging" a non-string value for the purposes of output. This is the same imaging that is used in tracing procedure calls.)

Problem 7: Q: The following procedure is proposed as a generator of "words" -- strings of consecutive letters -- in the lines of the input file. It does not work properly, however. What does it actually do and what is the cause of the problem? Rewrite the procedure to work properly. 
procedure genword()
   local line
   static letters

   initial letters := &lcase ++ &ucase

   while line := read() do
      line ?
         while tab(upto(letters)) do
            suspend tab(many(letters))

end
A: The problem lies in the suspend expression. suspend is like every -- it forces its argument to generate all its results. Although neither tab nor many have alternative results, tab does restore the value of &pos if it is resumed to produce a second result. Hence, &pos is always restored to its position prior to the first word and this procedure loops, continually returning the first word of the first line of input!

There are two ways of circumventing this problem: use of an auxiliary identifier or explicitly preventing generation of alternatives in the suspend expression, and hence the backtracking done by tab. Thus, the while loop can be rewritten as 
while tab(upto(letters)) do
   {
      t := tab(many(letters))
      suspend t
   }
or 
while tab(upto(letters)) do
   suspend tab(many(letters)) \ 1
Incidentally, this problem is sufficiently insidious that it deserves attention in the design of Icon. The subtlety of the problem lies in the fact that, except for reversible assignments, Icon does data backtracking only in tab and move.
Icon home page