《Structure and Interpretation of Computer Programs》lecture 19 webha2

6.001 Structure and Interpretation of Computer Programs. Copyright o 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 5. Environment as explicit parameter environment out as an explicit parameter. Up until now we could rely on just having a single environment in which to store (eva1'(pus*64)) bindings for variables. It made sense to have a global (eval '(plus* 6 4)environment) environment in which to hold names for procedures and global I .al rocedures that call val have extra argument lookup and define use evironment from argument 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. Loo kup and define* are going to use that environment argument to specify where to work exphcit paramet Slide 15.6.2 This is actually a really boring change! The functionality of 14 this evaluator is exactly the same as the previous version. All do is extend eval to take an environment as arguments, and then make sure that all the dispatch functions also take environments as arguments. Other a 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 5. Environment as explicit parameter Notice in fact that the only non-trivial case is that dealing with application inside of eval. Remember that this is the dispatch (eva1(p1us*64)) that says that we have to apply the object that represents the (eval ' (plus* 6 4) environment) procedure to its arguments. Notice the change we need. As all procedures that call eval have extra argument before, we will evaluate the first subexpression of the tree lookup and define use environment from argument tructure to get the procedure, now including the environment o other change from evaluator 4 as an argument In order to get the values of the other expressions before we could just map eval down the list of expressions. He Only nontrivial code: case for application? in eval however, we have to evaluate each expression with respect to the environment so we need a lambda here to capture that ..old 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.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 o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 15.7 Slide 15.7.1 6. Defining new procedures Want to add new procedures interpreter. We would like to be able to add new procedures. If I. For example, a scheme+ program you think about it, once we add this ability we have all the basic components of an interpreter: we can deal with primitive (define* twice*(lambda*(x*)(plus* x***))) 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 6. Defining new procedures Slide 15.7.2 Want to add new procedu o do this, we need to add to our evaluator the ability to capture For example, a scheme* program a computation in a procedure. Earlier in the term we saw this (define* twice* (lambda* (x*)(plus* x with Scheme: that a lambda expression could capture a (twice* 4) common pattern of computation. Now we are going to see how to add that ability to an evaluator, by creating something that Add a case for lambdas to eval will deal with lambda-like expressions he value of l ambda* is a compound procedure .Extend apply to handle compound procedures Here is our strategy for accomplishing this. First, we will need plement environment model another dispatch in our evaluator, something that deals explicitly with lambda* expressions. We would like the a0 value of the l ambda* 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 app ly 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 m.时:3? Adding the dispatch to eval is straightforward. Well need a - mm new tag checker for lambda* expressions, and a new dispatch clause inside eval to a procedure to handle the …1 wane.tp create of lambda* objects. Notice where we add this oAale-6oepsvd aww biar dispatch clause: it must come before the application case, since 1 ambda大 I 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. 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 o 2004 by Massachusetts Institute of Technology Slide 15.7. 4 So what should eval-lambda do? Remember that eval tal put a tree structure representing a ( i+ssas,"aane.…ps 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 I 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 Ma ke-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 we are assuming that the body contains exactly one expression. That is a design choice that we could change 3 Also notice that we have made a decision about the body of a procedure. by using the caddr of the expressi Slide 15.7.5 3mhd”) So adding the new form to create pi ocedure objects is pretty I straightforward. We will have to eventually work out what make-compound does but that is basically an n←p abstraction issue Now the question is: how do I change app ly? Remember that app ly is going to evaluate the first subexpression of a tree structure, get out the appropriate procedure, evaluate all the arguments getting back a list of those values, and then we want to apply that procedure to that list In the case of primitive things, inherited things from Scheme like +, etc, apply was just a matter of doing the basic operation. Now, we need to extend apply In this case, when we go to apply an operator to a list of operands, we will need to check for type. Is it a primitive operation? If yes, we just apply the underlying Scheme procedure as before. Is it a compound operator, that is, are evaluating an expression in which we are using a procedure that we created in our evaluator using lambda*? In this case we need to implement the idea of the environment model Thus, we get the body of the operator, that is, we pull out the piece that we glued together when we made the procedure object. Now we want to evaluate that body. But we are going to evaluate that with respect to an environment, created by taking

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 is: how do I change apply? Remember that apply is going to evaluate the first subexpression of a tree structure, get out the appropriate procedure, evaluate all the arguments getting back a list of those values, and then we want to apply that procedure to that list. In the case of primitive things, inherited things from Scheme like +, * etc., apply was just a matter of doing the basic operation. Now, we need to extend apply. Slide 15.7.6 In this case, when we go to apply an operator to a list of operands, we will need to check for type. Is it a primitive operation? If yes, we just apply the underlying Scheme procedure as before. Is it a compound operator, that is, are we evaluating an expression in which we are using a procedure that we created in our evaluator using lambda*? In this case we need to implement the idea of the environment model. Thus, we get the body of the operator, that is, we pull out the piece that we glued together when we made the procedure object. Now we want to evaluate that body. But we are going to evaluate that with respect to an environment, created by taking

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology the operands passed in, taking the formal parameters of the procedure object, and binding them together. This new environment should extend the previous one, in case we need things from there Thus when we have a compound application, we will grab the body of the procedure and evaluate it in a new nvironment, which has access to everything in the previous environment, plus bindings for the formal parameters of the procedure to the values passed in Note what this does. Given this version of app ly we have a wonderfully cyclic structure. Eval of an expression with respect to an environment in the general case will reduce to app l ying a procedure to a set of arguments, and that will reduce in the general case to eva luating a new expression the body of the operator) with respect to a new environment. In this way, eval and app ly will work hand-in-hand in terms of unwrapping the abstractions of the procedures down to primitive operations on primitive objects Slide 15.7.7 6.Defining ne All that is left to do is to implement the"double bubble"ideaas an abstract data type. We can do that by creating a tag for a a p swlI compound procedure and having the constructor(make compound) simply glue things together in a list, with the appropriate predicate and selectors associated with this data 今工然1 abstraction. This is not the only way to do this all we need is some method for gluing things together and getting them back Implementation of lambda* Slide 15.7.8 Looking at the code helps us understand our changes, but it is probably easier to see the changes by watching the evolution of the evaluation of an expression. Let's trace through the evaluation of a lambda* expression That is, we are evaluating a tree structure whose first element is the symbol mbda*, whose second element is a list of parameters, and whose third element is an expression constituting the body of the procedure. We are evaluating this with respect to some environment, say the global environment 4 Slide 15.7.9 Implementation of lambda* As before, please follow along in the code (for part 6) So eval takes in that tree structure representing this expression and checks it for different types of expressions (number, symbol, etc. ) Eventually eval reaches the case for handling lambda* expressions, Thus, we will dispatch on type to eval-lambda, the specific procedure designed to evaluate l ambdax's

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. the operands passed in, taking the formal parameters of the procedure object, and binding them together. This new environment should extend the previous one, in case we need things from there. Thus when we have a compound application, we will grab the body of the procedure and evaluate it in a new environment, which has access to everything in the previous environment, plus bindings for the formal parameters of the procedure to the values passed in. Note what this does. Given this version of apply we have a wonderfully cyclic structure. Eval of an expression with respect to an environment in the general case will reduce to applying a procedure to a set of arguments, and that will reduce in the general case to evaluating a new expression (the body of the operator) with respect to a new environment. In this way, eval and apply will work hand-in-hand in terms of unwrapping the abstractions of the procedures down to primitive operations on primitive objects. Slide 15.7.7 All that is left to do is to implement the "double bubble" idea as an abstract data type. We can do that by creating a tag for a compound procedure and having the constructor (make￾compound) simply glue things together in a list, with the appropriate predicate and selectors associated with this data abstraction. This is not the only way to do this; all we need is some method for gluing things together and getting them back apart. Slide 15.7.8 Looking at the code helps us understand our changes, but it is probably easier to see the changes by watching the evolution of the evaluation of an expression. Let's trace through the evaluation of a lambda* expression. That is, we are evaluating a tree structure whose first element is the symbol lambda*, whose second element is a list of parameters, and whose third element is an expression constituting the body of the procedure. We are evaluating this with respect to some environment, say the global environment. Slide 15.7.9 As before, please follow along in the code (for part 6). So eval takes in that tree structure representing this expression and checks it for different types of expressions (number, symbol, etc.). Eventually eval reaches the case for handling lambda* expressions, Thus, we will dispatch on type to eval-lambda, the specific procedure designed to evaluate lambda*'s

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.7.10 Implementation of lambda* Eval-lambda starts with the same tree structure as an (va1'( anda·(x*)(1口xx*))cE eval-lambda'(lambda*(x*)(plus*** x*))GE,I argument, plus some pointer to the global environment(GE) What does it do? It walks down the tree structure of the first argument, and grab the arguments(that's the cadr). Similarly, walk down the tree structure and grab the body(thats the caddr)(note that we are assuming there is only one expression in the body In this case, the cadr will return the list(x*)and the caddo will return the list(plus* x* x*). let me stress agai that we are simply getting these as tree structure; there is no glue them together using make-compound Valuation yet. Having acquired those two structures, we then Slide 15.7.11 Implementation of lambda* So the evaluation reduces to this expression. This is simply Keval(l anbda* (x*)(plus.x*I*))GE) using our constructor to glue these pieces together, and in this (eval-lambda '(lambda* (Et*)(plus* x**))GE) case that converts to this form make-compound +(x*).(plus* x* x*)GE Implementation of lambda* Slide 15.7.12 eva1(1 anda·(x)(p1unx请x*))cE and thus we are down to a basic primitive. We are going to teval-lambda' (ambdat (x+)(plust x+ x+) Ge, construct a new list structure, with a type tag, a list of make- compound《x*)·(p1us★x*x*)GE parameters, a body and the environment in which this (list 'compound ' (**)1(plus*****)GE) l ambda* expression was created

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.7.10 Eval-lambda starts with the same tree structure as an argument, plus some pointer to the global environment (GE). What does it do? It walks down the tree structure of the first argument, and grab the arguments (that's the cadr). Similarly, walk down the tree structure and grab the body (that's the caddr) (note that we are assuming there is only one expression in the body). In this case, the cadr will return the list (x*) and the caddr will return the list (plus* x* x*). Let me stress again that we are simply getting these as tree structure; there is no evaluation yet. Having acquired those two structures, we then glue them together using make-compound. Slide 15.7.11 So the evaluation reduces to this expression. This is simply using our constructor to glue these pieces together, and in this case that converts to this form.... Slide 15.7.12 ... and thus we are down to a basic primitive. We are going to construct a new list structure, with a type tag, a list of parameters, a body and the environment in which this lambda* expression was created

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.7.13 And that says that the evaluation of this expression returns thisImplementation oflambda* list structure. That is actually quite nice! We have created a new(eval'(lambda(x")(plus.x*I"))GE) object in our language, we have evaluated a lambda*and (x*)(plus (make-compound +(x*)'(plus* x* x*) GE created a procedure object. When we go to do an application(as (list ' compound '(x*),plus* x***)GE) we will see shortly)we need an expression represented as list structure so that we can pull out the pieces, and here they are All of the parts we will need for an application are represented as list structure within this list, so that we easily use those within the evaluator Implementation of lambda* Slide 15.7.14 (eva1(1 anda·(x*)(p1u·x*x*)c hus, this piece of list structure represents a procedure. It is our eval-1ambda.(lambda(**)(plus* g+ x*))Ge) particular way of creating a data structure for a procedure: it has compound'《x*} us★xtx)GE a tag identifying it as a compound procedure, a set of (list 'compound (**)(plus* x***)GE) parameters, and a body, all represented in the format we expect as a parsed tree 面中一 scm Slide 15.7.15 Defining a named procedure Now that we can create procedures in our interpreter, we (eval ,(define* twice* naturally want to give them names, and that just uses our (lambda* (E*)(plus* x* x*)))GE) define* expressions. How does this work? First of all, we will have some initial bindings in our environment Defining a named procedure Slide 15.7.16 as shown here in our abstract table representation for an (eval ,(define* twice (lambda* (x*)(plus* x* x*)))GE) environment. This environment includes prior bindings for might also have some other bindings based on builti We names to numbers and for symbols to boolean values procedures, for example, we may have installed a primitive twice procedure for plus大

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.7.13 And that says that the evaluation of this expression returns this list structure. That is actually quite nice! We have created a new object in our language, we have evaluated a lambda* and created a procedure object. When we go to do an application (as we will see shortly) we need an expression represented as list structure so that we can pull out the pieces, and here they are. All of the parts we will need for an application are represented as list structure within this list, so that we easily use those within the evaluator. Slide 15.7.14 Thus, this piece of list structure represents a procedure. It is our particular way of creating a data structure for a procedure: it has a tag identifying it as a compound procedure, a set of parameters, and a body, all represented in the format we expect as a parsed tree. Slide 15.7.15 Now that we can create procedures in our interpreter, we naturally want to give them names, and that just uses our define* expressions. How does this work? First of all, we will have some initial bindings in our environment ... Slide 15.7.16 ... as shown here in our abstract table representation for an environment. This environment includes prior bindings for names to numbers and for symbols to Boolean values. We might also have some other bindings based on built in procedures, for example, we may have installed a primitive procedure for plus*

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.7.17 and as we saw from our earlier work, plus* would be Defining a named procedure represented by a primitive procedure, in this case as list (lambda* (x*)(plus* x* x*)))GE) structure with a tag identifying it as a primitive and a pointer to the actual primitive code. Remember that this was installed in the global environment when we loaded up our evaluator PLus Defining a named procedure Slide 15.7.18 (eva1’( define* twice That is, there is a pointer from plus* in the global (lambda* (x*) (plus* x* x*)))GE) environment(that table)to the actual representation of the bject 卫1m包 dure Slide 15.7.19 Defining a named procedure So what happens when we evaluate the expression shown at the (eval ,(define* twice* top? Eval will dispatch this to eval-define which (lambda* (x*)(plus* x* x*)))GE will create a binding for the symbol twice* in the environment, to the value returned by evaluating (lambda* (x*)(plus* x* x*)).We know what that latter 七Wice rocedure evaluation will return, that is the thing we just saw and it gives us back this structure symbol[ 4I+AB-L symbol plus* Defining a named procedure Slide 15.7.20 We do need to worry about where the environment part of the (eval ,(define* twice (lambda* (x*)(plus* x* x *))) structure points to, and we know it should point to the environment in which the evaluation was done, hence to this twice symbolIa A+LV

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.7.17 ... and as we saw from our earlier work, plus* would be represented by a primitive procedure, in this case as list structure with a tag identifying it as a primitive and a pointer to the actual primitive code. Remember that this was installed in the global environment when we loaded up our evaluator. Slide 15.7.18 That is, there is a pointer from plus* in the global environment (that table) to the actual representation of the object. Slide 15.7.19 So what happens when we evaluate the expression shown at the top? Eval will dispatch this to eval-define which will create a binding for the symbol twice* in the environment, to the value returned by evaluating (lambda* (x*) (plus* x* x*)). We know what that latter evaluation will return, that is the thing we just saw and it gives us back this structure. Slide 15.7.20 We do need to worry about where the environment part of the structure points to, and we know it should point to the environment in which the evaluation was done, hence to this frame

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.7.21 and the binding of the name twice to this value will Defining a named procedure take place in this environment. Thus we add a pairing to the (lambda* (x*)(plus* x* x*)))GE) table of the symbol twice* and a pointer to this structure symbol ymbo Defining a named procedure Slide 15.7.22 (eva1’( define* twice So notice what has happened. We have created the ability to (lambda* (*)(plus* x* x*)))GE) create names for procedures in our environment, that point to one of these procedure objects. Thus we can now refer to that procedure object by name, thus building in a level of 卫1m包 abstraction 七w⊥ce★ 口[团 Slide 15.7.23 Implementation of apply (1) So let's look at the use of this abstraction, by looking at the evaluation of an expression that involves a name for one of these procedures. We want to see how eval and apply work together to unwrap the abstraction to more primitive First, let's evaluate the expression shown with respect to the global environment Implementation of apply (1) (eval '(twice* 4) GE) Eval will deduce that this is an application, thus reducing to (apply (eval ' twice* GE) this apply expression. We must evaluate the first (map (lambda (e)(eval e GE))'(4)) subexpression ( which we simply grab from the tree structure) and apply the result to the list we get by mapping eva l down the list of arguments in the initial expression. Note that all of these evaluations take place with respect to the same environment

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.7.21 ... and the binding of the name twice* to this value will take place in this environment. Thus we add a pairing to the table of the symbol twice* and a pointer to this structure. Slide 15.7.22 So notice what has happened. We have created the ability to create names for procedures in our environment, that point to one of these procedure objects. Thus we can now refer to that procedure object by name, thus building in a level of abstraction. Slide 15.7.23 So let's look at the use of this abstraction, by looking at the evaluation of an expression that involves a name for one of these procedures. We want to see how eval and apply work together to unwrap the abstraction to more primitive expressions. First, let's evaluate the expression shown with respect to the global environment. Slide 15.7.24 Eval will deduce that this is an application, thus reducing to this apply expression. We must evaluate the first subexpression (which we simply grab from the tree structure) and apply the result to the list we get by mapping eval down the list of arguments in the initial expression. Note that all of these evaluations take place with respect to the same environment

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.7.25 And what does the evaluation of the pieces do? Twice* imPlementation of apply ( just a symbol, so eval dispatches to a lookup, which returns (eval(twice* 4)GE) (apply (eval 'twice* GE) this list structure that captures the pieces of the procedure (map (lambda (e) (eval e GE)),(4))) Clabel, argument list, body and inherited environment) (apply (list 'compound + (x*)'(plus*** **)GE) Evaluating the arguments simply returns the list (4)since numbers are self-evaluating. Thus we are ready to apply this representation of a compound procedure to a list of argument Implementation of apply (1) Slide 15.7.26 (eval ,(twice* 4) GE) And the code for app ly indicates that we should grab(using list manipulation procedures)the formal parameters of the (map (lambda (e) (eval e GE)),(4))) app1y(1itt' comPound’(x*)(p⊥us*x*x*)GE) procedure, take the list of argument values supplied, and glue them together with respect to the original environment in which (eval ,(plus* x* x*) the procedure was created, to create a new frame. That is just (extend-env-with-new-frame'(**).(4) GEl some list manipulation that we havent detailed yet Conceptually, we know what this should do: create a new table (or environment)with the formal parameters bound to the argument list, and which is scoped by the environment in which the procedure was created And then, we walk down the tree representation for the procedure object( this version of a double bubble"), grab off the body, and we will evaluate that new expression in this new environment. Note that this is all just list manipulation, we have not evaluated any of the pieces, we are simply setting up to do that Slide 15.7.27 Implementation of apply (1) So extending the environment will be some kind of abstract data type manipulation that creates a new environment, call it ( apply (eval' twice GE) El in which those variables have been bound We are now (map (lambda (e) (eval e GE)),(4))) going to evaluate this new expression with respect to that environment extend-env-with-new-frame (x*)'(4)GE) (eva1(p1us±

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.7.25 And what does the evaluation of the pieces do? Twice* is just a symbol, so eval dispatches to a lookup, which returns this list structure that captures the pieces of the procedure (label, argument list, body and inherited environment). Evaluating the arguments simply returns the list (4) since numbers are self-evaluating. Thus we are ready to apply this representation of a compound procedure to a list of argument values. Slide 15.7.26 And the code for apply indicates that we should grab (using list manipulation procedures) the formal parameters of the procedure, take the list of argument values supplied, and glue them together with respect to the original environment in which the procedure was created, to create a new frame. That is just some list manipulation that we haven't detailed yet. Conceptually, we know what this should do: create a new table (or environment) with the formal parameters bound to the argument list, and which is scoped by the environment in which the procedure was created. And then, we walk down the tree representation for the procedure object (this version of a "double bubble"), grab off the body, and we will evaluate that new expression in this new environment. Note that this is all just list manipulation, we have not evaluated any of the pieces, we are simply setting up to do that. Slide 15.7.27 So extending the environment will be some kind of abstract data type manipulation that creates a new environment, call it E1, in which those variables have been bound. We are now going to evaluate this new expression with respect to that environment

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.7.28 Implementation of apply (1) Conceptually, we have some new table structure, as shown here, with a new table for the binding of x* and a pointer to (apply (eval 'twice* GE) p (lambda (e) (eval e GE))'(4)) the enclosing environment (GE). We are now evaluating with (apply (list, compound (x*).(plus* ** x*) Ge)respect to this environment El Notice how we have reduced evaluation of one expression with (eval ,(plus* x* x*) ztend-env-with-new-frame 1(**)+(4)GE respect to some environment to evaluation of a simpler (eval (plus* x* **)El expression with respect to a new, extended environment. There is a basic cycle of the environment model, and more specifically, of our evaluator Slide 15.7.29 Implementation of apply (1) Before we carry on tracing through the evaluation of this (eval '(twice* 4) ome-other-environment simpler expression with respect to this new environment, let's (apply (eval twice stop and look at an important point. Suppose we started off the (eval e GE 4)) overall evaluation of(twice* 4), not in the global environment. but in some other environment. hat would (eva1’(pLus*x*x appen? (extend-env-with-new-frame 1(**).(4)GE) The application would have to do an evaluation of the eva1’(p1usx*x*}E1 ubexpressions, and those would also be with respect to this new environment since that is passed down as part of the evaluation Implementation of apply (1) Slide 15.7.30 So at this stage we would use that same new environment (eval '(twice* 4)GBy some-other-environment) (map (lambda (e)(eval e GE),(4)) (eval '(Plus* x***) (extend -env-with-new-frame ' (**).(4)GE)) (eval (plus* x* **) El E1 Slide 15.7.31 Implementation of apply (1) But when we get to the actual application, notice that here the (eval(twice* 4)By some-other-environment) environment doesn't change, because the global environment d here comes from the creation of the procedure When we apply (eval '* Ge (map (lambda (e)(eval e GE)'(4)) evaluated the lambda* expression that created the appy(1 ist + compound’(x*)·(p1us*x*x*)￠) procedure object, part of that creation as a link to the (eva1’(pLus*x*x* environment in which the I ambda was evaluated. And that (extend-env-with-new-frame.(x*).(4)(GE)) means that evaluating the body is going to extend this environment not the environment we called it in. Thus although we can evaluate this expression in any environment name value the environment that gets inherited by the procedure is exactly that one in which it was created

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.7.28 Conceptually, we have some new table structure, as shown here, with a new table for the binding of x* and a pointer to the enclosing environment (GE). We are now evaluating with respect to this environment E1. Notice how we have reduced evaluation of one expression with respect to some environment to evaluation of a simpler expression with respect to a new, extended environment. There is a basic cycle of the environment model, and more specifically, of our evaluator. Slide 15.7.29 Before we carry on tracing through the evaluation of this simpler expression with respect to this new environment, let's stop and look at an important point. Suppose we started off the overall evaluation of (twice* 4), not in the global environment, but in some other environment. What would happen? The application would have to do an evaluation of the subexpressions, and those would also be with respect to this new environment since that is passed down as part of the evaluation. Slide 15.7.30 So at this stage we would use that same new environment. Slide 15.7.31 But when we get to the actual application, notice that here the environment doesn't change, because the global environment used here comes from the creation of the procedure. When we evaluated the lambda* expression that created the procedure object, part of that creation as a link to the environment in which the lambda* was evaluated. And that means that evaluating the body is going to extend this environment, not the environment we called it in. Thus, although we can evaluate this expression in any environment, the environment that gets inherited by the procedure is exactly that one in which it was created