Chapter 4
Evaluation Order and Infinite Lists

Kurt NÝrmark
Department of Computer Science, Aalborg University, Denmark


Abstract
Previous lecture
Index References Contents
In this lecture we will study the impact of the order of evaluation.


Referential Transparency

Program: The forms discussed.
"NEXT: infinite evaluation and errors"

((lambda (x) 1) some-infinite-calculation)

(define (some-infinite-calculation) (some-infinite-calculation))

((lambda (x) 1) (some-infinite-calculation))

((lambda (x) 1) 
   ((lambda (x) (x x)) (lambda (x) (x x))) )

((lambda (x) 1) (/ 5 0))

"NEXT: delay and force examples"

(delay (+ 5 6))

(force (delay (+ 5 6)))

(force 11)

(define pr (delay (+ 5 6)))

(+ 7 pr)

(+ 7 (force pr))

"NEXT: Streams stuff - prerequisites"

(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream x y)
     (cons x (delay y)))))

(define head car)

(define (tail stream) (force (cdr stream)))

(define empty-stream? null?)

(define the-empty-stream '())


(define (stream-section n stream)
  (cond ((= n 0) '())
        (else (cons (head stream)
              (stream-section 
                (- n 1)
               (tail stream))))))

(define (add-streams s1 s2)
 (let ((h1 (head s1))
       (h2 (head s2)))
   (cons-stream 
    (+ h1 h2)
    (add-streams (tail s1) (tail s2)))))

"NEXT: Stream examples"

(define ones (cons-stream 1 ones))

ones

(stream-section 7 ones)

(define (integers-starting-from n)
 (cons-stream n 
  (integers-starting-from (+ n 1))))

(define nat-nums
  (integers-starting-from 1))

nat-nums

(stream-section 10 nat-nums)

(define nat-nums 
 (cons-stream 1 
  (add-streams ones nat-nums)))

(stream-section 10 nat-nums)

(define fibs
  (cons-stream 0
    (cons-stream 1
      (add-streams (tail fibs) fibs))))

fibs

(stream-section 15 fibs)

"NEXT: The sieve of Eratosthenes"

(define (sieve stream)
   (cons-stream
     (head stream)
     (sieve 
       (filter-stream
         (lambda (x) (not (divisible? x (head stream))))
         (tail stream)))))

(define (divisible? x y)
  (= (remainder x y) 0))

(define (filter-stream p lst)
  (cond ((empty-stream? lst) the-empty-stream)
        ((p (head lst)) (cons-stream (head lst) (filter-stream p (tail lst))))
        (else (filter-stream p (tail lst)))))

(define primes (sieve (integers-starting-from 2)))

primes

(stream-section 100 primes)

"THE END"

Referential transparency
Slide Annotated slide Contents Index
References 

Two equal expressions can substitute each other without affecting the meaning of a functional program

  • Referential transparency

    • provides for easy equational reasoning about a program

    • does not rely on a particular notion of equality

      • Reference equality, shallow equality and deep equality do all apply

    • is a major contrast to imperative programming

Equals can be replaced by equals

References

An illustration of referential transparency
Slide Annotated slide Contents Index
References 

With referential transparency it is possible to perform natural program transformations without any concern of side effects

Figure. It is possible to rewrite one of the expressions above to the other, provided that F is a pure function. Below, we have illustrated an example where F is of procedural nature. Notice that F assigns the variable c, such that it becomes critical to know how many times F is called.


Introduction to Evaluation Order

Arbitrary evaluation order - with some limits
Slide Annotated slide Contents Index
References 

In a functional program an expression is evaluated with the purpose of producing a value

An expression is composed of subexpressions

Figure. An illustration of an expression with subexpressions. In this context we will assume that and is defined as a function. In Scheme, and is not definede as a function, because of the short circuit evaluation rule. If and is short circuited the evaluation order of the surrounding expression is constrained.

  • Subexpressions can be evaluated in an arbitrary order provided that

    • no errors occur in subexpressions

    • the evaluation of all subexpressions terminate

  • It is possible to evaluate subexpressions in parallel

Infinite evaluations and error evaluations
Slide Annotated slide Contents Index
References 

What is the value of the following expressions?

Program: Constant functions with problematic actual parameter expressions.
((lambda (x) 1) some-infinite-calculation)

((lambda (x) 1) (/ 5 0))

Program: A more concrete version of the infinite calculation from above. The function infinite-calculation just calls itself without ever terminating.
(define (infinite-calculation)
  (infinite-calculation))

((lambda (x) 1) (infinite-calculation))

(let ((x (infinite-calculation)))
  1)


; Another example:

((lambda (x) 1) 
   ((lambda (x) (x x)) (lambda (x) (x x))) )

Infinite evaluations and error evaluations - clarification
Slide Annotated slide Contents Index
References 

What is the value of the following expressions?

Program: Constant functions with problematic actual parameter expressions.
((lambda (x) 1) some-infinite-calculation)

((lambda (x) 1) (/ 5 0))

  • Different evaluation orders give different 'results'

    • The number 1

    • A non-terminating calculation/an erroneous calculation

  • Two different semantics of function application are involved:

    • Strict: A function call is well-defined if and only if all actual parameters are well-defined

    • Non-strict: A function call can be well-defined even if one or more actual parameters cause an error or enters an infinite calculation

Scheme is strict


Rewrite rules, reduction, and normal forms

Rewrite rules
Slide Annotated slide Contents Index
References 

The rewrite rules define semantics preserving transformations of expressions

The goal of applying the rewrite rules is normally to reduce an expression to the simplest possible form, called a normal form

  • Overview of rewrite rules

    • Alpha conversion: rewrites a lambda expression

    • Beta conversion: rewrites function calls

      • Expresses the idea of substitution, as described by the substitution model

    • Eta conversion: rewrites certain lambda expressions to a simpler form

The alpha rewrite rule
Slide Annotated slide Contents Index
References 

An alpha conversion changes the names of formal parameters in lambda expression

The concept alpha conversion: Formal parameters of a lambda expression can be substituted by other names, which are not used as free names in the body

Legal conversion:

Table. An example of an alpha rewriting. The name a replaces x and the name y replaces y.
Expression

Converted Expression

(lambda (x y) (f x y))
(lambda (a b) (f a b))
 

Illegal conversion:

Table. Examples of an illegal alpha conversion. f is a free name in the lambda expression. A free name is used, but not defined (bound) in the lambda expression. In case we rename one of the parameters to f, the free name will be bound, hereby causing an erroneous name binding.
Expression

Converted Expression

(lambda (x y) (f x y))
(lambda (a f) (f a f))
 

Reference

The beta rewrite rule
Slide Annotated slide Contents Index
References 

A beta conversion tells how to evaluate a function call

The concept beta conversion: An application of a function can be substituted by the function body, in which formal parameters are substituted by the corresponding actual parameters

Legal conversions:

Table. Examples of beta conversions. In all the three examples the function calls are replaced by the bodies. In the bodies, the formal parameters are replaced by actual parameters.
Expression

Converted Expression

((lambda(x) (f x)) a)
(f a)
((lambda(x y) (* x (+ x y))) (+ 3 4) 5)
(* 7 (+ 7 5))
((lambda(x y) (* x (+ x y))) (+ 3 4) 5)
(* (+ 3 4) (+ (+ 3 4) 5))
 

Reference

The eta rewrite rule
Slide Annotated slide Contents Index
References 

An eta conversion lifts certain functions out of a "redundant lambda convolute"

The concept eta conversion: A function f, which only passes its parameters on to another function e, can be substituted by e

(lambda(x) (e x)) <=> e   provided that x is not free in the expression e

Legal conversion:

Table. An example of an eta rewriting.
Expression

Converted Expression

(lambda (x) (square x))
square
(lambda (x) ((lambda(y) (* y y)) x))
(lambda(y) (* y y))
 

Illegal conversion:

Table. An example of an illegal eta conversion. The eta conversion rule says in general how 'e' is lifted out of the lambda expressions. In this example, e corresponds to the emphasized inner lambda expression (which is blue on a color medium.) However, x is a free name in the inner lambda expression, and therefore the application of the eta rewrite rule is illegal.
Expression

Converted Expression

(lambda(x) ((lambda(y) (f x y)) x))
(lambda(y) (f x y))
 

Reference

Normal forms
Slide Annotated slide Contents Index
References 

A normal form represents our intuition of the value of an expression

The concept normal form: An expression is on normal form if it cannot be reduced further by use of beta and eta conversions

  • About normal forms

    • Some expressions have no normal form

    • Alpha conversions can be used infinitely, and as such they do not play any role in the formulation of a normal form

    • A normal form is a particular simple expression, which is equivalent to the original expression, due to the application of the conversions (reductions)

Program: An example of a Scheme expression without a normal form.
((lambda (x) (x x)) 
    (lambda (x) (x x)))

Program: Scheme expressions - some of which are in normal form.
7                                  ; Normal Form

(+ 6 1)                            ; Not Normal Form

(lambda (x) (+ x 1))               ; Normal Form  

((lambda (x) (+ x 1)) 6)           ; Not Normal Form  (pending beta reduction)

(lambda (x) 
  (+ ((lambda (y) (+ y 1)) 5) 1))  ; Not Normal Form - but Weak Head Normal Form

(lambda (x)                        ; Not Normal Form  (pending eta reduction)
   ((lambda (y) (- y)) x))         

(lambda (y) (- y))                 ; Normal Form

Is a normal form always unique?

Reference

The ordering of reductions
Slide Annotated slide Contents Index
References 

Given a complex expression, there are many different orderings of the applicable reductions

The concept normal-order reduction: Using normal-order reduction, the first reduction to perform is the one at the outer level of the expression (the leftmost reduction first).
The concept applicative-order reduction: Using applicative-order reduction, the first reduction to perform is the inner leftmost reduction.

  • Normal-order reduction represents evaluation by need

  • Applicative-order reduction evaluates all constituent expressions, some of which are unnecessary or perhaps even harmful.

    • As such, there is often a need to control the evaluation process with special forms that use non-standard evaluation strategies

An example of normal versus applicative evaluation
Slide Annotated slide Contents Index
References 

Reduction of the expression

((lambda(x y) (+ (* x x) (* y y))) (fak 5) (fib 10))

Figure. Normal vs. applicative reduction of a Scheme expression

Program: The necessary Scheme stuff to evaluate the expression.
(define (fak n)
  (if (= n 0) 1 (* n (fak (- n 1)))))

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) (fib (- n 2))))))

((lambda(x y) (+ (* x x) (* y y)))  (fak 5)  (fib 10))

Normal-order reduction can lead to repeated evaluation of the same subexpression

Theoretical results
Slide Annotated slide Contents Index
References 

The theoretical results mentioned on this page assure some very satisfactory properties of functional programming

Figure. The rewriting => is confluent if for all e, e 1 and e 2 , for which e => e 1 and e => e 2 , there exists an e 3 such that e 1 => e 3 and e 2 => e 3

The first Church-Rosser theorem.   If e1 <=> e2 then there exists an e3 such that e1 => e3 and e2 => e3

  • Rewriting with beta and eta conversions are confluent

The second Church-Rosser theorem.   If e0 => ... => en , and if en is on normal form, then there exists a normal-order reduction of e0 to en

  • Normal-order reduction is the most powerful evaluation order

Reference

Practical implications
Slide Annotated slide Contents Index
References 

We will here describe the practical consequences of the theoretical results mentioned on the previous page

  • During the evaluation of an expression, it will never be necessary to backtrack the evaluation process in order to reach a normal form.

    • There are no blind alleys in the evaluation of an expression

  • An expression cannot be converted to two different normal forms (modulo alpha conversions, of course).

  • If an expression e somehow can be reduced to f in one or more steps, f can be reached by normal-order reduction - but not necessarily by applicative-order reduction

Normal-order reduction is more powerful than the applicative-order reduction

Scheme and ML uses applicative-order reduction

Haskell is an example of a functional programming language with normal-order reduction

Conditionals and sequential boolean operators
Slide Annotated slide Contents Index
References 

There are functional language constructs - special forms - for which applicative order reduction would not make sense

  • (if b x y)

    • Depending on the value of b, either x or y are evaluated

    • It would often be harmful to evaluate both x and y before the selection

      • (define (fak n) (if (= n 0) 1 (* n (fak (- n 1)))))

  • (and x y)

    • and evaluates its parameters from left to right

    • In case x is false, there is no need to evaluate y

    • Often, it would be harmful to evaluate y

      • (and (not (= y 0)) (even? (quotient x y)))

Lazy evaluation
Slide Annotated slide Contents Index
References 

We will now deal with a practical variant of normal-order reduction

The concept lazy evaluation: Lazy evaluation is an implementation of normal-order reduction which avoids repeated calculation of subexpressions

Figure. An illustration of lazy evaluation of a Scheme expression. Notice, that Scheme does not evaluate the expression in this way. Scheme uses applicative-order reduction.

Reference


Delayed evaluation and infinite lists in Scheme

Delayed evaluation in Scheme
Slide Annotated slide Contents Index
References 

Scheme does not support normal-order reduction nor lazy evaluation

But Scheme has an explicit primitive which delays an evaluation

Syntax:

(delay expr) => promise

Syntax:

(force promise) => value

Program: A principled implementation of delay and force in Scheme.
c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/delay-force-principle.scm

Program: Real implementations of delay and force. The first definition uses the R5RS macro facility, whereas the last one uses a more primitive macro facility, which happens to be supported in MzScheme.
c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/delay-force.scm

References

Examples of delayed evaluation
Slide Annotated slide Contents Index
References 

Table. Examples of use of delay and force.
Expression

Value

(delay (+ 5 6))
#<promise>
(force 11)
error
(let ((delayed (delay (+ 5 6))))
  (force delayed))
11
 

Infinite lists in Scheme: Streams
Slide Annotated slide Contents Index
References 

We can work with lists of infinite length by delaying the evaluation of every list tail using delay

As an invariant, every list tail will be delayed

Program: Stream primitives. Notice the way head is defined to be an alias of car.
c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/stream-primitives.scm

Program: An implementation of cons-stream in R5RS Scheme.
c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/stream.scm

The functions mentioned above are taken from the book

Structure and Interpretation of Computer Programs

Reference

Example streams
Slide Annotated slide Contents Index
References 

Table. Examples of streams. ones is an infinite streams of the element 1. stream-section is a function that returns a finite section of a potentially infinite stream. nat-nums is stream of all the natural numbers, made by use of the recursive function integers-starting-from. The fourth row shows an alternative definition of nat-nums. Finally, fibs is the infinite stream of Fibonacci numbers.
Expression

Value

(define ones (cons-stream 1 ones))
(1 . #<promise>)
(stream-section 7 ones)
(1 1 1 1 1 1 1)
(define (integers-starting-from n)
 (cons-stream n 
  (integers-starting-from (+ n 1))))

(define nat-nums
  (integers-starting-from 1))

(stream-section 10 nat-nums)
(1 2 3 4 5 6 7 8 9 10)
(define nat-nums 
 (cons-stream 1 
  (add-streams ones nat-nums)))

(stream-section 10 nat-nums)
(1 2 3 4 5 6 7 8 9 10)
(define fibs
  (cons-stream 0
    (cons-stream 1
      (add-streams (tail fibs) fibs))))

(stream-section 15 fibs)
(0 1 1 2 3 5 8 13 21 34 55 89 144 
 233 377)
 

Program: The functions stream-section and add-streams.
c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/stream.scm

Program: All Scheme stream stuff collected in one file.
c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/stream-stuff.scm

Stream example: The Sieve of Eratosthenes
Slide Annotated slide Contents Index
References 

The Sieve of Eratosthenes is a slightly more sophisticated example of the use of streams

Program: The sieve stream function.
(define (sieve stream)
   (cons-stream
     (head stream)
     (sieve 
       (filter-stream
         (lambda (x) (not (divisible? x (head stream))))
         (tail stream)))))

Figure. An illustration of the generation of prime numbers in The Sieve of Eratosthenes

Applications of The sieve of Eratosthenes
Slide Annotated slide Contents Index
References 

The sieve process produces the stream of all prime numbers

Table. The first 25 prime numbers made by sieving a sufficiently long prefix of the integers starting from 2.
Expression

Value

(define primes 
  (sieve 
    (integers-starting-from 2)))

(stream-section 25 primes)
(2 3 5 7 11 13 17 19 23 29 31 37 41 
 43 47 53 59 61 67 71 73 79 83 89 97)
 

Program: All the functions necessary to use the Sieve of Eratosthenes. In addition, however, you must load the Scheme stream stuff. The most remarkable function is filter-streams, which illustrates that it is necessary to rewrite all our classical higher order function to stream variants. This is clearly a drawback!
(define (sieve stream)
   (cons-stream
     (head stream)
     (sieve 
       (filter-stream
         (lambda (x) (not (divisible? x (head stream))))
         (tail stream)))))

(define (divisible? x y)
  (= (remainder x y) 0))

(define (filter-stream p lst)
  (cond ((empty-stream? lst) the-empty-stream)
        ((p (head lst)) (cons-stream (head lst) (filter-stream p (tail lst))))
        (else (filter-stream p (tail lst)))))

(define (integers-starting-from n)
 (cons-stream n 
  (integers-starting-from (+ n 1))))

(define primes (sieve (integers-starting-from 2)))

Exercises
Slide Annotated slide Contents Index
References 

Exercise 4.5. Finite streams

The function list produces a list of some given elements.

Make a similar function stream that produces a stream of some given elements.

As an example, (stream 1 2 3 4 5) should produce the finite stream of 1, 2, 3, 4 and 5.

Exercise 4.5. A stream of factorial numbers

Make a stream of all factorial numbers: 1 2 6 24 120 ...

Please go for a recursive definition, in the same style as used for nat-nums and fib.

As part of the solution, you may need a multiplicative stream function similar to add-streams. For that purpose make a higher-order function, combine-streams, that combines two (infinite) streams with a binary function.

Exercise 4.5. Stream appending and stream merging

We have seen a number of useful stream funtions, as counterparts to well-known list functions.

First, consider if/how to program a stream-append function, as a counterpart to append. Here is a possible recursive append function for lists:

  (define (my-append lst1 lst2)
    (cond ((null? lst1) lst2)
          (else (cons (car lst1) (my-append (cdr lst1) lst2)))))

How will your stream-append function work on infinite streams, such as nat-nums or fibs?

Now program a similar function, stream-merge, that merges two streams by simple alternation.

How will stream-merge function work on initinite streams? And on finite streams?

Can you use stream-merge to produce as stream of all integers (in some arbitrary order), based on two other streams with fixed starting points?

Exercise 4.5. A stream of square root numbers

It is well-known that the square root function can be implemented by use of Newton's method. In case you need some background, you can consult this video.

If we need to find sqrt(x) based on an initial quess g, we can iteratively improve our guess by this simple function:

(define (improve-sqrt-guess guess x)
  (/ (+ guess (/ x guess)) 2))

Produce a stream of real numbers, starting with the initial guess 1.0, that will converge towards sqrt(x).

You may find the following stream variant of map useful:

  (define (map-stream f stream)
    (cond ((empty-stream? stream) the-empty-stream)
          (else (cons-stream (f (head stream)) (map-stream f (tail stream))))))


Collected references
Contents Index
Equality in Scheme
Our earlier discussion of referential transparency
Foldoc: alpha conversion
Foldoc: beta conversion
Foldoc: eta conversion
Foldoc: normal form
Foldoc: church-rosser
Foldoc: lazy evaluation
R5RS: force
R5RS: delay
SICP: Streams

 

Chapter 4: Evaluation Order and Infinite Lists
Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
Generated: October 3, 2017, 15:47:58