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. 

Referential transparency Slide Annotated slide Contents Index References 




An illustration of referential transparency Slide Annotated slide Contents Index References 

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 

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. 

Infinite evaluations and error evaluations Slide Annotated slide Contents Index References 

Program: Constant functions with problematic actual parameter expressions.


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

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

Program: Constant functions with problematic actual parameter expressions.




Rewrite rules, reduction, and normal forms 
Rewrite rules Slide Annotated slide Contents Index References 


The alpha rewrite rule Slide Annotated slide Contents Index References 

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. 

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. 


The beta rewrite rule Slide Annotated slide Contents Index References 

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. 


The eta rewrite rule Slide Annotated slide Contents Index References 

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. 

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. 


Normal forms Slide Annotated slide Contents Index References 

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

Program: An example of a Scheme expression without a normal form. 

Program: Scheme expressions  some of which are in normal form. 



The ordering of reductions Slide Annotated slide Contents Index References 

The concept normalorder reduction: Using normalorder reduction, the first reduction to perform is the one at the outer level of the expression (the leftmost reduction first).  
The concept applicativeorder reduction: Using applicativeorder reduction, the first reduction to perform is the inner leftmost reduction. 

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

Figure. Normal vs. applicative reduction of a Scheme expression 
Program: The necessary Scheme stuff to evaluate the expression. 


Theoretical results Slide Annotated slide Contents Index References 

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 ChurchRosser theorem. If e_{1} <=> e_{2} then there exists an e_{3} such that e_{1} => e_{3} and e_{2} => e_{3} 

The second ChurchRosser theorem. If e_{0} => ... => e_{n} , and if e_{n} is on normal form,
then there exists a normalorder reduction of e_{0} to e_{n} 


Practical implications Slide Annotated slide Contents Index References 



Conditionals and sequential boolean operators Slide Annotated slide Contents Index References 



Lazy evaluation Slide Annotated slide Contents Index References 

The concept lazy evaluation: Lazy evaluation is an implementation of normalorder 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 applicativeorder reduction. 

Delayed evaluation and infinite lists in Scheme 
Delayed evaluation in Scheme Slide Annotated slide Contents Index References 

Syntax: 

Syntax: 

Program: A principled implementation of delay and force in Scheme. 

Examples of delayed evaluation Slide Annotated slide Contents Index References 
Table. Examples of use of delay and force. 

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

Program: Stream primitives. Notice the way head is defined to be an alias of car. 
Program: An implementation of consstream in R5RS Scheme. 


Example streams Slide Annotated slide Contents Index References 
Table. Examples of streams. ones is an infinite streams of the element 1. streamsection is a function that returns a finite section of a potentially infinite stream. natnums is stream of all the natural numbers, made by use of the recursive function integersstartingfrom. The fourth row shows an alternative definition of natnums. Finally, fibs is the infinite stream of Fibonacci numbers. 

Program: The functions streamsection and addstreams. 
Program: All Scheme stream stuff collected in one file. 
Stream example: The Sieve of Eratosthenes Slide Annotated slide Contents Index References 

Program: The sieve stream function. 

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 

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

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 filterstreams, which illustrates that
it is necessary to rewrite all our classical higher order function to
stream variants. This is clearly a drawback! 

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 natnums and fib: (define ones (consstream 1 ones)) (define natnums (consstream 1 (addstreams ones natnums))) (define fibs (consstream 0 (consstream 1 (addstreams (tail fibs) fibs)))) As part of the solution, you may need a multiplicative stream function similar to addstreams. For that purpose make a higherorder function, combinestreams, that combines two (infinite) streams with a binary function. Here are all the necessary definitions you need to get started: (definesyntax consstream (syntaxrules () ((consstream x y) (cons x (delay y))))) (define head car) (define (tail stream) (force (cdr stream))) (define emptystream? null?) (define theemptystream '()) (define (streamsection n stream) (cond ((= n 0) '()) (else (cons (head stream) (streamsection ( n 1) (tail stream)))))) (define (addstreams s1 s2) (let ((h1 (head s1)) (h2 (head s2))) (consstream (+ h1 h2) (addstreams (tail s1) (tail s2))))) (define ones (consstream 1 ones)) (define natnums (consstream 1 (addstreams ones natnums))) 
Exercise 4.5. Stream appending and stream merging  We have seen a number of useful stream funtions, as counterparts to wellknown list functions. First, consider if/how to program a streamappend function, as a counterpart to append. Here is a possible recursive append function for lists: (define (myappend lst1 lst2) (cond ((null? lst1) lst2) (else (cons (car lst1) (myappend (cdr lst1) lst2))))) How will your streamappend function work on infinite streams, such as natnums or fibs? Now program a similar function, streammerge, that merges two streams by simple alternation. How will streammerge function work on initinite streams? And on finite streams? Can you use streammerge 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: (definesyntax consstream (syntaxrules () ((consstream x y) (cons x (delay y))))) (define head car) (define (tail stream) (force (cdr stream))) (define emptystream? null?) (define theemptystream '()) (define (streamsection n stream) (cond ((= n 0) '()) (else (cons (head stream) (streamsection ( n 1) (tail stream)))))) 
Exercise 4.5. A stream that converges to the square root a number  It is wellknown 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 (improvesqrtguess 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 (mapstream f stream) (cond ((emptystream? stream) theemptystream) (else (consstream (f (head stream)) (mapstream f (tail stream)))))) Here is all you need to get started: (define (improvesqrtguess guess x) (/ (+ guess (/ x guess)) 2)) (definesyntax consstream (syntaxrules () ((consstream x y) (cons x (delay y))))) (define head car) (define (tail stream) (force (cdr stream))) (define emptystream? null?) (define theemptystream '()) (define (streamsection n stream) (cond ((= n 0) '()) (else (cons (head stream) (streamsection ( n 1) (tail stream)))))) (define (mapstream f stream) (cond ((emptystream? stream) theemptystream) (else (consstream (f (head stream)) (mapstream 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: October 2, 2018, 16:02:41