6.001 Recitation #10 – March 12, 2003

RI: Konrad Tollmar

www.ai.mit.edu/~konrad/6001

• Data mutation

1. Evaluate these expressions:

1. (define x 10)

2. (set! x 6)

3. (+ x 3)

4. x

5. (set! x (+ x 3))

6. x

7. (define y (cons 1 (cons 2 nil)))

8. (define z '(a b))

9. (cons y z)

10. (append y z)

11. (set-car! y 6)

12. y

13. (set-cdr! y nil)

14. y

15. (set-cdr! y z)

16. y

17. (set-car! z 12)

18. y

2. Append!

Rewrite append to append! That do not make a copy of the first list and cons'd it onto the second. Use instead side effects to append two lists without creating a copy of one of them.

3. Remember values

Write a function called seen? that takes one argument and returns #t only if that function has been called before with that argument. Assume you have the function element? that takes an object and a list, and returns #t if the object is in the list.

4. Write make-ring

Rings are circular list structures. If we define a ring r with

(define r (make-ring (list 1 2 3 4)))

then

(nth 0 r) ==> 1

(nth 1 r) ==> 2

…

(nth 4 r) ==> 1

Write procedure make-ring.

Write the procedures rotate-right and rotate-left takes rotate the ring one the right and one to the left. (hint: start with the somewhat easier rotate-left).

5. Traditional LISP structure: association list

Represent the table as the alist:

((x 15) (y 20))

We should be able to find elements in the alist:

(define a1 '((x 15) (y 20)))

(find-assoc 'y a1) ==> 20

(define (find-assoc key alist) .. )

We should be able to insert a new element in the alist:

(define a2 (add-assoc 'z 10 a1))

a2 ==> ((z 10) (x 15) (y 20))

(find-assoc 'z a2) ==> 10

(define (add-assoc key val alist) .. )

But - Alists are not an abstract data type

. It missing a constructor, ie it use quote or list to directly construct. So there is no abstraction barrier. Therefore, the implementation is exposed.

(define a1 ‘((x 15) (y 20)))

Lets instead use an alternative Table: a set of bindings, a pairing of a key and a value

Abstract interface to a table:

Make create a new table

put! key value insert a new binding, replaces any previous binding of that key

get key look up the key, return the corresponding value

This definition IS the table abstract data type

(define table1-tag .. )

(define (make-table1) .. )

(define (table1-get tbl key) .. )

(define (table1-put! tbl key val) .. )