《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 6.001 Notes: Section 15.1 Slide 15.1.1 Why do we need an interpreter? Our goal over the next few lectures is to build an interpreter which in a very basic sense is the ultimate in programming, since doing so will allow us to define our language This is a somewhat surprising statement. But, in fact, as we will see through these lectures, it really is correct. The reason it is correct is the following Every expression we write in our language has a meaning associated with it. Deducing the meaning associated with an expression is the process of evaluation. And therefore, if we can define the program that executes that deduction for us, our definition of that program (i.e. our definition of the interpreter) provides for us the exact specification of what's legal in our anguage and how to deduce meanings of expressions within our language Our goal is to work through this understanding in stages. We will explore a series of examples, initially some very simple examples, but culminating in a full-scale Scheme evaluator. We are going work our way up to this, letting you see how to add the different pieces into an interpreter Before you proceed, however, there is a code handout that goes with this lecture. I suggest that you stop, go back to the web page, and print out a copy of the code to have next to you as we go through the lecture Why do we need an interpreter? Slide 15.1.2 First, let's set the stage for why we want to do this, why do we modules t want to build an interpreter? Why do we need an interpreter? Think about what we have seen so far in this course we have spent a lot of time talking about, and using, the ideas of abstraction, both procedural and data. We know that this is a powerful idea, as it lets us bury details, and it certainly suppor the expression of ideas at an appropriate level. Said another way, we can think about what we want to do and separate that from the details of how to actually make it happen

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 15.1 Slide 15.1.1 Our goal over the next few lectures is to build an interpreter, which in a very basic sense is the ultimate in programming, since doing so will allow us to define our language. This is a somewhat surprising statement. But, in fact, as we will see through these lectures, it really is correct. The reason it is correct is the following: Every expression we write in our language has a meaning associated with it. Deducing the meaning associated with an expression is the process of evaluation. And therefore, if we can define the program that executes that deduction for us, our definition of that program (i.e. our definition of the interpreter) provides for us the exact specification of what's legal in our language and how to deduce meanings of expressions within our language. Our goal is to work through this understanding in stages. We will explore a series of examples, initially some very simple examples, but culminating in a full-scale Scheme evaluator. We are going work our way up to this, letting you see how to add the different pieces into an interpreter. Before you proceed, however, there is a code handout that goes with this lecture. I suggest that you stop, go back to the web page, and print out a copy of the code to have next to you as we go through the lecture. Slide 15.1.2 First, let's set the stage for why we want to do this, why do we want to build an interpreter? Why do we need an interpreter? Think about what we have seen so far in this course. We have spent a lot of time talking about, and using, the ideas of abstraction, both procedural and data. We know that this is a powerful idea, as it lets us bury details, and it certainly supports the expression of ideas at an appropriate level. Said another way, we can think about what we want to do and separate that from the details of how to actually make it happen

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.1.3 But eventually, we need a process for unwinding all of those Why do we need an interpreter? abstractions, to get the value that corresponds to an expression's. Abstractions let us bury details and focus on use of meaning. That means we need to implement semantics of modules to sole large systems Interpreting expressions Need to unwind abstractions at execution time to deduce Why do we need an interpreter? Slide 15.1. 4 Abstractions let us bury details and focus on use of Notice the words I used. I said, "we need a process for modules to sole large systems unwinding those abstractions".If we can have such a process, Need to unwind abstractions at execution time to deduce hen we should be able to describe it in a procedure: that is our meaning language for describing processes Have seen such a process- Environment Model In fact, you have already seen a version of this description, just not as a procedure. what was the description?.the ow want to describe that process as a procedure environment model! If you think about it that makes sense. The environment model just described the process for how to determine a meaning I associated with an expression, which in turn just unwrapped the abstractions down to the primitive operations. Today, we want to talk about how to actually build an evaluator as a procedure rather than as that abstract environment model Slide 15.1 Stages of an interpreter First, what are the stages of an interpreter? For the kind of Lexical analy? languages we are considering, Scheme or Lisp like languages, typically there are five stages. There is a lexical analyzer, a Parse parser, an evaluator that typically works hand-in-hand with an environment, and there is a printer Evaluator Let's look at what goes on in each of these at a high level, before we build them evironment

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.1.3 But eventually, we need a process for unwinding all of those abstractions, to get the value that corresponds to an expression’s meaning. That means we need to implement semantics of interpreting expressions. Slide 15.1.4 Notice the words I used. I said, "we need a process for unwinding those abstractions". If we can have such a process, then we should be able to describe it in a procedure: that is our language for describing processes. In fact, you have already seen a version of this description, just not as a procedure. What was the description? ... the environment model! If you think about it, that makes sense. The environment model just described the process for how to determine a meaning associated with an expression, which in turn just unwrapped the abstractions down to the primitive operations. Today, we want to talk about how to actually build an evaluator as a procedure rather than as that abstract environment model. Slide 15.1.5 First, what are the stages of an interpreter? For the kind of languages we are considering, Scheme or Lisp like languages, typically there are five stages. There is a lexical analyzer, a parser, an evaluator that typically works hand-in-hand with an environment, and there is a printer. Let's look at what goes on in each of these at a high level, before we build them

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.1.6 Stages of an interpreter Linput to each stage To do that, let's talk about the input and output characteristics Lexical analyzer of each of them By focusing on the input to each successive stage in the interpretation, we can get a sense of what should happen at each stage, and thus get a sense of how to build an interpreter Eva1uat。r Environmen p⊥nte Slide 15.1.7 Stages of an interpreter input to each stage The initial input is a string of characters, which represents the Lexical analyzer) "(average 4(+55)) typewritten version of the expression we want to evaluate. Th is exactly the thing that we would type in at a terminal if we Parser wanted to have an expression evaluated So the initial input is a tring of characters Evaluato Printer Stages of an interpreter input to each stage Slide 15.1. 8 Lexical analy: r(average 4(+ 55))" The first step is to use a lexical analyzer to convert that string of characters into units or words This is shown here. where the average Parser string gets converted into a set of words or isolated characters like"("and")"and+and numbers. Thus the input to the next Evaluator stage is an ordered sequence of these units or words Env⊥ ronment Printer Slide 15.1.9 Stages of an interpreter input to each stage The second stage then parses those words into a structure that Lexical analyzer) "(average 4(+55) we can use for evaluation. In particular, we convert the linear sequence of words into a tree structure. We are using pairs here Parser for convenience but that is not required we could use any other 回国国 representation of trees as well Evaluator As we do this, we are going convert the self-evaluating expressions into their internal values So notice the form we get Environment for the next stage: it's a tree structure, and hanging off of the symbol + leaves of the tree are numbers, symbols, or other objects that Printer are represented as basic words. This is the input to the next

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.1.6 To do that, let's talk about the input and output characteristics of each of them. By focusing on the input to each successive stage in the interpretation, we can get a sense of what should happen at each stage, and thus get a sense of how to build an interpreter. Slide 15.1.7 The initial input is a string of characters, which represents the typewritten version of the expression we want to evaluate. This is exactly the thing that we would type in at a terminal if we wanted to have an expression evaluated. So the initial input is a string of characters. Slide 15.1.8 The first step is to use a lexical analyzer to convert that string of characters into units or words. This is shown here, where the string gets converted into a set of words or isolated characters like "(" and ")" and "+" and numbers. Thus the input to the next stage is an ordered sequence of these units or words. Slide 15.1.9 The second stage then parses those words into a structure that we can use for evaluation. In particular, we convert the linear sequence of words into a tree structure. We are using pairs here for convenience but that is not required. We could use any other representation of trees as well. As we do this, we are going convert the self-evaluating expressions into their internal values. So notice the form we get for the next stage: it's a tree structure, and hanging off of the leaves of the tree are numbers, symbols, or other objects that are represented as basic words. This is the input to the next stage

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Stages of an interpreter input to each stage Slide 15.1.10 Lexical a (average 4 (+ 55)) Now comes the heart of the interpreter. We want to take that tree structure and deduce its value. first. notice the form of tree (Parser structure. We will talk about this in detail later, but you can 回回 the parser has converted to a tree Evaluator Every time we see an"(", indicating the beginning of a new Environment we build up a tree where each horizontal slice through the tree Printer corresponds to some combination. Now what is the evaluator m supposed to do? It wants to take that tree structure, plus an environment,and interpret it. And what does that mean? Thin of the environment as a way of associating names with more primitive values. It acts much like a dictionary. The evaluator will use a set of rules to walk through this tree, looking up values associated with symbols from the environment, i.e. from that dictionary, and then using the rules to reduce complex expressions to simpler things culminating in some simple value that we will return 15.L.11 Stages of an interpreter input to each stage] value becomes input to the final stage. The printer simply Lexical analyzer) "(average 4(+55)) converts things back into the appropriate form for display on the monitor and then Parse 凹回回 Eva1uat⊙ symbol Environment avera symbol+5 7 Stages of an interpreter input to each stage Slide 15.1.12 Lexical analyzer m(average 4(+ 55)) that just gets displayed to the user average arser Eva1uat。r 口→[团 ment) Bera Printer 7

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.1.10 Now comes the heart of the interpreter. We want to take that tree structure and deduce its value. First, notice the form of tree structure. We will talk about this in detail later, but you can already see how the parser has converted things into a tree. Every time we see an "(", indicating the beginning of a new combination, we have created a new list structure. If the parser is already inside a list structure, it drops down a level, so that we build up a tree where each horizontal slice through the tree corresponds to some combination. Now what is the evaluator supposed to do? It wants to take that tree structure, plus an environment, and interpret it. And what does that mean? Think of the environment as a way of associating names with more primitive values. It acts much like a dictionary. The evaluator will use a set of rules to walk through this tree, looking up values associated with symbols from the environment, i.e. from that dictionary, and then using the rules to reduce complex expressions to simpler things, culminating in some simple value that we will return. Slide 15.1.11 That value becomes input to the final stage. The printer simply converts things back into the appropriate form for display on the monitor, and then ... Slide 15.1.12 ... that just gets displayed to the user

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 15.1.13 So here is a summary of that process in words Role of each part of the interpreter break up input string into"words"called tokens Parser also convert self-evaluating tokens to their internal values #f is converted to the internal false value Printe convert value to human-readable output string Goal of this lecture Slide 15.1.14 lement an interpreter for a programming language Our goal is to implement an interpreter. Actually, that's not quite right. Our goal is for you to understand what goes into an Only write evaluator and environment use schemes reader for lexical analysis and parsing interpreter, which we will explore by implementing one. Since use scheme's printer for output the key part of an interpreter, the crucial part, is the evaluator, to do this, our language must look like scheme we are going to concentrate almost exclusively on that. We are going to use Scheme for all the rest of the pieces, that is, we All names end with a star will use Scheme's lexical analyzer and parser, and Scheme's Start with a simple calculator for arithmeti printer, rather than building them from scratch. This means of Progressively add scheme* features course that we will need to create an evaluator for a language that looks a lot like scheme in the sense of having a tree structure as the output of its parser and a set of rules for manipulating that tree structure, as the way of dealing with the actual evaluation. It also says that the syntax of the language we are going to use to demonstrate an interpreter will need to look at lot like Scheme, in terms of things lke using parentheses to delimit expressions and other related issues We say this because we don,'t want you to get confused between what is going in Scheme and the general ideas of building an evaluator and interpreter. Our goal is to build an interpreter, especially the evaluator part, and let you going to build our own simple language and its evaluator For convenience, we are going to call this language are see how that occurs and use that to explore the idea of how these things implement the rules for a language. w Scheme*. It has a lot of the characteristics of Scheme, but we will use the convention that a* will be placed at the end of every expression in our language, to distinguish it from the corresponding Scheme expression We'll start with a simple evaluator and work our way up The first simple evaluator will be one that handles simple arithmetic expressions 6.001 Notes: Section 15.2

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 15.1.13 So here is a summary of that process in words. Slide 15.1.14 Our goal is to implement an interpreter. Actually, that's not quite right. Our goal is for you to understand what goes into an interpreter, which we will explore by implementing one. Since the key part of an interpreter, the crucial part, is the evaluator, we are going to concentrate almost exclusively on that. We are going to use Scheme for all the rest of the pieces, that is, we will use Scheme's lexical analyzer and parser, and Scheme's printer, rather than building them from scratch. This means of course that we will need to create an evaluator for a language that looks a lot like Scheme in the sense of having a tree structure as the output of its parser and a set of rules for manipulating that tree structure, as the way of dealing with the actual evaluation. It also says that the syntax of the language we are going to use to demonstrate an interpreter will need to look at lot like Scheme, in terms of things like using parentheses to delimit expressions and other related issues. We say this because we don't want you to get confused between what is going in Scheme and the general ideas of building an evaluator and interpreter. Our goal is to build an interpreter, especially the evaluator part, and let you see how that occurs and use that to explore the idea of how these things implement the rules for a language. We are going to build our own simple language and its evaluator. For convenience, we are going to call this language, Scheme*. It has a lot of the characteristics of Scheme, but we will use the convention that a * will be placed at the end of every expression in our language, to distinguish it from the corresponding Scheme expression. We'll start with a simple evaluator and work our way up. The first simple evaluator will be one that handles simple arithmetic expressions. 6.001 Notes: Section 15.2

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