* 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? --