# Y Combinator

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!