“You’re very clever, young man, very clever,” said the old lady. “But it’s turtles all the way down!”
Recursion is among the simplest and most beautiful concepts in computer science. In the simplest sense, a recursive structure refers to itself. We most frequently think about recursion in functions like factorial where the function calls itself. Among the most beautiful things about recursion is it can be added with almost no language extensions. For example, factorial looks something like this:
We can write recursive functions with no extension to our language with virtually no extensions. Now we have an iteration capability similar to what is provided by Haskell and Lisp and available in virtually every modern language.
Let’s evaluate this new structure using our most receive statically scoped interpreter for
FBAE with types:
fact is defined, so why did we get an error message? Is
interp badly implemented? As it turns out, no. The problem is the definition of
Now let’s take a step backwards and evaluate
fact with our dynamically scoped interpreter for
Works fine! Why? Obviously something different in the way static and dynamic scoping handle definitions. Let’s look at dynamic scoping and why
eval works and then try to fix (no pun intended) the statically scoped
eval to include recursion.
To understand why recursion works with no extensions using dynamic scoping we need only look at what makes dynamic scoping dynamic. Remember, a dynamically scoped interpreter tries to evaluate a variable in the scope where it is used. Let’s look at
fact again annotated with definitions in scope:
Execution begins with nothing in scope when
bind begins evaluation. As the
lambda begins, it’s parameter is added to scope. Thus, the body of the
lambda can use
x. When the
x leaves scope, but as the
bind’s declaration closes
fact is added. When
fact 3 evaluates,
fact is define.
The call to
fact originally occurs within the scope of the
bind defining it. More importantly, the recursive call to factorial occurs in the same scope. There are two calls to
fact - one in
bind’s body and another within
fact itself. When
fact is called intially, it has clearly been defined. When it is called recursively, it is in the scope of the original call - where it is evaluated. Thus, the recursive call works just fine.
To understand why recursion fails using static scoping, we need to look carefully at scoping again:
This time we need to remember that the
lambda looks for identifiers in the scope where it is defined rather than where it executes. Looking at
lambda, the only variable in scope in its body is
x. It doesn’t yet have a value, but it is in scope when it is called on an actual parameter. In the body of
fact is applied to
3 its definition is in scope. Why then do we get an error saying
fact is not in scope?
We get a hint if we do the same evaluation, but this time using
0 as the argument to
When called on
fact in fact works.
fact 1 == 0. What about
fact 1? If you try this,
fact crashes with the same error that
fact is not found. What gives? It clearly was found once. Why not the second time?
The key is understanding
fact is evaluated in two places. The first time in the body of
bind where it is defined. The second time,
fact is evaluated in the body of
fact where it is not defined. The only identifier in scope is
x. A way to understand this is that
fact does not know about itself because it is in scope only in the body of
The first solution for recursion in a statically typed language we will explore is writing fixed-point combinators that implement recursion. These combinators come from the lambda calculus developed by Alonzo Church that along with Turing Machines are the two foundational models of algorithms and computing. The term combinator simply means a closed expression - one with no free variables. A fixed-point is a recursive structure used to construct sets. A fixed-point combinator is some $y$ such that:
for any function, $f$. For this study, you need not know any of these details, but if you are serious about the study of languages learning more about all of them is most definitely in your future!
We will look at three recursive constructs. The $\Omega$ is a trivial infinitely recursive structure. We’ll not be able to use it for much, but it defines a starting point for the
Y is a lazy fixed-point and
Z is an extension of
Y for strict languages. We’ll look carefully at
Y and take what we learn there to
Take a look at the following function application:
What will any of our evaluators this far do with this? Let’s see:
Interesting. It would seem that this particular expression evaluates to itself. It doesn’t stop there. This is an
app, not a value, so it will in turn be evaluated and again evaluate to itself. Which will evaluate to itself again and again and again. It does not terminate. Thus far, we’ve not even seen iteration or recursion and suddenly we have an expression that does not terminate when evaluated.
This structure is called the $\Omega$ combinator or simply $\Omega$ and is interesting precisely because when evaluated it does not terminate. It is the basis for recursion in an untyped language, but obviously not quite the function we want If you pop $\Omega$ into any of our
FBAE interpreters you’ll see this nontermination in action.
Let’s dissect $\Omega$ just a bit more and try to understand what it does. At its heart it’s a simple
lambda that applies its argument to itself:
x serves as both a function and its argument. We like to think of
app as simple function application and in one sense that’s what it is. In another sence,
app can define computational patterns. In this case a simple pattern that applies a function to itself that gives us recursion.
Hmmm. Every recursive function you’ve ever written makes a call to itself. Like this:
fact. In the $\Omega$ case no such call occurs. Or does it? Interestingly neither instance of
lambda has a name, but they are identical. The first
lambda gives the second
lambda a name when it is instantiated. Think about it. When the
app is evaluated, its argument gets the name
x and that
x becomes the same as the function it appears in. Do you see the recursion?
Passing a copy of
lambda x in (app x x) to itself and using that copy as a function gives us recursion.
(app x x) becomes $\Omega$ in side $\Omega$. What a beautiful construction!
If we evaluate this expression:
it terminates immediately because the second
lambda simply returns its argument. For $\Omega$ to work, the argument
lambda must be identical to the function
Now we have $\Omega$ and it’s groovy and we can’t use it for a darn thing other than locking up our evaluator. Time to move on.
Omega showed us how
lambda can create patterns. Let’s look at another one that is a touch more useful than omega:
This expression that we’ve named
Y looks a bit like omega, but with a twist. The first argument to
f which appears in the body in the function position of an
f would be some function that we will input to
Y. Let’s assume that we have such an
f we’ll call
F and apply
Y to it and see what we get:
Now it looks even more like $\Omega$. Lets evaluate the expression a few more times and see what we get:
It seems that each time we evaluate
(app Y F), we get a new copy of
F out in front of the expression. Whatever
F might be it gets called over and over again with something akin to $\Omega$ as one of its arguments. Regardless,
F will be called over and over again.
Having established that, let’s think about
F in two ways. First, can we program a kind of off switch in
F that turns off when we’ve evaluated
F enough times? Second, can we grab input data with
F? In addition to not terminating, $\Omega$ could not accept any input. Let’s think about the off switch first. If we can’t turn
Y off then it will be just as groovy as $\Omega$ and just as useless.
Whatever else is true about
F, its first argument is the
Y applied to
F. Evaluating that is what causes
F to be called recursively. If we want to turn
(app Y F) off then we can’t make that recursive call. Thankfully we have an
if that allows evaluating a condition. Let’s look at a pattern for
F’s first argument is the recursive call. If
c is 1, then
g is not called and
(app Y F) terminates. We don’t know what
c is yet, but we can look at what happens when it is not 1:
c is ever
false, the whole thing shuts down and returns a value.
off is not really a value in this case, but serves as a placeholder. What about 1?
That appears to work as well. So, the inclusion of an
F seems to give us the capability of turning off the recursion.
One last problem.
0 are great, but we really need the recursion to terminate as the result of a calculated value. Plus, it would be nice to return something that is, well, calculated rather than some constant value like
g is the function called to cause recursion and is right now the only argument to
F. Let’s try adding another that will serve as the data input to the calculation performed by
F. Let’s see how that works. First, let’s use a concrete value for
F and although our interpreter doesn’t do it, let’s hold it abstract. This particular
F sums up the values from 0 to its input argument
Now let’s set up the
The function we apply to
5 is obtained by applying
F. Then we apply the result to
Let’s evaluate the inner
app first resulting in
x bound to half of the
Y combinator application to
F. Now lets expand
F before going forward and evaluate the outermost
The result is now
g bound to
(app x x) in the environment. That seems a little odd, but look carefully at the environment.
x is already bound to half of the
Y application. That’s perfect!
g is really the recursive call we want to make if that substitution is performed. One more
app evaluation binds
z to 5:
Now we need to evaluate identifiers by replacing them with their values from the environment.
Now we have
5+(app (app x x) 4), but remember what we said about
(app x x). Using the current environment we can replace
x with the
This is exactly what we want. Compare the second term of the sum with our original expression. The only difference is we’re using 4 rather than 5, but that’s exactly what we want! So the
Y gives us a recursive operation builder that takes a non-recursive function like
F and makes it recursive. All this without
F knowing about itself!
The Y just discussed is often called the lazy Y because it only works using lazy evaluation. An alternative called the Z combinator does the same thing for strict languages with just a few changes. Z is often called the applicative Y combinator.
The form of the Z is as follows:
and unfortunately it is more involved than the traditional Y.
Z are not commonly used constructs in common language settings, they are here because they are beautiful. We have defined recursion without the concept of a global name space. Neither
Z or the functions that are arguments to them directly reference themselves. The only place we define names is in
lambda definitions or
bind definitions that could be replaced by
lambda applications! This is elegant and beautiful. If you are interested in pursuing this kind of thing further, a good course in programming language semantics should be on your list of courses to take.
Y combinator is historically important as it is an implementation of Curry’s Paradox. That would be Haskell Curry for whom Haskell and currying are named. Curry denied actually inventing currying, but that’s another story entirely. Curry’s Paradox is important because it introduces a contradiction in the lambda calculus that renders it useless as a deductive system. Another thing worth looking at that we don’t have time for here.
Finally, the Y Combinator that you’re likely more familiar with is the venture capital firm started by Paul Graham. Graham has several accomplishments to his name before the Y Combinator - PhD in Computer Science from MIT, MS in Painting from NYU, developed the first online web store for Yahoo (in Lisp I might add), just for starters. Hopefully you can see why he chose the name Y Combinator for his firm. The programming
Y effectively creates copies of itself as many times as needed. That’s precisely the same thing that Graham’s company does.
multiply x ythat works by starting with
ytimes using the Z combinator.