; CSE 341 - Section 6 - May 5th #lang racket (provide (all-defined-out)) ;======================== ; OUTLINE ;======================== ; *) memoization ; *) idiom that makes some algorithms (sometimes much) more efficient ; *) demonstration: speeding up naive fibonacci ; *) streams ; *) definition and use ;======================== ; REFRESHER -> FIBONACCI ;======================== (define (fibonacci x) (if (or (= x 1) (= x 2)) 1 (+ (fibonacci (- x 1)) (fibonacci (- x 2))))) ; why is this procedure slow? ; we end up recomputing many values due to the recursive structure of the solution ; runtime grows exponentially with x! (very bad!) ; one method of speeding up the naive fibonacci is to remember results from ; each recursive calls. ; this idiom is called *memoization* ; which is similar to force and delay, except a memoized function can take arguments ; memoization will allow fibonacci to become exponentially faster! ; we'll require a few things to implement memoization: ; 1) a memory local to a function that can remember results ; 2) a way to look up results in that memory ; let's review how we can achieve 1) ;======================== ; LEXICAL SCOPE ;======================== ; how do these procedures differ? (define example-1a (let ([v (fibonacci 35)]) ; only computes (fibonacci 35) once (lambda (x) (+ x v)))) ; every call to example-1a makes use of the cached result (define example-1b (lambda (x) (let ([v (fibonacci 35)]) ; computes (fibonacci 35) every call (+ x v)))) ;======================== ; LEXICAL SCOPE & MUTATION ;======================== ; we care even more about scoping rules in the presence of mutation! ; which of these procedures correctly keeps ; a global counter and increments it with x each call? (define example-2a (let ([counter 0]) ; remembers counter values between function calls (lambda (x) (begin (set! counter (+ counter x)) counter)))) (define example-2b (lambda (x) (let ([counter 0]) ; every call to the function uses a newly initialized counter (begin (set! counter (+ counter x)) counter)))) ; example-2a works correctly, but example-2b always returns x ;======================== ;MUTATION => MUTABLE PAIRS AND LISTS ;======================== ; it's important to have the right mental model for mutation in Racket ; as an example, consider mutable pairs and lists ; these are analogous to regular pairs and lists, but mutable! ; NOTE: they are NOT the same however ; they are completely different datatypes ; (with the exception that the empty list is also the empty mutable list) ; Use mutable types only when necessary! Prefer immutable! ; example use: ; (define mp (mcons 1 2)) ; (mpair? mp) ; (mcar mp) ; (mcdr mp) ; (set-mcar! mp 5) ; change first value in mutable pair mp to 5 ; (set-mcdr! mp 6) ; change second value in mutable pair mp to 6 ; (car mp) ; this (or other mixed uses mutable / immutable pairs & lists) gives you an error! ;======================== ; set! VS. set-mcar! and set-mcdr! ;======================== ; (define x 1) ; (set! x 5) ; this changes variable x to refer to the value 5 ; ; doesn't change the *VALUE* of 1 to 5. 1 is still 1. ; ; analogous to x = 5; in Java ; (set-mcar! mp 4) ; changes the "fields" of the mpair structure mp ; ; mcar and mcdr could be considered fields in a mpair structure ; ; analogous to mp.mcar = 4; in Java ;======================== ; ASSOCIATIVE LISTS ;======================== ; we now know how to create a cache local to a function that can remember results, ; and methods to mutate that cache. ; now we need a way to look up values in the cache ; associative lists are one simple way to achieve that ; an associative list is just a list of key-value pairs ; library function named "assoc" will do lookups by key in any valid associative list ; assoc locates the first pair in the list in which its car is equal? ; to the requested key value. Returns the entire pair found. If the key isn't found, it returns #f. ; (define my-list (list (cons 1 2) (cons 3 4) (cons 5 6) (cons "example" #t))) ; (assoc 3 my-list) ; (assoc 1 my-list) ; (assoc "example" my-list) ; (assoc 6 my-list) ; NOTE: assoc only looks at the car of each pair ;======================== ; MEMOIZATION -> REIMPLEMENTING FIBONACCI ;======================== (define memo-fibonacci (letrec([memo null] ; don't expose memo to outside world ; list of pairs (arg . result) [f (lambda (x) ; fibonacci only takes one argument, but memoization ; easily generalizes to multiple arguments (let ([ans (assoc x memo)]) ; saved result in cache? (if ans (cdr ans) ; return memoized answer (let ([new-ans (if (or (= x 1) (= x 2)) ; compute new answer 1 (+ (f (- x 1)) (f (- x 2))))]) (begin (set! memo (cons (cons x new-ans) memo)) ; save it new-ans)))))]) ; return new answer f)) ; return memoized function ; this implementation avoids exponential blowup! ; instead of taking time proportional to 2^x, takes time proportional to x (define memo-fibonacci2 (letrec ([memo '((0 . 0) (1 . 1))] ; you can put your base cases in results cache! [f (lambda (x) (let ([ans (assoc x memo)]) (if ans (cdr ans) (let ([new-ans (+ (memo-fibonacci2 (- x 1)) (memo-fibonacci2 (- x 2)))]) (begin (set! memo (cons (cons x new-ans) memo)) new-ans)))))]) f)) (define (memo-fibonacci3 x) (define ans (if (or (= x 1) (= x 2)) 1 (+ (memo-fibonacci3 (- x 1)) (memo-fibonacci3 (- x 2))))) (define f memo-fibonacci3) (set! memo-fibonacci3 (lambda (y) (if (= x y) ans (f y)))) ans) ;======================== ; STREAMS => REFRESHER ;======================== ; streams are another powerful programming idiom ; allow us to represent an infinite list without actually creating one ;======================== ; STREAMS => SIMPLE EXAMPLES ;======================== ; a stream is implemented as a thunk that evaluates to a pair of an element and another stream ; this is an infinitely recursive fefinition. There's no end to a stream! (define (ones) (cons 1 ones)) (define (take n stream) (if (= n 0) null (let ((s (stream))) (cons (car s) (take (- n 1) (cdr s)))))) (define natural-numbers (letrec ([next-nat (lambda (x) (cons x (lambda () (next-nat (+ x 1)))))]) ; return next pair (lambda () (next-nat 0)))) ; "seed" the stream ; how does this work? let's pull some results out of a stream to see ; natural-numbers ; just a thunk ; (natural-numbers) ; extract pair from stream ; ((cdr (natural-numbers))) ; get pair after next ; ((cdr ((cdr (natural-numbers))))) ; ... (define powers-of-two (letrec ([next-thunk (lambda (x) (cons x (lambda () (next-thunk (* x 2)))))]) (lambda () (next-thunk 1)))) ; see a pattern? (define (stream-maker init fn) (letrec ([next-thunk (lambda (x) (cons x (lambda () (next-thunk (fn x)))))]) (lambda () (next-thunk init)))) (define nats2 (stream-maker 0 (lambda (x) (+ x 1)))) (define powers2 (stream-maker 1 (lambda (x) (* x 2)))) ; recursive functions make elegant use of streams ; here's an example (define (number-until stream tester) (letrec ([f (lambda (stream ans) (let ([pr (stream)]) (if (tester (car pr)) ans (f (cdr pr) (+ ans 1)))))]) (f stream 1))) (define four (number-until powers-of-two (lambda (x) (= x 16)))) ; warning ->> it's very easy to make mistakes with parens when using streams ; for example: passing a pair instead of a stream ; code safely!