Exercise 1.
Exercise 3.12 of Abelson & Sussman
Chapter 2 dealt with compound data as a means for constructing computational objects that have several parts, in order to model real-world objects that have several aspects. In that chapter we introduced the discipline of data abstraction, according to which data structures are specified in terms of constructors, which create data objects, and selectors, which access the parts of compound data objects. But we now know that there is another aspect of data that chapter 2 did not address. The desire to model systems composed of objects that have changing state leads us to the need to modify compound data objects, as well as to construct and select from them. In order to model compound objects with changing state, we will design data abstractions to include, in addition to selectors and constructors, operations called mutators, which modify data objects. For instance, modeling a banking system requires us to change account balances. Thus, a data structure for representing bank accounts might admit an operation
(set-balance! <account> <new-value>)
that changes the balance of the designated account to the designated new value. Data objects for which mutators are defined are known as mutable data objects. Chapter 2 introduced pairs as a general-purpose "glue" for synthesizing compound data. We begin this section by defining basic mutators for pairs, so that pairs can serve as building blocks for constructing mutable data objects. These mutators greatly enhance the representational power of pairs, enabling us to build data structures other than the sequences and trees that we worked with in section 2.2. We also present some examples of simulations in which complex systems are modeled as collections of objects with local state.
Exercise 3.12 of Abelson & Sussman
Suppose that the following definitions have been provided.
(define x (cons 1 3))
(define y 2)
A CS 61A student, intending to change the value of x to a pair with car equal to 1 and cdr equal to 2, types the expression (set! (cdr x) y) instead of (set-cdr! x y) and gets an error. Explain why.
a. Provide the arguments for the two set-cdr! operations in the blanks below to produce the indicated effect on list1 and list2. Do not create any new pairs; just rearrange the pointers to the existing ones.
> (define list1 (list (list 'a) 'b))
list1
> (define list2 (list (list 'x) 'y))
list2
> (set-cdr! ________ ________)
okay
> (set-cdr! ________ ________)
okay
> list1
((a x b) b)
> list2
((x b) y)
b. After filling in the blanks in the code above and producing the specified effect on list1 and list2, draw a box-and-pointer diagram that explains the effect of evaluating the expression (set-car! (cdr list1) (cadr list2)).
Exercises 3.13 and 3.14 in Abelson & Sussman
Exercises 3.16, 3.17, 3.21, 3.25, and 3.27 in Abelson & Sussman
You don't need to draw the environment diagram for exercise 3.27; use a trace to provide the requested explanations. Treat the table procedures lookup and insert! as primitive; i.e. don't trace the procedures they call. Also, assume that those procedures work in constant time. We're interested to know about the number of times memo-fib is invoked.
In all these exercises, don't use a list as an intermediate value. (That is, don't convert the vectors to lists!)
Write vector-append, which takes two vectors as arguments and returns a new vector containing the elements of both arguments, analogous to append for lists.
Write vector-filter, which takes a predicate function and a vector as arguments, and returns a new vector containing only those elements of the argument vector for which the predicate returns true. The new vector should be exactly big enough for the chosen elements. Compare the running time of your program to this version:
(define (vector-filter pred vec)
(list->vector (filter pred (vector->list vec))))
Sorting a vector:
Do the following reading:
You should be starting part 2 of the project this week.
Abelson & Sussman, exercises 3.19 and 3.23.
Exercise 3.19 is incredibly hard but if you get it, you'll feel great about yourself. You'll need to look at some of the other exercises you skipped in this section. Exercise 3.23 isn't quite so hard, but be careful about the O(1) - i.e. constant-time requirement.
Write the procedure cxr-name. Its argument will be a function made by composing cars and cdrs. It should return the appropriate name for that function:
> (cxr-name (lambda (x) (cadr (cddar (cadar x)))))
CADDDAADAR