-----------------------------------------
Tutorial notes #8 for 4/9 or 4/10/2007
TA: Stephen McCamant
Email: smcc@mit.edu
Location: 36-113A or 36-115
http://people.csail.mit.edu/smcc/6.001-sp07/
-----------------------------------------
Project 3
I probably won't be able to give back
your projects before the next quiz, but
I'll send out a list of common issues by
email.
-----------------------------------------
Project 4
The object-oriented adventure game is
already posted. It should be fun, but
you'll notice it's also quite long.
There's a substantial design-your-own
part, for which you'll need to write up
a proposal a week before the final due
date.
-----------------------------------------
Louis's mutation problem
The following code attempts to count the
number of repeated elements in a list.
What's wrong with it?
(define (remove-dups! lst)
(cond ((null? lst))
((null? (cdr lst)))
((= (car lst) (cadr lst))
(set-cdr! lst (cddr lst))
(remove-dups! lst))
(else
(remove-dups! (cdr lst)))))
(define (count-dups lst)
(let ((old lst))
(remove-dups! lst)
(- (length old) (length lst))))
"count-dups" modifies its argument,
which is unexpected for a procedure
named "count". Adding a "!" on the end
would make this clearer, but better not
to modify in the first place. More
seriously, it always returns 0, since
"old" is just another reference to the
same list that gets modified by
remove-dups!, so it has its repeats
removed too.
How can we fix it?
Make a copy of the list before modifying
it.
(define (copy-list lst)
(append lst '()))
(define (count-dups lst)
(let ((copy (copy-list lst)))
(remove-dups! copy)
(- (length lst) (length copy))))
Also useful, while we're on the subject:
(define (copy-tree tree)
(if (pair? tree)
(cons (copy-tree (car tree))
(copy-tree (cdr tree)))
tree))
-----------------------------------------
Environment model review
The environment model is a more
realistic model of Scheme evaluation
in which we keep track of the values of
variables using an "environment", a
chain of boxes called "frames" that hold
bindings of variable names to values.
New rules for the environment model:
variable: look up, starting in current
frame and going up to enclosing frames
until found
define: make new binding in current
frame
set!: find binding as for lookup, and
replace value
lambda: create "double bubble": left
half points to parameters and body,
right to enclosing environment
To apply a compound procedure:
* Evaluate each subexpression
* Create new frame
* New frame points to same parent as
right half of double bubble
* Bind parameter names to values
* Evaluate body in new environment
-----------------------------------------
Environment model exercises: basic
(define (infix a + b)
(+ a b))
(infix 3 * 6)
GE
+------------------------------+
|infix:-+ |
|*:-----+----------------------+--->#<prim mult><--+
|+:-----+----------------------+--->#<prim add> |
| | | |
+-------+-^----------------^---+ |
| | | |
V | +---+---+ |
( )( ) |a: 3 | |
| |+: ----+-------------------+
> p: a + b |b: 6 |
b: (+ a b) +-------+
The result is 18.
(define pi 3.14159)
(define (circle-area r)
(* pi r r))
(let ((pi 3))
(circle-area 10))
GE
+------------------------------+ +------+
|pi: 3.14159 | E2|r: 10 |
|circle-area:-+ |<-----| |
| +-----+ | | |
| | | +------+
+-------+-^----------------^---+
| | |
V | +---+---+
( )( ) E1 |pi: 3 |
| | |
> p: r | |
b: (* pi r r) +-------+
The result is 314.159.
-----------------------------------------
A procedure with memory
I'd like to define a procedure named
running-sum that returns the sum of all
the numbers you've ever passed to it.
For instance:
(running-sum 10)
-> 10
(running-sum 10)
-> 20
(running-sum 5)
-> 25
How can I write running-sum?
(define running-sum
(let ((sum 0))
(lambda (arg)
(set! sum (+ sum arg))
sum)))
Show how running-sum works using the
environment model
After the first call to running sum:
GE +--------------------------------+
|running-sum:-+ |
| | |
| | |
| | |
+-------------+----------------^-+
| | E2
V E1 +---+---+ +-------+
( )( )--------->|sum: 10|<--+arg: 10|
| | | | |
> p: arg +-------+ +-------+
b: (set!...
-----------------------------------------
Boxes
A "box" is like a pair, except it holds
only one thing, rather than two. Like
pairs, we want to be able to mutate
boxes. We'll have three basic operation,
make-box, get-value, and set-value!:
(define a (make-box 1))
(define b (make-box 2))
(define c b)
(get-value c)
-> 2
(get-value a)
-> 1
(set-value! a 10)
(get-value a)
-> 10
(set-value! c 20)
(get-value b)
-> 20
It's easy to implement boxes using
pairs:
(define (make-box v) (cons 'box v))
(define get-value cdr)
(define set-value! set-cdr!)
However, suppose we didn't have mutable
pairs. How could we create boxes using
just higher-order procedures and set!?
(define (make-box v)
(lambda (msg arg)
(cond ((eq? msg 'get)
v)
((eq? msg 'set)
(set! v arg)))))
(define (get-value box)
(box 'get #f))
(define (set-value! box v)
(box 'set v))
By the way, even though boxes may not
seem that useful, they are built into
DrScheme: look up "box" in the online
help if you're curious.
-----------------------------------------
Environment model exercise: hair pulling
; Type: A -> (B -> A)
(define (k x)
(lambda (y) x))
; Type:
; (A -> (B -> C)), (A -> B) -> (A -> C)
(define (s x y)
(lambda (z)
((x z) (y z))))
((s k k) 42)
;-> 42