Stages of an interpreter 6 001 SICP Variations on a Scheme input to each stage average 4 5 5 Lexical analyzer average 4 Parser Beyond Scheme designing language variants Lazy evaluation Complete conversion normal order evaluator Upward compatible extension lazy lazy memo 5 symbol average 4 5 Evaluator Environment symbol Printer 7 7 1 40 Evaluation model Alternative models for computation Applicative Order evaluate all arguments then apply operator Normal Order go ahead and apply operator with unevaluated argument subexpressions evaluate a subexpression only when value is needed to print by primitive procedure that is primitive procedures are strict in their arguments 3 40 4 40 Applicative Order Example Normal Order Example define foo x write line inside foo x x define foo x write line inside foo x x foo begin write line eval arg 222 begin write line eval arg 222 foo begin write line eval arg 222 Evaluating argument to foo Evaluating second part of argument begin write line inside foo From body of foo 222 222 eval arg inside foo 2 40 Normal Order Lazy Evaluation Rules of evaluation If expression is self evaluating e g a number just return value If expression is a name look up value associated with that name in environment If expression is a lambda create procedure and return If expression is special form e g if follow specific rules for evaluating subexpressions If expression is a compound expression Evaluate subexpressions in any order If first subexpression is primitive or built in procedure just apply it to values of other subexpressions If first subexpression is compound procedure created by lambda evaluate the body of the procedure in a new environment which extends the environment of the procedure with a new frame in which the procedure s parameters are bound to the supplied arguments 222 5 5 begin write line inside foo begin w l eval arg 222 begin w l eval arg 222 inside foo eval arg We first evaluated argument then substituted value into the body of the procedure From body of foo As if we substituted the unevaluated expression in the body of the procedure eval arg 444 444 5 40 6 40 1 Normal order lazy evaluation versus applicative order How can we implement lazy evaluation How can we change our evaluator to use normal order Create delayed objects expressions whose evaluation has been deferred Change the evaluator to force evaluation only when needed Why is normal order useful What kinds of computations does it make easier define l apply procedure arguments env changed cond primitive procedure procedure apply primitive procedure procedure list of arg values arguments env compound procedure procedure l eval sequence procedure body procedure extend environment procedure parameters procedure list of delayed args arguments env procedure environment procedure else error Unknown proc procedure 7 40 Lazy Evaluation l eval 8 40 Meval versus L Eval Most of the work is in l apply need to call it with actual value for the operator just expressions for the operands the environment define l eval exp env cond self evaluating exp exp application exp l apply actual value operator exp env operands exp env else error Unknown expression exp define meval exp env cond self evaluating exp exp cond exp meval cond if exp env application exp mapply meval operator exp env list of values operands exp env else error Unknown expression type EVAL exp define l eval exp env cond self evaluating exp exp cond Exp application exp l apply actual value operator exp env operands exp env else error Unknown expression exp 9 40 Actual vs Delayed Values 10 40 Representing Thunks define actual value exp env force it l eval exp env Abstractly a thunk is a promise to return a value when later needed forced define list of arg values exps env Used when applying a primitive procedure if no operands exps cons actual value first operand exps env list of arg values rest operands exps env Concretely our representation thunk exp env define list of delayed args exps env Used when applying a if no operands exps compound procedure cons delay it first operand exps env list of delayed args rest operands exps env 11 40 12 40 2 Thunks delay it and force it Memo izing evaluation define define define define In lazy evaluation if we reuse an argument have to reevaluate each time In normal evaluation argument is evaluated once and just referenced Can we keep track of values once we ve obtained them and avoid cost of reevaluation delay it exp env list thunk exp env thunk obj tagged list obj thunk thunk exp thunk cadr thunk thunk env thunk caddr thunk define force it obj cond thunk obj actual value thunk exp obj thunk env obj else obj define actual value exp env force it l eval exp env 13 40 14 40 Memo izing Thunks Thunks Memoizing Implementation Idea once thunk exp has been evaluated remember it define evaluated thunk obj tagged list obj evaluated thunk define thunk value evaluated thunk cadr evaluated thunk If value is needed again just return it rather than recompute Concretely mutate a thunk into an evaluated thunk thunk exp env evaluated result thunk define force it obj cond thunk obj let result actual value thunk exp obj thunk env obj set car obj evaluated thunk set car cdr obj result set cdr cdr obj result evaluated thunk obj thunk value obj else obj 15 40 16 40 Lazy Evaluation other changes needed Laziness and Language Design Example need actual predicate value in conditional if We have a dilemma with lazy evaluation Advantage only do work when value actually needed Disadvantages not sure when expression will be evaluated can be very big issue in a language with side effects may evaluate same expression more than once define l eval if exp env if true actual value if predicate exp env l eval if consequent exp env l eval if alternative exp env Example don t need actual value in assignment define l eval assignment exp env set variable value assignment variable exp l eval assignment value exp env env ok Memoization doesn t fully resolve our dilemma Advantage Evaluate expression at most once Disadvantage What if we want evaluation on each use Alternative approach give programmer control 17 40 18 40 3 Variable Declarations lazy and lazy memo Syntax Extensions Parameter Declarations Handle lazy and lazy memo extensions in an upwardcompatible fashion define first variable var decls car var decls define rest variables var decls cdr var decls define declaration pair lambda a b lazy c d lazy memo a c are normal variables evaluated before
View Full Document
Unlocking...