6.001 Recitation #7

         5-minute-problem #6: Implementing Tables with Procedures
                       (posed, Wed 9/24)

We want to implement an abstract data type, Table, with the following
contract:
(1) There is a variable, the-empty-lookup-table, whose value is a
    Table (called the "empty" table).
                      the-empty-lookup-table : TABLE
(2) There are procedures
                 lookup : (Sch-integer x Table) -> Value
          revised-table : (Sch-integer x Value x Table) --> Table
    such that:
                  (lookup n (revised-table n v t)) ==> v
    and the combinations
                   (lookup j (revised-table n v t))
                   (lookup j t)
    return the SAME value when the values of j and n are different integers.

We will implement Table's as procedures, where lookup is done by
application:

(define (lookup n t) (t n))
(define the-empty-lookup-table (lambda (n) "does not matter"))
(define (revised-table n v t) <...the blank...> )

FILL IN THE BLANK to complete the definition of revised-table, and explain
your definition.  Suppose the following top-level definitions are
evaluated in order:

(define table1 (revised-table 1 7 the-empty-lookup-table))
(define table2 (revised-table 2 9 table1))
(define table3 (revised-table 1 13 table2))

Determine the values returned by each of the following expressions, and
explain why by carrying out substitution model calculations.

(lookup 2 table3)    ;Table THREE

(lookup 1 table3)    ;Table THREE

(lookup 1 table2)    ;Table TWO



                           SOLUTION (presented 9/26)

(define (revised-table n v t)
  (lambda (m) (if (= m n) v (lookup m t))))

Let's see how this works by doing some substitution model calculations:

TABLE1:
      
(revised-table 1 7 the-empty-lookup-table)

                    ;substitute the values of the variables:
((lambda (n v t) (lambda (m) (if (= m n) v (lookup m t))))
 1 7
 (lambda (n) "does not matter"))

                    ;apply the operator to get the lambda-expression
                    ;describing the value of TABLE1:
(lambda (m)
  (if (= m 1)
      7 
      (lookup m (lambda (n) "does not matter"))))


-------------------------------------------------------

TABLE2:

(revised-table 2 9 table1)

((lambda (n v t) (lambda (m) (if (= m n) v (lookup m t))))
 2 9
 (lambda (m)
   (if (= m 1)
       7 
       (lookup m (lambda (n) "does not matter")))))

                   ;the value of TABLE2:
(lambda (m)
  (if (= m 2)
      9
      (lookup m
              (lambda (m)
                (if (= m 1)
                    7 
                    (lookup m (lambda (n) "does not matter")))))))

---------------------------------------

                         ;(LOOKUP 1 TABLE2) should return 7:
(lookup 1 table2)

((lambda (n t) (t n))               ;value of LOOKUP
 1
 (lambda (m)                        ;value of TABLE2
  (if (= m 2)
      9
      (lookup m
              (lambda (m)
                (if (= m 1)
                    7 
                    (lookup m (lambda (n) "does not matter"))))))))

                                  ;to apply the operator, substitute 1 for
                                  ;N and the lambda expression for TABLE2
                                  ;into the operator body (T N):
((lambda (m)
  (if (= m 2)
      9
      (lookup m
              (lambda (m)
                (if (= m 1)
                    7 
                    (lookup m (lambda (n) "does not matter")))))))
 1)

                                  ;apply: substitute 1 for the M'S BOUND
                                  ;BY THE LAMBDA (M) OF THE OPERATOR:
(if (= 1 2)
    9
    (lookup 1
            (lambda (m)      ;these M's get left alone at this step
              (if (= m 1)       
                  7 
                  (lookup m (lambda (n) "does not matter"))))))

(if #f
    9
    (lookup 1
            (lambda (m)
              (if (= m 1)
                  7 
                  (lookup m (lambda (n) "does not matter"))))))

(lookup 1
        (lambda (m)
          (if (= m 1)
              7 
              (lookup m (lambda (n) "does not matter"))))))

((lambda (n t) (t n)) 1
                      (lambda (m)
                        (if (= m 1)
                            7 
                            (lookup m (lambda (n) "does not matter")))))

((lambda (m)
   (if (= m 1)
       7 
       (lookup m (lambda (n) "does not matter"))))
 1)


(if (= 1 1)
    7 
    (lookup 1 (lambda (n) "does not matter")))

(if #t
    7 
    (lookup 1 (lambda (n) "does not matter")))

7                ;IT WORKED!