I'm happy that I finally got lambdas into a Scheme interpreter that I've been working on at Hackerschool. This means that I have a fully fledged programming language that can compute anything that any other programming language can. I was so excited that I immediately wanted to write a simple factorial function when I realized that I still didn't have a routine that defined names for values. This is a problem if you want to write a recursive function like this:

    (define (factorial n)
        (if (= n 0)
            1
            (* n (factorial (- n 1)))))

You can't name things (yet), even if all you want to do with a name is use it to do a recursive call.

Scott Feeney at Hackerschool reminded me that there's a function called the y combinator that allows you to do exactly this. So I read this terrific article and wrote this:

    (((lambda (f)
            ((lambda (x) (f (x x)))
                (lambda (x) (f (lambda (y) ((x x) y))))))
        (lambda (me)
                (lambda (n)
                        (if (= n 0)
                        1
                        (* n (me (- n 1)))
                        ))))
        10)     ;; computes factorial of 10

Note: no names! It is a y combinator applied to a half baked factorial function:

    (lambda (me)
        (lambda (n)
            (if (= n 0)
            1
            (* n (me (- n 1))))))

Note the parameter name me. The y combinator is going to take this function and apply it to itself. This is where the recursion takes place.

I could go through an explanation of the y combinator, but I'll just point you to the terrific article already mentioned. It's terrific.

What a thrill to see this work in a repl that I threw together myself for my own (partial) Scheme implementation. The work in progress is in a repo here. Happy Thursday!