Chapter 5
The Order of Evaluation

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


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


Referential transparency

Referential transparency
Slide Annotated slide Contents Index
References Textbook 

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 cannot be distinguished by functional means

    • 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 Textbook 

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 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 Textbook 

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.

  • Subexpressions can be evaluated in an arbitrary order provided that

    • no errors occur in subexpressions

    • the evaluation of all subexpressions terminates

  • It is possible, and without problems, to evaluate subexpressions in parallel

A motivating example
Slide Annotated slide Contents Index
References Textbook 

What is the value of the following expression?

Program: A constant function with an actual parameter expression, the evaluation of which never terminates.
((lambda (x) 1) some-infinite-calculation)

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

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

A motivating example - clarification
Slide Annotated slide Contents Index
References Textbook 

What is the value of the following expression?

Program: A constant function with an actual parameter expression, the evaluation of which never terminates.
((lambda (x) 1) some-infinite-calculation)

Program: A variation of the example in Scheme.
(define (infinite-calculation)
  (infinite-calculation))

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

  • Different evaluation orders give different 'results'

    • The number 1

    • A non-terminating 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 an infinite calculation


Rewrite rules, reduction, and normal forms

Rewrite rules
Slide Annotated slide Contents Index
References Textbook 

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 general 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 Textbook 

An alpha conversion changes the names of lambda expression formal parameters

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 b 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 Textbook 

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 Textbook 

An eta conversion lifts certain function calls out of a 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
 

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 Textbook 

Normal forms represent our intuition of the value of an expression

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

  • About normal forms

    • 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

Is a normal form always unique?

Reference

The ordering of reductions
Slide Annotated slide Contents Index
References Textbook 

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 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 withspecial formsthat use a non-standard evaluation strategy

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

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))

It appears to be the case that normal order reduction can lead to repeated evaluation of the same subexpression

Theoretical results
Slide Annotated slide Contents Index
References Textbook 

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

Figure. The rewriting => is confluent if for all e, e1 and e2, for which e => e1 and e => e2, there exists an e3 such that e1 => e3 and e2 => e3

The first Church-Rosser theorem. Rewriting with beta and eta conversions are confluent.

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

Reference

Practical implications
Slide Annotated slide Contents Index
References Textbook 

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.

  • 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 Textbook 

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 z)

    • and evaluates its parameter from left to right

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

    • Often, it would be harmful to evaluate y and z

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

Lazy evaluation
Slide Annotated slide Contents Index
References Textbook 

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 Textbook 

Scheme does not support normal-order reduction nor lazy evaluation

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.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/delay-force-principle.scm

Program: Real implementations of delay. 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.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/delay-force.scm

References

Examples of delayed evaluation
Slide Annotated slide Contents Index
References Textbook 

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 Textbook 

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.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/stream-primitives.scm

Program: An implementation of cons-stream in R5RS Scheme.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/stream.scm

The functions mentioned above stem from the book Structure and Interpretation of Computer Programs

Reference

Example streams
Slide Annotated slide Contents Index
References Textbook 

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.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/stream.scm

Program: All Scheme stream stuff collected in one file.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/stream-stuff.scm

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

The Sieve of Eratosthenes is a 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 Textbook 

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)))


Collected references
Contents Index
Equality in Scheme
Foldoc: 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 5: The Order of Evaluation
Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
Generated: January 3, 2014, 09:34:07