CS61A Lecture 24Clicker poll Goalsmce reviewHow many calls to mc-eval?Slide 6Slide 7REVIEW What is a procedure?How many calls to mc-eval? DEMOcalls to mc-eval(fact 1)Slide 12(fact 2)(fact 3)PowerPoint PresentationanalzyeanalyzeSlide 18Slide 19Slide 20Slide 21Slide 22analyze-quotedTwo versions of analyze-quotedWrite analyze-ifanalyze-if solution(analyze '(if #t 3 4))Slide 28Do we save time using the analyzing mce?Compiling JavaCompilersFrames in MCE (below the line)Environments (below the line)Slide 34Environments (Below the line)CS61A Lecture 242011-08-01Colleen Lewis1Clicker poll Have you started project 4 part 1?A)Yes – we’re done!B)Yes – we’re close to done!C)Yes – we started D)Yes – we started reading the project/codeE)No – we haven’t started2Goals•Increase comfort with the meta-circular evaluator (MCE)•Identify inefficiency•See efficiency improvement using analyze•Connect the ideas in analyze to compiling 3mce review•You could define new functions in mce?–A. True–B. False4How many calls to mc-eval?;;; M-Eval input:(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))A)1 B) 2C) 3D) 4 E) 5Does this make any calls to mc-apply?A) Yes B) NO!!!5How many calls to mc-eval?;;; M-Eval input:(define (simple x) x)A)1 B) 2 C) 3 D) 4 E) 5(define (mc-eval exp env) (display (list 'mc-eval 'exp: exp)) (newline) (cond ((self-evaluating? exp) exp)(mc-eval exp: (define (simple x) x))(mc-eval exp: (lambda (x) x))6How many calls to mc-eval?;;; M-Eval input:(simple 5)A)1 B) 2 C) 3 D) 4 E) 5(mc-eval exp: (simple 5))(mc-eval exp: simple)(mc-eval exp: 5)(mc-eval exp: x)7REVIEW What is a procedure?STk> (mc-eval '(lambda (x) (* x x)) '(((a) 3)))(procedure (x) ((* x x)) (((a) 3)))8car cdr((a).(3))Params: xBody: (+ x x)Globala: 3procedurecar cdr(x)car cdr((* x x))car cdrcar cdrHow many calls to mc-eval?DEMO(fact 0)(procedure (n) ((if (= n 0) 1 (* n (fact (- n 1))))) env)9123456 7 89calls to mc-eval(mc-eval exp: (fact 0))(mc-eval exp: fact)(mc-eval exp: 0)(mc-eval exp: (if (= n 0) 1 (* n (fact (- n 1)))))(mc-eval exp: (= n 0))(mc-eval exp: =)(mc-eval exp: 0)(mc-eval exp: n)(mc-eval exp: 1)10(fact 1)(fact 1)(mc-eval exp: (fact 1))(mc-eval exp: fact)(mc-eval exp: 1)(mc-eval exp: (if (= n 0) 1 (* n (fact (- n 1)))))(mc-eval exp: (= n 0))(mc-eval exp: =)(mc-eval exp: 0)(mc-eval exp: n)(mc-eval exp: (* n (fact (- n 1))))(mc-eval exp: *)(mc-eval exp: (fact (- n 1)))(mc-eval exp: fact)(mc-eval exp: (- n 1))(mc-eval exp: -)(mc-eval exp: 1)(mc-eval exp: n)11(mc-eval exp: (if (= n 0) 1 (* n (fact (- n 1)))))(mc-eval exp: (= n 0))(mc-eval exp: =)(mc-eval exp: 0)(mc-eval exp: n)(mc-eval exp: 1)(mc-eval exp: n)(fact 1)(fact 1)(mc-eval exp: (fact 1))(mc-eval exp: fact)(mc-eval exp: 1)(mc-eval exp: (if (= n 0) 1 (* n (fact (- n 1)))))(mc-eval exp: (= n 0))(mc-eval exp: =)(mc-eval exp: 0)(mc-eval exp: n)(mc-eval exp: (* n (fact (- n 1))))(mc-eval exp: *)(mc-eval exp: (fact (- n 1)))(mc-eval exp: fact)(mc-eval exp: (- n 1))(mc-eval exp: -)(mc-eval exp: 1)(mc-eval exp: n)12(mc-eval exp: (if (= n 0) 1 (* n (fact (- n 1)))))(mc-eval exp: (= n 0))(mc-eval exp: =)(mc-eval exp: 0)(mc-eval exp: n)(mc-eval exp: 1)(mc-eval exp: n)(fact 2)13(mc-eval exp: (if (= n 0) 1 (* n (fact (- n 1)))))(mc-eval exp: (= n 0))(mc-eval exp: =)(mc-eval exp: 0)(mc-eval exp: n)(mc-eval exp: (* n (fact (- n 1))))(mc-eval exp: *)(mc-eval exp: (fact (- n 1)))(mc-eval exp: fact)(mc-eval exp: (- n 1))(mc-eval exp: -)(mc-eval exp: 1)(mc-eval exp: n)(mc-eval exp: (if (= n 0) 1 (* n (fact (- n 1)))))(mc-eval exp: (= n 0))(mc-eval exp: =)(mc-eval exp: 0)(mc-eval exp: n)(mc-eval exp: (* n (fact (- n 1))))(mc-eval exp: *)(mc-eval exp: (fact (- n 1)))(mc-eval exp: fact)(mc-eval exp: (- n 1))(mc-eval exp: -)(mc-eval exp: 1)(mc-eval exp: n)(mc-eval exp: (if (= n 0) 1 (* n (fact (- n 1)))))(mc-eval exp: (= n 0))(mc-eval exp: =)(mc-eval exp: 0)(mc-eval exp: n)(mc-eval exp: 1)(mc-eval exp: n)(mc-eval exp: n)(mc-eval exp: (fact 2))(mc-eval exp: fact)(mc-eval exp: 2)(fact 3)14(mc-eval exp: (if (= n 0) 1 (* n (fact (- n 1)))))(mc-eval exp: (= n 0))(mc-eval exp: =)(mc-eval exp: 0)(mc-eval exp: n)(mc-eval exp: (* n (fact (- n 1))))(mc-eval exp: *)(mc-eval exp: (fact (- n 1)))(mc-eval exp: fact)(mc-eval exp: (- n 1))(mc-eval exp: -)(mc-eval exp: 1)(mc-eval exp: n)(mc-eval exp: (if (= n 0) 1 (* n (fact (- n 1)))))(mc-eval exp: (= n 0))(mc-eval exp: =)(mc-eval exp: 0)(mc-eval exp: n)(mc-eval exp: (* n (fact (- n 1))))(mc-eval exp: *)(mc-eval exp: (fact (- n 1)))(mc-eval exp: fact)(mc-eval exp: (- n 1))(mc-eval exp: -)(mc-eval exp: 1)(mc-eval exp: n)(mc-eval exp: (if (= n 0) 1 (* n (fact (- n 1)))))(mc-eval exp: (= n 0))(mc-eval exp: =)(mc-eval exp: 0)(mc-eval exp: n)(mc-eval exp: 1)(mc-eval exp: n)(mc-eval exp: n)(mc-eval exp: (fact 2))(mc-eval exp: fact)(mc-eval exp: 2)(mc-eval exp: (if (= n 0) 1 (* n (fact (- n 1)))))(mc-eval exp: (= n 0))(mc-eval exp: =)(mc-eval exp: 0)(mc-eval exp: n)(mc-eval exp: (* n (fact (- n 1))))(mc-eval exp: *)(mc-eval exp: (fact (- n 1)))(mc-eval exp: fact)(mc-eval exp: (- n 1))(mc-eval exp: -)(mc-eval exp: 1)(mc-eval exp: n)(define (mc-eval exp env) (cond ((self-evaluating? exp)...((variable? exp)...((quoted? exp) ...((assignment? exp) ...((definition? exp) ...((if? exp) ...((lambda? exp) ...((begin? exp) ...((cond? exp) ...((application? exp) ...(else (error “what?"))))15Each call to mc-eval could have a lot of sub-calls!Most didn’t depend upon the environment so I could do in advanceanalzye(define (mc-eval exp env) ( env))What is the domain and range of analyze?A.Domain: function Range: function B.Domain: expression Range: function C.Domain: function Range: expression D.Domain: expression Range: expression E.Other16(analyze exp)analyzeanalyzeList representing expressionSTK Scheme expression(λ(env)17(define (mc-eval exp env) ((analyze exp) env))analyze(define (analyze exp) (cond ((self-evaluating? exp) ((quoted? exp) … ((variable? exp) … ((assignment? exp) … ((definition? exp) … ((if? exp) … ((lambda? exp) … ((begin? exp) … ((cond? exp) … ((application? exp) … (else (error "Unknown" exp))))18(define (mc-eval exp env) ((analyze exp) env))(define (mc-eval exp env) (cond ((self-evaluating? exp) exp)((quoted? exp) (text-of-quotation exp)) ((variable? exp)(lookup-variable-value exp env))…(define (analyze exp) (cond ((self-evaluating? exp) (analyze-self-evaluating exp)) ((quoted? exp) (analyze-quoted exp)) ((variable? exp)
View Full Document
Unlocking...