; CSE 341 - Section 6 - May 4th #lang racket (provide (all-defined-out)) ;======================== ; OUTLINE ;======================== ; *) Mutation ; *) Memoization ; *) Background: scoping, associative lists ; *) Idiom that makes some algorithms (sometimes much) more efficient ; *) Demonstration: speeding up naive fibonacci ; *) Streams ; *) Definition and use ; 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 ; 1) a memory local to a function that can remember results ;======================== ;MUTATION ;======================== ; Racket is like most (all?) other languages in that there are ; * "values", data structures in memory; ; * "variables", names which can refer to data structures. ; Racket's facilities for mutation: ; ; (set! var value) ; re-binds the name `var` to refer to `value` ; (in the namespace `var` is defined in) ; ; (mcons value value) ; builds a "mutable pair" -- just like (cons value value), ; but supports the next four functions... ; ; (set-mcar! mp value) ; (set-mcdr! mp value) ; changes the *pair data structure* mp refers to, ; so the car/cdr is now `value` ; ; (mcar mp) ; (mcdr mp) ; exactly like `car` and `cdr`, except they operate on `mcons`s instead ; Not interchangeable with `car` and `cdr`! ; ; Example use: (define mp (mcons 1 2)) (define mp2 mp) (set-mcar! mp "l") ; change first value in mutable pair mp to "l" (set-mcdr! mp "r") ; change second value in mutable pair mp to "r" mp ; => (mcons "l" "r") mp2 ; => (mcons "l" "r") (set! mp (mcons 3 4)) mp ; => (mcons 3 4) mp2 ; => (mcons "l" "r") ; Note that (set! mp ...), ; unlike (set-mcar! mp ...), ; did *not* modify the data structure! ; It just made mp point at a new object! ; 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! ;======================== ; LEXICAL SCOPE ;======================== ; how do these procedures differ? (define accumulate-1 (let ([acc 0]) (lambda (x) (begin (set! acc (+ acc x)) acc)))) (define accumulate-2 (lambda (x) (let ([acc 0]) (begin (set! acc (+ acc x)) acc)))) ; 2) a way to look up results in that memory ;======================== ; ASSOCIATIVE LISTS ;======================== ; Associative lists (lists of key-value pairs) ; are one simple way to achieve that! ; library function named "assoc" will do lookups by key in any associative list ; (assoc value my-list) ; returns the first pair in the list in which its car is equal? ; to the given `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 3 6) (cons "example" #t))) ; note: ; > my-list ; '((1 . 2) (3 . 4) (3 . 6) ("example" . #t)) ; The apostrophe is syntactic sugar for list literals, ; the . is syntactic sugar for pairs. ; (assoc 1 my-list) ; => '(1 . 2) (assoc 3 my-list) ; => '(3 . 4) NOTE: not '(3 . 6) (assoc 6 my-list) ; NOTE: assoc only looks at the car of each pair ;======================== ; REFRESHER -> FIBONACCI ;======================== (define (fibonacci x) (if (or (= x 1) (= x 2)) 1 (+ (fibonacci (- x 1)) (fibonacci (- x 2))))) ;(println "Computing (fibonacci 38)...") ;(fibonacci 38) ; Why is this procedure slow? ; We end up recomputing many values, ; due to the doubly-recursive structure of the function. ; Runtime grows exponentially with x! Bad! Very bad! ; One method of speeding up the naive fibonacci is to remember results ; from previous calls. ; This idiom is called *memoization*. ; Memoization will allow fibonacci to become almost exponentially faster! ;======================== ; MEMOIZATION -> REIMPLEMENTING FIBONACCI ;======================== ; We now know: ; how to create a function-local cache that can remember things, ; methods to mutate that cache, ; and how to use an associative list! ; Now, let's combine all this to make a Fibonacci-number calculator ; that remembers its results instead of recomputing them. (define memo-fibonacci1 (let ([memory null]) ; don't expose memo to outside world (lambda (n) ; fibonacci only takes one argument, but memoization ; easily generalizes to multiple arguments (if (assoc n memory) ; saved result in cache? (cdr (assoc n memory)) (if (or (= n 1) (= n 2)) 1 (let ([result (+ (memo-fibonacci0 (- n 1)) (memo-fibonacci0 (- n 2)))]) (set! memory (cons (cons n result) memory)) result)))))) ;(print "Computing (memo-fibonacci0 38)...") ;(memo-fibonacci0 38) ; this implementation avoids exponential blowup! ; instead of taking time proportional to 2^x, takes time proportional to x ; Some other approaches: (define memo-fibonacci2 (letrec ([memo '((1 . 1) (2 . 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: ; they allow us to represent an infinite list, ; without actually creating one. ;======================== ; STREAMS => SIMPLE EXAMPLES ;======================== ; A stream is implemented as a "thunk" (0-argument function) ; that evaluates to a pair of an element and another stream. ; This is an infinitely recursive definition. 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!