6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 16.1 Slide 16.1.1 Building up a language Last time, we completed building our evaluator. And as you saw, we slightly misled you. We started off saying we were going to user Scheme's lexical analyzer and parser, but then build our own evaluator, which we did initially for arithmetic expressions, then for defines, then for applications, and eventually we ended up with something that basically looked ke scheme's evaluator written in Scheme Today, we are going to build on that idea, by examining the actual Scheme evaluator. We will run through a quick, but grand tour of the full evaluator, looking at several key ideas First,remember that we are basically describing the process of /4 evaluation, which in our case means making the environment model a concrete set of procedures. Second, the essential message is that by defining the process of evaluation, we are also defining our language. This means that the evaluator design then provides the basis on which we can create abstractions, especially procedural abstractions, as it provides the mechanism for unwinding the abstraction back down to primitive pieces when we want to get an actual value. And finally, given that designing an evaluator is essentially equivalent to defining a language, we are going to look at how variations in a Scheme evaluator can lead to very different language behavior Building up a language Slide 16.1.2 o do this, we are going to have to look at several different rts of the lar guage design. we eval and apply, then look at how we support the syntax of the language, how we create and manipulate the environments that let us look up values that are associated with that syntax, and then how primitives are installed into the initial primitives and initial env or global environment. Finally, we will put together the overal infrastructure for letting a user interact with the evaluator, and d-eval we will see all of these pieces as we quickly walk through our As with previous lectures, there is a code handout that goes with this lecture, and we suggest you print out a copy and have it available as we walk through our discussion
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 16.1 Slide 16.1.1 Last time, we completed building our evaluator. And as you saw, we slightly misled you. We started off saying we were going to user Scheme's lexical analyzer and parser, but then build our own evaluator, which we did initially for arithmetic expressions, then for defines, then for applications, and eventually we ended up with something that basically looked like Scheme's evaluator, written in Scheme! Today, we are going to build on that idea, by examining the actual Scheme evaluator. We will run through a quick, but grand tour of the full evaluator, looking at several key ideas. First, remember that we are basically describing the process of evaluation, which in our case means making the environment model a concrete set of procedures. Second, the essential message is that by defining the process of evaluation, we are also defining our language. This means that the evaluator design then provides the basis on which we can create abstractions, especially procedural abstractions, as it provides the mechanism for unwinding the abstraction back down to primitive pieces when we want to get an actual value. And finally, given that designing an evaluator is essentially equivalent to defining a language, we are going to look at how variations in a Scheme evaluator can lead to very different language behavior. Slide 16.1.2 To do this, we are going to have to look at several different parts of the language design. We will start with the core of eval and apply, then look at how we support the syntax of the language, how we create and manipulate the environments that let us look up values that are associated with that syntax, and then how primitives are installed into the initial or global environment. Finally, we will put together the overall infrastructure for letting a user interact with the evaluator, and we will see all of these pieces as we quickly walk through our full evaluator. As with previous lectures, there is a code handout that goes with this lecture, and we suggest you print out a copy and have it available as we walk through our discussion
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 16.1.3 Let's start with the heart of the interpreter. We have already The Core Evaluator eval/apply seen this with our simple interpreter from the last lecture. The core essence of the evaluator is a tight loop, in which the evaluation Eval of an expression with respect to an environment reduces in the general case to an application of a procedure to a set of arguments. This in turn generally reduces to an evaluation of a Apply simpler expression( the body of the procedure)with respect to a new environment(one in which the formal parameters of the procedure have been bound to the arguments passed in) This loop continues, unwinding expressions, until it reaches the application of a primitive procedure to primitive values or the evaluation of a primitive data object The Core Evaluator Slide 16.1. 4 evallapply) Our convention is that we will use an eva l that does dispatch core Eval on type. Thus, it checks the expression type, and based on that, sends the expression to a procedure designed to handle that type ur convention on app ly is that it w aluate the argum d then apply the dure that is t value of the first argument to the values of the other Core evaluator eval: dispatch on expression type Slide 16.1.5 Meal So here is our implementation ofeval. Notice its form. First it is a dispatch on type, so it checks the expression to figure out fond((self- walnut ing which type matches. Once it does, it sends the expression to a inition exp env procedure specific to that type. Notice that we are assuming a data abstraction for checking types. We are not making any make-procedure (lanbda-parameters exp) anbda-bodly exp) assumptions about how types are represented, but are rather using a set of procedures to check each type. This will allow us al (oond-> to cleanly add to or alter our types, without having to change (operator exp) env) the evaluator directl ssion type-- BVAL" exp))))
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 16.1.3 Let's start with the heart of the interpreter. We have already seen this with our simple interpreter from the last lecture. The essence of the evaluator is a tight loop, in which the evaluation of an expression with respect to an environment reduces in the general case to an application of a procedure to a set of arguments. This in turn generally reduces to an evaluation of a simpler expression (the body of the procedure) with respect to a new environment (one in which the formal parameters of the procedure have been bound to the arguments passed in). This loop continues, unwinding expressions, until it reaches the application of a primitive procedure to primitive values or the evaluation of a primitive data object. Slide 16.1.4 Our convention is that we will use an eval that does dispatch on type. Thus, it checks the expression type, and based on that, sends the expression to a procedure designed to handle that type of expression. Our convention on apply is that it will first evaluate the arguments, and then apply the procedure that is the value of the first argument to the values of the others. Slide 16.1.5 So here is our implementation of eval. Notice its form. First, it is a dispatch on type, so it checks the expression to figure out which type matches. Once it does, it sends the expression to a procedure specific to that type. Notice that we are assuming a data abstraction for checking types. We are not making any assumptions about how types are represented, but are rather using a set of procedures to check each type. This will allow us to cleanly add to or alter our types, without having to change the evaluator directly
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 16.1.6 Notice the order in which we check things in eval. We first start out by checking for primitives, things like self-evaluating expressions, or variables. These are easy things to deal with else (error " Unknown expression type -- EVAL,"exp)))) Slide 16.1.7 Meal Next, we check out the special forms. Remember that this is an (detine (egal exp expression that does not follow the normal rules of evaluation for compound expressions. These are things like assignment or 1=1 definition, in which we only want to evaluate one of the (it? exp) (eval-if exp env)) subexpressions, or things like if, where we know we want to (make-procedure laRbda-parameters exp) ambda-body exp) evaluate in a different order. Each of these expressions we will treat separately, with a specific procedure to deal with that kind al (condence (be in-actions exp) of expression. We've added a couple of new ones, and we will come back to those shortly The issue to note is that this section "Unknown expression type--BVAL"exp)))) deals with all the special forms Slide 16.1. 8 Finally, we get to an application. This is the case where we are alue exp env treating an expression that has a set of subexpressions that we will evaluate, then apply the operator (or value of the first subexpression )to all the rest of them. We have left make-procedure (lanbda-parameters exp) application? as an abstraction to check if something (lambda-body exp) agin? exp)(es ence (bogin-aotions exp)anv)) is an application, but as you saw with our earlier evaluators, most likely we will just make sure this is a combination, meaning we will assume that if the expression is a compound else (error expression but not a known special form, then it must be an application
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 16.1.6 Notice the order in which we check things in eval. We first start out by checking for primitives, things like self-evaluating expressions, or variables. These are easy things to deal with. Slide 16.1.7 Next, we check out the special forms. Remember that this is an expression that does not follow the normal rules of evaluation for compound expressions. These are things like assignment or definition, in which we only want to evaluate one of the subexpressions, or things like if, where we know we want to evaluate in a different order. Each of these expressions we will treat separately, with a specific procedure to deal with that kind of expression. We've added a couple of new ones, and we will come back to those shortly. The issue to note is that this section deals with all the special forms. Slide 16.1.8 Finally, we get to an application. This is the case where we are treating an expression that has a set of subexpressions that we will evaluate, then apply the operator (or value of the first subexpression) to all the rest of them. We have left application? as an abstraction to check if something is an application, but as you saw with our earlier evaluators, most likely we will just make sure this is a combination, meaning we will assume that if the expression is a compound expression but not a known special form, then it must be an application
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 16.1.9 In general, however, we see that our evaluator has exactly the Meal kind of form that we slowly evolved in our previous examples.(define(meal Given an expression and an environment, eval will check the type of the expression, using some abstractions that we will ion? erp) (eval-definition exp en get to, to see if it is a primitive, or if it is a special form, or ultimately if it is an application In each case. eval mmake-procedure -body exp) dispatches that expression to a specific pr ocedure exp) ev) already seen many of these pieces. We know that for variables we should just look up the value of the variable in the telse (error Unknow ion t RVAL environment. We know that for quoted expressions, we should simply grab the expression as tree structure and return it Similarly for the special forms: a definition should create a new binding for a name and a value in the environment; an if should change the order of evaluation of the For an application, we should evaluate the first subexpression( the operator), then evaluate all the other ubexpressions, and apply that operator to that list of values. Notice that I have slightly misled you because we don 't have to assume that the operator is the first subexpression Operator is simply some data abstraction that will get the appropriate subexpression but it could in fact be some piece other than the first or leftmost one Basic Semantics: meval& apply Slide 16.1.10 Here is a quick synopsis of what we see on that evaluator. It self-evaluating, quoted dispatches on type: first for primitives, either self-evaluating vanables and the ey things or things that should not be evaluated; then for ariable definition, lookup and assignment expressions that deal with variables and their manipulation within the environment (creating, looking up, or changing values of variables), then for conditionals, ways of branching depending on the value of an expression; then procedure application sequences 1n Note there are several new forms here that we will have to define: quoted objects, cond, and begin. Let's take a look at some of these Slide 16.1.ll Side comment- procedure body In our evaluators from the previous lectures, when we applied a. The procedure body is a sequence of one or more procedure to a set of arguments, we saw that reduced to simply evaluating the body of the procedure with respect to a new defin environment Evaluation of the body was simply a case of using th⊥nq(+x1)) eval on that expression, and that was because we assumed the body was just a single expression. Before we introduced In m-apply, we eval-sequence the procedure body mutation into our language, this made perfect sense, because the value of the body would be the value of the last expression in it, and it only made sense to have one expression, since any other expressions value in a body would be lost Once we have mutation, however, expressions can do things other than return values they can create side effects. So a generalization for an evaluator is to let the body of a procedure be a sequence of one or more expressions. That is shown here, in which we define foo to be a procedure whose body has two expressions. The first does something, probably a side effect, and the second of
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 16.1.9 In general, however, we see that our evaluator has exactly the kind of form that we slowly evolved in our previous examples. Given an expression and an environment, eval will check the type of the expression, using some abstractions that we will get to, to see if it is a primitive, or if it is a special form, or ultimately if it is an application. In each case, eval dispatches that expression to a specific procedure. We have already seen many of these pieces. We know that for variables, we should just look up the value of the variable in the environment. We know that for quoted expressions, we should simply grab the expression as tree structure and return it. Similarly for the special forms: a definition should create a new binding for a name and a value in the environment; an if should change the order of evaluation of the subexpressions. For an application, we should evaluate the first subexpression (the operator), then evaluate all the other subexpressions, and apply that operator to that list of values. Notice that I have slightly misled you because we don't have to assume that the operator is the first subexpression. Operator is simply some data abstraction that will get the appropriate subexpression but it could in fact be some piece other than the first or leftmost one. Slide 16.1.10 Here is a quick synopsis of what we see on that evaluator. It dispatches on type: first for primitives, either self-evaluating things or things that should not be evaluated; then for expressions that deal with variables and their manipulation within the environment (creating, looking up, or changing values of variables); then for conditionals, ways of branching depending on the value of an expression; then procedure application. Note there are several new forms here that we will have to define: quoted objects, cond, and begin. Let's take a look at some of these. Slide 16.1.11 In our evaluators from the previous lectures, when we applied a procedure to a set of arguments, we saw that reduced to simply evaluating the body of the procedure with respect to a new environment. Evaluation of the body was simply a case of using eval on that expression, and that was because we assumed the body was just a single expression. Before we introduced mutation into our language, this made perfect sense, because the value of the body would be the value of the last expression in it, and it only made sense to have one expression, since any other expression's value in a body would be lost. Once we have mutation, however, expressions can do things other than return values: they can create side effects. So a generalization for an evaluator is to let the body of a procedure be a sequence of one or more expressions. That is shown here, in which we define foo to be a procedure whose body has two expressions. The first does something, probably a side effect, and the second of
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology which computes and returns a value We still have to figure out how to do evaluation of a sequence(we ll get to that in a second) but given the idea that evaluating a sequence could take a of expressions, evaluate them in order and return the value of the last one we can now let bodies have multiple expressions, and inside of app ly we can generally evaluate the body as a sequence, not a single expression Apply Slide 16.1.12 Thus, our apply, our way of dealing with applications of (defino ( ly procodure arguments procedures to arguments, will be slightly different. As before, it will have a way of dealing with primitive procedures, in this rocedure body case just sending the expression to the underlying machine urcpar actors prooeduro) else (eror wine, PEEtre environment AppLY procedure we built using a lambda), we make a slight change.We still create a new environment, binding the parameters of the procedure(obtained using the appropriate data abstraction)to the values of the arguments in a frame that extends the L environment specified by the procedure object.Within this new environment, we will evaluate the body of the procedure, but notice here we will evaluate it as a sequence, not as a single expression Thus, we will treat the body as a set of expressions, evaluate each one in order, and then return the value of the last one as the value of the entire application With that, we now see the intertwining of eval and apply. Let's take a look at some of the specific pieces Slide 16.1.13 Pieces of Eval&Apply First, self-evaluating expressions. Remember that exp is just a tree structure, and in this case, we simply return that tree structure directly. Thus numbers get returned without any nition cxp anv)】 additional work r? exp) (eval-if exp env)) (make-prooedure parameters exp) L ambda-body exp) (begin? cxp) sequcnce (bagin-actions exp (else (er Pieces of Eval&Apply Slide 16.1 14 define If an expression is just a variable(a symbol) we will just look le-value exp env)) up that variable's value in the environment, and we 'll deal with details of that shortl 2计1(>如 4
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. which computes and returns a value. We still have to figure out how to do evaluation of a sequence (we'll get to that in a second) but given the idea that evaluating a sequence could take a series of expressions, evaluate them in order and return the value of the last one, we can now let bodies have multiple expressions, and inside of apply we can generally evaluate the body as a sequence, not a single expression. Slide 16.1.12 Thus, our apply, our way of dealing with applications of procedures to arguments, will be slightly different. As before, it will have a way of dealing with primitive procedures, in this case just sending the expression to the underlying machine primitive. For compound procedures (application of something we built using a lambda), we make a slight change. We still create a new environment, binding the parameters of the procedure (obtained using the appropriate data abstraction) to the values of the arguments in a frame that extends the environment specified by the procedure object. Within this new environment, we will evaluate the body of the procedure, but notice here we will evaluate it as a sequence, not as a single expression. Thus, we will treat the body as a set of expressions, evaluate each one in order, and then return the value of the last one as the value of the entire application. With that, we now see the intertwining of eval and apply. Let's take a look at some of the specific pieces. Slide 16.1.13 First, self-evaluating expressions. Remember that exp is just a tree structure, and in this case, we simply return that tree structure directly. Thus numbers get returned without any additional work. Slide 16.1.14 If an expression is just a variable (a symbol) we will just look up that variable's value in the environment, and we'll deal with details of that shortly