6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 15.6 Slide 15.6.1 The next stage in the evolution of our evaluator is to pull the environment out as an explicit parameter. Up until now we could rely on just having a single environment in which to store bindings for variables. It made sense to have a global environment in which to hold names for procedures and global variables. We are about to start moving towards application, in fact we built a simple version of application but we want to extend that to procedures that need local environments. Thus let's pull out the environment explicitly. So we will have to change our evaluator from simply evaluating expressions to evaluating expressions with respect to some environment. What changes to we need? All procedures must now call eval with that extra argument of an environment. Lookup and define* are going to use that environment argument to specify where to work. Slide 15.6.2 This is actually a really boring change! The functionality of this evaluator is exactly the same as the previous version. All we do is extend eval to take an expression and an environment as arguments, and then make sure that all the dispatch functions also take environments as arguments. Other than make those changes, everything else is exactly as before. Of course now when we evaluate an expression we have to specify what environment, and we will need an initial or global environment to start with. This will contain bindings for built in procedures. Otherwise this is just bookkeeping. It will allow us to extend our evaluator in a more general way. Slide 15.6.3 Notice in fact that the only non-trivial case is that dealing with application inside of eval. Remember that this is the dispatch that says that we have to apply the object that represents the procedure to its arguments. Notice the change we need. As before, we will evaluate the first subexpression of the tree structure to get the procedure, now including the environment as an argument. In order to get the values of the other expressions before we could just map eval down the list of expressions. Here, however, we have to evaluate each expression with respect to the environment so we need a lambda here to capture that procedure. We will come back to this shortly, but you can see from a Scheme perspective this makes sense. We are mapping a procedure that evaluates each subexpression with respect to the environment passed in. This is the only non-trivial extension in this case.6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 15.7 Slide 15.7.1 Now we are ready to make our last big extension to our interpreter. We would like to be able to add new procedures. If you think about it, once we add this ability we have all the basic components of an interpreter: we can deal with primitive expressions, with special forms, and with applications, and as along as we can create our own procedures, those applications could include arbitrary nesting of expressions. How do we add new procedures? We would like to create a name for something we make with the equivalent of a lambda. We want to capture procedures within lambda's and then use that procedure as an application. Slide 15.7.2 To do this, we need to add to our evaluator the ability to capture a computation in a procedure. Earlier in the term we saw this with Scheme: that a lambda expression could capture a common pattern of computation. Now we are going to see how to add that ability to an evaluator, by creating something that will deal with lambda-like expressions. Here is our strategy for accomplishing this. First, we will need another dispatch in our evaluator, something that deals explicitly with lambda* expressions. We would like the value of the lambda* expression to return a compound procedure, however we decide to define it. Second, given the ability to create our own procedures, we will need to extend apply to handle such procedures. Right now apply is just set up to handle built in things we inherit from Scheme, but we need to have it also handle procedures we create. And then we should go back and finish the environment model, since it will become essential in the application of procedures. Slide 15.7.3 Adding the dispatch to eval is straightforward. We'll need a new tag checker for lambda* expressions, and a new dispatch clause inside eval to a procedure to handle the create of lambda* objects. Notice where we add this dispatch clause: it must come before the application case, since lambda* is a special form. It should really also come after the checks for the primitive expressions (numbers or symbols). The ordering of where within the special forms it falls is not crucial.6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.7.4 So what should eval-lambda do? Remember that eval takes as input a tree structure representing a lambda* expression, which it then passes to this procedure, together with a pointer to the environment. So first, we need to walk down that tree structure, and grab off the arguments of the expression, the formal parameters if you like. That's what the cadr does. And we want to walk further along the tree and grab the body of the expression, that is the caddr. Having pulled off those two pieces, without evaluation, we then want to glue together some representation of a procedure as a set of arguments, a body, and an environment. This should sound familiar, as it sounds a lot like what we have when we do evaluation with our "double bubble" notation in the environment model. There we have a similar representation for a procedure: formal parameters, body and environment. Make-compound is doing a similar thing here. Note that there is no call to eval inside eval-lambda. None of these expressions is being evaluated; we are simply manipulating tree structure. Also notice that we have made a decision about the body of a procedure. By using the caddr of the expression, we are assuming that the body contains exactly one expression. That is a design choice that we could change. Slide 15.7.5 So adding the new form to create procedure objects is pretty straightforward. We will have to eventually work out what make-compound does, but that is basically an abstraction issue. Now the question
View Full Document
Unlocking...