116.001 SICPAnalyze Eval and Computability• One more variant: Analyze evaluator• Does every expression stand for a value?• Are there things we can't compute?• Summary2Hi Prof. Grimson and Prof. Darrell, So far, your class has a response rate of 29%. However, we're aiming to get at least 50% for each class. Please send out another email to your classlist, and stress how valuable their feedback is to both the instructors and future students of 6.001. Also, remind them that they can win VI Socks! The URL is http://ug.mit.eduThanks for your cooperation! Brian 3The Eval/Apply Cycle• Eval and Apply execute a cycle that unwinds our abstractions• Reduces to simple applications of built in procedure to primitive data structures•Key:• Evaluator determines meaning of programs (and hence our language)• Evaluator is just another program!!EvalExp & envApplyProc & args4Examining the role of Eval• From perspective of a language designer• From perspective of a theoretician5Eval from perspective of language designer• Dynamic vs. lexical scoping• Applicative order vs. Lazy evaluation• Full normal order• By specifying arguments• Just for pairs• Decoupling analysis from evaluation6Eval is expensive (and not very clever)(define (foo n)(cond ((= 0 n) . . .)(else (set! x (bar n))(foo (bar n)))))in eval: ((assignment? exp) (eval-assignmt exp env))(define (assignment? exp) (tagged-list? exp ’set!))(define (eval-assignmt exp env)(set-variable-value! (assignmt-variable exp)(eval (assignmt-value exp) env)env))• Sure be nice to avoid this cost.27Eval is expensive (and not very clever)(define (fact n) (if (= n 1) 1 (* n (fact - n 1))))8static analysis: work done before execution• straight interpreter• advanced interpreteror compilerinterpreterexpressionenvironmentvaluestaticanalysisexprenvironmentvalueexecution9Reasons to do static analysis• Improve execution performance• avoid repeating work if expression contains loops• simplify execution engine• Catch common mistakes early• garbled expression• operand of incorrect type• wrong number of operands to procedure• Prove properties of program• will be fast enough, won't run out of memory, etc.• significant current research topic10Strategy of the analyze evaluatoranalyzeexprenvironmentvalueexecutionExecution procedure a scheme procedureEnv → anytypeEPanalyze: expression → (Env → anytype)(define (a-eval exp env)((analyze exp) env))11Implementing analyze(define (analyze exp)(cond((number? exp) (analyze-number exp))((variable? exp) (analyze-variable exp))((assignment? exp) (analyze-assignmt exp))...))12Implementing number analysis• analyze-number is easy(define (analyze-number exp)(lambda (env) exp))(black: analysis phase) (blue: execution phase)(define (a-eval exp env)((analyze exp) env))313Analyzing definitions• Assume the following procedures for definitions like(define x (+ y 1))(definition-variable exp) x(definition-value exp) (+ y 1)(define-variable! name value env) add bindingto env• Implement analyze-definition• The only execution-phase work is define-variable!• The definition-value might be an arbitrary expression14Implementation of analyze-definition(define (analyze-definition exp)(let ((var (definition-variable exp))(vproc (analyze (definition-value exp))))(lambda (env)(define-variable! var (vproc env) env))))black: analysis phase blue: execution phase(define (a-eval exp env)((analyze exp) env))15Implementation of analyze-assignmt(define (analyze-assignmt exp)(let ((var (assignmt-variable exp))(vproc (analyze (assignmt-value exp))))(lambda (env)(set-variable! var (vproc env) env))))black: analysis phase blue: execution phase(define (a-eval exp env)((analyze exp) env))16Example of analyze: variable name lookupanalyzepienvironmentpi 3.143.14executionp: envb: (lookup name env)name pischeme'senvironmentevaluatordata structfoofoo17Subexpressions(analyze '(if (= n 1) 1 (* n (...))))• analysis phase:(analyze '(= n 1)) ==> pproc(analyze 1) ==> cproc(analyze '(* n (...)))==> aproc• execution phase(pproc env) ==> #t or #f (depending on n)if #t, (cproc env)if #f, (aproc env)18Implementation of analyze-if(define (analyze-if exp)(let ((pproc (analyze (if-predicate exp)))(cproc (analyze (if-consequent exp)))(aproc (analyze (if-alternative exp))))(lambda (env)(if (true? (pproc env))(cproc env)(aproc env)))))black: analysis phase blue: execution phase419Visualization of analyze-ifanalyze(if (= n 1)1(* n (...)))p: envb: (if (true? (pproc env))(cproc env)(aproc env))pproc ...cprocaproc ...p: envb: expexp 120Implementing lambda• Body stored in double bubble is an execution procedure•old make-procedurelist<symbol>, expression, Env → Procedure• new make-procedurelist<symbol>, (Env->anytype), Env → Procedure(define (analyze-lambda exp)(let ((vars (lambda-parameters exp))(bproc (analyze (lambda-body exp))))(lambda (env) (make-procedure vars bproc env))))21Implementing apply: analysis phase(apply (foo n) (bar x) (baz y))(define (analyze-application exp)(let ((fproc (analyze (operator exp)))(aprocs (map analyze (operands exp))))(lambda (env)(execute-application (fproc env)(map (lambda (aproc) (aproc env))aprocs)))))22Implementing apply: execution phase(define (execute-application proc args)(cond((primitive-procedure? proc) ...) ((compound-procedure? proc)((procedure-body proc)(extend-environment (parameters proc)args(environment proc))))(else ...)))23Summary• output of analyze is an execution procedure• given an environment• produces value of expression• within analyze• execution phase code appears inside (lambda (env) ...)• all other code runs during analysis phase• recursively call analyze on subexpressions• create an execution procedure which stores the EPs for subexpressions as local state• double bubble stores execution procedure, not expression24The dream of a universal machine…525The dream of a universal machineACME Universal machineIf you can say it, I can do it™A clock keeps time…A clock keeps time…A tide clock keeps track of tides…A tide clock keeps track of tides…A bright red Ferrari F-430…A bright red Ferrari F-430…EVAL26What is Eval really?•We do describe devices, in a language called Scheme• We have a machine that takes those descriptions and then behaves exactly as they specify•Evaltakes any program as input and reconfigures itself to simulate that input program• EVAL is a universal machine27It wasn’t always
View Full Document
Unlocking...