6.001                                                    Recitation #7
                                                         A.R. Meyer
                           NOTES FOR FRI, 9/26


In class problems:

                                PROBLEM 1

Question 1.
1A. Draw the box and pointer diagram for the list structure
representing the list structure Scheme would print out as
        ((1 13) (2 9) (1 7))
1B. Write a list expression whose value is given by this diagram.

(Actually, in class the question was reversed: given the diagram, produce
an expression whose value would be represented by the diagram, but the
diagram is too hard to include here in a text file.  That's also why we
won't draw the solution to this question :-)


The list in Question 1 is another representation of table3 from
5-min-problem #6 presented at the beginning of recitation.  In this
implementation a table is represented as a list of "bindings" each of
which is a list of length two consisting of an integer "index" and the
"value" bound to that index.

To LOOKUP index N in this representation, search through the list of
bindings in the representation until reaching the first binding whose
index equals N; the value to return is the value in the binding.  We'll
use the empty list to represent the-empty-lookup-table:
        (define the-empty-lookup-table '())

Question
2A. Define LOOKUP for this representation.
2B. Define REVISED-TABLE for this representation.
2C. Draw the box-and-pointer diagram resulting from
      (define table1 (revised-table 1 7 the-empty-lookup-table))
      (define table2 (revised-table 2 9 table1))
      (define table3 (revised-table 1 13 table2))
   in this representation.


                               SOLUTION 1:
1B.  (list (list 1 13) (list 2 9) (list 1 7))


                               SOLUTION 2:

2A.
(define (empty? table) (null? table))
(define (first-pair bindings) (car bindings))

                or more concisely (and efficiently):
(define empty? null?)
(define first-binding car)

(define rest-of-bindings cdr)
(define index-in-binding car)
(define (value-in-binding binding) (car (cdr binding)))

                            or more concisely:
(define value-in-binding cadr)

(define (lookup n t)
  (if (empty? t)
      (list "No such index: " n "in " t)
      (let ((binding1 (first-binding t)))
        (if (= n (index-in-binding binding1))
            (value-in-binding binding1)
            (lookup n (rest-of-bindings t))))))

2B. (define (revised-table n v t)
     (cons (list n v) t))

2C. Same as 1A with the variables TABLE3 TABLE2 and TABLE1 shown bound to
    the first, second and third cons-cells in the list of bindings.