Hocus-pocus, we have recursion!

I was recently reading Reg Braithwaite's post "But Y whould I want to do a thing like this?" when from some sense of foreshadowing I decided on first few paragraphs to answer the question "How do you curry a y-combinator?"

Naturally, I chose scheme instead of ruby (I find scheme is the easiest language for dealing with complex lambda thinking, for obvious reasons).

My very first stab at the problem looked like this.

(lambda (y)
  (lambda (x) 
    (if (eq? x 0) 5 
        (y (- x 1)))))

This is obviously wrong, though it seemed right enough that I typed it out. One might gain some insight from the way I initially thought about this problem.

"The inner function won't be visible to the global environment, so there would be no way for someone to reference it while calling. To solve this I can reverse the order of the parameters and pass the function to the outer lambda. This should make things work."

Now, naturally, if you're familiar with scheme this function obviously won't work after thinking it through. Say we called it define-five (you'll note this toy example always returns 5 for positive integers), we might call like ((define-five define-five) 1) which sets y to be define-five. Now when the recursion is attempted it will call (define-five (- 1 1)). Of course, this will return a function... because the return value of define-five is a lambda expression!

Obviously, I must have been wrong about my parameter ordering, so I'd try currying it the other way, giving it a quick attempt I started with.

(lambda (x)
  (lambda (y) 
    (if (eq? x 0) 5 
        (y (- x 1)))))

Tracing through this, we find out it won't work at all. The return value of define-five is now a y-combinator with a fixed x value. I decided this might be a little harder problem than I anticipated at this point and sat down for a few minutes to think it through. After some thought, I decided to investigate using let. A few false starts later I realized let isn't needed, but it does simplify the code a lot. Here is the shortest version of the curried y-combinator factorial function I've written.

(define fact-generator
  (lambda (y)
    (lambda (cur)
      (if (eq? cur 0) 1
          (* cur ((y y) (- cur 1)))))))

This is the first working example on this page. You'll note that in the process of making it work I switched it to a realistically testable example (the standard factorial). I will use the let-ified version below for explanation because it is much easier to read.

(define fact-generator
  (lambda (y)
    (lambda (cur) 
      (if (eq? cur 0) 1
          (let ((rec-fun (y y)))
            (* cur (rec-fun (- cur 1))))))))

This is pretty exciting. Before I go too much further, lets show what it looks like to call fact-generator.

> (fact-generator fact-generator)
#<procedure>
> ((fact-generator fact-generator) 5)
120

To walk through this function is fairly informative. We note the y combinator is passed to the outer lambda, which we deal with later. The inner lambda starts out like all recursive factorial functions, if cur is zero return one. Then we have the clever bit that took some effort to arrive at. Since we are passed a function that generates recursive functions when passed itself, we go ahead and call it on itself and it returns a recursive function! Note that since y is fact-generator, rec-fun is being set to (fact-generator fact-generator) which of course is the inner lambda with an appropriately bound y! Of course we finish by multiplying cur with the result of the recursive call one smaller.

I then went back to reading the linked post, in which he starts talking about y-combinator generators. At first I thought we were talking about the same thing (mind you, my ruby is shaky so I had trouble reading some of his code), but over time I grew more concerned that I had solved the same problem as him. I went back over to DrScheme to see if I could code a function that takes a y-combinator-generator and generates a "recursive" function. For some reason, after reading his ruby I didn't see the result right away... I'd already written that function.

(define gen-recurse
  (lambda (fun-generator)
    (fun-generator fun-generator)))

> ((gen-recurse fact-generator) 5)
120

Of course putting it all together in glorious scheme goodness gives us the following

(define rec-fact
  (let ((rec-generator 
    (lambda (y)
      (lambda (cur) 
        (if (eq? cur 0) 1
            (let ((rec-fun (y y)))
              (* cur (rec-fun (- cur 1)))))))))
    (rec-generator rec-generator)))

> (rec-fact 5)
120

And we have transparently created recursion from nothing, such that people calling rec-fact have no idea it's even defined recursively. Score one for lambda.

Sean