Evaluation and universal machines The Eval/Apply Cycle What is the role of evaluation in defining a language? Eval and Apply execute a cycle that unwinds our abstractions Reduces to simple applications of built in procedure to Evaluator determines meaning of programs(and hence ur language) Evaluator is just another program Examining the role of Eval Eval from perspective of language designer From perspective of a language designer From perspective of a theoretician Dynamic vs lexical scoping Lazy evaluation Full normal order By specifying arguments Just for pairs Decoupling analysis from evaluation static analysis: work done before execution Reasons to do static analysis env⊥ ronment avoid repeating work if expression contains loops simplify execution engine expression- interpreter Catch common mistakes early operand of incorrect type advanced interpreter environment wrong number of operands to procedure Prove properties of program will be fast enough, wont run out of memory, etc static expr-analysi execut⊥on
1 1/33 Evaluation and universal machines • What is the role of evaluation in defining a language? • How can we use evaluation to design a language? 2/33 The 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!! Eval Exp & env Apply Proc & args 3/33 Examining the role of Eval • From perspective of a language designer • From perspective of a theoretician 4/33 Eval 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 evaluation 5/33 static analysis: work done before execution • straight interpreter • advanced interpreter or compiler expression interpreter environment value static analysis expr environment execution value 6/33 Reasons 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 topic
Eval is expensive Summary of part 1 (eval .(define (fact n) static analysis (E(=n1)1(n(fact(-n1)))))GE) work done before execution (eval'(fact4)GE) catch mistakes (=n1)E1) which executes the case statement in eval four times (eva1·(fact3)E1 static analysis: eliminate execution cost of eval (eval .(a n 1) E2) which executes the case statement in eval four times The analyze evaluator avoids this cost Strategy of the analyze evaluator Example of analyze: variable name lookt environment environme 3.14 analyze H+EE→ execution Execution proced analyze execution+3.14 a scheme procedure analyze: expression→(Env→ anytype) ookup name env) efine (a-eval exp env ((analyze exp) env)) Implementing variable name lookup Implementing number analysis (define (analyze exp) Implementing analyze-number is also easy ((number? exp) (analyze-number exp) (define (analyze-number exp) ((variable? exp)(analyze- (black: analysis phase)(blue: execution phase (define (analyze-variable exp) (lambda (env) (lookup-variable exp env)) (black: analysis phase)(blue: execution phase 2
2 7/33 Eval 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 cost 8/33 Summary of part 1 • static analysis • work done before execution • performance • catch mistakes • prove program properties • analyze evaluator • static analysis: eliminate execution cost of eval 9/33 Strategy of the analyze evaluator expr analyze environment execution value Execution procedure a scheme procedure Env → anytype EP analyze: expression → (Env → anytype) (define (a-eval exp env) ((analyze exp) env)) 10/33 Example of analyze: variable name lookup pi analyze environment pi 3.14 execution 3.14 p: env b: (lookup name env) name pi scheme's environment evaluator data struct foo foo 11/33 Implementing 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/33 Implementing number analysis • Implementing analyze-number is also easy (define (analyze-number exp) (lambda (env) exp)) (black: analysis phase) (blue: execution phase)
Summary of part 2 Subexpressions (hardest concept today output of analyze is an execution procedure given an environment produces value of expression analysis phase alyze .(s n 1) aa> proc analyze 1) within analyze execution phase code appears inside execution phas all other code runs during analysis phase (pproc env)a>#t or #f(depending on n if# mplementation of analyze-if Visualization of analyze-if efine (analyze-if exp) 1 (let ((pproc (analyze (if-predicate exp))) (if(s n 1) proc (proc (analyze (if-consequent exp))) proc (aproc (analyze (if-alternative exp)))) (n(..))) aproc (ambda (env) (true? (pprc env)) analyze apr。eenv))))) blue: execution phase (if (true? (pprc env)) (aproc env)) Your turn Implementation of analyze-definition Assume the following procedures for definitions like (define x ( y 1)) (define (analyze-definition exp) (let ((var (definition-variable exp)) (definition-variable exp lyze (definition-value exp)))) (definition-value exp) (+y1) (lambd (define-variable! value env) add binding nv) env)))) env Implement analyze-definition black. a blue: execution phase The only execution-phase work is define-variable! The definition-value might be an arbitrary expression 3
3 13/33 Summary 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 phase 14/33 Subexpressions (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/33 Implementation 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 phase 16/33 Visualization of analyze-if analyze (if (= n 1) 1 (* n (...))) p: env b: (if (true? (pproc env)) (cproc env) (aproc env)) pproc ... cproc aproc ... p: env b: exp exp 1 17/33 Your 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 binding to env • Implement analyze-definition • The only execution-phase work is define-variable! • The definition-value might be an arbitrary expression 18/33 Implementation 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
Summary of part 3 Implementing lambda Within analyze Body stored in double bubble is an execution procedure cursively call analyze on subexpressions old make-procedure list, expression, Env- Procedure create an execution procedure which stores the EPs for subexpressions as local state new make-procedure listanytype), Env- Procedure proc (analyze (lambda-body exp))) (makke-procedure s bproc env))) Implementing apply: execution phase Implementing apply: analysis phase (define (execute-application proc args) (cond (define (analyze-application exp) ((primitive-procedure? proc) (let ((fproc (analyze (operator exp))) (aprocs (map analyze (operands exp)))) ((compound-procedure? proc) (lambda (env) ((procedure-body proc) (execute-application (extend-environment (parameters proc) (fproc env) (map (lambda (aproc) (aproc env)) )) Summary of part 4 What is Eval really? In the analyz Suppose you were a circuit design double bubble stores execution procedure, not Given a circuit diagram, you could transform it into an electric Now suppose you wanted to build a circuit that could take any such signal as input(any other circuit) and could then configure 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 inp and reconfigures itself to simulate that input program Sure-that's just EVALll-it's a UNIVERSAL MACHINE
4 19/33 Summary of part 3 • Within analyze • recursively call analyze on subexpressions • create an execution procedure which stores the EPs for subexpressions as local state 20/33 Implementing lambda • Body stored in double bubble is an execution procedure • old make-procedure list, expression, Env → Procedure • new make-procedure list, (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/33 Implementing 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/33 Implementing 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/33 Summary of part 4 • In the analyze evaluator, • double bubble stores execution procedure, not expression 24/33 What is Eval really? • Suppose you were a circuit designer • Given a circuit diagram, you could transform it into an electric signal 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 MACHINE
It wasn't always this obvious Why a Universal Machine? it should that the basic logics of a machine If EVAL can simulate any machine, and if EVAL is itself a description of a machine, then EvAL can simulate itself coincide with the logics of a machine intended to make bills This was our example of meal for a department store, I would regard this as the most mazing coincidence that I have ever encountered In fact, EVAL can simulate an evaluator for any other Just need to specify syntax, rules of evaluation ard Aiken, writing in 1956( designer of the Mark I lectronic Brain, developed jointly by IBM and Harvard An evaluator for any language can simulate any other tarting in 1939) language computable in one language is computable in any other language s InsI Iht Turing's insight Alan Mathison Turing ticularthe Led Turing to investigate Hilberts Entscheidungsproblem For many propositions it was easy to find such an algorithm. in proving that for certain propositions no such Is there some fixed definite process which, in principle, E.g, Suppose want to prove some theorem in geometry Consider a proofs from axioms in 1 step in 2 steps Turings insight The halting problem Turing proposed a theoretical model of a simple kind of If there is a problem that the universal machine can't solve (now called a Turing then no machine can solve, and hence no effective process any"effective process" can be carried out by such a Make list of all possible programs (all machines with 1 input) Encode all their possible inputs as integers Each machine can be characterized by its program List their outputs for all possible inputs(as integer, error or Showed how to code a universal machin Define f(n)=output of machine n on input n, plus 1 if output is a number Wrote the first EVAL Define f(n)=0 if machine n on input n is error or loops Yet we just described process for computing f?? Bug is that can't tell if a machine will always halt and produce
5 25/33 It 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 and Harvard starting in 1939) 26/33 Why a Universal Machine? • If EVAL can simulate any machine, and if EVAL is itself a description of a machine, then EVAL can simulate itself • This was our example of meval • In fact, EVAL can simulate an evaluator for any other language • Just need to specify syntax, rules of evaluation • An evaluator for any language can simulate any other language • Hence there is a general notion of computability – idea that a process can be computed independent of what language we are using, and that anything computable in one language is computable in any other language 27/33 Turing’s insight • Alan Mathison Turing • 1912-1954 28/33 Turing’s insight • Was fascinated by Godel’s incompleteness results in decidability (1933) • In any axiomatic mathematical system there are propositions that cannot be proved or disproved within the axioms of the system • In particular the consistency of the axioms cannot be proved. • Led Turing to investigate Hilbert’s Entscheidungsproblem • Given a mathematical proposition could one find an algorithm which would decide if the proposition was true of false? • For many propositions it was easy to find such an algorithm. • The real difficulty arose in proving that for certain propositions no such algorithm existed. • In general – Is there some fixed definite process which, in principle, can answer any mathematical question? • E.g., Suppose want to prove some theorem in geometry – Consider all proofs from axioms in 1 step – … in 2 steps …. 29/33 Turing’s insight • Turing proposed a theoretical model of a simple kind of machine (now called a Turing machine) and argued that any “effective process” can be carried out by such a machine • Each machine can be characterized by its program • Programs can be coded and used as input to a machine • Showed how to code a universal machine • Wrote the first EVAL! 30/33 The halting problem • If there is a problem that the universal machine can’t solve, then no machine can solve, and hence no effective process • Make list of all possible programs (all machines with 1 input) • Encode all their possible inputs as integers • List their outputs for all possible inputs (as integer, error or loops forever) • Define f(n) = output of machine n on input n, plus 1 if output is a number • Define f(n) = 0 if machine n on input n is error or loops • But f can’t be computed by any program in the list!! • Yet we just described process for computing f?? • Bug is that can’t tell if a machine will always halt and produce an answer
The Halting theorem Turing's history Halting problem: Take as inputs the description of Published this work as a student M will halt and produce an answer when given n as an Got exactly two requests for reprints One from Alonzo Church(professor of logic at Halting theorem (Turing): There is no way to write a program(for any computer, in any language)that solves Had his own formalism for notion of an effective the halting problem procedure, called the lambda calculus Completed Ph. D with Church, proving Church-Turing be an effective procedure can be carried out by a niversal machine (and therefore by any universal Turing's history orked as code breaker during Wll Ultra project, breaking Germans Enigma coding machine ned and buit the Bombe, machine for breaking messages from Designed statistical methods for breaking messages from German Navy Designed general-purpose digital computer based on this work ass marathoner- fifth in Olympic qualifying (2: 46: 03-10 minutes off Working on computational biology -how nature" computes biological forms. 6
6 31/33 The Halting theorem • Halting problem: Take as inputs the description of a machine M and a number n, and determine whether or not M will halt and produce an answer when given n as an input • Halting theorem (Turing): There is no way to write a program (for any computer, in any language) that solves the halting problem. 32/33 Turing’s history • Published this work as a student • Got exactly two requests for reprints • One from Alonzo Church (professor of logic at Princeton) – Had his own formalism for notion of an effective procedure, called the lambda calculus • Completed Ph.D. with Church, proving Church-Turing Thesis: • Any procedure that could reasonably be considered to be an effective procedure can be carried out by a universal machine (and therefore by any universal machine) 33/33 Turing’s history • Worked as code breaker during WWII • Key person in Ultra project, breaking German’s Enigma coding machine • Designed and built the Bombe, machine for breaking messages from German Airforce • Designed statistical methods for breaking messages from German Navy • Spent considerable time determining counter measures for providing alternative sources of information so Germans wouldn’t know Enigma broken • Designed general-purpose digital computer based on this work • Turing test: argued that intelligence can be described by an effective procedure – foundation for AI • World class marathoner – fifth in Olympic qualifying (2:46:03 – 10 minutes off Olympic pace) • Working on computational biology – how nature “computes” biological forms. • His death