-
Notifications
You must be signed in to change notification settings - Fork 0
/
Lambda_lifting.txt
178 lines (123 loc) · 3.22 KB
/
Lambda_lifting.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
f x = let dingo z = z + x
in
let
bingo w = dingo (47 - w)
in
g (bingo 419)
g u = let mango x = x + h u
in
let
dingo k = k
in
mango (dingo u)
h w = 42
-----------------------------------------------------
f 14 = {47 - 419 + 14 + 42} = -358 (this i u in the function g)
f 14 = -316
-----------------------------------------------------
LAMBDA LIFTING: step 1) Rename every function so it has a unique name
f x = let dingo1 z = z + x
in
let
bingo w = dingo1 (47 - w)
in
g (bingo 419)
g u = let mango x = x + h u
in
let
dingo2 k = k
in
mango (dingo2 u)
h w = 42
-----------------------------------------------------
LAMBDA LIFTING: step 2) For every functioin f, replace every free variable
in the definition of f with an additional argument of f. Pass that argument
as an additional argument to every call of f.
- STARTING WITH: dingo1
f x = let dingo1 z dingo_x = z + dingo_x
in
let
bingo w = dingo1 (47 - w) dingo_x
in
g (bingo 419)
g u = let mango x = x + h u
in
let
dingo2 k = k
in
mango (dingo2 u)
h w = 42
- REPLACING FOR: bingo
f x = let dingo1 z dingo_x = z + dingo_x
in
let
bingo w bingo_dingo_x = dingo1 (47 - w) bingo_dingo_x
in
g (bingo 419 x)
g u = let mango x = x + h u
in
let
dingo2 k = k
in
mango (dingo2 u)
h w = 42
- REPLACING FOR: mango
f x = let dingo1 z dingo_x = z + dingo_x
in
let
bingo w bingo_dingo_x = dingo1 (47 - w) bingo_dingo_x
in
g (bingo 419 x)
g u = let mango x mango_u = x + h mango_u
in
let
dingo2 k = k
in
mango (dingo2 u) u
h w = 42
LAMBDA LIFTING: step 3) Replace every local function definition with
no free variables with a global function that has the same definition.
f x = let dingo1 z dingo_x = z + dingo_x
in
let
bingo w bingo_dingo_x = dingo1 (47 - w) bingo_dingo_x
in
g (bingo 419 x)
g u = let mango x mango_u = x + h mango_u
in
let
dingo2 k = k
in
mango (dingo2 u) u
h w = 42
REPLACING dingo1 to dingo1'
f' x = let
bingo w bingo_dingo_x = dingo1' (47 - w) bingo_dingo_x
in
g (bingo 419 x)
dingo1' z dingo_x = z + dingo_x
REPLACING bingo to bingo'
f' x = g (bingo' 419 x)
dingo1' z dingo_x = z + dingo_x
bingo' w bingo_dingo_x = dingo1' (47 - w) bingo_dingo_x
REPLACING mango to mango'
g' u = let
dingo2 k = k
in
mango' (dingo2 u) u
h w = 42
mango' x mango_u = x + h mango_u
REPLACING dingo2 to dingo2'
g' u = mango' (dingo2' u) u
h w = 42
mango' x mango_u = x + h mango_u
dingo2' k = k
"nothing" will happen to h since h is already a global function.
FINAL PROGRAM AFTER LAMBDA LIFTING.
f' x = g (bingo' 419 x)
dingo1' z dingo_x = z + dingo_x
bingo' w bingo_dingo_x = dingo1' (47 - w) bingo_dingo_x
g' u = mango' (dingo2' u) u
h w = 42
mango' x mango_u = x + h mango_u
dingo2' k = k