# Iteration and Sequences: Dot Product¶

The next function we’ll look at calculates the inner product, or *dot
product*, of two one-dimensional arrays of numbers. This is defined as
the sum of the pairwise products of numbers from the arrays. As an added
complication, we’ll not fix the length of the arrays, so our Pascal
version will use conformant arrays, a late addition to the language.

```
function dotProduct(x: array[xlo..xhi: integer] of real,
y: array[ylo..yhi: integer] of real): real;
var
i: integer;
sum: real;
begin
if (xhi - xlo <> yhi - ylo)
error("dotProduct: arrays of different lengths");
sum := 0.0;
for i := xlo to xhi do
sum := sum + x[i] * y[i - xlo + ylo];
dotProduct := sum
end;
```

Because a dot product only makes sense for arrays of the same length, we
need to check that the arrays have the same length before proceeding.
Since Pascal has no built-in error-handling facilities, we’ve invented a
minimal interface – a procedure named `error`

which takes a string
description of the error – that has to be implemented on every
different system using non-standard facilities.

There is one other complication worth mentioning here. Since the two
arrays can have different lower bounds and the loop index `i`

starts
at the value for the array `x`

, it has to be adjusted before being
used as a subscript for `y`

.

Our first Dylan version of this function uses a while loop:

```
define method dot-product (x, y)
if (size(x) ~= size(y))
error("dot-product: arrays of different lengths")
end if;
let sum = 0;
let i = 0;
while (i < size(x))
sum := sum + x[i] * y[i]
end while;
sum
end method dot-product;
```

Let’s first look at the syntactic differences. Other than using `~=`

for the “is not equal to” relationship, Dylan is very similar to Pascal
for the operations needed in this function. The operator `:=`

is used
for assignment to an existing variable (as opposed to `=`

, which is
used for setting the initial value for a variable created with `let`

)
and the notation `*array*[*index*]`

is used for subscripting. As
with `if`

, the `while`

statement is always ended with `end`

, and
no explicit `begin`

is needed.

The main difference between these two functions is in how they manipulate the arrays. When declaring an array in Pascal, a programmer specifies both the lower and upper bound; these bounds can be integers, characters, or enumerated types. In this regard, Dylan is less flexible than Pascal: arrays are always indexed with increasing integers starting at zero. (Many other languages, such as C, share this restriction. Fortran is similar, but it starts all arrays at one.)

In standard Pascal, the length of all arrays must be known ahead of
time. The one exception to this is the conformant array feature of ISO
Pascal, where the bounds of the array are treated as an extra set of
parameters to a function which accepts an array as an argument. In
Dylan, all arrays carry with them their length, so we only have to
specify the size of an array when it is not already known, such as when
the array is first created. The function `size`

is used to obtain the
length of the array. For any array `a`

, the valid indexes of the array
are from `0`

to `size(a) - 1`

; that is, `size(a)`

elements,
starting at zero.

One more thing to note is that, in Pascal, we had to invent the
`error`

procedure and say that it is implemented in some
platform-dependent way. Our Dylan version also calls a function named
`error`

, but this function is a part of the Dylan language. The full
behavior of `error`

is rather complicated and beyond the scope of this
tutorial – Dylan has a powerful exception handling and recovery
mechanism for dealing with and possibly correcting errors discovered
while a program is running – but if you’re running the program in a
debugger, a call to error will generally result in the debugger stopping
the program and reporting the message.

The original Pascal version of this function used a `for`

loop, which
has a direct equivalent in Dylan, as we see in this version of the
function:

```
define method dot-product (x, y)
unless (size(x) = size(y))
error("dot-product: arrays of different lengths")
end unless;
let sum = 0;
for (i :: <integer> from 0 to size(x) - 1)
sum := sum + x[i] * y[i]
end for;
sum
end method dot-product;
```

We’ve changed the error check at the beginning of the function from an
`if`

statement to an `unless`

, which executes its body if the
condition is false. Sometimes, often with error checks, it is clearer to
write a conditional with `unless`

than with an `if`

that tests the
opposite condition. Note that there is no `else`

clause for
`unless`

; if you need to do one thing if something is true and another
if it is false, use `if`

or `case`

.

The `for`

loop in Dylan takes several forms, one of which we see
above, which is called a *numeric for clause*. The syntax of `for`

in
Dylan is similar to the `while`

statement, except instead of a
condition inside parentheses, we have a clause that describes the loop.
A numeric for clause counts from a number to some other. In this case,
the for-clause counts from zero to one less than the size of the array.
The syntax of the clause is straightforward:

`variable from initial-value to bounding-value`

As in Pascal’s `for`

statement and unlike the `while`

loop, the
initial value and the bounding value are evaluated exactly once, before
the first iteration of the loop.

Unlike the Pascal `for`

loop, Dylan’s `for`

defines the loop
variable – `i`

in this example – as part of its job. That is, no
declaration of `i`

outside the loop is needed or used. This also means
that the loop variable can’t be used outside the body of the loop. (I
included a type declaration for `i`

above, just to show that one could
be used; typically, it would be omitted.)

The for loop above is not very typical Dylan code. If written first in Dylan, it might look more like this, taking advantage of a few constructs that don’t correspond directly to ones in Pascal:

```
define method dot-product (x, y)
let sum = 0;
for (i from 0 below x.size)
sum := sum + x[i] * y[i]
finally
sum
end for
end method dot-product;
```

(We’ve eliminated the error check at the beginning of the function from this and future versions, not because it is unnecessary, but because it would stay the same – there is no need to repeat it.)

We see here a slight variation on numeric iteration. The word `to`

in
the iteration clause has been changed to `below`

. While `to`

means
all values between the initial value through, and including, the final
value, `below`

means all those values from the initial value that are
less than, but not equal to, the bounding value.

In addition to what we’ve seen here, numeric iteration clauses can use
the `by`

keyword, which introduces an amount to count by, as in
Pascal. The `by`

phrase can be omitted, as we’ve seen, in which case
the value is incremented by one each time through the loop. Also, we can
identify the ending condition with `above`

, the opposite of `below`

,
which means the loop runs while the values are greater than the bound.
The ending condition can even be omitted, which leaves a (potentially)
infinite loop – something other than finishing the numeric iteration
would have to happen to terminate the loop.

The value specified by `below`

in the loop is also a new construct,
`x.size`

. This is a Dylan shorthand for calling a function of one
argument. That is, `expression.function-name`

is the same thing as
`function-name(expression)`

. So the expression here is exactly
the same as `size(x)`

, just written somewhat differently. (The
hecklers in the audience might observe that it isn’t much of a
shorthand: just one fewer character.)

Pascal and C programmers, among others, are used to using the syntax
`expression.name`

for referring to fields of a compound object
like a record. It makes sense to wonder why this notation was chosen for
something else in Dylan, especially when that something else – calling
functions – already had a perfectly reasonable syntax. The reason is
that calling a function in Dylan is the only way to access fields in
compound objects; we’ll see more of this later.

The last thing to note about this version of the function is that the
`for`

statement is the last one in the function, so the value returned
by `dot-product`

is the value of the `for`

. What value does the loop
return? Normally, there is no meaningful value to return from a loop, so
an arbitrary one – the false value – was picked in Dylan. But
sometimes it’s useful to return a value from a loop, and that’s what the
`finally`

clause is for. After the `for`

loop is done, all the
statements in the `finally`

clause – here it’s just one expression –
are evaluated, and the value of the last is returned. One detail worth
knowing is that the statements after `finally`

are still part of the
`for`

statement, so the variable from the numeric iteration clause can
still be used.

All our versions of `dot-product`

so far have worked in basically the
same way: step through the arrays by counting from 0 to one less than
the size of the array, and doing something with each element in the
array. This is all we use the variable `i`

for, and it’s pretty common
that loop variables are used in this way. Dylan provides a very
convenient way of doing this kind of iteration, using what’s known as a
*collection iteration clause*:

```
define method dot-product (x, y)
let sum = 0;
for (xi in x, yi in y)
sum := sum + xi * yi
finally
sum
end for
end method dot-product;
```

Here we’ve done away with the numeric iteration clause, and replaced it
with two collection iteration clauses. Note that a `for`

loop may have
an arbitrary number of iteration clauses, and when any of them
completes, the loop is done. The iteration clause *variable* `in`

*expression*, where the expression is an array, means execute the loop
for each element in the array, from first to last, setting the variable
to each value in succession. Thus the first time the loop executes,
`xi`

holds the value `x[0]`

and `yi`

holds `y[0]`

; the second
time through, `xi`

holds `x[1]`

and `yi`

holds `y[1]`

; and so
on.

The use of multiple iteration clauses in a `for`

is relatively common.
Note that a single loop can mix numeric and collection iteration clause,
along with a third form, general iteration, which we’ll see later. The
important thing to realize is that the loop ends when *any* of the
clauses causes it to end.

Again, we haven’t declared types for the parameters `x`

and `y`

and
have just referred to them as arrays. This is inaccurate in two ways.
The first, and more minor, is that one-dimensional arrays are referred
to as *vectors* in Dylan. While the code will work on multi-dimensional
arrays, it doesn’t really make mathematical sense except for vectors –
there is no dot product of an array of two or more dimensions.

The more important reason that describing the arguments to
`dot-product`

as arrays is wrong is that this function will work for
other types of arguments as well. Dylan has several different types
known collectively as *sequences*, all of which share several
properties: they hold a collection of objects which are numbered from
zero. Vectors are one kind of sequence; others are strings, linked
lists, ranges of numbers, and queues. The subscripting notation using
`[]`

, the `size`

function, and collection iteration clauses – among
many other operations – may be used with all sequences.

Sequences are just one kind of *collection* in Dylan. A collection is a
kind of object which can hold other objects. The most commonly used
collection which isn’t a sequence is a *table*, which is Dylan’s
built-in version of a hash table. Where sequences use integers starting
at zero as indexes, tables can use any object.

Collections are used extensively by most Dylan programs. This should not
be a surprise to people who know Pascal: many complex data structures in
Pascal programs are collections of other objects, usually built up from
arrays, linked lists, etc. One major difference is that where Pascal
only defines the array type, in Dylan there are a variety of existing
collection types to use. Moreover, there is powerful set of operations
predefined on collections and sequences; we’ll see two of these in our
next version of `dot-product`

.

Another aspect of collections is that users can define their own collection types. Again, this is no surprise. What is different from Pascal is that, when programmers follow a few rules when creating a new kind of collection, it can be used with any of the predefined functions that operate on collections. We’ll see more about this in a later section.

Turning back to the example at hand, there is one more thing to
understand about using collection iteration clauses instead of numeric
iteration and indexing: the performance impact of the choice. When we
used numeric iteration, to calculate the dot-product we had to evaluate
`x[i]`

and `y[i]`

each time through the loop. For vectors this makes
perfect sense, as indexing into a vector is an efficient operation. But
if `x`

is a linked list, for example, finding `x[i]`

requires
stepping through the first `i - 1`

elements of the list, which makes
evaluating `x[i]`

inside the loop an expensive operation. In more
precise terms, it changes the computational complexity of the function
from *O(n)* for vectors to *O(n^2)* for lists, where *n* is the length
of the arguments.

On the other hand, collection iteration is designed to be efficient when
possible. For both linked lists and arrays, iterating through the
collection takes time proportional to the length of the list, so the
version of `dot-product`

which uses collection iteration has *O(n)*
complexity for both vectors and lists. In general, one should use
collection iteration when iterating over the elements of a collection
without concern for what their index values are.

Now let’s take a look at a very different version of `dot-product`

,
this time using two built-in collection operations, `reduce`

and
`map`

:

```
define method dot-product (x, y)
local method add(a, b)
a + b
end method add;
local method multiply(m, n)
m * n
end method mul;
let x*y-sequence = map(multiply, x, y);
reduce(add, 0, x*y-sequence)
end method dot-product;
```

The thing to note about this function is that there is no explicit iteration clause. Instead, the iteration is done by the built-in functions.

Let’s carefully step through what this function does. First, it defines
two local functions – `add`

and `mul`

– which, respectively, add
and multiply their arguments. It then calls the function `map`

.
`Map`

is what is known as a *higher-order function*, which means it is
a function that takes a function as an argument. `Map`

creates a new
collection from the results of calling a function on each element of one
or more existing collections. The first argument to `map`

is the
function to use; all the other arguments are collections to draw
elements from. In this case, we’ve applied `map`

to the function
`multiply`

and the two sequences which were arguments, so it produces
a sequence that has `x[0] * y[0]`

as its first element,
`x[1] * y[1]`

as its second, and so on. (The resulting sequence is
only as long as the shorter of the original sequences. If one is longer,
only the elements which have corresponding members in the shorter
sequence are used. As above, we’ll assume that the sequences are of the
same length.)

The result of map, a sequence of the products of the elements of `x`

and `y`

is then attached to the local variable named `x*y-sequence`

.
There’s nothing special about the use of the asterisk in this name –
it’s just one of the characters which is legal in Dylan as part of a
name – but sometimes it is convenient to name a variable with a
mathematical expression.

Next, we call the function `reduce`

, which is also a higher-order
function. Where `map`

applies a function to the elements of one or
more collections to produce a new collection, `reduce`

combines the
elements of a collection with a function to produce a single value.
`Reduce`

takes three arguments: a function, an initial value, and a
collection. It keeps track of the result value, which starts off as the
initial value argument. For each element of the collection, it computes
the result of the function called with the value of the result so far
and the current element, and uses that as the next value of the result.
When every element of the collection has been seen, the value that has
been computed so far is retuned.

In our call to `reduce`

, the function used for combining values is
`add`

, which sums two numbers, and the initial value is `0`

, which
is the identity for addition. Therefore, this call to `reduce`

produces the sum of the members of a collection. In this case, the
collection being summed contains the products of the elements of the
arguments, so the result is the dot product.

However, there is a potential drawback to using this approach for
implementing `dot-product`

: it might be less efficient than a version
that directly used a loop. The reason is that memory might have to be
allocated for the intermediary result `x*y-sequence`

, and allocating
that memory takes some time, as does freeing it when it is no longer in
use. (Dylan uses *garbage collection*, also known as *automatic storage
reclamation*, to free memory that isn’t being used anymore, but whether
the programmer or the system does it, freeing the memory does take some
time. A full discussion of garbage collection is beyond the scope of
this essay.) So we potentially have a bigger (more memory) and slower
(more time) program. A very clever compiler could eliminate this use of
extra memory, perhaps by inlining the functions and rewriting them
internally as loops, but programmers concerned with efficiency probably
shouldn’t count on such an optimization unless they know their compiler
very well.

By the way, there is nothing special about higher-order functions:
anyone can write them. Here, for example, is a portable version of
`reduce`

, which could be used if it wasn’t already part of the
language:

```
define method reduce
(function :: <function>, initial, collection :: <collection>)
=> value;
let result = initial;
for (element in collection)
result := function(result, element)
finally
result
end for
end method reduce;
```

This implementation is a direct translation into Dylan of the
description given above. For once, I’ve given types for the arguments,
because that’s how the types are specified by the language definition.
The major difference from other functions we’ve seen so far is an
argument, `function`

, is used as a function, inside the `for`

loop;
that works just as one might expect it to.

The previous version of `dot-product`

used three locally-bound
identifiers (`add`

, `multiply`

, and `x*y-sequence`

) that were only
used once. As in Pascal, if an expression is used only once, there is no
need to associate it with a name. Unlike Pascal, though, functions in
Dylan are expressions, and can be created anonymously, that is, without
names. So we can rewrite `dot-product`

as:

```
define method dot-product (x, y)
reduce(method (a, b) a + b end,
0, map(method (m, n) m * n end, x, y))
end method dot-product;
```

In this version of `dot-product`

, the function we use as the first
argument to `reduce`

is the expression:

```
method (a, b)
a + b
end
```

This expression creates a method – with exactly the same meaning as the
`add`

method from our previous version – but doesn’t give it a name.
Nonetheless, this method can be used anywhere `add`

could have been.
Similarly, `multiply`

has been changed to another anonymous method.

We also eliminated the variable `x*y-sequence`

, substituting the
`map`

expression for it in the call to `reduce`

. The meaning of the
function hasn’t changed, however, so the potential inefficiency of
allocating extra memory for the result of `map`

remains.

The full syntax for an anonymous method is

```
method (arguments ...) => results ...;
body
end method
```

and, as with all other methods, the description of the results and the
word `method`

after `end`

can be omitted. Since it doesn’t have a
name, there is no name to put after the `end method`

.

These examples of `map`

and `reduce`

have been somewhat artificial
in order to introduce the use of higher-order functions. A version of
`dot-product`

in Dylan would more likely be written as:

```
define method dot-product (x, y)
reduce(\+, 0, map(\*, x, y))
end method dot-product;
```

In the previous two examples, we created a function which took two
arguments and added them. The first time it was named `add`

; the
second, it was anonymous and passed as the first argument to `reduce`

.
In fact, there is no real need to create such a function, because one
already exists: it’s called `+`

.

Because `+`

is normally used as an operator in traditional arithmetic
notation, it is easy to forget that it’s a function. In Pascal and C, in
fact, operators like `+`

have different rules from functions and can’t
just be used like any other function, but in Dylan they can. To avoid
syntactic confusion with `+`

used as an operator, when, for example,
we refer to the function name in order to pass it as an argument to
another function we have to precede it with a backslash, as above.

This function has the same result as the previous two, but we have
avoided introducing the intermediate functions and let `map`

and
`reduce`

call `*`

and `+`

directly.

This version of `dot-product`

is very concise and, for a programmer
used to `map`

and `reduce`

, easy to read. There are some very common
idioms in Dylan built around these and other operators. For example,
there is no built-in function to sum a sequence: `reduce`

obviates the
need for it.

The use of higher-order functions is usually associated with the
*functional* style of programming, which is identified with languages
such as Standard ML, Haskell, and some dialects of Lisp, notably Scheme.
In Dylan it is often convenient to use this style for parts of programs
– often those dealing with operations on collections, as we’ve seen –
and use other styles, such as object-oriented or procedural, in other
parts. One of the goals for Dylan is to support multiple styles, because
there is no one single, “right” way to structure a program. The
functional style is a useful one, and is well supported in Dylan; we’ll
see more of it later.

On the other hand, it is possible to take this approach to extremes and
write large, complicated expressions with no named intermediate values.
While some people enjoy writing large blocks of code that way, the
result is often an unreadable program. APL, another language which makes
pervasive use of higher-order functions, is often criticized for
encouraging a “write-only” programming style, with very complex
expressions. Introducing a few named values with `let`

or splitting
one method into several that calculate different parts of a result can
often turn a large, hard-to-follow expression into something more
readable and maintainable.

Back – Conditions and Multiple Values: The Quadratic Formula

Copyright © 1995 Paul Haahr. All rights reserved.