《Structure and Interpretation of Computer Programs》lecture 19 webhan

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.2.1 Our plan is to start by building an evaluator that handles 1. Arithmetic calculator arithmetic expressions, and in fact we will restrict ourselves just Want to evaluate arithmetic expressions of two arguments arithmetic expressions of two or fewer arguments. We would lke to be able to evaluate things like the example shown on the us*24(p1us*56)} slide: adding 24 to whatever we get by adding 5 and 6 Notice the at the end of the symbol p lus to indicate that this is something that we will build within our language Slide 15.2.2 1. Arithmetic calculator dand (wir e) teu? (car e)sm) And here is some code that captures how we will evaluate expressions of this form. This is identical to the code listed in he separate code handout, and I suggest you have that page 如B·e}) handy as we go through this development ea但1·24但56) Slide 15.2.3 Notice what we are doing here. We are using our knowledge of Scheme to describe the process of evaluating expressions in this (m:如如y( check .pisx h teur tca e)al new language. We are writing, in Scheme, the description of that process Okay, what do we need? We have a procedure for evaluating expressions in our new language, called eval. Notice its ewa1(1w2456) form. It has a way of dealing with the base case, which is an expression that just consists of a number. And to do that it uses type checking Then, we have a way of dealing with the compound case. Here, e it uses type checking to see if we have a sum and notice how this works. It uses the key word of the expression to determine the type of that expression. If the expression is a sum then we will just add, using the primitive operation of addition, the values of the subexpressions. But a ke oint arises here! To get those values we need to evaluate each subexpression as well, since we don't know at this stage if they are just numbers or are themselves compound expressions

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.2.1 Our plan is to start by building an evaluator that handles arithmetic expressions, and in fact we will restrict ourselves just arithmetic expressions of two or fewer arguments. We would like to be able to evaluate things like the example shown on the slide: adding 24 to whatever we get by adding 5 and 6. Notice the * at the end of the symbol plus to indicate that this is something that we will build within our language. Slide 15.2.2 And here is some code that captures how we will evaluate expressions of this form. This is identical to the code listed in the separate code handout, and I suggest you have that page handy as we go through this development. Slide 15.2.3 Notice what we are doing here. We are using our knowledge of Scheme to describe the process of evaluating expressions in this new language. We are writing, in Scheme, the description of that process. Okay, what do we need? We have a procedure for evaluating expressions in our new language, called eval. Notice its form. It has a way of dealing with the base case, which is an expression that just consists of a number. And to do that it uses type checking. Then, we have a way of dealing with the compound case. Here, it uses type checking to see if we have a sum and notice how this works. It uses the keyword of the expression to determine the type of that expression. If the expression is a sum then we will just add, using the primitive operation of addition, the values of the subexpressions. But a key point arises here! To get those values we need to evaluate each subexpression as well, since we don't know at this stage if they are just numbers or are themselves compound expressions

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.2.4 We are just walking through a tree Let's look at this in more detail. First, let's look at the input to this evaluation process. Remember that our expression, which we typed in, is converted into list structure, as a tree of symbols and numbers. It looks like what is shown on the slide. and this is what gets handed to the evaluator as a representation of our example expression. So let's treat this as if this exact tree structure were passed in to eval Slide 15.2.5 We are just walking through a tree And what does eval do with this input? Check the code on the handout eva l grabs the list and tests its tag. That means it first checks to see if this whole thing is a number. Since it is not, it takes the first element of this list structure and checks to see if it is the special symbol plus x [→“ 如m are just walking through a tree Slide 15.2.6 H+ Having done that it dispatches on type to the right procedure to handle this kind of expression. Having determine that it is sum by checking the tag, it sends it off to eval-sum, and (mn-→[团 We apply the procedure to the expression sum? checks the tag Slide 15.2.7 We are just walking through a tree o now eval has reduced this to applying eval-sum to →z the tree structure shown notice what the body ofeval sum does It walks down the tree, grabbing out subexpressions, that is the first and second components of this sum. Eval-sum then converts this into adding, using the built-in primitive, whatever I get by evaluating the first subexpression and whatever I get by evaluating the second subexpression

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.2.4 Let's look at this in more detail. First, let's look at the input to this evaluation process. Remember that our expression, which we typed in, is converted into list structure, as a tree of symbols and numbers. It looks like what is shown on the slide, and this is what gets handed to the evaluator as a representation of our example expression. So let's treat this as if this exact tree structure were passed in to eval. Slide 15.2.5 And what does eval do with this input? Check the code on the handout. Eval grabs the list and tests its tag. That means it first checks to see if this whole thing is a number. Since it is not, it takes the first element of this list structure and checks to see if it is the special symbol plus*. Slide 15.2.6 Having done that it dispatches on type to the right procedure to handle this kind of expression. Having determine that it is a sum by checking the tag, it sends it off to eval-sum, and this is (for now at least) just a normal procedure application. We apply the procedure to the expression. Slide 15.2.7 So now eval has reduced this to applying eval-sum to the tree structure shown. Notice what the body of eval￾sum does. It walks down the tree, grabbing out the two subexpressions, that is the first and second components of this sum. Eval-sum then converts this into adding, using the built-in primitive, whatever I get by evaluating the first subexpression and whatever I get by evaluating the second subexpression

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 152.8 We are just walking through a tree That leads to this form Notice what we have done we have amn→→[一 reduced evaluation of one expression into some simple primitive operations on evaluation of other subexpressions. And 日-团 what has that done? It has literally just walked down the tree structure that represents this expression, pulling out the right ((eval 24)(eval-4-4B-4u pieces It has used the tag to tell us who to send the expression to, and then it has simply grabbed cars and cdrs of the list structure and handed them off to new evaluations now at this stage, evaluating the first subexpression(eval 24) asy. We see from our code that it will use type checking to tm determine this is a number and simply return that expression And thats nice! This is just pointing to the number 2 4 so the number 24 gets returned What about the other piece? Slide 15.2,9 Well this just looks like the kind of expression we started with We are just walking through a tree We are evaluating some list structure that happens to represent →团 a sum. It's got a tag at the front to say it is one of these plus* expressions, so we can do exactly the same thing The evaluation of this expression will unwrap into an eval +(ea124)(evA1 sum of the same list structure. and that will reduce to a primitive application of t to whatever I get by evaluating the subexpressions, and that I get by walking down the tree, grabbing the right pieces, applying eval and getting back the We are just walking through a tree Slide 15.2.10 And now we see that we have unwrapped this abstraction down to some primitive operations, primitive application of addition E ra to some simple expressions, in this case just numbers And of ourse this will finally reduce to the answer we exl unwrapped it into successive evaluations until it reduces to a se of applications of primitive built-in procedures to primitive +(eva15)(eva16)) values

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.2.8 That leads to this form. Notice what we have done: we have reduced evaluation of one expression into some simple primitive operations on evaluation of other subexpressions. And what has that done? It has literally just walked down the tree structure that represents this expression, pulling out the right pieces. It has used the tag to tell us who to send the expression to, and then it has simply grabbed cars and cdrs of the list structure, and handed them off to new evaluations. Now at this stage, evaluating the first subexpression (eval 24) is easy. We see from our code that it will use type checking to determine this is a number and simply return that expression. And that’s nice! This is just pointing to the number 24 so the number 24 gets returned. What about the other piece? Slide 15.2.9 Well this just looks like the kind of expression we started with. We are evaluating some list structure that happens to represent a sum. It's got a tag at the front to say it is one of these plus* expressions, so we can do exactly the same thing. The evaluation of this expression will unwrap into an eval￾sum of the same list structure, and that will reduce to a primitive application of + to whatever I get by evaluating the subexpressions, and that I get by walking down the tree, grabbing the right pieces, applying eval and getting back the numbers. Slide 15.2.10 And now we see that we have unwrapped this abstraction down to some primitive operations, primitive application of addition to some simple expressions, in this case just numbers. And of course this will finally reduce to the answer we expect. However, a key thing to note is how this simple evaluator has taken in a tree structure representing an expression and has unwrapped it into successive evaluations until it reduces to a set of applications of primitive built-in procedures to primitive values

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.2.11 Since this is important, these stages of eval unwrapping into 1. Arithmetic calculator simpler and simpler things, and the dispatching on type to the correct procedure, let's look at this one more time. In this case What are the argument and return values of eval each let's focus on how eval unwinds the abstraction, and what time it is called in the evaluation of ine 17? values are returned at each stage of the evaluation. As before you may find it convenient to have a copy of the code in front of you as we go through this examination 1. Arithmetic calculator Slide 15.2.12 4(p1us*56}》) So we start with eval of this full expression. We,'ve put a he argument and return values of eval each in front of the expression to show that we want list structure time it is called in the evaluation of line 17? equivalent to this expression Thus we start with an eval of this expression (eval ,(plus* 24 (plus* 5 6)) Slide 15.2.13 Arithmetic calculator Eval first checks the type of this expression, deduces that it p1us*24(p1ust56》 is not a number, but is a sum(because of the type tag), so this expression gets dispatched to eval-sum. Eval sends the. What are the argument and return values of eval each expression to the procedure that is exactly set up to deal with this particular form of list structure eval-sum'(plus* 24 (plus* 56)) 4 1. Arith metic calculator Slide 15.2.14 p1us*24(p1us*56》) Now, eval-sum says, "go ahead and add whatever I get by What are the argument and return values of eval each evaling each of the pieces". We haven't actually specified ime it is called in the evaluation of line 17? in what order to do the subpieces, but for convenience assun hat it is done from left to right. So we now need to trace do the tree, and get(eval 24) Keval 24 wA1'(P1uB+24(u*56)}

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.2.11 Since this is important, these stages of eval unwrapping into simpler and simpler things, and the dispatching on type to the correct procedure, let's look at this one more time. In this case, let's focus on how eval unwinds the abstraction, and what values are returned at each stage of the evaluation. As before, you may find it convenient to have a copy of the code in front of you as we go through this examination. Slide 15.2.12 So we start with eval of this full expression. We've put a ' in front of the expression to show that we want list structure equivalent to this expression. Thus we start with an eval of this expression. Slide 15.2.13 Eval first checks the type of this expression, deduces that it is not a number, but is a sum (because of the type tag), so this expression gets dispatched to eval-sum. Eval sends the expression to the procedure that is exactly set up to deal with this particular form of list structure. Slide 15.2.14 Now, eval-sum says, "go ahead and add whatever I get by evaling each of the pieces". We haven't actually specified in what order to do the subpieces, but for convenience assume that it is done from left to right. So we now need to trace down the tree, and get (eval 24)

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.2.15 Eval once again checks the type of this expression, deducesArithmetic calculator it is a number, and just returns that expression, literally a p1us*24(p1us*56}) pointer to that thing which is an internal representation for the What are the argument and return values of eval each number 24 time it is called in the evaluation of ine 17? (424)24 W业1让(P124@L让+56 A'(p1u+24(1u+56) 1. Arithmetic calculator Slide 152.16 4(p1us*56}》) Next, eval has to evaluate the second subexpression, so this is the eval of the expression shown at top right. As before he argument and return values of eval each time it is called in the evaluation of line 17? we are going to dispatch on type, i. e. check to see what kind of beast"this is, deduce that it is a"sum"and therefore pass this on to the right procedure to handle sums Wa124 Slide 15.217 Arithmetic calculator Once more, eval-sum will reduce to applying the addition p1us*24(p1ust56》 operation to whatever it gets by evaluating the subpieces. Thus, we need to extract the subexpressions and once again apply What are the argument and return values of eval each time it is called in the evaluation of line 17? eval to them. Notice the nice recursive unwinding that is going on here a1u'(plus*56》) sva124)24 1-到让鼻'(Pu*241u*56) 1. Arith metic calculator Slide 15.2.18 p1us*24(p1us*56》) ell this just unwraps one more time. Again, we will apply What are the argument and return values of eval each to whatever we get by evaluating the two pieces, and eval in he evaluation of line 17? both cases just dispatches on type, determines the expression is a number and returns the expression as the value (ea15)5a66 va1-积‘(Plu56)) (42424(c4(1us56)) A1让'(P1*24@1划+56 wA1'(P1uB+24(u*56)}

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.2.15 Eval once again checks the type of this expression, deduces it is a number, and just returns that expression, literally a pointer to that thing which is an internal representation for the number 24. Slide 15.2.16 Next, eval has to evaluate the second subexpression, so this is the eval of the expression shown at top right. As before, we are going to dispatch on type, i.e. check to see what kind of "beast" this is, deduce that it is a "sum" and therefore pass this on to the right procedure to handle sums. Slide 15.2.17 Once more, eval-sum will reduce to applying the addition operation to whatever it gets by evaluating the subpieces. Thus, we need to extract the subexpressions and once again apply eval to them. Notice the nice recursive unwinding that is going on here. Slide 15.2.18 Well this just unwraps one more time. Again, we will apply + to whatever we get by evaluating the two pieces, and eval in both cases just dispatches on type, determines the expression is a number and returns the expression as the value