Lab 5:

Hierarchical Data

We have already seen that cons can be used to combine not only numbers but pairs as well. (You made use of this fact, or should have, in doing exercises 2.2 and 2.3 from SICP.) As a consequence, pairs provide a universal building block from which we can construct all sorts of data structures.

The ability to create pairs whose elements are pairs is the essence of list structure's importance as a representational tool. We refer to this ability as the closure property of cons. In general, an operation for combining data objects satisfies the closure property if the results of combining things with that operation can themselves be combined using the same operation. Closure is the key to power in any means of combination because it permits us to create hierarchical structures - structures made up of parts, which themselves are made up of parts, and so on.

From the outset of this course, we've made essential use of closure in dealing with procedures, because all but the very simplest programs rely on the fact that the elements of a combination can themselves be combinations. In this section, we take up the consequences of closure for compound data. We describe some conventional techniques for using pairs to represent sequences and trees. In the project, you will create a graphics language that illustrates closure in a vivid way.


finish this during section

Exercise 1.

Do the following exercises - these should be quick and easy:

Exercise 2.

Do SICP Ex. 2.55; explain your answer to your TA.

Exercise 3.

Do SICP Ex. 2.27. This is the central exciting adventure of today's lab! Think hard about it.

Exercise 4.

Each person individually make up a procedure named mystery that, given two lists as arguments, returns the result of applying exactly two of cons, append, or list to mystery's arguments, using no quoted values or other procedure calls.

Type your mystery definition into a file, and have one of your partners load it into Scheme and try to guess what it is by trying it out with various arguments. After everyone has tried someone else's procedure, decide with your partners which procedure was hardest to guess and why, and what test cases were most and least helpful in revealing the definitions.

If you don't know anyone else working on the same lab, create the mystery procedure, and give a (small) set of input-output pairs which would allow someone else to determine the definition of mystery.

Exercise 5.

Make sure you understand the calculator program, which was discussed in the lecture notes. You will have to extend it in the homework. The program is in ~cs61as/lib/calc.scm


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

Exercise 6.

Complete the following:

Warning: The things that SICP calls "trees" are what we call "deep lists". They are not the general Trees for which we use make-tree, datum, and children. You should be using cons, car, cdr, and related procedures to solve the questions in SICP about trees.

Exercise 7.

Extend the calculator program from lecture to include words as data, providing the operations first, butfirst, last, butlast, and word.

Unlike Scheme, your calculator should treat words as self-evaluating expressions except when seen as the operator of a compound expression. That is, it should work like these examples:

calc: foo
calc: (first foo)
calc: (first (butfirst hello))

The program is in ~cs61as/lib/calc.scm

Exercise 8.

Do the following reading:

Project 2

Finish this before the deadline. Apart from that, we don't care when.

Do project 2. 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:

> (cs)
> (ht)
> (===your-painter=== full-frame)
For example:

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

Extra for Experts

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

Exercise 9.

Read section 2.3.4 and do exercises 2.67 - 2.72.

Exercise 10.

Programming by example: In some programming systems, instead of writing an algorithm, you give examples of how you'd like the program to behave, and the language figures out the algorithm itself:

> (define pairup (regroup '((1 2) (3 4) ...)))
> (pairup '(the rain in spain stays mainly on the plain))
((the rain) (in spain) (stays mainly) (on the))

Write regroup. Read ~cs61as/lib/regroup.problem for details.