CSSE 304 Day 21
Memoization Multi-value returns Continuations intro
MEMOIZATION (A BRIEF DIVERSION ABOUT EFFICIENCY)
1
Background: the assoc family
• A list of 2-lists, is called an association list.
Each 2-list is treated as a key-value pair.
• The assoc procedure finds a key and its
associated value (along with the rest of the list).
• > (assoc ‘c ‘((a 1) (b 2) (c 3) (d 4) (e 5))) (c 3)
• assoc uses equal? when testing the keys. assq uses eq? assv uses eqv?
Example of a Memoizing (Caching) Function
Without caching:
(define fibonacci
(lambda (n)
(if (or (zero? n) (= n 1))
1
(+ (fibonacci (- n 2))
(fibonacci (- n 1))))))
Very simple to define, but it has a problem!
2
Timing the fibonacci function
>(define time-fib
(lambda (n)
(collect)
(time
(fibonacci n))))
>(time-fib 30)
no collections
770 ms elapsed cpu time 770 ms elapsed real time 0 bytes allocated
1346269
> (time-fib 31) (time (fibonacci n))
no collections
1220 ms elapsed cpu time
1220 ms elapsed real
time
0 bytes allocated
2178309
> (time-fib 32) (time (fibonacci n))
no collections
2010 ms elapsed cpu
time
2020 ms elapsed real
time
0 bytes allocated
3524578
> (time-fib 33) (time (fibonacci n))
no collections
3240 ms elapsed cpu
time
3240 ms elapsed real
time
0 bytes allocated
5702887
fibonacci with caching (memoization)
(define fib-memo (let ([max 1]
[sofar ‘((1 . 1) (0 . 1))])
(lambda (n)
(if (<= n max)
(cdr (assq n sofar))
(let* ([v1 (fib-memo (- n 1))]
[v2 (fib-memo (- n 2))]
[v3 (+ v2 v1)])
(set! max n)
(set! sofar (cons
(cons n v3) sofar))
v3)))))
max and sofar are used to cache previously computed values of fib-memo
3
Timing the fib-memo function
>(define time-memo
(lambda (n)
(collect)
(time (fib-memo n))))
> (time-memo 30)
(time (fib-memo n))
no collections
0 ms elapsed cpu time
0 ms elapsed real time
464 bytes allocated
1346269
> (time-memo 120) (time (fib-memo n))
no collections
0 ms elapsed cpu time
0 ms elapsed real time
2704 bytes allocated
8670007398507948658051921
> (time-memo 480)
(time (fib-memo n))
no collections
10 ms elapsed cpu time
10 ms elapsed real time
18168 bytes allocated
149131696402327401278275120573021480 636486507112094019661502199265467 79697987984279570098768737999681
> (time-memo 1920)
(time (fib-memo n))
no collections
0 ms elapsed cpu time
0 ms elapsed real time
201096 bytes allocated
130548509585974025289403903399342332 195533153264149057012466373585260 855440922729886517665791348772431 832647927017501018894903833887134 985970384628647382836605175649149 276410087245331524919858263915987 811572358836471880641113736192407 569546597943636025003714415011830 903968180799768315063395136835768 779659490153054076902321531244169 951765324840758127291467883962057 798767411224848804669073085015870 721
Wouldn’t it be nice …
• if a procedure could return multiple values? • Like in Python:
4
Multi-value returns in a functional programming context
VALUES, CALL-WITH-VALUES, WITH-VALUES, MVLET
Ongoing Example
Suppose we want to calculate list-average using just one traversal of the non-empty list.
First approach
Helper procedure returns a list of the sum and the length.
(define list-average
(letrec ([helper (lambda (L)
(if (null? L)
(list 0 0) ; sum, length
(let ([return (helper (cdr L))])
(list (+ (car return) (car L))
(+ 1 (cadr return))))))])
(lambda (L)
(apply / (helper L)))))
5
values, call-with-values
Thevaluesprocedure allowsourcodetoreturn multiple values.
the call-with-values procedure provides a context for the reception of multiple return values.
(values v1 …) returns the values v1 … (call-with-values producer consumer)
producer is a procedure that is allowed to be applied to zero arguments, and
consumer is a procedure that can be applied to the number of values that will be returned by producer. The producer will usually use values to return its values.
call-with-values examples
Simple example:
>(call-with-values
(lambda () (values 3 4))
cons)
(3 . 4)
Unusual examples that illustrate how call‐with‐values works
> (call-with-values values
(lambda args args))
> (call-with-values + list)
> (call-with-values list list)
6
call-with-values examples
Simple example:
> (call-with-values
(lambda () (values 3 4)) list)
(3 4)
Unusual examples that illustrate how call-with- values works.
> (call-with-values values (lambda args args))
()
> (call-with-values + list) (0)
> (call-with-values list list) (())
A simple example from TSPL
Split a list into elements from even and odd positions of original list.
(define split
(lambda (ls)
(if (or (null? ls) (null? (cdr ls)))
(values ls ‘())
(call-with-values
(lambda () (split (cddr ls)))
(lambda (odds evens)
(values (cons (car ls) odds)
(cons (cadr ls) evens)))))))
> (split ‘(a b c d e f))
(a c e)
(b d f)
> (list (split ‘(a b c d e f)))
Exception: returned two values to single value return
context
> (call-with-values (lambda () (split ‘(a b c d e f))) list)
((a c e) (b d f))
7
Version of list-average that uses call-with-values
(define list-average
(letrec ([helper (lambda (L)
(if (null? L)
(values 0 0) ; sum, length
(call-with-values
(lambda () (helper (cdr L)))
(lambda (sum len)
(values (+ sum (car L))
(+ 1 len))))))])
(lambda (L)
(call-with-values (lambda ()(helper L))
/))))
with-values
Most of the time when we use call-with-values, the
(lambda () …) is just a wrapper for the code we really want to execute
We can define a new syntactic form to simplify this. (define-syntax with-values
(syntax-rules ()
[(_ expr consumer)
(call-with-values
(lambda () expr)
consumer)]))
Why can’t with‐values be a procedure?
Example of with‐values:
> (with-values (split ‘(a b c d e f)) list) ((a c e) (b d f))
8
Shorter version of list-average that uses with-values
(define list-average
(letrec ([helper
(lambda (L)
(if (null? L)
(values 0 0) ; sum, length
(with-values
(helper (cdr L))
(lambda (sum len)
(values (+ sum (car L))
(+ 1 len))))))])
(lambda (L)
(with-values (helper L) / ))))
mv-let (mv is for multiple-valued) For the frequent case where the consumer
is also defined by (lambda …), here is another convenient abbreviation:
(define-syntax mvlet
(syntax-rules ()
((_ ((x …) e0) e1 e2 …)
(with-values e0
(lambda (x …) e1 e2 …)))))
9
list-average using mv-let
(define list-average
(letrec
([helper
(lambda (L)
(if (null? L)
(values 0 0) ; sum, length
(mvlet ((sum len)
(helper (cdr L)))
(values (+ sum (car L))
(+ 1 len)))))])
(lambda (L)
(with-values (helper L) / ))))
•
–
–
Some practice exercises
Use call-with-values or one of the simplified versions to write:
(subst-leftmost s1 s2 slist) substitutes the symbol s1 for the leftmost occurrence of the symbol s2 in slist; all later occurrences of s2 are left unchanged. No subpart of slist is traversed more than once, and once (if ever) the leftmost occurrence of s2 has been found, previously untraversed portions of slist are not traversed.
(max-interior bintree) from the homework.
10
For many students, this section is a step up in difficulty from anything that we have done previously in this course.
CONTINUATIONS AND CPS
Control Flow
• Lately we have talked about data-types, scope, binding, and environments
• Another important issue is flow of control
– What are some of the control flow mechanisms in Java?
• In Scheme (or any expression-oriented language), the most basic control-flow issues are
– What is the current expression to be evaluated?
– Once that is done, what remains to be done with the value of the current expression?
11
Control flow
• The two most basic things that affect flow of control in a program are:
• The ___c_o_n_t_in_u_a_t_io_n______ which tells what is to be done with that value.
expression
• The current ______________ to be evaluated.
Scheme Control Flow
• In Scheme (or any expression-oriented language), the most basic control-flow issues are
– What is the current expression to be evaluated?
– Once that is done, what remains to be done with the value of the current expression?
12
Scheme Control Flow Details
• What is the current expression to be evaluated?
• Once that is done, what remains to be done with the value of the current expression?
• Consider the evaluation of (+ a 5) in the process of evaluating
(- 4 (* b (+ a 5))).
• What remains to be done with the value of (+ a 5) ?
• Can we express that as a procedure?
• We can call that procedure the continuation of the
(+ a 5) computation
• The process of Scheme evaluation can be expressed as
– Loop:
• Evaluate the current expression
• Apply the current continuation to the result
• In A18, you will rewrite your interpreter in this style, which is known as continuation-passing style (CPS).
More Examples
• What is the continuation of (< x 5) in
(if(