Recursion is for suckers

Or, how to implement letrecs in a λ-calculus-based language (such as CoreML, a subset of ML) with ordinary, nonrecursive functions.

This post is probably only going to be of interest if you’re interested in programming languages, or perhaps were someone who once struggled to implement letrecs in a CoreML interpreter in a certain grad-level class at Purdue a year ago. (Hi, Jeff!)

But hey, I can rationalize this post by claiming it’s part of my studying for Tuesday’s Programming Languages midterm. Yeah, that’s it.

Suppose you’re working in a language like CoreML that has three types of expressions when it comes to functions:

  • Fn(id, body): defines an anonymous function with argument id and body body.
  • App(e1, e2): call function e1 with argument e2.
  • Letrec(name, arg, funBody, expBody): defines a recursive function named name with argument arg and body funBody, and evaluate expression expBody in a context where function name is defined.

Although a function defined with Fn can’t refer to itself, it turns out that you can rewrite an arbitrary Letrec using only a series of Fn and App expressions! It may not result in the most efficient implementation of an interpreter for the language, but it does result in a simpler one.

Naturally, we first need to figure out how to get a Fn — or, equivalently, a λ-abstraction — to invoke itself, which is the essense of recursion. An obvious first attempt might be:

(λ x . x x) (λ x . x x)

With this we have infinite self-application. Notice that if you try to reduce the above expression, you end up with exactly what you started with! Adding an actual function call is straightforward:

(λ x . f (x x)) (λ x . f (x x))

Each time you reduce that, you end up with the expression you started with passed in as the argument to function f. That gives us a recursive call sequence, but it’s not very useful, since any attempt to fully evaluate the expression will never terminate. Let’s try this:

(λ y . (λ x . f (x x y)) (λ x . f (x x y)) y)

This expression is what we call a normal form — there’s no reductions that can be done on it. Not until you give the above λ-abstraction an argument, like so:

(λ y . (λ x . f (x x y)) (λ x . f (x x y)) y) y

Now we’re back to the infinite-series-of-recursive-calls we had before. But the addition of the extra y thrown into the mix does buy us something — it gives us a way to prevent the endless series of reductions. Let’s try throwing in a little more abstraction:

Zf = (λ y . (λ x . (f (λ y . x x y))) (λ x . (f (λ y . x x y))) y)

This works quite nicely! Here’s an example. Let’s say f is a functional for the recursive function:

f = λ fact . λ n . if n = 0 then 1 else n * fact(n – 1)

Notice that f takes two arguments: fact (the function to call to perform the recursion) and n (the actual argument to the factorial function). Look what happens when we call Zf with argument 3:

Zf 3

(λ y . (λ x . (f (λ y . x x y))) (λ x . (f (λ y . x x y))) y) 3

(λ x . (f (λ y . x x y))) (λ x . (f (λ y . x x y))) 3

f (λ y . (λ x . (f (λ y . x x y))) (λ x . (f (λ y . x x y))) y) 3

f Zf 3

Hang on! It turns out that for any n and f:

Zf n = f Zf n

And since we defined f so that its first argument is what we use instead of a recursive call, we’d end up calling Zf again with a new argument! Plus, since Zf is by itself a normal form, it doesn’t expand until we give it an argument; and even then, it only expands once until we’re ready to call it again.

Anyway, back to the example:

f Zf 3

(λ n . if n = 0 then 1 else n * Zf(n – 1)) 3

if 3 = 0 then 1 else 3 * Zf(3 – 1)

3 * (Zf 2)

3 * (f Zf 2)

3 * (2 * (Zf 1))

3 * (2 * (f Zf 1))

3 * (2 * (1 * (Zf 0)))

3 * (2 * (1 * (f Zf 0)))

3 * (2 * (1 * 1)))

6

Thus, we can use Zf to convert a functional that represents a recursive function into something that behaves just like a truly recursive function. In CoreML, Fn is equivalent to a λ-abstraction and App is equivalent to a β-reduction. Therefore, we can easily adapt this into a way to convert every Letrec in a CoreML program into a collection of Fn and App expressions, thus eliminating the most complicated type of expression from consideration in the interpreter!

From what Suresh said in class, I don’t think this was quite the approach he had expected us to take on the last project — his implementation this the same sort of one-call-at-a-time expansion, but on the Letrec itself. An equivalent approach, but I like mine better.

5 Responses

  1. You just reminded me why I’m not so keen on going back to finish my PhD. :)

  2. You mean there’s a reason people normally don’t actually write programs in λ-calculus? Besides running away screaming the first time they see Church numerals? :-)

  3. Sweet Jesus.

  4. Just because λ-calculus doesn’t have integrals, doesn’t mean it doesn’t have its own kind of black magic. :-)

  5. I never, in my wildest horrific imagination, thought that calculus, the holiest of secular mathematics, would join forces with religion. Now I’ve got to deal with sin and integrals…

Comments are closed.