4 STREAMS

4.1 Basic Constructs
4.2 Operations on Streams
4.3 Empty Streams
4.4 Expression Evaluation Rules
4.5 Algebraic Laws
4.6 Quantifiers
4.7 Example: Parental Relations
4.8 Undefined Values
4.9 Quantifier Propagation
4.10 Recursive Stream Definitions
4.11 Summary
4.12 References

 

In all our examples so far, we assumed that an expression represents only one value. However, there are often situations in daily life where an expression may represent many things. For example, if we are talking about all the employees who are speaking Spanish or about all the customers living in New York, we are using expressions which may represent several entities. The same applies to numeric values. For instance, we can talk about all the odd numbers between 0 and 50 or about all the prime numbers between 1 and 100. In those cases, the corresponding expressions are representing more than one value. If such an expression is evaluated then its result is a stream of values.

In this chapter we will discuss what stream expressions are and how they can produce streams of data items. Stream expressions are also called multi-value expressions. In later chapters we will explain how the concept of streams can be used for all kinds of problems and how it has a profound influence on the way problems are solved.

But, before we are going to discuss this in more detail, we need to explain the meaning of the term "data item" as we will use frequently in our discussions. From daily experience we know that employees, customers, integer numbers, and real values are all different things. However, the rules we are going to discuss are applicable to all kinds of data items. Data items may be used to represent employees, customers, integer numbers, real values, as well as many other things. Therefore we will use the general word "data item" if we mean those things. Consequently, a stream is a sequence of data items. Later on, in following chapters, we will discuss how the different data items may be represented.

4.1 Basic Constructs

In order to express multiple data items in expressions we will need a number of basic language constructs. The first one is to express a series of data items:

( expr1, expr2, expr3 ... )

We will call this a serial-expression. It consists of a series of expressions, separated by comma's and enclosed in parentheses. Here are some examples:

( 1, 2, 3, 7, 11, 13)

( 3.4, 5.6, 7.8, 9.2)

('A', 'D', 'A', 'M')

( x - y, x + y, x * y, x / y)

The first example is an expression representing 6 integer values. The expression in the second example represents 4 real values. The expression of the third example represents 4 characters. The expression of the last example consists of 4 values which are computed.

The evaluation of a serial-expression results in a corresponding stream of data items.

A serial-expression may also contain other serial-expressions. For example:

( 2, (9, 7), (4, 5, 6), 3, 8)

is equivalent to:

( 2, 9, 7, 4, 5, 6, 3, 8)

The second language construct we will discuss is the range-expression. A range-expression is only defined in the language for integer values and represents a stream of successive integer values. Examples are:

3 .. 7 is a shorthand notation for ( 3, 4, 5, 6, 7)

m .. n represents the stream ( m, m+1, m+2 ..., n)

In the last example the number of integer values is variable and depends on the actual values of m and n.

4.2 Operations on Streams

Operations on expressions representing multiple data items are straightforward extensions of operations on single data items:

2 * ( 3, 4, 5)   results in   ( 6, 8, 10)

2 - ( 3, 4, 5)   results in   (-1, -2, -3)

( 3, 4, 5) - 2   results in   ( 1, 2, 3)

These examples are showing the effect of an infix operation with one operand which is a single data item and the other operand which represents a stream of data items.

Let us now give some examples where both operands of an infix operation are streams of data items (we have replaced the words "results in" by the equivalent notation "=>"):

( 2, 3) + ( 4, 5, 6)   =>   ( 6, 7, 8, 7, 8, 9)

( 2, 3) * ( 4, 5, 6)   =>   ( 8, 10, 12, 12, 15, 18)

( 2, 3) - ( 4, 5, 6)   =>   ( -2, -3, -4, -1, -2, -3)

From these examples it will be clear what the general rules are for the evaluation of infix-operations on streams: Take from the left operand the first data item and apply the operation with that data item to all the data items of the right operand; take then the second data item of the left operand and apply the operation with that second data item to all the data items of the right operand again, and so on. We make that explicit in the following example:

( 2, 3, 4) * ( 4, 5, 6)  will be evaluated as: 

( 2 * ( 4, 5, 6), 3 * ( 4, 5, 6), 4 * ( 4, 5, 6) ) which is:

( ( 8, 10 ,12), ( 12, 15, 18), ( 16, 20, 24) ) which is:

( 8, 10, 12, 12, 15, 18, 16, 20, 24) 

Let us now use some examples of prefix-operations:

- ( 2, 3, 4) => ( -2, -3, -4)

+ ( 2.3, 3.4, 4.5) => ( +2.3, +3.4, +4.5)

not ( true, false, true) => ( not true, not false, not true)

Streams as arguments of functions are also allowed as shown in the following examples:

f( ( 2, 3, 4) ) => ( f(2), f(3), f(4) )

g( (2, 3), (4, 5) ) => ( g(2,4), g(2,5), g(3,4), g(3,5) )

The rules for the evaluation of prefix operations and functions are similar to the rules discussed before.

The evaluation of stream expressions in general, consists of the evaluation of its constituent operations according to the normal evaluation rules. For example,

( 2, 3, 4) - ( 5, 6) * ( 7, 8)

is evaluated in the normal precedence order: first the multiplication operation and then the subtraction operation.

We may also use range expressions as part of stream expressions as illustrated by the following examples:

2 * 1 .. 5 => ( 2, 4, 6, 8, 10) 

1 .. 3 - 1 .. 3 => ( 0, -1, -2, 1, 0, -1, 2, 1, 0)

( 21, 2 * 13 .. 15, 33)	=> ( 21, 26, 28, 30, 33)

Notice that the range operator .. has a higher precedence level than the * operator.

Exercises:

4.1 Evaluate the following expressions:

(3, 4, 5) - 4

(9, 8, 7) / (3, 2)

(4, 5) ** (3, 2)

(2, 3, 4) - (5, 6) * (7, 8) 

(9, 7, 5) < (5, 7 ,9) 

(8, 7, 5) >= (7, 5, 8) 

not (false, true ,false)

abs ( (-0.5, 2.4, -5.6) )

(3..4) ** (2..3)

(5, 6) .. (6, 7)

real (1..5) + 0.5

4.2 Describe in one expression the odd numbers between 0 and 50.

4.3 Describe in one expression the stream 29, 27, 25,.., -27, -29.

4.3 Describe in one expression the stream 3.10, 3.11, 3.12,..,7.09, 7.10.

Before proceeding to our next topic two remarks may be worthwhile: First, although we are using in many of our examples for the sake of simplicity integer numbers, the principles are equally applicable to other types of data items. The second remark is that single value expressions are special cases of the more general multiple value expressions.

4.3 Empty Streams

If we are searching for entities with specific properties such as all blue cars in the street or all employees speaking Spanish we may expect a number of items satisfying the criteria. However, it is also possible that there are no items with the required properties. How do we cope with these kinds of situations? To answer such questions, let us examine in more detail the range expression. A range expression represents a stream of integer values. To recall:

m .. n represents the stream ( m, m+1, m+2 ..., n)

Now we can distinguish three situations depending on the actual values of m and n:

· if m < n the stream consists of n - m + 1 values

· if m = n the stream consist of only one value

· if m> n the stream is empty; in this case there are no values between m and n.

The important question is now: How are the above-mentioned operations defined for empty streams? The answer is very simple: any operation or function call where an operand represents an empty stream will also produce an empty stream. In the following, we will represent an empty stream by two adjacent parentheses ( ), although this is not a legal language construct. Later on, we will discuss how an empty stream can be expressed in the language.

Here are some examples of operations on empty streams:

+( ) => ( )

2 * ( ) => ( )

2 - ( ) => ( )

( ) - ( ) => ( )

( ) + ( 4, 5, 6) => ( )

( 2, 3) * ( ) => ( )

f(( )) => ( )

g((2,3),( )) => ( )

So, in general, if one of the operands in an expression represents an empty stream the whole expression represents an empty stream. Also, if one of the arguments of a function call represents an empty stream, the result of the function is an empty stream.

However, if an expression represents an empty stream and it is part of a serial-expression then the result is not necessarily the empty stream, as is shown by the following example:

( 2, ( ), 5) => ( 2, 5)

4.4 Expression Evaluation Rules

Now we are able to formulate some general rules about the evaluation of expressions. We have seen that the operands of prefix-operations, the operands of infix-operations, and the arguments of function calls are expressions which may represent streams of data items. In the following we will use for simplicity as synonym for argument the term operand and as synonym for function the term operation.

The execution of an expression is known as its evaluation. The evaluation of an expression results in the evaluation of its operands and the application of the operations. In general, an operand may represent a stream of zero, one, or more data items.

If an operand represents a stream with more than one data item, the operation will be repeatedly performed for all the data items of the operand.

If an expression consists of a prefix-operator and its operand, then the number of evaluations is equal to the number of data items represented by the operand.

If an expression consists of a infix-operator and its two operands, then the number of evaluations is equal to the product of the numbers of data items of each operand.

If an expression consists of a function call with N operands then the number of evaluations is equal to the product of the numbers of data items of each operand.

As a consequence, if one of the operands represents an empty stream ( which means that the number of data items is zero) then the product will be zero and the operation will not be performed.

If all operands of an operation represent only one data item, the product will be one and the operation will be performed once, which is for single-value expressions the normal case.

In all other cases the evaluation of an expression is repeated for each data item of its operands, producing a stream of data items.

Now we are able to apply these rules to some examples. Let us assume that A represents the stream ( 3, 4, 5), B the stream ( 7, 9), and C the empty stream ( ), then evaluation of the following expressions will result in the following number of distinct evaluations:

2 * A 		<< results in 1 * 3 = 3 evaluations of 2 * A >>

A - 5 		<< results in 3 * 1 = 3 evaluations of A - 5 >>

A + B 		<< results in 3 * 2 = 6 evaluations of A + B >>

B * A 		<< results in 2 * 3 = 6 evaluations of B * A >>

A * A 		<< results in 3 * 3 = 9 evaluations of A * A >>

A * C 		<< results in 3 * 0 = 0 evaluations of A * C >>

C + B 		<< results in 0 * 2 = 0 evaluations of C + B >>

The same rules also apply to function calls. Suppose that F is a function with three parameters, then the number of evaluations of F is determined by the product of the number of data items of its arguments:

F(A, A, A) 	<< results in 3 * 3 * 3 = 27 evaluations of F >> 

F(A, B, B) 	<< results in 3 * 2 * 2 = 12 evaluations of F >>

F(A, B, C) 	<< results in 3 * 2 * 0 =  0 evaluations of F >>

Exercises:

4.4 Determine the number of evaluations of the following expressions:

(9, 8, 7) / (3, 2)

(4, 5) ** (3, 2)

(4, 5) * (2, 3, 4) - (5, 6, 7, 8) 

(9, 7, 5) < (5, 7 ,9) 

(4..3) ** (2..3)

(5, 6) .. (6, 7)

abs (1..100)

1..20 + 1..100

4.5 Algebraic Laws

One of the questions we have to answer is: are the elementary algebraic laws as defined for numbers, also applicable to streams of numbers? To answer that question, we will first recall the laws of the elementary algebraic operations, addition and multiplication, as given in the following overview:

(1)   a + b = b + a 				commutativity

(2)   (a + b) + c = a + (b + c) = a + b + c 	associativity

(3)   0 + a = a

(4)   a + (-a) = 0

(5)   a * b = b * a 				commutativity

(6)   (a * b) * c = a * (b * c) = a * b * c 	associativity

(7)   a * (b + c) = a * b + a * c 		distributivity

(8)   1 * a = a

(9)   0 * a = 0 

Let us start with the first rule: Is a + b = b + a also true for streams? If we assume that a represents (2, 3) and b represents (4, 6) then a + b = (6, 8, 7, 9) and b + a = (6, 7, 8, 9). This means that, in this example, both results are not equal, or, a + b <> b + a. In general, the laws of commutativity are not holding in case of streams.

Exercises:

4.6. Are the laws of distributivity and associativity valid for streams?

4.7. Which of the above-mentioned algebraic laws are still applicable to numeric streams in general?

4.8. Which of the above-mentioned algebraic laws are applicable to numeric streams if at least one of the operands represents an empty stream or represents only one value?

 

4.6 Quantifiers

With the preceding evaluation rules about expressions we are now able to construct definitions which are representing streams of data items. Let us start with a simple example:

f (integer, integer) -> multi (integer);
f (p, q) = p .. q;

This definition is based on the range operation. For example, the evaluation of f(3, 6) will result in the stream (3, 4, 5, 6); but the evaluation of f(7, 2) will result in an empty stream.

The fact that our definition may produce more than one data item is reflected in its signature. As part of the result specification in a signature a so-called quantifier may be used. A quantifier specifies how many data items may be returned. There are four quantifiers defined in the language with the following meaning:

multi	specifies that zero, one, or more data items of the given type may be returned
single	specifies that one and only one data item of the given type will be returned
optional	specifies that zero or one data item of the given type may be returned
nothing	specifies that no data item will be returned

If the quantifier multi is used in a specification then an evaluation of the definition produces as many data items as can be produced by the definition depending on the values of the arguments. Take as an example:

g (integer, integer) -> multi (integer);
g (p, q) = ( p - q, p + q, p .. q );

This definition will produce a stream of at least two data items but may be more, depending on the values of p and q. For example, the evaluation of g(7, 2) will result in only two data items: (5, 9); but the evaluation of g(3, 5) will result in the stream (-2, 8, 3, 4, 5).

The quantifier single is used if the definition produces one data item. If in a specification no quantifier has been specified, as default the quantifier single is assumed. This means, for example, that the definition:

F (integer, integer) -> integer;
F (x, y) = x + y;

is equivalent with:

F (integer, integer) -> single (integer);
F (x, y) = x + y;

If the quantifier optional is used in a specification then an evaluation of the definition produces zero, or maximally one data item even if more data items can be produced by the definition.

The quantifier optional can be used if you want to limit the number of data items to a maximum of one, even if there are more. For example, if you need only one employee speaking Spanish, you have to use the optional quantifier. (The multi quantifier would give you all the Spanish speaking employees). The optional quantifier (as well as the multi quantifier) also takes care of the situation that there are no data items with the required characteristics ( which means an empty stream).

Take as an example:

h (integer, integer) -> optional (integer);
h (p, q) = p .. q;

This definition is similar to the first example in this section; the difference is that here the optional quantifier is used. In this case the evaluation of h (3, 6) will result in a stream with only one data item, the value 3. The evaluation of h (7, 2) will result in an empty stream.

The quantifier nothing is used if no data items are produced by the definition. The quantifier nothing can be interpreted as the name of a special, built-in type which has no values. Because there are no values, there are also no operations defined on nothing. Function-definitions specified with the nothing quantifier are comparable to what in some other programming languages are called procedures.

Let us see how the nothing quantifier may be used in a definition:

G (integer, integer) -> nothing;
G (p, q) = print(p + q);

In this example, the definition calls another definition which also returns nothing.

4.7 Example: Parental Relations

As said earlier, definitions are not restricted to streams of integer values. Any type may be used in the result-specification of a definition. As an illustration we will give an example which makes use of a symbolic enumeration type. It defines parental relations which can be used to answer questions about ancestors. These relations are defined as follows:

type Person = (Mary, George, John, Liz, Albert, Alice, Jane, Harry, Unknown );

mother (Person) -> Person;
mother (=Mary)   = Liz;
mother (=George) = Liz;
mother (=John)   = Alice;
mother (=Liz)    = Jane;
mother (others)  = Unknown;

father (Person) -> Person;
father (=Mary)   = John;
father (=George) = John;
father (=John)   = Albert;
father (=Liz)    = Harry;
father (others)  = Unknown;

parents(Person) -> multi (Person);
parents( P ) = ( father(P), mother(P) );

grandmothers(Person) -> multi (Person);
grandmothers( P ) = ( mother( father(P)), mother( mother(P)) );

grandfathers(Person) -> multi (Person);
grandfathers( P ) = ( father( father(P)), father( mother(P)) );

grandparents(Person) -> multi(Person);
grandparents( P ) = parents( parents(P) );

The first two lines in this example introduces the type Person and enumerates the names of the relevant persons, including an Unknown person. The following lines are introducing the mothers and the fathers of the different persons. And then some parental relations are given. Each parental relation defines that for a given person multiple persons may be returned. For example, a person has always two parents and four grandparents. So, the parent definition produces for one person a stream of two persons and a grandparent definition produces two times a stream of two persons.

In an interactive session we may now question the system about the ancestors of a person. We will show some questions with their answers:

mother(Mary)?
Liz

father(mother(George))?
Harry

parents(Mary)?
John
Liz

parents(Harry)?
Unknown
Unknown

grandfathers(Mary)?
Albert
Harry

grandparents(George)?
Albert
Alice
Harry
Jane

These examples show how definitions may produce multiple answers.

Exercises:

4.9. Define grandparents in terms of grandmothers and grandfathers.

4.10. How many answers are produced by asking the question:

grandparents (grandparents (grandparents (George) ))?

And what are the answers?

4.11. The simplicity of the example of parental relations may mislead you. To get a better understanding of the power of stream producing definitions, write in one of your favorite programming languages a program which performs the same functions as the preceding family relations example.

4.8 Undefined Values

Functions are not always defined for all the values of their arguments. For example, the square root function is not defined for negative numbers. That means that Ö -2 is undefined if we exclude complex numbers. So, the call sqrt (-2) causes an exceptional condition which may result in an abnormal termination of the program. In many situations this is not acceptable. With an optional value definition this can be avoided, as shown here:

Sqrt (real) -> optional (real);
Sqrt (X) = sqrt (X) when X >= 0.0;

We define a new square root function, called Sqrt, which will return the square root if the argument is not negative, otherwise no value will be returned. In this way abnormal program termination is avoided.

In this example we used the when construct. This is a special expression which is discussed in Chapter 6, Section 2, "Conditionals". The expression:

f (a) when a > b

denotes an optional value for f (a) and is equivalent to:

if a > b then f (a)

4.9 Quantifier Propagation

Similar to the type propagation method as described in the preceding chapter, also quantifier information is propagated in an expression at translation time. The quantifier information in the result-specification of a selected definition is used to determine the quantifiers of the (sub-)expressions.

The quantifier propagation rules are used in the following order:

• if all operands of a sub-expression have the quantifier single, the sub-expression has the quantifier single.

• if at least one of the operands of a sub-expression has the quantifier nothing, the sub-expression is illegal, because the nothing quantifier represents no value. In general, expressions which are returning nothing may not be part of other expressions.

• if at least one operand of a sub-expression has the quantifier multi, the sub-expression has the quantifier multi.

• if one or more of the operands of a sub-expression have the quantifier optional and all other operands of a sub-expression have the quantifier single, the sub-expression has the quantifier optional.

Examples are:

2 + 3 			<< single + single -> single >>

2 * print(x) 		<< single * nothing -> Illegal >>

2 * (1..N) 		<< single * multi -> multi >>

2 * ( a when a < 5 ) 	<< single * optional -> optional >>

The quantifier propagation rules are used to determine the quantifier of an expression. In addition, there are conformance rules which are used to verify if expressions at the right-hand side of definition rules are in conformance with the specified quantifier in the result-specification. These conformance rules are:

1. If the quantifier in a result-specification is single then the corresponding expressions must also be single.

2. If the quantifier in a result-specification is multi then the corresponding expressions may be single, optional, or multi .

3. If the quantifier in a result-specification is optional then the corresponding expressions may be single, or optional.

4. If the quantifier in a result-specification is nothing then the corresponding expressions must be nothing.

Here are some examples:

f (integer) -> integer;
f (3) = 3; 			<< conformance: single with single>>
f (5) = 1 .. 5; 		<< no conformance: multi with single>>
f (x) = 2 * x; 			<< conformance: single with single>>

g (integer) -> multi (integer);
g (5) = 1 .. 5; 		<< conformance: multi with multi >>
g (7) = 7; 			<< conformance: single with multi >>
g (x)= x when x > 10; 		<< conformance: optional with multi >>

4.10 Recursive Stream Definitions

A recursive stream definition is a recursive definition which produces a stream of data items. Let us examine the following example definition:

from (integer) -> multi (integer);
from (n) = ( n, from (n+1) );

This is a definition which calls itself, is therefore recursive, and it produces a stream of integer values as specified by its result specification. But, what is it doing? We start with some substitutions:

from (n) = ( n, from (n+1) );
	 = ( n, ( n+1, from (n+2) ) );
	 = ( n, ( n+1, ( n+2, from (n+3) ) ) );
	 = ( n, ( n+1, ( n+2, ( n+3, from (n+4) ) ) ) );
	 = ( n, ( n+1, ( n+2, ( n+3, ( n+4, from (n+5) ) ) ) ) ); 

			etc.

If we take the last line and apply some simplifications, we get:

from (n) = ( n, n+1, n+2, n+3, n+4, from (n+5) );

This makes clear that the from definition produces for a given n a stream of successive integers, starting from n. And because no boundary condition has been given, this stream is, in principle, infinite. After each element of the stream there is always another element defined, and so on.

The fact that a definition may produce an infinite stream of data items illustrates an important evaluation principle applied to streams in general. Because it is impossible to compute all the elements of an infinite stream, and it is often not practical to compute all the elements of a finite stream at once, the elements of a stream are computed when needed. This type of evaluation is sometimes called lazy evaluation, or delayed evaluation, in contrast to normal, eager evaluation, where expressions are evaluated independent of their need. An execution model for delayed evaluation is discussed in the following chapter.

To give another example of a recursive stream definition let us return to the factorial function of Chapter 3. This function is recursively defined, as we discussed. It returns the value of n! in:

factorial (integer) -> integer;
factorial (1) = 1;
factorial (n) = n * factorial (n - 1);

This definition gives only one answer. It does not give all the factorials as we sometimes may wish. To get all the factorials we will need another definition:

Factorials (integer, integer) -> multi (integer);
Factorials (n, p) = ( p, Factorials (n+1, (n+1) * p) );

This definition produces an infinite stream of factorials if it is called by Factorials (1,1). The first parameter denotes n, the second n!. Repetitive substitution of the call gives:

Factorials (1,1) = ( 1, Factorials (2, 2) )
		 = ( 1, ( 2, Factorials (3, 6) ) )
		 = ( 1, ( 2, ( 6, Factorials (4, 24) ) ) )
		 = ( 1, ( 2, ( 6, ( 24, Factorials (5, 120) ) ) ) )
		 = ( 1, ( 2, ( 6, ( 24, ( 120, Factorials (6, 720) ) ) ) ) )

					etc.

Note that the Factorials definition works "bottom up", starting from 1, in contrast to the factorial definition of the preceding chapter which works "top-down", starting from n.

Exercise: 4.12. Make a recursive stream definition which produces an infinite stream of Fibonacci numbers.

4.11 Summary

· Expressions may represent streams of multiple data items.

· Operations on stream expressions are straightforward extensions of operations on single data items.

· The number of evaluations of an expression is equal to the product of the items in the operand streams.

· There are four quantifiers which may be used in signatures:

multi specifies that zero, one or more data items of the given type may be returned.

single specifies that one and only one data item of the given type will be returned.

optional specifies that zero or one data item of the given type may be returned.

nothing specifies that no data item will be returned.

· Quantifier propagation rules are used to determine the quantifiers of expressions.

· Quantifier conformance rules are used to verify if definition rules are in conformance with quantifier specifications.

· Stream definitions may produce infinite streams.

 

4.12 References

Abelson and Sussman (1985) are discussing streams in Scheme, which is a Lisp dialect. Lazy evaluation as defined in some functional programming languages is discussed by Henderson(1980), and Bird and Wadler (1988).

Part 1: Language Description

Chapter 4: Streams