CS61A Summer 2011                        Homework 4

Topic:  Data Abstraction

Reading: Abelson & Sussman, Sections 2.1 and 2.2.1 (pages 79-106) 


Abelson & Sussman, exercises 2.7, 2.8, 2.10, 2.12, 2.17, 2.20, 2.22, 2.23

(Note Regarding 2.10: “Spans zero” means that one bound is ≤ zero and the other is ≥ zero!)

(Note Regarding 2.12: Don’t use sentence procedures!)

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)

((lead axe) (bass axe) (rhythm axe) drums)

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

((four calling birds) (three french hens) (two turtle doves))

Note: Programming Project 2 is due 7/5.  This is a solo project!  It consists of all the exercises in Section 2.2.4 of the text.  You can’t actually draw anything until you finish the project! To begin, copy the file ~cs61a/lib/picture.scm to your directory.  To draw pictures, once you’ve completed the exercises, use the following commands from the STK prompt:

> (cs)

> (ht)

> (====your-painter-here===== full-frame)

For example:

> (wave full-frame)

> ((square-limit wave 3) full-frame)

Note: You do not need a transcript for this project, but you will still need to turn in a paper copy by 11:00am on Wednesday.

Please put your Name, Your TA’s name and your login in your file!

Extra for experts:

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.

Abelson & Sussman, exercise 2.6. Besides addition, invent multiplication and exponentiation of non-negative 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 ~cs61a/lib/church-hint for some suggestions.


Unix feature of the week:         rm, mv, cp, rmdir, ln -s 

Emacs feature of the week:         M-% (find and replace text)