; CSE 341 - Section 6 - May 9th #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) (cond [(= x 0) 0] [(= x 1) 1] [#t (+ (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 a generalization of promises to functions with more than 0 arguments ; this is a common dynamic programming technique in when you have immutability ; memoization will allow fibonacci to become exponentially faster! ; when we have a pure function with no inputs, it can only have a single output. thus we can use promises ; when we have a pure function with _multiple_ inputs, we need to remember the values for _any_ input. ; with fibonacci, we'd like to have some way to remember ; the result of (fibonacci 0), (fibonacci 1), (fibonacci 2), etc. ; Let's review 0-arg functions first. ;======================== ; PROMISES: FORCE + DELAY ;======================== (define (my-delay th) (mcons #f th)) (define (my-force p) (if (mcar p) (mcdr p) (begin (set-mcar! p #t) (set-mcdr! p ((mcdr p))) (mcdr p)))) ; now we'll build up the tools we need to do full memoization ;======================== ; 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]) (lambda (x) (begin (set! counter (+ counter x)) counter)))) (define example-2b (lambda (x) (let ([counter 0]) (begin (set! counter (+ counter x)) counter)))) ; example-2a works correctly, but example-2b always returns x ; notice that in 2a, counter belongs to example-2a's closure, which is only created once. ; in 2b, counter belongs to the lambda's closure, which is created every time example-2b is called. ;======================== ; 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 ;======================== ; ASSOCIATION 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 ; association lists are one simple way to achieve that ; an association list is just a list of key-value pairs ; library function named "assoc" will do lookups by key in any valid association 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 (cond ; compute new answer [(= x 0) 0] [(= x 1) 1] [#t (+ (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)) ; simpler, but possibly more confusing ; build a chain of closures ; each closure remembers one input ; uses chains of closures is a common way to implement maps in functional programming languages (define (memo-fibonacci3 x) (define ans (cond [(= x 0) 0] [(= x 1) 1] [#t (+ (memo-fibonacci3 (- x 1)) (memo-fibonacci3 (- x 2)))])) (define f memo-fibonacci3) (set! memo-fibonacci3 (lambda (y) (if (= x y) ans (f y)))) ans) ; notice the connection between promises and memoization ; with promises, we look up a boolean of whether the value has been computed or not ; we could just have easily used a map whose only defined key is unit i.e. '() ; with memoization, we allow our keys to range over more complicated input values and we need to store more than just one piece of data ;======================== ; STREAMS => REFRESHER ;======================== ; streams are another powerful programming idiom ; allow us to represent an infinite list without actually creating one ;======================== ; STREAMS => SIMPLE EXAMPLES ;======================== ; note: we have take, but it's on your hw so I hid it! ; 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)) ; how would we write a stream that produces natural numbers? ; now we need some state (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!