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.
(((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!