Structure and Interpretation of Computer Programs Recitation 126.001 Mar. 12, 2004Whee! More ADT’s (tables)1. Table proceduresDefined in lecture: make-table, table-put!, table-getReal scheme (a-lists)• (assoc key alist) Finds and returns an association using equals?• (assq key alist) Same, but uses eq?• (assv key alist) Same, but uses eqv?• Plenty of other not-quite-as-useful onesProblems1. Evaluations(assq ’foo ’((1 baz) (foo bar) ("Hi" "Bye")))(assoc ’(1 2) ’((foo xyzzy) (1 5) (2 3) ((1 2) 10)))(car (assq ’bar ’((bar 2) (baz 3) (foo 4))))(assq ’bar (cdr (assq ’baz ’((foo ((bar baz) (baz xyzzy))) (bar ((bar foo)))))))2. Truth tablesInput 1 Input 2Output#t #t #t#t #f#f#f #t#f#f #f#fInput 1 Input 2Output#t #t #t#t #f#t#f #t#t#f #f#f(a) Write a procedure lookup that, given two inputs and a truth table, looks up the output.(define (lookup t1 t2 lookup-table)16.001: SICP Recitation 123. Frames(a) (define (make-frame)(b) (define (define-variable frame varname value)(c) (define (get-variable-value frame varname)4. Hash tablesMIT Scheme defines a h ash-table object with the following procedures:• (make-eq-hash-table [initial-size]) Constructs a new, empty hash table in whichkeys will be compared with eq?• (make-eqv-hash-table [initial-size]), (make-equal-hash-table [initial-size]),(make-string-hash-table [initial-size]) S ame, but use different comparisons.• (hash-table/get hash-table key default) Looks up a key in a hash table (returnsdefault if the key isn’t found• (hash-table/put! hash-table key value) Inserts a key-value pair into the hashtable
View Full Document
Unlocking...