|
Assignment 5 discusses simplifications of trees. This page shows a few more examples.
Once a tree has been built by the compiler, all identifiers refer to globally defined identifiers. To simplify an identifier, just look up its value in the symbol table.
Here is a very simple example. When program
def frog = 50 end def toad = frog + 1 end def main = toad end
is compiled, three entries are made in the symbol table, which looks like this.
--key-- -------value-------
"frog" NUM(50)
"toad" OP(PLUS)
/ \
ID("frog") NUM(1)
"main" ID("toad")
The interpreter creates tree ID("main") and simplifies it. Here are the simplification steps. Trees are shown in abbreviated form for clarity and simplicity.
main ⇒ toad
⇒ +
/ \
frog 1
⇒ +
/ \
50 1
⇒ 51
In reality, showing a simplification in steps like this is a little misleading. Not all of the trees that are shown are actually constructed.
To simplify an identifer node, you fetch the value of that identifier from the symbol table, then simplify the tree that you get. So the first two steps above,
main ⇒ toad
⇒ +
/ \
frog 1
are a reasonable start.
To simplify a + node, you simplify each subtree, then add the two answers. So two recursive calls to the simplifier are as follows.
frog ⇒ 50 1 ⇒ 1(Note that the simplifier needs to be prepared to simplify a number by returning the same number.)
Now the call to simplify that is working on tree
+
/ \
frog 1
gets the two results, 50 and 1. It adds, gets 51,
and returns 51 as a tree.
The rule for simplifying an APPLY node is as follows. This is called the β-reduction rule (because that is what it is called in a branch of mathematics called λ-calculus). To simplify
APPLY
/ \
A B
first compute the simplified values A' of A
and B' of B. Check that the root of
A' is a FUN node. Showing the whole tree again,
we have
APPLY
/ \
FUN B'
|
X
Build a copy X' of X where each active PARAM
node is replaced by B'. (A PARAM node in
X is active if it points to the FUN node shown.)
The result of simplification is tree X'.
Now let's do an example involving a function.
def g x y = x * y end def main = g 4 7 end
First, entries for "g" and "main" are made in the symbol table.
--key-- ---------value---------
"g" FUN(1)
|
FUN(2)
|
*
/ \
PARAM PARAM
(1) (2)
"main" APPLY
/ \
APPLY 7
/ \
g 4
Simplification goes as follows. Simplifications of subtrees (actually done by recursive calls to the simplifier) are shown by redrawing the whole tree. The root of the subtree that is about to be simplified is shown in red. Simplificatons of numbers are skipped.
main
⇒
APPLY
/ \
APPLY 7
/ \
g 4
⇒
APPLY
/ \
APPLY 7
/ \
FUN(1) 4
|
FUN(2)
|
*
/ \
PARAM PARAM
(1) (2)
⇒
APPLY
/ \
FUN(3) 7
|
*
/ \
4 PARAM
(3)
⇒
*
/ \
4 7
⇒ 28
Look at the first APPLY step that is simplified. One of the PARAM has been replaced by 4, and a new FUN node has been created. It is crucial that the new tree is created without altering the previous tree, which is is exactly the tree that is stored in the symbol table for "g". If you change that tree, you change the value of g.
Finally, let's do the following program.
def main =
cat b a
end
def a = [2, 4, 6] end
def b = [8, 10] end
def cat x y =
case
isNull x => y
| else => head x : cat (tail x) y
end
end
The symbol table looks as follows.
--key-- -------value-------
"main" APPLY
/ \
APPLY a
/ \
cat b
"a" :
/ \
2 :
/ \
4 :
/ \
6 []
"b" :
/ \
8 :
/ \
10 []
"cat" FUN(1)
|
FUN(2)
|
----IF-----
/ | \
isNull PARAM :
| (2) / \
PARAM / \
(1) head APPLY
| / \
PARAM APPLY PARAM
(1) / \ (2)
cat tail
|
PARAM
(1)
Here are the steps of simplification.
main
⇒
APPLY
/ \
APPLY a
/ \
cat b
⇒
APPLY
/ \
APPLY a
/ \
FUN(1) b
|
FUN(2)
|
-----IF-----
/ | \
isNull PARAM :
| (2) / \
PARAM / \
(1) head APPLY
| / \
PARAM APPLY PARAM
(1) / \ (2)
cat tail
|
PARAM
(1)
⇒
APPLY
/ \
FUN(3) a
|
-----IF-----
/ | \
isNull PARAM :
| (3) / \
b / \
head APPLY
| / \
b APPLY PARAM
/ \ (3)
cat tail
|
b
⇒
-----IF----
/ | \
isNull a :
| / \
b / \
head APPLY
| / \
b APPLY a
/ \
cat tail
|
b
⇒
-----IF----
/ | \
isNull a :
| / \
: / \
/ \ head APPLY
8 : | / \
/ \ b APPLY a
10 [] / \
cat tail
|
b
⇒
-----IF----
/ | \
false a :
/ \
/ \
head APPLY
| / \
b APPLY a
/ \
cat tail
|
b
⇒
:
/ \
/ \
head APPLY
| / \
b APPLY a
/ \
cat tail
|
b
⇒
----:---
/ \
head APPLY
| / \
: APPLY a
/ \ / \
8 : cat tail
/ \ |
10 [] b
⇒
----:----
/ \
head APPLY
| / \
: APPLY a
/ \ / \
8 CONS cat tail
/ \ |
10 [] b
⇒
----:----
/ \
head APPLY
| / \
CONS APPLY a
/ \ / \
8 CONS cat tail
/ \ |
10 [] b
⇒
---:---
/ \
8 APPLY
/ \
APPLY a
/ \
cat tail
|
b
At this point, cat is replace by its value and tail(b) is simplified. To reduce space, here is the result of both simplifications.
⇒
---:------
/ \
8 ---APPLY---
/ \
---APPLY--- a
/ \
FUN(1) :
| / \
FUN(2) 10 []
|
-----IF-----
/ | \
isNull PARAM :
| (2) / \
PARAM / \
(1) head APPLY
| / \
PARAM APPLY PARAM
(1) / \ (2)
cat tail
|
PARAM
(1)
⇒
---:---
/ \
8 APPLY
/ \
FUN(4) a
|
-----IF-----
/ | \
isNull PARAM ---:---
| (4) / \
: / \
/ \ head APPLY
10 [] | / \
: APPLY PARAM
/ \ / \ (4)
10 [] cat tail
|
:
/ \
10 []
⇒
---:---
/ \
8 -----IF-------
/ | \
isNull a ---:---
| / \
: / \
/ \ head APPLY
10 [] | / \
: APPLY a
/ \ / \
10 [] cat tail
|
:
/ \
10 []
⇒
---:---
/ \
8 -----IF-------
/ | \
false a ---:---
/ \
/ \
head APPLY
| / \
: APPLY a
/ \ / \
10 [] cat tail
|
:
/ \
10 []
To reduce space, I will replace head(10:[]) by 10 and tail(10:[]) by [].
⇒
---:---
/ \
8 ---:---
/ \
10 APPLY
/ \
APPLY a
/ \
cat []
Simplification again replaces cat with its value from the symbol table and simplifies two APPLY nodes, yielding
⇒
---:---
/ \
8 ---:---
/ \
10 --IF--
/ | \
isNull a :
| / \
[] / \
head APPLY
| / \
[] APPLY a
/ \
cat tail
|
[]
Replacing isNull([]) by true and simplifying the IF node yields
⇒
:
/ \
8 :
/ \
10 a
⇒
:
/ \
8 :
/ \
10 :
/ \
2 :
/ \
4 :
/ \
6 []
Further simplification will replace all of the : nodes by CONS nodes.
|