1 ;; Exercise 3.25.  Generalizing one- and two-dimensional tables, show how to implement a table in which values are stored under an arbitrary number of keys and different values may be stored under different numbers of keys. The lookup and insert! procedures should take as input a list of keys used to access the table. 
2 
3 ;; we could actually keep the procedure as-is, by treating the list of keys as a single key and comparing equality of lists. The downside to this is that there would be no organization based on keys.
4 
5 (define (make-table) (list '*table*))
6 
7 (define (assoc key records)
8     (cond ((null? records) false)
9 	  ((equal? key (caar records)) (car records))
10 	  (else (assoc key (cdr records)))))
11 
12 (define (lookup keys table)
13   (if (null? keys)
14       (error "no keys passed to lookup")
15       (cond 
16        ;; table is the record
17        ((null? (cdr keys)) (cdr table)) 
18        (((cdr table)
19 	  
20 	  (lookup (cdr keys) 
21        ((
22 ;; the problem here is that the user could actually insert, for his value, a list structure that resembled a subtable. This would trick our lookup procedure into thinking that there is no value for this specific key.
23 
24 ;; for example, suppose someone tried to insert
25 
26 (insert! '(usa new-york) (list (cons new-york 1)) tbl)
27 ;; this would shadow the previous entry by appearing earlier in the table
28 ;; I think this implementation is really insecure
29 
30 	  (let ((subtable (assoc (car keys) (cdr table))))
31 	(if subtable
32 
33 		...
34 		(lookup (cdr keys) subtable))
35 	    false)))
36 
37       	((null? (cdr keys))
38 	 (if (
39 	
40 ;;too many keys
41 
42   (let ((local-table (list '*table*)))
43     (define (lookup key-1 key-2)
44       (let ((subtable (assoc key-1 (cdr local-table))))
45         (if subtable
46             (let ((record (assoc key-2 (cdr subtable))))
47               (if record
48                   (cdr record)
49                   false))
50             false)))
51     (define (insert! key-1 key-2 value)
52       (let ((subtable (assoc key-1 (cdr local-table))))
53         (if subtable
54             (let ((record (assoc key-2 (cdr subtable))))
55               (if record
56                   (set-cdr! record value)
57                   (set-cdr! subtable
58                             (cons (cons key-2 value)
59                                   (cdr subtable)))))
60             (set-cdr! local-table
61                       (cons (list key-1
62                                   (cons key-2 value))
63                             (cdr local-table)))))
64       'ok)    
65     (define (dispatch m)
66       (cond ((eq? m 'lookup-proc) lookup)
67             ((eq? m 'insert-proc!) insert!)
68             (else (error "Unknown operation -- TABLE" m))))
69     dispatch))
70 
71 (define (test-case actual expected)
72   (newline)
73   (display "Actual:   ")
74   (display actual)
75   (newline)
76   (display "Expected: ")
77   (display expected)
78   (newline))
79 
80 (define tbl (make-table))
81 ;; 2nd number refers to population in millions
82 (insert! '(usa california los-angeles) 3.88 tbl)
83 (insert! '(usa new-york new-york) 8.41 tbl)
84 (insert! '(china beijing) 21.15 tbl)
85 (insert! '(china shanghai) 24.15 tbl)
86 (insert! '(pakistan karachi) 23.5 tbl)
87 (insert! '(hong-kong) 7.22 tbl)
88 (insert! '(singapore) 5.4 tbl)
89 (test-case (lookup '(usa california los-angeles) tbl) 3.88)
90 (test-case (lookup '(china shanghai) tbl) 24.15)
91 (test-case (lookup '(singapore) tbl) 5.4)
92 (test-case (lookup '(usa california rowland-heights) tbl) #f)
93 (test-case (lookup '(usa new-york) tbl) #f)
94 (test-case (lookup '(usa new-york new-york) tbl) 8.41)
95 (test-case (lookup '(usa new-york new-york new-york) tbl) #f)
96 
97 
98 
99 
100