----------------------------------------- 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 modelAfter 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