Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Chapter 8, Evaluation Model, in the 2018 version of the textbook Exploring Languages with Interpreters and Functional Programming.

Browser Advisory: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of September 2018 is a recent version of Firefox from Mozilla.

Evaluation of Functional Programs

Lecture Goals

Introduce model for evaluation of functional programs
Characterize time and space complexity of functional programs
Characterize programs that terminate normally with the correct result

Referential Transparency

Referential transparency:: A symbol (e.g. variable) always represents the same value within some well-defined context (e.g. function body)

Probably most important property of purely functional languages
It enables manipulation of code like mathematics — “Equals can be replaced by equals”

Substitution (Reduction) Model

Rewriting (reducing) expression to “simpler” equivalent form
- replacing subexpression matching left side of equation by right side with argument substitution
- replacing primitive application (e.g. + or *) by its value

Redex:: a subexpression that can be reduced

Selecting Redexes (1)

By position in expression

leftmost redex first — leftmost reducible subexpression before any other
rightmost redex first — rightmost reducible subexpression before any other

Selecting Redexes (2)

By whether contained within another redex

outermost redex first — reducible subexpression not contained within another redex before others
innermost redex first — reducible subexpression not containing another redex before others

Haskell uses leftmost outermost redex first

Function Example

    fact1 :: Int -> Int 
    fact1 n = if n == 0 then 
                  1 
              else 
                  n * fact1 (n-1)

Consider else clause with n with value 2
```
    2 * fact1 (2-1)
```
Multiplication not reducible because need both arguments
Redex 2-1 is innermost
Redex fact1 (2-1) is outermost

Leftmost Outermost (1)

	`fact1 2`
$\Longrightarrow$	{ replace `fact1 2` using definition }
	`if 2 == 0 then 1 else 2 * fact1 (2-1)`
$\Longrightarrow$	{ evaluate `2 == 0` }
	`if False then 1 else 2 * fact1 (2-1)`
$\Longrightarrow$	{ evaluate `if` }
	`2 * fact1 (2-1)`
$\Longrightarrow$	{ replace `fact1 (2-1)` using definition, add implicit parentheses }
	`2 * (if (2-1) == 0 then 1 else (2-1) * fact1 ((2-1)-1))`
$\Longrightarrow$	{ evaluate `2-1` in condition }

Leftmost Outermost (2)

	`2 * (if 1 == 0 then 1 else (2-1) * fact1 ((2-1)-1))`
$\Longrightarrow$	{ evaluate `1 == 0` }
	`2 * (if False then 1 else (2-1) * fact1 ((2-1)-1))`
$\Longrightarrow$	{ evaluate `if` }
	`2 * ((2-1) * fact1 ((2-1)-1))`
$\Longrightarrow$	{ evaluate leftmost `2-1` }
	`2 * (1 * fact1 ((2-1)-1))`
$\Longrightarrow$	{ replace `fact1 ((2-1)-1)` using definition, add implicit parentheses }
	`2 * (1 * (if ((2-1)-1) == 0 then 1`
	`else ((2-1)-1) * fact1 ((2-1)-1)-1))`
$\Longrightarrow$	{ evaluate `2-1` in condition }

Leftmost Outermost (3)

	`2 * (1 * (if (1-1) == 0 then 1`
	`else ((2-1)-1) * fact1 ((2-1)-1)-1))`
$\Longrightarrow$	{ evaluate `1-1` in condition }
	`2 * (1 * (if 0 == 0 then 1`
	`else ((2-1)-1) * fact1 ((2-1)-1)-1))`
$\Longrightarrow$	{ evaluate `0 == 0` }
	`2 * (1 * (if True then 1`
	`else ((2-1)-1) * fact1 ((2-1)-1)-1))`
$\Longrightarrow$	{ evaluate `if` }
	`2 * (1 * 1)`
$\Longrightarrow$	{ evaluate `1 * 1` }

Leftmost Outermost (4)

	`2 * 1`
$\Longrightarrow$	{ evaluate `2 * 1` }
	`2`

String Reduction Model

Rewriting model in example uses string reduction
- represent expression as string
- replace a substring by equivalent string
But sometimes results in repeated reductions of same subexpression
Below subsequently reduces (2-1) three times

	`2 * fact1 (2-1)`
$\Longrightarrow$	`2 * (if (2-1) == 0 then 1 else (2-1) * fact1 ((2-1)-1))`

Graph Reduction Model

More efficient rewriting model uses graph reduction
- use directed acyclic graph to represent expression
- make repeated argument use shared subgraph
- replace one subgraph by equivalent subgraph
Below reduces shared occurrences of (2-1) in one step

	`2 * fact1 (2-1)`
$\Longrightarrow$	`2 * (if (2-1) == 0 then 1 else (2-1) * fact1 ((2-1)-1))`
$\Longrightarrow$	`2 * (if 1 == 0 then 1 else 1 * fact1 (1)-1))`

Leftmost Outermost Graph (1)

	`fact1 2`
$\Longrightarrow$	{ replace `fact1 2` using definition }
	`if 2 == 0 then 1 else 2 * fact1 (2-1)`
$\Longrightarrow$	{ evaluate `2 == 0` in condition }
	`if False then 1 else 2 * fact1 (2-1)` }
$\Longrightarrow$	{ evaluate `if` }
	`2 * fact1 (2-1)`
$\Longrightarrow$	{ replace `fact1 (2-1)` using definition, add implicit parentheses }
	`2 * (if (2-1) == 0 then 1 else (2-1) * fact1 ((2-1)-1))`
$\Longrightarrow$	{ evaluate `2-1` because of condition (3 occurrences in graph) }
	`2 * (if 1 == 0 then 1 else 1 * fact1 (1-1))`
$\Longrightarrow$	{ evaluate `1 == 0` }

Leftmost Outermost Graph (2)

	`2 * (if False then 1 else 1 * fact1 (1-1))`
$\Longrightarrow$	{ evaluate `if` }
	`2 * (1 * fact1 (1-1))`
$\Longrightarrow$	{ replace `fact1 ((1-1)` using definition, add implicit parentheses }
	`2 * (1 * (if (1-1) == 0 then 1 else (1-1) * fact1 ((1-1)-1))`
$\Longrightarrow$	{ evaluate `1-1` because of condition (3 occurrences in graph) }
	`2 * (1 * (if 0 == 0 then 1 else 0 * fact1 (0-1))`
$\Longrightarrow$	{ evaluate `0 == 0` }
	`2 * (1 * (if True then 1 else 0 * fact1 (0-1))`
$\Longrightarrow$	{ evaluate `if` }

Leftmost Outermost Graph (3)

	`2 * (1 * 1)`
$\Longrightarrow$	{ evaluate `1 * 1` }
	`2 * 1`
$\Longrightarrow$	{ evaluate `2 * 1` }
	`2`

Time Complexity

Time measure:: number of steps in leftmost outermost graph reduction

fact1 n requires 5n + 3 reductions
Alternatively count dominant operations – n multiplications, n recursive calls
Time complexity: O(n )

Space Complexity

Space measure:: maximum graph size needed for leftmost outmost graph reduction

Size of expression graph is total number of operands

Largest expression for fact1 2 has 20 operands

    2 * (1 * (if (1-1) == 0 then 1 else (1-1) * fact1 ((1-1)-1))

Largest expression for fact1 n has size 2n + 16
- multiplication for each in range [1..n ] plus 16 for full if expression
Space complexity: O(n ).

Termination

Each recursive call gets closer to base case
For n > 0, fact1 n calls fact1 (n-1)
For n == 0, fact1 terminates normally
For n < 0, fact1 does not terminate normally

Key Ideas

Referential transparency
Reduction strategies (leftmost vs. rightmost, innermost vs. outermost)
String and graph reduction models
Time and space complexity
Termination

Exploring Languages with Interpreters and Functional Programming Chapter 8 Evaluation Model