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
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 16.1.15 Next, let's skip down to procedure applications. With our Pieces of Eval&Apply hange, we can see that the evaluator gets the value of the operator by recursively evaluating that subexpression, then gets uotation exp a list of values of the other expressions(note that we explicitly ((assigmnent? exp)(e [(definition require a list here)by evaluating each piece in turn and ((if? exp) (eval-if axp env)) constructing a list. note however that our data abstraction ake-procedure lanbda-paraneters cox (lambda-body exp) isolates the issue of the order of the arguments from our nv)) ons exp)env)) evaluator. We don't know if the operator is the first expression or not in this case. Operator will simply select out whatever we decide on in terms of syntax for our language And as we saw, apply will now evaluate the sequence of expressions that it assumes the body contains Pieces of Eval&Apply Slide 16.1.16 What about i fs? We know that an i f expression should take env)) a set of expressions, evaluate the first subexpression(or rather ve are assuming it is the first subexpression) and then <<ir? exp)(eval-if exp env)) depending on that value, either evaluates the consequent or the parameters exp) alternative (begin-aations exp)env)) exp)))) Slide 16.1.17 And what about begins? Remember that a sequence is either dofine Pieces of Eval&Apply something identified by an explicit begin statement or is p) exp) 也 xP.) used as the body of a procedure, as we just saw. In this case, we want to extract the set of expressions, and evaluate them. We exp)(eval-if exp env)) use the following trick, shown on the next slide (lambda-body exp) (mapp ly (meal (operator exp) env) wn express ion EVAL exp))))
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 16.1.15 Next, let's skip down to procedure applications. With our change, we can see that the evaluator gets the value of the operator by recursively evaluating that subexpression, then gets a list of values of the other expressions (note that we explicitly require a list here) by evaluating each piece in turn and constructing a list. Note, however, that our data abstraction isolates the issue of the order of the arguments from our evaluator. We don't know if the operator is the first expression or not in this case. Operator will simply select out whatever we decide on in terms of syntax for our language. And as we saw, apply will now evaluate the sequence of expressions that it assumes the body contains. Slide 16.1.16 What about ifs? We know that an if expression should take a set of expressions, evaluate the first subexpression (or rather we are assuming it is the first subexpression) and then depending on that value, either evaluates the consequent or the alternative. Slide 16.1.17 And what about begins? Remember that a sequence is either something identified by an explicit begin statement or is used as the body of a procedure, as we just saw. In this case, we want to extract the set of expressions, and evaluate them. We use the following trick, shown on the next slide
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 16.1.18 Pieces of Eval&Apply Our plan is to evaluate each of the expressions in order. When define (eval-s we get to the last one, we should return its value as the value of 1 (first-exp exps) env)) the entire sequence. We will bury some of the details behind exps exps)env)))) data abstractions, but we can see the general form for ignument-variable evaluating a sequence. If we have the last expression, we will neval (assigmnent-value exp) exp) simply evaluate it and return the value. If it is not, we evaluate it, then recursively walk down the sequence and do the same thin Slide 16.1.19 Pieces of Eval&Apply Expressions like definitions and assignments either create or change existing bindings of variables and values in the <der ine (eval-ge val (first-exp exps) anv) environment. Notice the form, however. In both cases, we get We simply get out the part of the expression that corresponds to(define the variable as a tree structure manipulation, however, without neval (definition-v evaluation. Then we do the appropriate manipulation of the env〕 environment Notice how by using data abstractions we have not specified what order the expressions will take. While we will eventually decide that, from the perspective of this code, any change in that order will not affect the evaluation process Pieces of Eval&Apply Slide 16.1.20 So there is the whirlwind tour of eval and apply.We (define (eval-sequence exps al (first-exp exps]env)) have buried some details behind some data abstractions which (else (neval (rirst (eval-soquence (rest -axps exps) anv))) we will address shortly. The part that you see here really is the heart of evaluation The essence of the evaluator is a tight loop, in which the (define (oval-definition 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 I with respect to a new environment(one in which the formal parameters of the procedure have been bound to the arguments passed in), while inheriting values from other environments 6.001 Notes: Section 16.2
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 16.1.18 Our plan is to evaluate each of the expressions in order. When we get to the last one, we should return its value as the value of the entire sequence. We will bury some of the details behind data abstractions, but we can see the general form for evaluating a sequence. If we have the last expression, we will simply evaluate it and return the value. If it is not, we evaluate it, then recursively walk down the sequence and do the same thing. Slide 16.1.19 Expressions like definitions and assignments either create or change existing bindings of variables and values in the environment. Notice the form, however. In both cases, we get out the part of the expression that corresponds to the new value, and actually evaluate it, by recursively applying meval to it. We simply get out the part of the expression that corresponds to the variable as a tree structure manipulation, however, without evaluation. Then we do the appropriate manipulation of the environment. Notice how by using data abstractions we have not specified what order the expressions will take. While we will eventually decide that, from the perspective of this code, any change in that order will not affect the evaluation process. Slide 16.1.20 So there is the whirlwind tour of eval and apply. We have buried some details behind some data abstractions, which we will address shortly. The part that you see here really is the heart of evaluation. 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), while inheriting values from other environments. 6.001 Notes: Section 16.2
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 16.2.1 So what have we done so far? Basically we have defined the Syntactic Abstraction syntax semantics of our language. By defining eval and apply.Semantics we have specified what the language means and the model of What the language mea computation we are going to use. Notice that we have done this in terms of data abstractions. Everything we have used to pull out list structure from expressions has used an abstraction E.g. how to signal different expressions There are no cars and cdrs anywhere in the code so far Separation of syntax and semantics This is important, because we have separated the syntax of the language from the semantics of the language. But eventually we c)→( do need to focus on the syntax, the details of how we write 4 legal expressions in our language. This will force us to specify things like how to identify kinds of expressions, and the order of arguments. At the same time, this separation of syntax from semantics is extremely useful, as it allows us to very easily change the syntax without having to change the actual evaluator. We simply change the interface to the abstractions. We are now going to examine this issue, by looking at details of implementing the abstractions and by looking at changes to that abstraction Basic Syntax Slide 16.2.2 Routines to detect expression The second page of the code handout contains all of this in much more detail. Here we will simply highlight some of the pair? exp)(eq? (car exp) tag))) ey issues in syntax (define (if? exp) (tagged-list? exp if)) First, we need a set of routines to detect different kinds of Eine (lambda? exp) (define (application? exp expressions. An easy way to do this is to have each one of them check to see if it is a"tagged"list. So, for example if? wil check to see if the expression is a list, that is something constructed out of cons pairs. It will then check to see if the first element of that list is the symbol if. Ditto for lambda m For application, we will use a slightly different form. We will checkers for a special form but is in fact a list of expressions, we can treat as an application. This means that we ta assume that anything that has not been caught by one of the tag may get into some trouble but it is the easiest way of allowing us to generalize to having any kind of procedure applied to any set of expressions as long as that procedure was created using our lambda Slide 16.2.3 Given that we can detect different kinds of expressions and ship. Rou them off to the procedures that handle them, those procedures(def will also need to have ways of getting information out of Kand (pair? exp) (eq? (car exp expressions. They will have to have ways of pulling out pieces (if? exp) (tagged-list? (lambda? exp) (tagged- y walking down the list structure. So, for example, if we have (application? oxp) (pair? oxp)) an application, we need a way of getting out the operator, and the other expressions. Here we will assume that the first y pression is the operator, so we use car to get it out of the expression. And we will assume that operands is a list of all the remaining expressions, so we use cdr to get that part Of 4 course we could have made a different design choice. as we will see. The key point is that we now have an abstraction that pulls out pieces to pass on to the evaluator
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 16.2.1 So what have we done so far? Basically we have defined the semantics of our language. By defining eval and apply we have specified what the language means and the model of computation we are going to use. Notice that we have done this in terms of data abstractions. Everything we have used to pull out list structure from expressions has used an abstraction. There are no cars and cdrs anywhere in the code so far. This is important, because we have separated the syntax of the language from the semantics of the language. But eventually we do need to focus on the syntax, the details of how we write legal expressions in our language. This will force us to specify things like how to identify kinds of expressions, and the order of arguments. At the same time, this separation of syntax from semantics is extremely useful, as it allows us to very easily change the syntax without having to change the actual evaluator. We simply change the interface to the abstractions. We are now going to examine this issue, by looking at details of implementing the abstractions and by looking at changes to that abstraction. Slide 16.2.2 The second page of the code handout contains all of this in much more detail. Here we will simply highlight some of the key issues in syntax. First, we need a set of routines to detect different kinds of expressions. An easy way to do this is to have each one of them check to see if it is a "tagged" list. So, for example, if? will check to see if the expression is a list, that is something constructed out of cons pairs. It will then check to see if the first element of that list is the symbol if. Ditto for lambda. For application, we will use a slightly different form. We will assume that anything that has not been caught by one of the tag checkers for a special form but is in fact a list of expressions, we can treat as an application. This means that we may get into some trouble but it is the easiest way of allowing us to generalize to having any kind of procedure applied to any set of expressions as long as that procedure was created using our lambda. Slide 16.2.3 Given that we can detect different kinds of expressions and ship them off to the procedures that handle them, those procedures will also need to have ways of getting information out of expressions. They will have to have ways of pulling out pieces by walking down the list structure. So, for example, if we have an application, we need a way of getting out the operator, and the other expressions. Here we will assume that the first subexpression is the operator, so we use car to get it out of the expression. And we will assume that operands is a list of all the remaining expressions, so we use cdr to get that part. Of course we could have made a different design choice, as we will see. The key point is that we now have an abstraction that pulls out pieces to pass on to the evaluator
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Basic Syntax Slide 16.2. 4 Routines to detect express And we will need routines that manipulate expressions, that is and(pax?●a)(eq?(cx·x)tag))) walk along the expressions finding pieces. For example, if we are apply ing a procedure to a set of arguments, we need to get :21 out different parts of the argument list. So we will have something to check if there are arguments, something to get the out of expressions next operand, and something to get the other operands. This is ine (operands just list structure that we are manipulating. Notice that we have made an explicit choice about order, assuming the operands are arranged in a left-to-right ordering Overall, our syntax(see page 2 of the code)is defined by f expressions to deal with the list structure that is passed in to the evaluator. These procedures walk down the list structure to test for kind of expression, to get out pieces or otherwise manipulate that list structure Slide 16.2.5 Example- Changing Syntax The rest of the code on page 2 of the handout just fills out the rest of the details of the syntax, the representation of expressions. Look it over to be sure you understand it, but it is basically the same sort of material tagged lists for identifying types, list operations(car and cdr)to get out pieces As we said earlier, one of the reasons for using data abstractions everywhere within eval is to let us separate the syntax from the semantics Eval and apply defir The syntax tells us how to write legal expressions In this se semantics, how expressions get their values in this language anguage. By doing that separation, we can make changes to the syntax without affecting the semantics. Here is one such example Example-Changing Syntax Slide 16.2. 6 Suppose you wanted a verbose"application syntax Suppose I decide that rather than having the convention that the (CAIL ARGS ..) operator is the first subexpression of a combination, and the for example-(CALL (lambda (x)(.xx) ARGS 5) operands are all the other subexpressions, instead I want to be much more verbose. I might want expressions like the one shown here, explicitly identifying the procedure and the arguments. How would I make this change to my language?
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 16.2.4 And we will need routines that manipulate expressions, that is, walk along the expressions finding pieces. For example, if we are applying a procedure to a set of arguments, we need to get out different parts of the argument list. So we will have something to check if there are arguments, something to get the next operand, and something to get the other operands. This is just list structure that we are manipulating. Notice that we have made an explicit choice about order, assuming the operands are arranged in a left-to-right ordering. Overall, our syntax (see page 2 of the code) is defined by a set of expressions to deal with the list structure that is passed in to the evaluator. These procedures walk down the list structure to test for kind of expression, to get out pieces or otherwise manipulate that list structure. Slide 16.2.5 The rest of the code on page 2 of the handout just fills out the rest of the details of the syntax, the representation of expressions. Look it over to be sure you understand it, but it is basically the same sort of material: tagged lists for identifying types, list operations (car and cdr) to get out pieces. As we said earlier, one of the reasons for using data abstractions everywhere within eval is to let us separate the syntax from the semantics. Eval and apply define the semantics, how expressions get their values in this language. The syntax tells us how to write legal expressions in this language. By doing that separation, we can make changes to the syntax without affecting the semantics. Here is one such example. Slide 16.2.6 Suppose I decide that rather than having the convention that the operator is the first subexpression of a combination, and the operands are all the other subexpressions, instead I want to be much more verbose. I might want expressions like the one shown here, explicitly identifying the procedure and the arguments. How would I make this change to my language?
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 16.2.7 We have already hinted at the answer. All we need to do Example-Changing Syntax hange the syntax. For example, now checking to see if Suppose you wanted a " verbose"application syntax something is an application involves looking to see if the first (CALL ARGS ..) element of the list is the special symbol CALL. This is clearly for example-(cALL (ambda (x)(**)ARGs S) different from our earlier version, where we assumed any combination that was not a special form was an application Here, we are explicitly identifying applications Example-Changing Syntax Slide 16.2.8 Suppose you wanted a verbose"application syntax So how do i get out the pieces? Before, we would have gotter the operator as the first subexpression, here it is the second (CAIL ARGS ..) for example-(CALL (lambda (x)(. x x) ARGS 5) subexpression, since the first subexpression is the symbol CALL. And for the operands, we have to skip past the ARGS Changes-only in the syntax routines to get the right parts. Again, the key point: all I have changed the syntax, the routines that walk down the tree structure and pull out the pieces. Nothing has changed in valor apply Slide 16.2,9 Implementing"Syntactic sugar The second reason for separating syntax from semantics is that it allows us to easily accommodate alternative forms for mple fundamental" core "in the evaluator expressions. We often call this"syntactic sugar", meaning that Easy way to add alternative/convenient syntax? it looks nicer, but it actually just coats the same underlyi pplica idea, with a sweeter way of expressing the same thing. Let me let ( show you an example. Remember let? e2>)) We could treat let as a special form and write a handler for it. We could have something that handles dispatches, having (lambda ( ) ) that let is just a cleaner way of creating a procedure, then applying it to capture some local state variables Said another way, a let expression is really just the same as the expression shown here That is, we create a lambda, whose argument list is the same as the arguments for the bindings in the let, whose body is just the body of the let, and that lambda would then be applied to expressions whose values we want to bind to those names. These are equivalent forms. as we saw in the environment model, they create exactly the same kind of structure So rather than building a special form for let, let's see how we could use syntax and syntactical manipulation to convert this form of let into an application of a procedure to a set of arguments
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 16.2.7 We have already hinted at the answer. All we need to do is change the syntax. For example, now checking to see if something is an application involves looking to see if the first element of the list is the special symbol CALL. This is clearly different from our earlier version, where we assumed any combination that was not a special form was an application. Here, we are explicitly identifying applications. Slide 16.2.8 So how do I get out the pieces? Before, we would have gotten the operator as the first subexpression, here it is the second subexpression, since the first subexpression is the symbol CALL. And for the operands, we have to skip past the ARGS to get the right parts. Again, the key point: all I have changed is the syntax, the routines that walk down the tree structure and pull out the pieces. Nothing has changed in eval or apply. Slide 16.2.9 The second reason for separating syntax from semantics is that it allows us to easily accommodate alternative forms for expressions. We often call this "syntactic sugar", meaning that it looks nicer, but it actually just coats the same underlying idea, with a sweeter way of expressing the same thing. Let me show you an example. Remember let? We could treat let as a special form and write a handler for it. We could have something that handles dispatches, having detected expressions of this type (let). But we could also realize that let is just a cleaner way of creating a procedure, then applying it to capture some local state variables. Said another way, a let expression is really just the same as the expression shown here. That is, we create a lambda, whose argument list is the same as the arguments for the bindings in the let, whose body is just the body of the let, and that lambda would then be applied to expressions whose values we want to bind to those names. These are equivalent forms. As we saw in the environment model, they create exactly the same kind of structure. So rather than building a special form for let, let's see how we could use syntax and syntactical manipulation to convert this form of let into an application of a procedure to a set of arguments