6.001 Recitation 24: Explicit Control EvaluatorRI: Gerald Dalley, [email protected], 10 May 2007http://people.csail.mit.edu/dalleyg/6.001/SP2007/Announcements• Next Monday/Tuesday: last tutorial• Next Wednesday: last recitation (exam review)• Next Thursday: last lecture• Exam:– Tues. 22 May, 1:30-4:30pm, Johnson Athletic Center.– 3 pages of notes are allowed.– Topics on the final will cover the entire semester (basic procedures, recursion/iteration, orders ofgrowth, HOPs, data structures), but significant parts will be from the last third of the courseafter Quiz 2 (OOP, evaluators, lazy evaluation with and without memoization, streams, registermachines, etcifnextchar...).Explicit Control Evaluator: The Important ContractsFunction Assumptions Promiseseval-dispatch• expression in exp,• environment in env,• return address in continue• end up at continue• result in valapply-dispatch• procedure to be applied in proc,• list of arguments in argl,• return address at the top of the stack• top of stack popped,• stack top → end address• result in valeval-sequence• sequence of expressions in unev,• environment in env,• return address at the top of the stack• eval the expressions in sequence,• top of stack popped,• stack top → end address• result of the final expression in valCalling ConventionsIn general, a call to eval-dispatch should look like this:< save registe rs whose values are ne ed ed later >( assign exp < exp ressi on to evaluate >)( assign env < env ironm ent in which to evaluate express ion >)( assign cont inue <label >)( goto e val-d isp atch )<label >< restore any saved registers >< use the expre ssion value st ored in val >But often exp, env, and/or continue already have the proper value.eval-sequence and apply-dispatch use a different convention/contract for storing the return point (continue).this is just a performance optimization to minimize use of the stack (tail recursion).1Adding AND to the Explicit Control EvaluatorLet’s add the special form and to the explicit control evaluator. For simplicity, we’ll only worry about andsof two s ub-expressions. Assume that we have primitive ops and-first-exp and and-second-exp. first we add aclause to eval-dispatch:eval- dis patch...( test ( op and ?) ( reg exp ))( branch ( label ev-and ))...Fill in the blanks b elow:ev -a nd1 ( assign unev M )2 ( assign exp M )3 ( save con ti nue )4 ( save env)5 ( save unev )6 ( assign cont inue e val -af ter -fi rst )7 ( goto M )eva l-aft er- fir st8 ( r es tore M )9 ( r es tore M )10 ( test ( op true ?) ( reg val ))11 ( branch (label e val -se cond- arg ))12 ( assign val #f)13 ( restore M )14 ( goto ( reg con tinue ))eva l-sec ond -ar g15 ( assign exp M )16 ( assign conti nue aft er-se cond )17 ( goto M )after -se co nd18 M19 ( goto ( reg con tinue ))Hand evaluate the expression (and #t (and #f #t))exp env continue val unev stack (gr ows right) pc(and #t (and #f #t)) GE halt eval-dispatch(and #t (and #f #t)) GE halt ev-and#t GE eval-after-first (and #f #t) halt GE (and #f #t) eval-dispatch#t GE eval-after-first (and #f #t) halt GE (and #f #t) ev-self-eval#t GE eval-after-first #t (and #f #t) halt GE (and #f #t) eval-after-first#t GE eval-after-first #t (and #f #t) halt eval-second-arg(and #f #t) GE after-second #t (and #f #t) halt eval-dispatch(and #f #t) GE after-second #t (and #f #t) halt ev-and#f GE eval-after-first #t #t halt after-second GE #t eval-dispatch#f GE eval-after-first #t #t halt after-second GE #t ev-self-eval#f GE eval-after-first #f #t halt after-second GE #t eval-after-first#f GE after-second #f #t halt after-second#f GE halt #f #t halt2Does this ev-and routine handle tail recursion? Compare the behavior of regular scheme and our explicitcontrol evaluator when evaluating the expressions below.( define ( list ? x )( or ( null ? x )( and ( pair ? x) ( list ? ( cdr x )))))( define z ( list 1))( s et -cdr ! z z)( list ? z)How could we change the code above so that it handles tail-recursion? Hint: remove lines 16 through 19 andadd tw o lines in their place.• new 16: M• new 17: MCan we get rid of the new line 16 by moving another line somewhere?Could we remove line 12 without changing the value returned by the code? Why or why not?How can we get rid of line 15 by changing another line?To be continued...Assume the Scheme expressions below are evaluated in sequence by eval-dispatch. Determine what label isin the continue register when eval-dispatch is called to evaluate the subexpressions. Assume that the continueregister contains the label halt when each top-level expression is evaluated.( if # f(+ 3 2)(* 3 2))• What’s the value in the continue register when #f is evaluated? M• What’s the value in the continue register when * is evaluated? M(+ (* x x ) (- 2))• What’s the value in the continue register when (* x x) is evaluated? M( define fact( lambda ( n )( if (= n 1)1(* n ( fact (- n 1))))))( fact 2)• What’s the value in the continue register when the if consequent 1 is evaluated? M• What’s the value in the continue register when 2 is evaluated? M( define i fact( lambda ( n product )( if (= n 1)pr oduct( ifact (- n 1) (* n pr oduct )))))( ifact 2 1)• What’s the value in the continue register when the if consequent product is evaluated? M• What’s the value in the continue register when 1 is evaluated? M3SolutionsAnnouncements• Next Monday/Tuesday: last tutorial• Next Wednesday: last recitation (exam review)• Next Thursday: last lecture• Exam:– Tues. 22 May, 1:30-4:30pm, Johnson Athletic Center.– 3 pages of notes are allowed.– Topics on the final will cover the entire semester (basic procedures, recursion/iteration, orders ofgrowth, HOPs, data structures), but significant parts will be from the last third of the courseafter Quiz 2 (OOP, evaluators, lazy evaluation with and without memoization, streams, registermachines, etcifnextchar...).Explicit Control Evaluator: The Important ContractsFunction Assumptions Promiseseval-dispatch• expression in exp,• environment in env,• return address in continue• end up at continue• result in valapply-dispatch• procedure to be applied in proc,• list of arguments in argl,• return address at the top of the stack• top of stack popped,• stack top → end address• result in valeval-sequence• sequence of expressions in unev,• environment in env,• return address at the top of the stack• eval the expressions in sequence,• top
View Full Document
Unlocking...