Simple recursion

Now that we have function application and a way to define functions, can we start cranking out programs? Almost. The last big feature we need is recursion. Remember our trusty friend factorial:

The lambda expression only needs one argument, so our lambda-one would actually be good enough for this. But what about the reference to factorial inside the lambda? The special form for lambda-one is perfectly happy with this, it just calls evalScheem with an environment.

The trouble could happen when evalScheem gets down to the recursive call to factorial. At that point we have to worry about which environment we're using. The lambda-one definition used whatever environment it was given when called. So the important place to look is in define.

My existing old define looked like this:

If you study that line carefully, you'll notice that the environment we pass to evalScheem which in turn will get passed to lambda-one is the original environment in which the define is called.

Does that environment allow references to the variable that is being defined? Not at first. But you can see that the environment is updated with a new binding, so after the define returns that old environment does allow references to the variable being defined!

New update step

If you're used to purely functional programming, this might seem a little weird. We're actually modifying a data structure, not just creating a new one. This is the easiest way to implement recursion.

How do we do this update step with our new environments? Let's create a helper function to do it.

Remember that our environments look like this:

Write a function add_binding that takes an environment env, a variable name v, and a value val. It should update env in place to add a top-most binding from v to val, and still include all existing bindings. For simplicity you can assume env is not { }.


This is easier than you think. Remember that you're not creating a new environment, you're modifying the existing one. Our environments can already handle multiple variable bindings at each scope level. All you need to do is add a binding from v to val at the top-most level, no need for more levels.

Prev Next