CS61A Lecture 23Clicker poll scheme-1 ReviewMetacircular Evaluator (MCE) read-eval-print loopToday’s PlanPowerPoint PresentationSlide 7More things create/use ADTs (makes not-new stuff different)What do environments look like?Frames in MCE (below the line)Environments (below the line)Slide 12Environments (Below the line)Slide 14How do we look-up values from environments?How do we look-up values from environments? (continued)Slide 17How many times is scan called?What does this environment look like?What is a procedure?Slide 21Printing Environments is…What would scheme print (wwsp)?Lexical vs. Dynamic ScopeLOGOCommands versus OperationsParentheses can be usedVariables vs. ProceduresQuoting things in LOGOThere are no special forms!Defining a functionScope - We have framesNew frames extend the CURRENT environment (not the environment in which they were created)SolutionsSlide 35CS61A Lecture 232011-07-28Colleen Lewis1Clicker poll Are you in a two person group for project 4?A)Yes – I have my partnerB)No – I plan to work individuallyC)No – But I want a partner2scheme-1 Review(define (scheme-1) (display "Scheme-1: ") (flush) (print (eval-1 (read))) (scheme-1))Whatever you typed in is treated as a listeval-1 evaluated these listsInfinite loopMetacircular Evaluator (MCE) read-eval-print loop(define (driver-loop) (prompt-for-input input-prompt) (let ((input (read))) (let ((output (mc-eval input the-global-environment))) (announce-output output-prompt) (user-print output))) (driver-loop))4The big idea!Today’s Plan•Is mc-eval basically the same as eval-1?–Yes•Is mc-apply basically the same as apply-1?–Yes•How is this different than scheme-1? –Everything has its own ADT!–We have environments and can define things! 5The big idea!(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?"))))6NewNew(not ver y interesting)(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?"))))7(mc-eval '(sq 3) '())Is caught by:A. quoted?B. lambda? C. application?(mc-eval 'x '())Is caught by:A. self-evaluating?B. variable? C. quoted?More things create/use ADTs(makes not-new stuff different)STk> (eval-1 '(lambda (x) (* x x)))(lambda (x) (* x x))STk> (mc-eval '(lambda (x) (* x x)) '())(procedure (x) ((* x x)) ())8ADT overkill?This is tagged with procedure, but we already had it tagged with lambda.What do environments look like?9Frames in MCE(below the line)((x y) . (2 4))or((x y) 2 4 )10Globalx: 2y: 4E1a: 5b: 7c: 3((a b c) . (5 7 3))or((a b c) 5 7 3 )(define (frame-variables frame)(car frame))(define (frame-values frame)(cdr frame))Environments(below the line)List of frames! (define the-empty-environment '())(extend-environment '(x y) ;; vars'(2 4) ;; valsthe-empty-environment) ;; base-env(define (extend-environment vars vals base-env)(cons (make-frame vars vals) base-env))11Error checking omittedEnvironments(below the line)List of frames! (define the-empty-environment '())(extend-environment '(x y) ;; vars'(2 4) ;; valsthe-empty-environment) ;; base-env12car cdr((x y).(1 2))Globalx: 2y: 4FrameEnvironmentEnvironments (Below the line)13Globalx: 2y: 4E1a: 5b: 7c: 3car cdr((x y).(1 2))car cdr((a b c).(5 7 3))14Globalx: 2y: 4E3a: 5b: 7c: 3car cdr((x y).(1 2))car cdr((a b c).(5 7 3))E1E2car cdr(().())E3 is the current frame. Draw the environment. How many elements are in the list you made?A. 1 B. 2 C. 3 D. 4 E. 5How do we look-up values from environments? (define (scan vars vals) (cond ((null? vars) ...) ;; look in enclosing env. ((eq? var (car vars)) (car vals)) (else (scan (cdr vars) (cdr vals)))))15How do we look-up values from environments? (continued)(define (lookup-variable-value var env) (define (env-loop env) (if (eq? env the-empty-environment) (error "Unbound variable" var) (let ((frame (first-frame env))) (scan (frame-variables frame) (frame-values frame))))) (env-loop env))16How do we look-up values from environments? (define (scan vars vals) (cond ((null? vars) (env-loop (enclosing-environment env))) ((eq? var (car vars)) (car vals)) (else (scan (cdr vars) (cdr vals)))))17How many times is scan called? A. Once for each frameB. Once for each variable in the environmentC. Once for each variable you are looking upD. OTHERWrite a definition for (enclosing-environment env)18What does this environment look like?19STk>(define a 3)STk>(define sq (lambda (x) (* x x)))Params: xBody: (* x x)Globala: 3sq:car cdr((a sq).(3 ???))What is a procedure?STk> (mc-eval '(lambda (x) (* x x)) '(((a) 3)))(procedure (x) ((* x x)) (((a) 3)))20car cdr((a).(3))Params: xBody: (+ x x)Globala: 3procedurecar cdr(x)car cdr((* x x))car cdrcar cdrWhat does this environment look like?21STk>(define a 3)STk>(define sq (lambda (x) (* x x)))Params: xBody: (* x x)Globala: 3sq:car cdr((a sq).(3 (procedure (x) ((* x x))___)))The environmentPrinting Environments is…A. going to be really helpful to see what is going on in mc-evalB. not going to be possible because they are really bigC. not going to be possible because they contain infinite structures22What would scheme print (wwsp)?(define (my-scope x) (lambda () x))(define (current-scope x thunk) (thunk))STk> (define my-thunk (my-scope 3))my-thunkSTk> (current-scope 4 my-thunk)Prints: A. 3 B. 4 C. error D. ???23Lexical vs. Dynamic Scope•Scheme – Lexical Scope–Extend the frame that the procedure was created in•Logo – Dynamic Scope–Extend the frame that the procedure was called from24LOGO Demo 25Commands versus Operations•In LOGO procedures are divided into–Operations – return values–Commands – don’t return values•You have to start each instruction with a commandprint sum 2 326Parentheses can be usedprint (sum 2 3 4 5)print 3*(4+5)27Variables vs. Procedures•We can have a function and a variable with the same name in LOGO.•How to make a variable: make "x 10print :xmake "sum 15print sum :x :sum28Quoting things in LOGO•We use " instead of single quotes.make "name "colleen print :namemake "my-sent [a b c]print
View Full Document
Unlocking...