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.

"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 Our earlier discussion of referential transparency Equality in Scheme

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.

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

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 Foldoc: alpha conversion

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 Foldoc: beta conversion

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 Foldoc: eta conversion

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 Foldoc: normal form

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 Foldoc: church-rosser

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 Foldoc: lazy evaluation

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.

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.

References R5RS: delay R5RS: force

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.

Program: An implementation of cons-stream in R5RS Scheme.

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

Reference SICP: Streams

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.

Program: All Scheme stream stuff collected in one file.

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: (define ones (cons-stream 1 ones)) (define nat-nums (cons-stream 1 (add-streams ones nat-nums))) (define fibs (cons-stream 0 (cons-stream 1 (add-streams (tail fibs) fibs)))) 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. Here are all the necessary definitions you need to get started: (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))))) (define ones (cons-stream 1 ones)) (define nat-nums (cons-stream 1 (add-streams ones nat-nums)))

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? Here is all you need to get started: (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))))))

Exercise 4.5. A stream that converges to the square root a number

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)))))) Here is all you need to get started: (define (improve-sqrt-guess guess x) (/ (+ guess (/ x guess)) 2)) (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 (map-stream f stream) (cond ((empty-stream? stream) the-empty-stream) (else (cons-stream (f (head stream)) (map-stream f (tail stream))))))

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: August 13, 2021, 14:52:00