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
lambda expression only needs one argument, so our
would actually be good enough for this. But what about the reference
factorial inside the
lambda? The special form for
is perfectly happy with this, it just calls
evalScheem with an environment.
The trouble could happen when
evalScheem gets down to the recursive call
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
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
the original environment in which the
define is called.
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
v, and a value
val. It should update
env in place to add
a top-most binding from
val, and still include all existing bindings.
For simplicity you can assume
env is not
valat the top-most level, no need for more levels.