* Is Recursion necessary?
** Mutual Recursion: Last Time
let x0 = e0
x1 = e2
x2 = e3
in
def f(y0):
e_f
and
def g(z0,z1):
e_g
in
e_bod
becomes
def f(env, y0):
let x0 = env[0],
x1 = env[1],
x2 = env[2],
f = mk_closure(1, f, env),
g = mk_closure(2, g, env),
in
e_f
and
...
in
let x0 = ...
...
let env = [x0, x1, x2] in
f = mk_closure(1, f, env),
g = mk_closure(2, g, env),
...
e_bod
But notice that this is a low-level transformation, we use mk_closure
to do it. Do we need it at all?
** Landin's Knot
Consider a recursive function
def fact(x):
if x == 0:
1
else:
x * fact(x - 1)
in
fact(5)
Say we hadn't implemented recursive functions, only lambda
functions. Could you write fact still?
Yes.
There is a trick called "Landin's Knot" after Peter Landin, who
discovered it.
let fact' = [ false ],
fact = lambda x:
if x == 0:
1
else:
x * fact'[0](x - 1)
end
in
fact'[0] := fact;
fact(5)
What's going on here? We have created a loop in the heap:
fact is a closure whose environment is just fact'. Initially this is
| 1 | lambda_code | ptr to [ false ] |
but after the mutation becomes
fact -> | 1 | lambda_code | ptr to [ fact ] |
So we are simulating the "circularity" of a recursive function using a
cycle in the heap.
-- In class Exercise --
More generally, you can implement mutual recursion this way as well:
How would you translate:
def even(x):
if x == 0:
true
else:
not(odd(x - 1))
and
def odd(x):
if x == 0:
false
else:
not(even(x - 1))
in
even(10)
let even_odd = [false, false] in
let even = lambda x:
let odd = even_odd[1],
if x == 0: true
else: not(odd(x - 1))
let odd = ...
in
even_odd[0] := even;
even_odd[1] := odd;
even(10)
general pattern
def f(x): e_f and
def g(y): e_g and ...
e'
could turn into
let funs = [ false , false , ... ] in
let f = lambda x: let f = e[0], g = e[1], ... in e_f end,
g = lambda y: let f = e[0], g = e[1], ... in e_g end
in
funs[0] := f;
funs[1] := g;
...
e'
-- How is the performance of this ? --
** Y
We can in fact do it without recursion,
in some ways the simplest way to do it.
Transform
def fact(x):
if x == 0:
1
else:
x * fact(x - 1)
in
fact(5)
into
let Y = ???
let fact = Y(lambda fact: lambda x:
if x == 0:
1
else:
x * fact(x - 1)
end)
in
fact(5)
where Y is a function we can implement inside our language!
Y = lambda f:
let w = (lambda x: f(lambda v: x(x)(v) end) end)
in w(w)
end
How does this work?
let Y = lambda f: let w = (lambda x: f(lambda v: x(x)(v) end) end) in w(w) end,
fact = Y(lambda fact: lambda x:
if x == 0:
1
else:
x * fact(x - 1)
end end)
in
fact(10)
-- How is the performance of this operation? --