Blog

“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:

Clearly `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 `fact`

.

Now let’s take a step backwards and evaluate `fact`

with our dynamically scoped interpreter for `FBAE`

:

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 `lambda`

closes, `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 `bind`

, where `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 `fact`

:

When called on `0`

, `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 `bind`

.

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`

and `Z`

constructs. `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 `Z`

.

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:

Clearly `fact`

calls `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 `lambda`

.

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 `app`

within `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 `Y`

is `f`

which appears in the body in the function position of an `app`

. So, `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`

:

`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:

Bingo. If `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 `if`

in `F`

seems to give us the capability of turning off the recursion.

One last problem. `1`

and `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 `off`

.

Remember that `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 `n`

.

Now let’s set up the `Y`

in `bind`

.

The function we apply to `5`

is obtained by applying `Y`

to `F`

. Then we apply the result to `5`

:

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 `app`

:

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 `lambda`

giving:

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.

While $\Omega$, `Y`

, and `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 `Y`

or `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.

The `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.

- Fixed-point combinator - A function $y$ such that for any function $f$, $y f = f (y f)$

- Implement the Z combinator using FBAE with static scoping.
- Implement
`multiply x y`

that works by starting with`0`

and adding`x`

to it`y`

times using the Z combinator.