Chapter 5: Expressions

The iterators control how many times the body is evaluated. Any number of iterators may be used on a loop, and each is either a "while" or a "for" iterator.

A loop with no iterator repeats forever, unless terminated by an error or some other event. For example:

#include "aldor"

-- This will repeat forever...

repeat {
        print << "Row, row, row your boat," << newline;
	print << "Gently down the stream." << newline;
	print << "Merrily, merrily, merrily , merrily," << newline;
	print << "Life is but a dream." << newline;
	print << newline;
}

Two forms, "break" and "iterate," may be used withing the loop body to control the loop evaluation, as described later on.

While-iterators

A "while" iterator, allows a loop to continue so long as a condition remains true. The syntax of a "while" iterator is

while condition

• If it is true, the evaluation of the loop proceeds.
• If it is false, then the loop is terminated.

Just as with "if" and other expressions having tests for control flow, if the condition of a"while" is not a Boolean value, then an appropriate "test" function is applied to determine the sense of the condition.

The following example shows a repeat loop using a while iterator:

#include "aldor"

import from Integer;

n := 10000;
k := 0;        -- 'k' counts the number of iterations.

while n ~= 1 repeat {
        k := k + 1;

        if odd? n then n := 3*n + 1 else n:= n quo 2;
}
print << "terminated after " << k << " iterations." << newline;

This loop counts the number of times the body has to be evaluated in order for n to reach one. When n reaches 1, the evaluation of the loop is terminated, and the count is printed. (It is a well-known conjecture that this process will terminate for all integer n > 0. This is sometimes called the "3n + 1 problem".)

In a case such as this it is important to give k an initial value, since the loop may be iterated zero times! In fact, if the while condition is false the first time that it is evaluated, then the repeat body will not be executed at all:

#include "aldor"
      
import from Integer;

n := 0;

while n > 0 repeat {
    -- This will never be executed.
    print << "Hello world!" << newline;
}

For-iterators

Very often, loops are used to traverse certain kinds of data structures, such as lists, arrays or tables, or to execute some operations for all the numerical values in a defined range.

"for" iterators make this sort of loop convenient to write. Take, for instance, the following examples:

-- Add up the elements of a list, return the sum.
sum(ls: List Integer): Integer == {
        n := 0;
        for i in ls repeat n := n + i;
        n
}

-- Add up the elements of an array, return the sum.
sum(arr: Array Integer): Integer == {
        n := 0;
        for i in arr repeat n := n + i;
        n
}

-- Add up the odd numbers in a range, return the sum.
sum(lo: Integer, hi: Integer): Integer == {
        n := 0;
        if even? lo then lo := lo + 1;

        for i in lo..hi by 2 repeat n := n + i;
        n
}

import from List Integer;

-- Use 'sum: List Integer -> Integer':
print << sum([1,2,3,4])     -- Prints '10'.

The "for" iterators in these examples all have the form

for lhs in Expr

The lhs part specifies a varable which will take on the successive values over the course of the iteration. The lhs has the form

[free] name [: Type]

The type declaration is optional. If it is missing, the type of the variable is inferred from the source of the values, Expr

The "free" part of the lhs determines the scope of the variable. Without it, a new variable of the given name is made local to the loop. If the word "free" is present, then the loop uses an existing variable from the context. In this case, the value of the variable is available after the loop terminates.

The example above can be rewritten useing a free loop variable:

# include "aldor"

import from Integer;

n := 10000;
k := 0                        -- Make a top-level variable 'k'.

for free k in 1.. repeat {   -- Use above 'k' freely in the loop.

        if odd? n then n := 3*n + 1 else n := n quo 2;

        if n = 1 then break; -- exit the loop if n = 1
}

-- Here the last value of 'k' is available.
print << "terminated after " << k << " iterations." << newline;

The previous example uses the "break" construct explained later in this section. When a break is evaluated it causes the termination of the loop. In this case, the break is the only exit point of the loop, because we are iterating over an open segment, producing infinitely many values: 1, 2, 3, ...

Now we turn our attention to the expression traversed by the "for" iterator. In the examples, we have seen

• a list, "i",
• an array, "a", and
• integer segments, "lo..hi by 2" and "1..".

In general, the "for" iterator expression must have type Generator T, where T is the type of the "for" variable. If the expression is not of this type, then an implicit type will be used. See chapter 9 for a description of generators and how to create new ones.

The examples we have seen work because the list, array and segment types provided by "libaldor" export generator functions. Other examples of generators provided by "libaldor" are "step", provided by SingleFloat, DoubleFloat and Float, which creates uniformly spaced points on a floting point interval, and "tails" which provides successive tails of a list.

There is a second form of "for" iterator which filters the values used. This has the form:

for lhs in Expr | condition

This kind of "for" iterator skips those values which do not satisfy the condition. For example, the sum example we saw earlier could have been wrtten as:

#include "aldor"

-- Add up the odd numbers in a range
sum(lo: Integer, hi: Integer): Integer == }
        n := 0;
        for i in lo..hi | odd? i repeat n := n + 1;
        n
}

Multiple interators

A "repeat" loop may have any number of iterators, with the following syntax:

iterator1 ... iteratorn repeat Body

The loop is repreated until one of the iterators terminates it: the first "while" which has false condition or the first "for" which consumes all its values ends the loop.

This is convenient when the termination condition does not relate directly to a "for" variable, or when structures are to be traversed in parallel.

Continuing the example from earlier, we may use a "while" to decide if the end has been reached, and, at the same time, use a "for" to count the number of times we have evaluated the loop body:

#include "aldor"

import from Integer;

n := 10000;
k := 0;

while n ~= 1 for free k in 1.. repeat
        if odd? n then n := 3*n + 1 else n := n quo 2;

print << "Terminated after " << k << " iterations." << newline;

Multiple "for" iterators can allow lists to be combined in an efficient way:

#include "aldor"
import from List Integer;

l1 := [1,2,3];
l2 := [8,7,6,5];
     
-- Add the pair-wise products in two lists.
x := 0;
for n1 in l1 for n2 in l2 repeat
        x := x + n1 * n2

print << "The result is " << x << newline

These two "for" iterators are used in parallel, like a zipper combining the two lists. The loop stops at the end of the shortest list, in this case giving a sum of three products.

This is not a double loop - to use all pairs with the number from l1 and the second number from ls, you would use two nested loops, each with its own "repeat":

#include "aldor"
import from List Integer;

l1 : [1,2,3];
l2 : [8,7,6,5];

x := 0;
for n1 in l1 repreat
        for n2 in l2 repeat 
                x := x + n1 * n2;
  
print << "The result is " << x << newline

Using more than one iterator is often the most efficient natural way to write a loop. A loop with two "for" iterators is more efficient than

...
m: SingleInteger := min(#l1, #l2);
for i in 1..m repeat
        x := x + l1.i * l2.i

because it does not need to traverse the lists each time to pick off the desired elements. And the code is more concise than

...
t1 := l1;
t2 := l2;
while (not empty? t1 and not empty? t2) repeat {
        x := x + first t1 * first t2;
        t1 := rest t1;
        t2 := rest t2;
}

Evaluating a "break" causes a loop to terminate. For example:

#include "aldor"
      
import from Integer;

n := 10000;
k := 0;        -- 'k' counts the number of iterations.

repeat {
        if odd? n then n := 3*n + 1 else n := n quo 2;
	      
        k := k + 1;

        if n = 1 then break;
}
print << "Terminated after " << k << " iterations." << newline

"break" is most useful when the condition which quits the loop falls most naturally in the middle or at the end of the loop body. Sometimes it is possible to change a test which appears at the end to a test at the begining. This helps make programs more readable, since one sees immediately what will cause the loop to end. Also, it allows the exit to be controlled by a "while" iterator, rather than an "if" and a "break".

Iterate

Evaluating an "iterate" abandons the current evaluation of the loop body and starts the next iteration. For example:

#include "aldor"
      
import from Integer;

n := 10000;
k := 0;         -- 'k' counts the number of iterations.

repeat {
        k := k + 1;
        if odd? n then { n := 3*n + 1; iterate }

        n := n quo 2;
        if n = 1 then break
}
print << "Terminated after " << k << " iterations." << newline;

This example does the same thing as the previous one, but is organized slightly differently. The "iterate" on the second line of the loop body causes the rest of the body to be skipped.

"iterate" can be used instread of placing the remainder of a loop body inside an "if" expression. This can make programs easier to read, by emphasizing that certain conditions are not expected, and by avoiding extra levels of indentation. It is particularly useful when the decision to go on to the next iteration of a loop is buried deep inside some other logic, rather than appearing at the top level of the loop body.

An "iterate" is equivalent to a "goto" branching to the end of the loop body. Thus, the meaning of "iterate" is independent of whether there are any "while" or "for" iterators controlling the loop.

If an "iterate" occurs inside nested loops, it steps the deepest one.

Definition in low-level terms

It is possible to express the loop behavious in terms of gotos and labels. A loop of the form

it1 it2 ... itn repeat Body

is equivalent to

{
      init1; init2; ... initn;
      @TOP
      step1; step2; ... stepn;
      Body;
      goto TOP;
      @DONE
}

Where, if it_i is "while cond_i", then init_i is empty and step_i is

if not condi then goto DONE

if it_i is "for lhs_i in expr_i | cond_i", then init_i is

gi := generator expri;

and step_i is

step! gi;
if empty? gi then goto DONE
lhsi := value gi
if not condi then goto TOP

(a "for" without a condition is treated as if the condition were "true").

In this, TOP, DONE and the g_i are generated names, and are not accessible to the other parts of the program.

Generate expressions are used to create generators. For a complete description of how to use generate to create a generator, see chapter 9. The general syntax for a generate expression is:

generate E
generate to n of E

E is an expression which represents code which will be evaluated each time a value is extracted from the generator. Evaluation begins at the start of the expression E and continues until an expression of the form

yield v

is processed, where v is the value to be passed back to the context which is collecting values from the generator. Each time a value is requested after the first value is yielded, control resumes after the yield expression which produced the previous value.

A collect expression provides a convenient shorthand for creating generators and aggregate objects. A collect expression has the form:

E iter₁ ... iter_n

where n >= 1. The iter_i are iterators, as described in section 5.13. Consider the following example:

#include "aldor"
...
import from Integer, List Integer;
print << [x*x for x in 1..10] << newline;
print << [x*y for x in 1..10 for y in 10..1 by -1];

This program creates a list of the squares of the integers from 1 to 10, and then a list of products of integers. Note that while can form an iterator, and can therefore be used in a collect expression.

Note that the square brackets are not part of the collect expression, but are simply a shorthand for a call to the function bracket, with the value of the collection as an argument. The domain List Integer from the Aldor base library exports a function with the signature bracket: Generator Integer -> %, which is called twice in the above example.

As collect expressions produce generators, one would expect that generate expressions and collect expressions are related. The collect expression:

Thus, x*y for x in 1..9 for y in 9..1 by -1 is the same as:

generate for x in 1..9 for y in 9..1 by -1 repeat yield x*y

Collect expressions provide a convenient notation for creating new aggregates, and require no additional functionality in the language.

Previous

Home

Contents

Next