Previous Table of Contents Next


6.2.2. Generators and Goal-Directed Evaluation

In the preceding section, the concept of alternation was introduced. As noted there, alternation may produce more than one value. Expressions that are capable of producing more than one value are called generators.

A generator produces more than one value only if the context in which it is evaluated requests more than one value. The values are produced in succession as they are requested.

There are two contexts in which a generator may be requested to produce more than one value: iteration and goal-directed evaluation.

6.2.2.1. Iteration

Iteration is produced by the control structure

    every exp1 do expr2

In this control structure, the generator expr1 is requested to produce all its values. For each one produced, expr2 is evaluated. For example,

    every i := 1 | 2 | 3 do
       write(i)

writes 1, 2, and 3.

A generator that is useful in iteration is

    i to j by k

which generates the integers from i to j with increments of k. The by clause is optional; if it is omitted, the increment defaults to 1. For example,

    every i :=  –5 to 5 do
       write(i)

writes –5, –4, … –1, 0, 1, … 4, 5.

The do clause in iteration is optional, and this expression can be written more compactly as

    every write(–5 to 5)

The function seq(i, j) generates an infinite sequence of integers, starting at i and incrementing by increments of j. If i or j is omitted, it defaults to 1. Thus, seq() generates the positive integers.

6.2.2.2. Goal-Directed Evaluation

Goal-directed evaluation, which is implicit in expression evaluation in Icon, attempts to obtain a successful result for a computation by requesting additional values from generators if necessary.

Failure drives goal-directed evaluation; it is failure that causes requests for additional values from generators.

A simple example is

    if (i | j) = 0 then proceed() else pause()

The generator (i | j) first produces the value of i, which is compared with 0. If the comparison succeeds, the then clause is evaluated. If, however, the comparison fails, another value is requested from (i | j), which produces the value of j. If the comparison succeeds, the then clause is evaluated. If it does not succeed, the failure causes another value to be requested from (i | j). Because it has no more values to generate, (i | j) = 0 fails and the else clause is evaluated. The net effect is that the then clause is evaluated if i or j equals 0, but the else clause is evaluated otherwise.

From an operational point of view, a generator that produces a value and is capable of producing additional values suspends. It is resumed to produce another value by a request in the context in which it is evaluated. If the context for evaluation leaves an expression in which there is a suspended generator, the suspended generator is discarded.

The extent of expression evaluation is limited by bounded expressions; after evaluation in a bounded expression is complete, suspended generators in the bounded expression are discarded and cannot be resumed. The control expressions in control structures are bounded. For example, in

    if expr1 then expr2

expr1 is bounded. If expr1 succeeds, any suspended generators in expr1 are discarded. Consequently, they cannot be resumed if expr2 fails. Expressions followed by semicolons or ends of lines also are bounded. Therefore, in

    expr1; expr2

after the evaluation of expr1 is complete, whether successful or not, any suspended generators in it are discarded and evaluation moves on to expr2.

6.2.2.3. Procedures as Generators

A procedure can generate a sequence of results by using suspend in place of return. An example is

    procedure power(i, j)

       k := i

       every 1 to j do {
          suspend k
          k *:=  i
          }

    end

This procedure generates the powers of i from 1 through j. It suspends for each power. If it is resumed, it computes the next power and produces it. If it reaches the end of the every loop, control flows off the end of the procedure, producing failure as mentioned earlier. This indicates that the procedure has no more values to produce.

Note that a generator may be capable of producing an unlimited number of values. Removing the limit on the powers in the previous procedure illustrates this:

    procedure power(i)

       k := i
       
       repeat {
          suspend k
          k *:=  i
          }

    end

Because a generator only produces values on request, a generator that is capable of producing an unlimited number of values may produce only a few. For example, the loop

    every j := power(i) do
       if j > 1000000 then break else write(j)

stops writing powers when a value exceeds 1,000,000. At this point, break terminates the loop and the suspended generator is discarded.

6.2.2.4. Other Control Structures

Limitation

The number of results that a generator is allowed to produce can be limited by using the control structure

    expr \ i

which limits expr to at most i results. For example,

    every write(power(i) \ 10)

writes only the first 10 powers of i.

Repeated Alternation

The control structure

    |expr

generates the values of expr repeatedly.

This can be useful for producing sequences, as in

    |(1 to 3)

which generates 1, 2, 3, 1, 2, 3, and so on.


Previous Table of Contents Next