; 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 37)]) ; 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 37)]) ; 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 ([prev-ans (assoc x memo)]) ; saved result in cache?
(if prev-ans
(cdr prev-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 function that uses the "memo table"
; this implementation avoids exponential blowup!
; instead of taking time proportional to 2^x, takes time proportional to x
(define memo-fibonacci2
(letrec([memo (list (cons 0 0) (cons 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))
;========================
; 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 definition. There's no end to a stream!
(define (ones)(cons 1 ones))
(define natural-numbers
(letrec ([next-nat (lambda (x)
(cons x (lambda () (next-nat (+ x 1)))))]) ; return next pair
(lambda () (next-nat 1)))) ; "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 2))))
; see a pattern?
(define (stream-maker fn arg)
(letrec ([next-thunk (lambda (x)
(cons x (lambda () (next-thunk (fn x arg)))))])
(lambda () (next-thunk arg))))
(define nats2 (stream-maker + 1))
(define powers2 (stream-maker * 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!