COMP0020: Functional Programming
Example Programs
COMP0020 Functional Programming Lecture 17
Graph Reduction
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 24 / 25
COMP0020: Functional Programming
Example Programs
Contents
Representation of lambda expressions :
I Abstract I Physical
Performing a beta reduction Reduction orders
Lazy and strict evaluation Parallel evaluation
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 25 / 25
COMP0020: Functional Programming
Example Programs
Abstract representation (1)
fx=x+3 main = f 5
(⁄ x . (x + 3)) 5
Syntax tree :
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 26 / 25
COMP0020: Functional Programming
Example Programs
Abstract representation (2)
z=3
fxy=x+y
main = f z z
(⁄z .((⁄x .(⁄y .(x + y)))z z ))3
Syntax tree after first beta reduction :
(sharing)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 27 / 25
COMP0020: Functional Programming
Example Programs
Abstract representation (3)
Now consider a recursive function definition :
f x = 3, if (x = 0)
= 1 + f (x ≠1), otherwise
main =f5
(Y (⁄ f . (⁄ x . (if (x = 0) 3 (1 + (f (x ≠ 1)))))) ) 5
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 28 / 25
COMP0020: Functional Programming
Example Programs
(Y (⁄ f . (⁄ x . (if (x=0) 3 (1+(f (x-1)))))) ) 5
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 29 / 25
COMP0020: Functional Programming
Example Programs
Alternative abstract representation
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 30 / 25
COMP0020: Functional Programming
Example Programs
Physical representation
Each node (and leaf) of the graph is held in memory Position in memory is irrelevant
I Just because two nodes occupy adjacent memory locations, that doesn’t mean they are related I Related nodes are connected using pointers (addresses)
Set aside a chunk of memory just to hold these nodes
I The “HEAP”
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 31 / 25
COMP0020: Functional Programming
Example Programs
Physical representation (2)
Each node requires su cient memory to store :
I A tag (@, l, “op”, IND, …)
I A pointer to a left subtree (alternatively, a number representing a built-in operator or a variable) I A pointer to a right subtree (alternatively, a variable or a constant such as a number)
We call each such small chunk of memory a “cell” The heap therefore consists of many cells
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 32 / 25
COMP0020: Functional Programming
Example Programs
Physical representation (3)
The heap :
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 33 / 25
COMP0020: Functional Programming
Example Programs
Performing a beta reduction
Make a COPY of the function body
Substitute the actual parameters for the formal parameters
OVERWRITE the root node of the expression with an indirection to the root node of the copy (preserves sharing)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 34 / 25
COMP0020: Functional Programming
Example Programs
Beta reduction (2)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 35 / 25
COMP0020: Functional Programming
Example Programs
Beta reduction (2)
A “redex” is a reducible expression, i.e. an expression that can be reduced by –, —, ÷ or ”-rule reduction
A program may contain many redexes
Evaluation of a program is a process of successive transformations (reductions) of the graph until the final value is found :
Decide which redex to reduce next Reduce it
Loop to 1.
1 2 3
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 36 / 25
COMP0020: Functional Programming
Example Programs
Redexes
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 37 / 25
COMP0020: Functional Programming
Example Programs
Reduction orders
There will often be many redexes that could be evaluated next
The evaluator must choose an EVALUATION ORDER : this may have a great e ect on the performance of the system (but not on its (partial) correctness)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 38 / 25
COMP0020: Functional Programming
Example Programs
Reduction orders
NORMAL ORDER EVALUATION
I starts at the top node and follows the left pointers until the first redex is found I leftmost outermost
I lazy evaluation.
APPLICATIVE ORDER EVALUATION
I leftmost innermost redex I strict evaluation
PARALLEL EVALUATION
I referential transparency
I redexes can be reduced in any order I may be reduced concurrently !
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 39 / 25
COMP0020: Functional Programming
Example Programs
Summary
Summary
Physical representation of lambda expressions Performing a beta reduction
Reduction orders
Lazy and strict evaluation
Parallel evaluation
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 40 / 25
COMP0020: Functional Programming
Example Programs
Summary
END OF LECTURE
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 41 / 25