Programming Corner from Icon Newsletter 11

March 8, 1983; Icon Version 5

Solutions to the Exercises in Newsletter 10

The first exercise asked for expressions that produced certain result sequences. There are several ways of doing these, of which one set follows. Some of the parentheses are unnecessary and are included only for clarity.

(1) The squares of the positive integers:

(i := 1) | |((i +:= 1) ^
2)

(2) The factorials: (j := i := 1) | |(j *:= (i +:= 1))

(3) The Fibonacci numbers: ((i | j) := 1) | (|(i | j) := i + j)

(4) All nonempty substrings of a string s:

s[(i := 1 to *s):((i +
1) to (*s + 1))]

(5) All the odd-sized substrings of s:

s[(i := 1 to *s):((i + 1) to
(*s + 1) by 2)]

The expression for generating the Fibonacci numbers is due to Bill Mitchell.

The second exercise turned the issue around and asked what result sequences were produced by certain expressions. The answers are:

(1) !&lcase || !&ucase: {

"aA", "aB",
"aC", ..., "zX", "zY", "zZ"

} (26^2 strings in all)

(2) (1 to 3) + (1 to 3): {2, 3, 4, 3, 4, 5, 4, 5, 6}

(3) (1 to 3) \ (1 to 3): {1, 1, 2, 1, 2, 3} (Note that the expression that limits a result sequence can, itself, be a generator.)

(4) (1 to 5) = (4 to 9): {4, 5}

(5) 1 = |0: this is a "black hole"! It never produces a result, but its evaluation does not terminate. The reason is that the right argument produces 0, which is not equal to 1. The resulting failure cause the the right argument to be resumed. Since it is a repeated alternation, it produces 0 again, and so on. This phenomenon led to the decision to make repeated alternation terminate if its argument ever has an empty result sequence. Otherwise, for example, |read() would turn into a black hole when the end of the input file is reached. Fortunately, expressions such as the one above do not seem to occur in ordinary programming contexts. This black-hole phenomenon should not be disturbing -- it is no worse than an expression such as

until 1 = 0

Limitation

In a recent letter, John Polstra commented that the limitation control structure prevents reversal of assignment in reversible-assignment expressions. For example, in

(x <- y) \ 1

the assignment to x is not reversed. This is intentional and not an implementation or design error. There are two factors involved. In the first place, the limitation control structure effectively stands between the expression it limits and the surrounding context. In this role, the limitation control structure simply limits the number of times the expression may be resumed. In the example above, the reversible assignment can be resumed only once ("resumed" as used here includes the initial evaluation, which assigns the value of y to x). On the other hand, reversal of the assignment occurs when the reversible assignment operation is resumed the second time. Although reversible assignment does not produce a second result, its resumption gives it the opportunity to reverse the assignment. The same thing is true of reversible exchange, tab(i), and move(i).

N Queens

The non-attacking 8-queens problem is used to the point of boredom in demonstrating backtrack programming. There is a solution in the Icon book. A more difficult problem is producing a program that will solve the n-queens problem, where n is a parameter. Try this one -- it is not trivial.

A Puzzle

What does the following program do, and why?

procedure main()
   write(
      "abcde" ? {
         p() := "x"
         write(&subject)
         &subject
         }
      )
end
procedure p()
   suspend &subject[2:3]
end

Icon home page