CS61A Lecture 12Clicker poll Slide 3(calc) reviewRemember calc-apply?(calc) read-eval-print loopcalc-eval(scheme-1) DOES NOT HAVE DEFINE!Working with large programs!Approximate hierarchy of callslambda-exp?Write lambda-exp? in terms of exp-checkerlambda-exp? SolutionSome HelpersWhat is string?lookupSlide 17(lookup name params args)Write lookup (some functionality missing)lookup full functionalityFull lookupmaybe-quoteSubstituteSlide 24Substitution using substitute (substitute exp params args bound)(substitute exp params args bound)Scheme substitution reviewSlide 28Slide 29(apply-1 proc args)apply-1Slide 32scheme-1eval-1Slide 35Slide 36eval-1 with wordsSlide 38PowerPoint Presentation(cond ((pair? exp) ____)Slide 41Slide 42Slide 43CS61A Lecture 122011-07-11Colleen LewisClicker poll Do you feel comfortable posting questions to piazza?A)Yes with my classmates and instructors seeing my nameB)Yes with my instructors, but not my classmates seeing my nameC)Yes with my instructors and classmates NOT seeing my nameD)No.Clicker poll Do you want me to keep printing lecture notes?A)YES!B)Not necessary if you post the notes online 24 hours in advanceC)Not necessary(calc) review(scheme-1) has lambda but NOT defineRemember calc-apply?STk> (calc-apply '+ '(1 2 3))6STk> (calc-apply '* '(2 4 3))24STk> (calc-apply '/ '(10 2))5STk> (calc-apply '- '(9 2 3 1))3(calc) read-eval-print loop(define (calc) (display "calc: ") (flush) (print (calc-eval (read))) (calc))calc-evalSTk> (calc)calc: (+ (* 2 4) 5)13(define (calc-eval exp) (cond ((number? exp) exp) ((list? exp) (calc-apply (car exp) (map calc-eval (cdr exp)))) (else (error “Calc: bad exp”))))‘+‘(8 5)(scheme-1)DOES NOT HAVE DEFINE!STk> (scheme-1)Scheme-1: (lambda (x) (* x x))(lambda (x) (* x x))Scheme-1: ((lambda (x) (* x x)) 3)9Working with large programs!•Start with small functions•Understanding code–Read it•Recursively figure out any functions it calls–Try to call the function to see what it does in different cases–Trace the function and try to call it from the functions that call it.Approximate hierarchy of callsscheme-1apply-1 eval-1substitutelookupmaybe-quotelambda-exp? if-exp? quote-exp? constant?exp-checkernumber? boolean? string? proceedure?lambda-exp?STk> (lambda-exp? '(lambda (x) (+ x 2)))#tSTk> (lambda-exp? '(+ 3 4))#fSTk> (lambda-exp? '+)#fSTk> (lambda-exp? '(lambda))#tIt isn’t as picky as we might hope…Write lambda-exp? in terms of exp-checker(define (exp-checker type) (lambda (exp) (and(pair? exp) (eq? (car exp) type))))(lambda-exp? '(lambda (x) (+ x 2)))Did you write it with syntactic sugar? A) Yes B)Nolambda-exp? Solution(define (exp-checker type) (lambda (exp) (and(pair? exp) (eq? (car exp) type))))(define (lambda-exp? exp) ((exp-checker 'lambda) exp))(define lambda-exp? (exp-checker 'lambda))Some Helpers(define quote-exp? (exp-checker 'quote))(define if-exp? (exp-checker 'if))(define (constant? exp) (or (number? exp) (boolean? exp) (string? exp) (procedure? exp)))What is string?STk> (string? "hello")#tSTk> (string? 123)#fSTk> (string? 'hello)#flookupApproximate hierarchy of callsscheme-1apply-1 eval-1substitutelookupmaybe-quotelambda-exp? if-exp? quote-exp? constant?exp-checkernumber? boolean? string? proceedure?(lookup name params args)STk> (lookup 'x '(x) '(3))3STk> (lookup 'y '(x y) '(2 3))3STk> (lookup 'y '(x) '(3))ySTk> (lookup '* '(x) '(3))*Just returns it if it isn’t in thereWrite lookup (some functionality missing)(define (lookup name params args) (cond ((null? params) name)((eq? name (car params))(car args))(else (lookup name (cdr params) (cdr args)))))lookup full functionalitySTk> (lookup 'fn '(x fn) '(3 (lambda (y) (* y y))))(lambda (y) (* y y))STk> (lookup 'x '(x) '(cat))(quote cat)cat was already a word, but we want to tell other people this thing IS ACTUALLY a word This already worksFull lookup (define (lookup name params args) (cond ((null? params) name)((eq? name (car params)) (maybe-quote (car args))(else (lookup name (cdr params) (cdr args)))))maybe-quote(define (maybe-quote value) (cond ((lambda-exp? value) value)((constant? value) value)((procedure? value) value)(else (list 'quote value))))SubstituteApproximate hierarchy of callsscheme-1apply-1 eval-1substitutelookupmaybe-quotelambda-exp? if-exp? quote-exp? constant?exp-checkernumber? boolean? string? proceedure?Substitution using substitute(substitute exp params args bound)STk> ((lambda (x) (* x x)) 3)9STk> (substitute '(* x x) '(x) '(3) '())(* 3 3)STk> ((lambda (x y) (+ x y)) 3 4)7STk>(substitute '(+ x y) '(x y) '(3 4) '())(+ 3 4)(substitute exp params args bound)STk> ((lambda (x) (lambda (y) (* x y)) ) 3) What does this return?#[closure arglist=(y) 7ff1cc48]A procedure that takes argument y and adds 3 to itSTk> (substitute '(lambda (y) (* x y)) '(x) '(3) '())(lambda (y) (* 3 y))Scheme substitution reviewSTk> ((lambda (x) (lambda (x)(* x x)) ) 4)#[closure arglist=(x) 7ff1a1f8]STk> (((lambda (x) (lambda (x) (* x x))) 4) 3)What does this return? A) 9 B) 16 C)??(substitute exp params args bound)STk> ((lambda (x) (lambda (x)(* x x)) ) 4)#[closure arglist=(x) 7ff1a1f8]STk> (substitute '(lambda (x) (* x x)) '(x) '(4) '())(lambda (x) (* x x))A recursive call will be made where bound will be '(x)Approximate hierarchy of callsscheme-1apply-1 eval-1substitutelookupmaybe-quotelambda-exp? if-exp? quote-exp? constant?exp-checkernumber? boolean? string? proceedure?(apply-1 proc args)STk> (apply-1 + '(3 4))7STk> (apply-1 '(lambda (x) (* x x)) '(3))9Unlike calc-apply apply-1 can be called with REAL scheme functionsOr lists representing functions Remember lambda-exp??apply-1(define (apply-1 proc args) (cond ((procedure? proc) (apply proc args))((lambda-exp? proc) (eval-1 (substitute (caddr proc) (cadr proc) args '())))(else (error "bad proc:" proc))))(lambda (x) (* x x))(substitute exp params args bound)Approximate hierarchy of callsscheme-1apply-1 eval-1substitutelookupmaybe-quotelambda-exp? if-exp? quote-exp? constant?exp-checkernumber? boolean? string? proceedure?scheme-1(define (scheme-1) (display "Scheme-1: ") (flush) (print (eval-1 (read))) (scheme-1))eval-1STk> (eval-1 5)5STk> (eval-1 '+)#[closure arglist=args 7ff53de8](cond ((constant? exp) exp)(cond ((symbol? exp) (eval exp))eval-1STk> (eval-1 '(if (> 3 4) 5 7))7(cond ((if-exp? exp) (if (eval-1 (cadr exp)) (eval-1 (caddr exp)) (eval-1 (cadddr exp))))eval-1STk> (eval-1 'x)*** Error:
View Full Document
Unlocking...