Evaluation and universal machinesThe Eval/Apply CycleExamining the role of EvalEval from perspective of language designerstatic analysis: work done before executionReasons to do static analysisEval is expensiveSummary of part 1Strategy of the analyze evaluatorExample of analyze: variable name lookupImplementing variable name lookupImplementing number analysisSummary of part 2Subexpressions (hardest concept today)Implementation of analyze-ifVisualization of analyze-ifYour turnImplementation of analyze-definitionSummary of part 3Implementing lambdaImplementing apply: execution phaseImplementing apply: analysis phaseSummary of part 4What is Eval really?It wasn’t always this obviousWhy a Universal Machine?Turing’s insightSlide 28Slide 29The halting problemThe Halting theoremTuring’s historySlide 331/33Evaluation and universal machines•What is the role of evaluation in defining a language?•How can we use evaluation to design a language?2/33The 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 & args3/33Examining the role of Eval•From perspective of a language designer•From perspective of a theoretician4/33Eval from perspective of language designer•Applicative order•Dynamic vs. lexical scoping•Lazy evaluation•Full normal order•By specifying arguments•Just for pairs•Decoupling analysis from evaluation5/33static analysis: work done before execution•straight interpreter•advanced interpreteror compilerinterpreterexpressionenvironmentvaluestaticanalysisexprenvironmentvalueexecution6/33Reasons 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 topic7/33Eval is expensive(eval '(define (fact n) (if (= n 1) 1 (* n (fact (- n 1))))) GE) ==> undef... (eval '(fact 4) GE) ...... (eval '(= n 1) E1) ...which executes the case statement in eval four times... (eval '(fact 3) E1) ... ... (eval '(= n 1) E2) ...which executes the case statement in eval four times•The analyze evaluator avoids this cost8/33Summary of part 1•static analysis•work done before execution•performance•catch mistakes•prove program properties•analyze evaluator•static analysis: eliminate execution cost of eval9/33Strategy of the analyze evaluatoranalyzeexprenvironmentvalueexecutionExecution procedure a scheme procedure Env anytype EPanalyze: expression (Env anytype) (define (a-eval exp env) ((analyze exp) env))10/33Example of analyze: variable name lookupanalyzepienvironmentpi 3.143.14executionp: envb: (lookup name env)name pischeme'senvironmentevaluatordata structfoofoo11/33Implementing variable name lookup(define (analyze exp) (cond ((number? exp) (analyze-number exp)) ((variable? exp) (analyze-variable exp)) ... ))(define (analyze-variable exp) (lambda (env) (lookup-variable exp env)))(black: analysis phase) (blue: execution phase)12/33Implementing number analysis•Implementing analyze-number is also easy(define (analyze-number exp)(lambda (env) exp))(black: analysis phase) (blue: execution phase)13/33Summary of part 2•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 phase14/33Subexpressions (hardest concept today)(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)15/33Implementation 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 phase16/33Visualization of analyze-ifanalyze(if (= n 1) 1 (* n (...)))p: envb: (if (true? (pproc env)) (cproc env) (aproc env))pproc ...cprocaproc ...p: envb: expexp 117/33Your turn•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 expression18/33Implementation 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 phase19/33Summary of part 3•Within analyze•recursively call analyze on subexpressions •create an execution procedure which stores the EPs for subexpressions as local state20/33Implementing lambda•Body stored in double bubble is an execution procedure•old make-procedure list<symbol>, expression, Env Procedure•new make-procedure list<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))))21/33Implementing 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 ...)))22/33Implementing apply: analysis phase(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)))))23/33Summary of part 4•In the analyze evaluator, •double bubble stores execution procedure, not expression24/33What is Eval
View Full Document
Unlocking...