Programming Corner from Icon Newsletter 35

March 1, 1991; Icon Version 8

Syntax

Steve Wampler sent us this question:
Why doesn't the following code produce a syntax error? I know why, given the absence of a syntax error, it's an infinite loop, but I don't understand why there isn't an error on the missing left hand side of the assignment operator

The code fragment he sent surely looks syntactically wrong: 
while next := read() do
   write(next)
Ken Walker provided the answer: Assignment in Icon has the form 
expr1 := expr2
where expr1 and expr2 can be any expressions. The control structure next is an expression, so the program fragment above is syntactically correct, with expr1 being next. Of course, when this expression is evaluated, it transfers control back to the beginning of the while loop.

Mistakes like the one above are easy enough to make -- next is a perfectly reasonable mnemonic for the intended use. And it's easy to forget that Icon is an expression-based language -- no statements, just expressions. That's useful in many situations, but it allows some ridiculous expressions to be syntactically correct.

A Prime Number Generator

Viktors Berstis sent us this interesting program for generating prime numbers. The technique is due to John Conway and uses the FRACTRAN language, which is interpreted here.

This procedure doesn't get very far without large integer arithmetic. Otherwise, the program does not terminate of its own accord. It stops generating results when the primes exceed the powers-of-two-table, but it keeps on computing primes until the program runs out of memory or something breaks.

One interesting thing about this technique is that each prime is computed from the preceding one.
A word of caution: the technique also is very slow. 
procedure main(arg)
   limit := integer(arg[1]) | 30
   every write(genprime(limit))      # typical usage
end
procedure genprime(limit)

#   This is a list of 14 fractions that encode a 
#   FRACTRAN program for computing prime numbers. 

   f := list(14)
   f[ 1] := fract(17,91)
   f[ 2] := fract(78,85)
   f[ 3] := fract(19,51)
   f[ 4] := fract(23,38)
   f[ 5] := fract(29,33)
   f[ 6] := fract(77,29)
   f[ 7] := fract(95,23)
   f[ 8] := fract(77,19)
   f[ 9] := fract( 1,17)
   f[10] := fract(11,13)
   f[11] := fract(13,11)
   f[12] := fract(15, 2)
   f[13] := fract( 1, 7)
   f[14] := fract(55, 1)

#  Construct a table of the powers of two.

   pot := table()
   power := 1
   every n := 0 to limit - 1 do {
      pot[power] := n
      power *:= 2
      }

#  Generate the primes.

   s := 2
   repeat {

   #  Multiply s by the first fraction that produces an
   #  integer result.

      x := !f & (s * x.numer) % x.denom = 0
      s := (s * x.numer) / x.denom

   # The exponent is prime if s is a power of two;
   #  if so, produce it.

      suspend \pot[s]

      }

end
Icon home page