# Y Combinator in Emacs Lisp

I talked today with Prabhakar Ragde, who is a resident at the Recurse Center until Oct15, and I was enlightened by lambda calculus as we figured out how to deduce the Y Combinator that is used a lot to make recursive functions.

Here I plan to post the implementation and derivation of the Y Combinator in Emacs Lisp.

:DISCLAIMER_BEGIN:

You will need to have lexical binding enabled for most of the examples to work, it is a buffer-local variable so make sure you paste everything on the same buffer.

(setq lexical-binding t)

:DISCLAIMER_END:

We'll take `factorial`

as it's good example of a recursive function

(defun factorial (number) (if (eq number 0) 1 (* number (funcall #'factorial (1- number))))) (factorial 5) ;; 120 (factorial 4) ;; 24

The recursion looks trivial right? Now lets try to implement it without referencing the name of the function, should be easy as well.

;; factorial (lambda (number) (if (eq number 0) 1 (* number (funcall fact? (1- number)))))

We find that we cannot reference back to the same lambda function as we don't
have a name for it, that's why we use **fact?** we'll have to figure out what to
put in there. Lets say that we have another function that **looks** like `factorial`

.

;; proto-factorial (lambda (fun) (lambda (number) (if (eq number 0) 1 (* number (funcall fun (1- number))))))

This is great! now we have a function that can take another function and that
returns a function that looks like `factorial`

. There is one little detail
though, the function that `proto-factorial`

accepts only takes a number, so we
could say that.

(let ((proto-factorial (lambda (fun) (lambda (number) (if (eq number 0) 1 (* number (funcall fun (1- number)))))))) (eq (funcall 'factorial 4) (funcall (funcall proto-factorial 'factorial) 4)))

This holds true but it's not what we want. We show that applying
`proto-factorial`

to `factorial`

gives us back `factorial`

which is cool, but we
need to not use `factorial`

at all, let's see if using `proto-factorial`

on itself
might work

(let ((proto-factorial (lambda (fun) (lambda (number) (if (eq number 0) 1 (* number (funcall fun (1- number)))))))) (funcall (funcall proto-factorial proto-factorial) 4))

It didn't T_T. What this tells us is that we have not provided enough arguments,
and that's true, because proto-factorial, the function we send, takes a function
and and returns a function that takes number, and the outer `funcall`

just takes
another number but no function. this is tricky, but we can have a way of doing
it, let's call the function on itself as an argument before passing another
number!

;; meta-factorial (lambda (fun) (lambda (number) (if (eq number 0) 1 (* number (funcall (funcall fun fun) (1- number))))))

This looks more promising! meta-factorial takes a function and returns a
function that depends on a number, but in this inner number-dependent function
instead of applying `fun`

to `(1- number)`

we apply the function to itself, and
then apply that result to `(1- number)`

, this way we got what we wanted, a
recursive function!. But still looks ugly, lets arrange it in a better way

(let ((meta-factorial (lambda (fun) (lambda (number) (if (eq number 0) 1 (* number (funcall (funcall fun fun) (1- number)))))))) (eq (funcall 'factorial 4) (funcall (funcall meta-factorial meta-factorial) 4)))

You might be thinking: "Wait what? did we just did a recursion by calling two
lambdas?" yes we did, it might not look like so here, but if you replace each
`meta-fact`

with the lambda definition, we eliminate references to functions and
are only left with lambda functions but the recursion still works! and we
haven't used a reference to a function from within itself. If you don't believe
me, then this is the ugly version:

(funcall (funcall #'(lambda (fun) (lambda (number) (if (eq number 0) 1 (* number (funcall (funcall fun fun) (1- number)))))) #'(lambda (fun) (lambda (number) (if (eq number 0) 1 (* number (funcall (funcall fun fun) (1- number)))))) ) 4)

This still returns what we wanted which is `4!`

. So what we have now is that
`meta-factorial`

evaluated on itself returns a function that takes a number and
that function is equivalent to `factorial`

.

We want a way to transform from proto-factorial function to `factorial`

because in
that way we can get recursion, out of a simpler function the only things that we
did was to take out the function call and call it on itself.

Let's see if we can define one such a function that takes as a parameter the proto-factorial and will output the meta-factorial version because in that case we would only need to apply that function twice and we would get our so desired factorial.

;; meta-factorial (lambda (fun) (funcall #'(lambda (fun2) (lambda (number) (if (eq number 0) 1 (* number (funcall fun2 (1- number)))))) (funcall fun fun)))

What we just did was to wrap the inner number-dependent function so that the
`(funcall fun fun)`

could be abstracted. This is called composing functions,
kinda like `g(x^2)`

could be written as `g(f(x))`

where `f(x) = x^2`

and we find
that this inner thing is actually, `proto-factorial`

!! This is great!, now we
can write meta `factorial`

in terms of proto `factorial`

. We just needed to wrap the
fun2 into a call to itself.

(let ((meta-factorial (lambda (fun) (lambda (number) (if (eq number 0) 1 (* number (funcall (funcall fun fun) (1- number))))))) (proto-factorial (lambda (fun) (lambda (number) (if (eq number 0) 1 (* number (funcall fun (1- number)))))))) (eq (funcall 'factorial 4) (funcall (funcall #'(lambda (r) (funcall proto-factorial (funcall r r))) #'(lambda (r) (funcall proto-factorial (funcall r r)))) 4)))

This is basically what we've been going for so much, if we could only make one
more abstraction so that in case of proto-factorial we could pass any function
wouldn't it be nice? well it **is** possible and it has a name! it's called the Y
combinator, and it looks like this:

(defun YCombinator (fun) (funcall #'(lambda (r) (funcall fun (funcall r r))) #'(lambda (r) (funcall fun (funcall r r)))))

Lets try it with our `factorial`

function!

(funcall (YCombinator #'(lambda (f) #'(lambda (n) (if (eq n 0) 1 (* n (funcall f (1- n)) ))))) 5)

This should work, but it just goes into an infinite recursive loop, :(.

Fortunately enough, I had been warned about this type of behavior due to the non-laziness from elisp, its eagerness it's not letting the code keep on going without evaluating stuff that shouldn't be evaluated yet, this doesn't happen in other languages such as haskell, but in emacs lisp the YCombinator should look a little bit different, like this:

(defun YCombinator (f) (funcall #'(lambda (x) (funcall f #'(lambda (y) (funcall (funcall x x) y)))) #'(lambda (x) (funcall f #'(lambda (y) (funcall (funcall x x) y))))))

There! now we have a working YCombinator that doesn't go into an infinite loop :) lets try it

(funcall (YCombinator #'(lambda (f) #'(lambda (n) (if (eq n 0) 1 (* n (funcall f (1- n))))))) 8)

There we go! :) this is the kind of stuff one learns in the Recurse Center. I
hope you liked it, I've seen implementations done in javascript and even python,
but not one in Emacs Lisp for the `factorial`

function. There was one that got it
right for the Fibonacci sequence but when I tried it on the `factorial`

it went
into the infinite loop,