Lecture 5 - Page 2 : 26
Functional Programming in Scheme
The Order of Evaluation
* Referential transparency
Referential transparency
An illustration of referential transparency
* Introduction to evaluation order
Arbitrary evaluation order - with some limits
A motivating example
A motivating example - 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
Referential transparency
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
Foldoc: referential transparency
Equality in Scheme
![Previous page: Referential transparency [Section] -- Keyboard shortcut: 'p'](./images/nav-left.gif "Previous page: Referential transparency [Section] -- Keyboard shortcut: 'p'")
