Lab 4:

Data Abstraction and Sequences

NOTE: From now on, we expect you to use Emacs, a text editor useful for coding in Scheme. We didn't introduce it earlier because it didn't quite make sense to make the new student responsible for learning Computer Science, Scheme, and Emacs during the first week. Here are some resources:

If you have any questions or problems with Emacs, ask your TA or post the question on Piazza!

In section 1.1.8, we noted that a procedure used as an element in creating a more complex procedure could be regarded not only as a collection of particular operations but also as a procedural abstraction. That is, the details of how the procedure was implemented could be suppressed, and the particular procedure itself could be replaced by any other procedure with the same overall behavior. In other words, we could make an abstraction that would separate the way the procedure would be used from the details of how the procedure would be implemented in terms of more primitive procedures. The analogous notion for compound data is called data abstraction. Data abstraction is a methodology that enables us to isolate how a compound data object is used from the details of how it is constructed from more primitive data objects.

The basic idea of data abstraction is to structure the programs that are to use compound data objects so that they operate on "abstract data." That is, our programs should use data in such a way as to make no assumptions about the data that are not strictly necessary for performing the task at hand. At the same time, a "concrete" data representation is defined independent of the programs that use the data. The interface between these two parts of our system will be a set of procedures, called selectors and constructors, that implement the abstract data in terms of the concrete representation. To illustrate this technique, we will consider how to design a set of procedures for manipulating rational numbers.

Labwork

finish this during section

Template

From now on, for most labs we will have template files for the labs in which you can write your answers. Type the following command at the terminal to copy the template file to the current directory (note the period at the end):

cp ~cs61as/autograder/templates/hw4.scm .

Exercise 1.

Try these in Scheme, starting from the left column:

(define x (cons 4 5))
(car x)
(cdr x)
(define y (cons 'hello 'goodbye))
(define z (cons x y))
(car (cdr z))
(cdr (cdr z))

Exercise 2.

Predict the result of each of these before you try it.

(cdr (car z))
(car (cons 8 3))
(car z)
(car 3)

Exercise 3.

Read over the following code and enter them into Scheme.

;; Enter these definitions into Scheme:
(define (make-rational num den)
  (cons num den))
(define (numerator rat)
  (car rat))
(define (denominator rat)
  (cdr rat))
(define (*rat a b)
  (make-rational (* (numerator a) (numerator b))
		 (* (denominator a) (denominator b))))
(define (print-rat rat)
  (word (numerator rat) '/ (denominator rat)))

;; Now try these:
(print-rat (make-rational 2 3))
(print-rat (*rat (make-rational 2 3) (make-rational 1 4)))

Now define a procedure +rat to add two rational numbers, in the same style as *rat above.

Exercise 4.

Do the following exercises:

Notes:

For 2.4, name the procedures proc-cons, proc-car, and proc-cdr.

Exercise 5.

This week you'll learn that sentences are a special case of lists, which are built out of pairs. Explore how that's done with experiments such as these:

(define x '(a (b c) d))
(car x)
(cdr x)
(car (cdr x))

Exercise 6.

SICP Ex. 2.18; this should take some thought, and you should make sure you get it right, but don't get stuck on it for a whole hour. Note: Your solution should reverse lists, not sentences! That is, you should be using cons, car, and cdr, not first, sentence, etc.

Homework

do this in section if possible; finish the rest at home

Exercise 7.

Complete the following:

Note: Spans zero means that one bound is <= zero and the other is >= zero!

Exercise 8.

Write a procedure substitute that takes three arguments: a list, an old word, and a new word. It should return a copy of the list, but with every occurrence of the old word replaced by the new word, even in sublists. For example,

(substitute '((lead guitar) (bass guitar)
              (rhythm guitar) drums)
            'guitar
            'axe)
;; Should output ((lead axe) (bass axe) (rhythm axe) drums)

Exercise 9.

Now write substitute2 that takes a list, a list of old words, and a list of new words; the last two lists should be the same length. It should return a copy of the first argument, but with each word that occurs in the second argument replaced by the corresponding word of the third argument:

(substitute2 '((4 calling birds)
               (3 french hens)
               (2 turtle doves))
             '(1 2 3 4)
             '(one two three four))
;; Expected output:
;; ((four calling birds)
;;  (three french hens)
;;  (two turtle doves))

Exercise 10.

Do the following reading:

Extra for Experts

Do this if you want to. This is NOT for credit.

Exercise 11.

Write the procedure cxr-function that takes as its argument a word starting with c, ending with r, and having a string of letters a and/or d in between, such as cdddadaadar. It should return the corresponding function.

Exercise 12.

SICP Ex. 2.6. Besides addition, invent multiplication and exponentiation of nonnegative integers. If you're really enthusiastic, see if you can invent subtraction. (Remember, the rule of this game is that you have only lambda as a starting point.) Read ~cs61as/lib/church-hint for some suggestions.