Lecture 4 - Page 16 : 27

Programming Paradigms Evaluation Order and Infinite Lists * Referential Transparency Referential transparency An illustration of referential transparency * Introduction to Evaluation Order Arbitrary evaluation order - with some limits Infinite evaluations and error evaluations Infinite evaluations and error evaluations - clarification * Rewrite rules, reduction, and normal forms Rewrite rules The alpha rewrite rule The beta rewrite rule The eta rewrite rule Normal forms The ordering of reductions An example of normal versus applicative evaluation Theoretical results Practical implications Conditionals and sequential boolean operators Lazy evaluation * Delayed evaluation and infinite lists in Scheme Delayed evaluation in Scheme Examples of delayed evaluation Infinite lists in Scheme: Streams Example streams Stream example: The Sieve of Eratosthenes Applications of The sieve of Eratosthenes Exercises

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

Foldoc: church-rosser