For more information, see also this enlightening post on recursion
It’s fucking weird. It’s also the crucial property of a language that makes it Turing-complete (that is, powerful enough to compute anything which can be computed). An equivalent property is to be able to write looping procedures which last an arbitrary number of iterations.
It’s often baked into a language and while it works it makes no sense intuitively.
So, we are going to pretend the Scheme language doesn’t have recursion, and create it ourselves. Our goal will be to write a factorial function which works while not referring to itself.
For reference, here is the procedure we are trying to emulate This will blow up the stack and fail miserably on even moderately large numbers. It is purely for pedagogical purposes.
1 Let’s go
Without recursion, we have the following hole in our logic:
Since we can’t call
fact (as it hasn’t been defined yet), what can we do?
What if - and please bear with me - somehow we were able to give
fact the next function it should call? Like this:
fact is a function which returns another anonymous function with an argument
call-me-next, which otherwise wraps our original function. Well, what if you were able to do something like this:
That is to say, what if you could get that anonymous function from
fact and then apply it to itself?
2 The universe is a snake beating itself
We want to automate the process of applying a function to itself, returning the composition of the two functions and saving the galaxy from the bug invaders.
Things we know:
This recursion-maker-function-thing will accept one argument, the function to be fucked with.
It will return the application of a function to itself.
Let’s sketch something:
When I run this, it tells me I’m a huge loser who will never find true love. But why?
fact-sort-of are functions which accept other functions as arguments. They return … functions which accept other functions as arguments. Passing in
5 just isn’t going to cut it.
3 Time is a cat circle
Let’s back up and think much more simply.
fact-sort-of returns a function which accepts a function, and we know that the one it accepts is going to be itself. Make your goddamn Inception jokes now, if you must.
Our goal is to write a factorial function that receives itself as an argument instead of referring to its own name.
We know that since this argument is itself, and it needs to be fed itself to work, that this argument is going to have to be fed to itself.
Thus, we define the correct function, and then we define it again as an argument to the first one.
HOLY JUMPING JEHOSEPHAT it worked. It worked! IT WORKED.
… why, again?
Imagine that the
lambda calls were replaced with
foo. Then the thing looks like this:
Okay, so this worked. But as wise men once said,
Our work is never over
4 I hate you so fucking much Gatlin
So how do we write a general function-fucker that works for any (single-argument) function? Let’s abstract our general technique:
target is a function which wishes to receive itself so that it can begin autophagia. The two
lambda expressions are going to be identical, though, so figuring out one means figuring out the other.
lambdas are also functions which expect to be given themselves as their next move, with the understanding that the first will receive the second as an argument OH MY GOD I’M CROSS EYED
The whole fucking point of this is to turn the
target into a recursive function, so we may as well cut the foreplay and call it:
So far, so good. Resisting the tempation to replace the ellipses with
target and be mocked again by the cruel lifetime of loneliness ahead, what should we give it?
It wants to receive a function it can call when it’s ready to call itself. The itself part expects to receive the actual function argument and do something with it. Let’s add this:
And what should that inner function do with its argument? Why, it should use
f, the roundabout reference back to
target, to –
HOLD IT RIGHT THERE DON’T YOU FUCKING DARE GIVE
f is a function expecting another function. It will not accept a number. FUCK WHEN DOES THIS END
wait wait wait didn’t we tie the knot earlier, so-to-speak, by passing
call-me-maybe to itself?
120, as expected. Let’s walk through what happens when we fuck the function:
(function-fucker fact-sort-of) ; => ((lambda (target) ((lambda (f) (target (lambda (arg) ((f f) arg)))) (lambda (f) (target (lambda (arg) ((f f) arg)))))) fact-sort-of) ; => ((lambda (f) (fact-sort-of (lambda (arg) ((f f) arg)))) (lambda (f) (fact-sort-of (lambda (arg) ((f f) arg))))) ; => (fact-sort-of (lambda (arg) ((lambda (f) (fact-sort-of (lambda (arg) ((f f) arg)))) (lambda (f) (fact-sort-of (lambda (arg) ((f f) arg))))))) ; => (lambda (n) (if (zero? n) 1 (* n ((lambda (arg) ((lambda (f) (fact-sort-of (lambda (arg) ((f f) arg)))) (lambda (f) (fact-sort-of (lambda (arg) ((f f) arg)))))) (- n 1))))) ; => ...
And that’s what the body of
function-fucker has an actual name. A fellow named Haskell Curry drummed it up, and it’s called the Y combinator (“combinator” is a fancy word for “function with one argument you ignorant pigfucker”).
Its name derives from the two identical lambda functions. Cute, huh?
xoxo Gatlin email@example.com