; 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!