MASSACHVSETTS INSTITVTE OF TECHNOLOGY
Department of Electrical Engineering and Computer Science
6.001---Structure and Interpretation of Computer Programs
Spring Semester, 1999

Recitation -- Wednesday, March 1

1. Some of the Important Things to Know

• Rules for Evaluation (substitution model) -- when in doubt stop thinking!
• Rules for Special Forms
• Iteration vs. Recursion
• Pairs, Lists, and Trees (defining, manipulating, contracts, abstractions)
• Higher Order Procedures (procedures returning procedures)
• Abstraction of List Operations ( map, accumulate, and filter.

2. Tricky Stuff

What are the values of the following expressions:

3. Writing Some Procedures

Write the following procedures:

4. Order of Growth

What's the order of growth of the procedure copy-some above? . Consider the following procedure to copy the last n elements of a list. What is the order of growth of last-n? .

 
(define (last-k k lst) 
  (if (= (length lst) k)
      lst
      (last-k k (cdr lst))))

5. Defining a New List Abstraction

Notice that it can take a long time to find the length of one of our list structures. Say we want to define a new sequence abstraction, similar to lists, but that can return the length in constant time. Here's the contract:

 
(head (attach x seq)) == x
(tail (attach x seq)) == seq
(seq-empty? empty-seq) == #t
(seq-empty? (attach x seq)) == #f
(seq-length seq) == the length in  time.

Notice that with either of these abstractions, lists behave in the same way as they did before, except that the length of a list can be computed in constant time. We traded time for space.

• About this document ...