G6021 Comparative Programming
Reduction and reduction graphs: functional expressions
A reduction graph simply shows all the different ways that an expression can be reduced. In this work we use three words interchangeably: reduce, simplify, and evaluate. We introduce some more terminology:
• A reducible expression (abbreviated to redex) is an expression that can be simplified. Ex- ample: 3+4 can be simplified to 7, so 3+4 is a redex. It is useful in our work that we underline redexes in expressions. Examples: 3 + 4, 3 + 4 ∗ 5, 1 ∗ 2 + 3 ∗ 4. Note that when wereducearedex,wemaycreateanewone: 3+4∗5→3+20. Wewillalsoseeexamples below where redexes overlap.
• An expression that does not have a redex is said to be in normal form. Example: 3 + 4 is not a normal form, but 7 is a normal form.
• We say that an expression has a normal form if there is a sequence of reductions that leads to a normal form. Example: 3 + 4 has a normal form, because 3 + 4 simplifies to 7 which is a normal form. infinity, defined in the lecture notes, is an example of an expression that does not have a normal form.
Reduce the following expressions to normal form, showing all alternative reductions with a reduction graph.
1. Draw the reduction graph for the expression 3 + 4 ∗ 5. Answer:
3+4∗5E3+20 E23
So this graph is just a sequence of edges with no branching.
2. Draw the reduction graph for (3 + 4) ∗ (3 + 4). Answer:
(3+4)∗(3+4) E 7∗(3+4) cc
(3 + 4) ∗ 7 E 7 ∗ 7 E 49
Complete this answer by underlining all redexes. Note that the number of reduc- tions possible for each expression is the same as the number of redexes in that expression.
3. Consider the following program written in Haskell syntax:
sq x = x*x
twice f x = f(f(x))
1
(a) Draw the reduction graph for sq (3+4)
Answer: There are two redexes in the initial expression. Can you underline
the remaining redexes in this graph? sq(3 + 4)
c
(3+4)∗(3+4) E 7∗(3+4)
cc (3 + 4) ∗ 7 E 7 ∗ 7
E sq 7
E 49
(b) Draw the reduction graph for twice sq 3
Answer: Try to complete this one I have started:
twice sq 3 c
sq(sq3)
sq(3) ∗ sq(3)
sq(3 ∗ 3)
2
‘
E
‘