11/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 topic27/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 procedureEnv → anytypeEPanalyze: 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)313/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 phase419/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-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))))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 really?• Suppose you were a circuit designer• Given a circuit diagram, you could transform it into an electricsignal encoding the layout of the diagram• Now suppose you wanted to build a circuit that could take any such signal as input (any other circuit) and could then reconfigure itself to simulate that input circuit• What would this general circuit look like???• Suppose instead you describe a circuit as a program• Can you build a program that takes any program as input and reconfigures itself to simulate that input program?• Sure – that’s just EVAL!! – it’s a UNIVERSAL MACHINE525/33It wasn’t always this obvious• “If it should turn out that the basic logics of a machine designed for the numerical solution of differential equations coincide with the logics of a machine intended to make bills for a department store, I would regard this as the most amazing coincidence that I have ever encountered”Howard Aiken, writing in 1956 (designer of the Mark I “Electronic Brain”, developed jointly by IBM
View Full Document
Unlocking...