Lecture 4 - Page 7 : 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
Infinite evaluations and error evaluations - clarification
What is the value of the following expressions?
((lambda (x) 1)
some-infinite-calculation
) ((lambda (x) 1)
(/ 5 0)
)
Constant functions with problematic actual parameter expressions.
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
![Next page: Rewrite rules, reduction, and normal forms [Section] -- Keyboard shortcut: 'n'](./images/nav-right.gif "Next page: Rewrite rules, reduction, and normal forms [Section] -- Keyboard shortcut: 'n'")
