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 <proc> ARGS <ard> <arg2>..) 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?