6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.2.1 Let's deal with the second issue first. What changes should we How can we implement lazy evaluation? make to eval and app ly in order to implement this new (define (l-apply procedure arguments env) i changed (cond ((primiti ve-procedure? procedure) idea of normal order evaluation(sometimes also called lazy pply-primitive-procedure evaluation). Note that it is called lazy evaluation because we (Iist-of-arg-values argunents env))) are only evaluating arguments when required, either because we ((compound-procedure? procedure) need to print them out or because we are down to primitive (procedure-body procedure procedures. So what changes are needed? 1t一E-de1ayd- arga ar e1器e《 error" Unknown proc" procedure))) How can we implement lazy evaluation? Slide 17.2.2 changed Let's start with the application of a compound procedure (cond ((primitive-procedure? procedure) something we have built with a lambda. We know we want to evaluate the body of that procedure in a new environment (list-of-arg-valuesargumentsenv))) ((compound-procedure? procedure) but what should the environment do? Extend- environment should take the set of parameters of the (extend-environrent (procedure ocedure) procedure, but glue together with them, not with the actual values, but with a set of delayed arguments. And what is a rocedure-environment procedure)))) (e1器e《eror" Unknown proc"pr delayed argument? Let's create a structure that let's us hold off on getting the actual value of an argument. That makes if you think of our example. When we want to apply a procedure we want to take the argument expressions and substitute them into the body without evaluation, but as unevaluated tree structure So our change in apply ing a compound procedure is to still evaluate the body of the procedure in a new environment, but rather than binding the procedure's parameters to their actual values, we will bind them to these pecial structures that keep track of the expression to be evaluated when required, plus we will have to keep track of the environment in which that evaluation should take place when required Slide 17.2.3 How can we im plement lazy evaluation? That last point is worth stressing, because it is a change. Prior (define (I-apply procedure arguments changed to this, apply didn t need to know about it's environment spply-prinitive-procedure We simply applied a procedure to a set of argument values Here, because we delay getting the argument values, we need to arguments env))) keep track of the information needed to actually compute the alues when needed. meaning the environment in which the expression should be evaluated Thus we need to pass the environment in as an argument to app l y so that we can pass procedure-env⊥ conment pr。ee (e1器e( error" Unknown proc"pro。 edure))) through to the construction of the delayed evaluation objects
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.2.1 Let's deal with the second issue first. What changes should we make to eval and apply in order to implement this new idea of normal order evaluation (sometimes also called lazy evaluation). Note that it is called lazy evaluation because we are only evaluating arguments when required, either because we need to print them out or because we are down to primitive procedures. So what changes are needed? Slide 17.2.2 Let's start with the application of a compound procedure, something we have built with a lambda. We know we want to evaluate the body of that procedure in a new environment, but what should the environment do? Extendenvironment should take the set of parameters of the procedure, but glue together with them, not with the actual values, but with a set of delayed arguments. And what is a delayed argument? Let’s create a structure that let's us hold off on getting the actual value of an argument. That makes sense if you think of our example. When we want to apply a procedure, we want to take the argument expressions and substitute them into the body without evaluation, but as unevaluated tree structure. So our change in applying a compound procedure is to still evaluate the body of the procedure in a new environment, but rather than binding the procedure's parameters to their actual values, we will bind them to these special structures that keep track of the expression to be evaluated when required, plus we will have to keep track of the environment in which that evaluation should take place, when required. Slide 17.2.3 That last point is worth stressing, because it is a change. Prior to this, apply didn't need to know about it's environment. We simply applied a procedure to a set of argument values. Here, because we delay getting the argument values, we need to keep track of the information needed to actually compute the values when needed, meaning the environment in which the expression should be evaluated. Thus we need to pass the environment in as an argument to apply so that we can pass it through to the construction of the delayed evaluation objects
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 17.2.4 How can we implement lazy evaluation? So with this change, compound procedure application will define (l-apply procedure arguments Env: changed correctly delay the evaluation of the arguments. We will cond ((primitive-procedure? procedur apply-primitive-procedure implement list-of-delayed-arguments shortly. Conceptually, we know that it should simply take a list ((conpound -procedure? procedure of expressions, and glue onto these expressions a marker that dentifies them as delayed Ultimately, however, we will red ce to a primit else (error Unknown proc procedure))) the arguments applying a primitive procedure, we need to ensure that the I arguments are reduced to actual values. This means we will force any delayed evaluation to now take place. Here again we will need to pass the environment into the procedure list-of-arg-values because we are going to have to walk our way down this list of expressions, asking each to be evaluated with respect to the environment Slide 17.2.5 How can we implement lazy evaluation? Notice that we have made only a small number of chang (define (I-apply proc app ly now takes an environment as an argument (primitive-procedure? procedure) (apply-prinitive-procedure application of a compound procedure constructs a set of delayed expressions; and application of a primitive procedure cedar constructs a set of actual values by evaluating any delayed argument. We have to implement the procedures to delay and (procedure-body procedure) force evaluation, but otherwise we have a very small set of anges (procedure-environment procedur e1器e《 error" Unknown proc"pr。 cedure)) Slide 17.2.6 Most of the work is in l-apply need to call it with What else do we have to change? Since we have changed actual value for the operato apply (which we here call l-apply for lazy apply),we need to change the use of that procedure in eval(which we fine (l-eval exp er here call I-eval). But in fact most of the work is now in l cond((≡。1f-va1 latina?exp)·xp) app ly. Here we call it with the actual value of the operator, ((app1⊥ea but just the expressions for the other arguments, plus the environment (e1器e《 errOr" Unknowm expression”exp)))) So our change to l-eval is very simple. When we get to an application, we pass the actual value of the operator(which ))to l-apply But notice that we just pass in the other expressions as tree structure, with no evaluation Notice that this is the only change to l-eval. All other expressions are still handled exactly as before Also notice that when app ly takes in these arguments, it may further pass the delayed arguments along unevaluated(if the application involves another compound expression ). Only when app l y reaches a primitive application will it force the arguments to be evaluated
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 17.2.4 So with this change, compound procedure application will correctly delay the evaluation of the arguments. We will implement list-of-delayed-arguments shortly. Conceptually, we know that it should simply take a list of expressions, and glue onto these expressions a marker that identifies them as delayed. Ultimately, however, we will reduce to a primitive application, and in that case, we want to do the actual work of evaluating the arguments. Thus, our other change will be to require when applying a primitive procedure, we need to ensure that the arguments are reduced to actual values. This means we will force any delayed evaluation to now take place. Here again we will need to pass the environment into the procedure list-of-arg-values because we are going to have to walk our way down this list of expressions, asking each to be evaluated with respect to the environment. Slide 17.2.5 Notice that we have made only a small number of changes: apply now takes an environment as an argument; application of a compound procedure constructs a set of delayed expressions; and application of a primitive procedure constructs a set of actual values by evaluating any delayed argument. We have to implement the procedures to delay and force evaluation, but otherwise we have a very small set of changes. Slide 17.2.6 What else do we have to change? Since we have changed apply (which we here call l-apply for lazy apply), we need to change the use of that procedure in eval (which we here call l-eval). But in fact most of the work is now in lapply. Here we call it with the actual value of the operator, but just the expressions for the other arguments, plus the environment. So our change to l-eval is very simple. When we get to an application, we pass the actual value of the operator (which means we need to be sure to do the evaluation) to l-apply. But notice that we just pass in the other expressions as tree structure, with no evaluation. Notice that this is the only change to l-eval. All other expressions are still handled exactly as before. Also notice that when apply takes in these arguments, it may further pass the delayed arguments along unevaluated (if the application involves another compound expression). Only when apply reaches a primitive application will it force the arguments to be evaluated