Scheme - 表の表現(n次元(一次元、二次元の一般化))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の3(標準部品化力, オブジェクトおよび状態)、3.3(可変データでのモデル化)、3.3.3(表の表現)、二次元の表、局所表の作り方の問題 3.25を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題3.25

コード(BBEdit)

sample.scm

(define (make-table same-key?)
  (let ((local-table (list '*table*)))
    (define (assoc key records)
      (cond ((null? records) false)
            ((same-key? key (caar records)) (car records))
            (else (assoc key (cdr records)))))
    (define (lookup keys)
      (define (iter keys table)
        (if (null? keys)
            (if table
                (cdr table)
                false)
            (let ((subtable (assoc (car keys) (cdr table))))
              (if subtable
                  (iter (cdr keys) subtable)
                  false))))
      (iter keys local-table))
    (define (insert! keys value)
      (define (iter! keys table)
        (if (null? keys)
            (set-cdr! table value)
            (let ((subtable (assoc (car keys) (cdr table))))
              (if subtable
                  (iter! (cdr keys) subtable)
                  (let ((p (list (car keys))))
                    (set-cdr! table (cons p
                                          (cdr table)))
                    (iter! (cdr keys) p))))))
      (iter! keys local-table)
      'ok)
    (define (dispatch m)
      (cond ((eq? m 'lookup-proc) lookup)
            ((eq? m 'insert-proc!) insert!)
            (else (error "Unknown operation -- TABLE" m))))
    dispatch))

(define t (make-table equal?))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> ((t 'insert-proc!) '(a) 1)

;Value: ok

1 ]=> ((t 'insert-proc!) '(b c) 2)

;Value: ok

1 ]=> ((t 'insert-proc!) '(c d e) 3)

;Value: ok

1 ]=> ((t 'insert-proc!) '(d e f) 4)

;Value: ok

1 ]=> ((t 'insert-proc!) '(e f g) 5)

;Value: ok

1 ]=> ((t 'lookup-proc) '(a))

;Value: 1

1 ]=> ((t 'lookup-proc) '(b c))

;Value: 2

1 ]=> ((t 'lookup-proc) '(c d e))

;Value: 3

1 ]=> ((t 'lookup-proc) '(d e f))

;Value: 4

1 ]=> ((t 'lookup-proc) '(e f g))

;Value: 5

1 ]=> ((t 'insert-proc) '(c d e) 10)

;Unknown operation -- TABLE insert-proc
;To continue, call RESTART with an option number:
; (RESTART 1) => Return to read-eval-print level 1.

2 error> ^C
Interrupt option (? for help): 
;Quit!

1 ]=> ((t 'insert-proc!) '(c d e) 10)

;Value: ok

1 ]=> ((t 'lookup-proc) '(c d e))

;Value: 10

一応出来たけど、上記のコードだとキーのリスト'(a)に値1を設定した後に、キーのリスト'(a b)に値2を設定しようとすると、キーを順に辿っていってキーのリスト'(a)に設定した値1はついじゃないのに、そのcdrを調べようとしてとしてエラーが発生する。だから、値はキーのリストではないと制限して、pair?でキーのリスト(n次元)に設定した値が対かどうか調べるようにして、対ではなかったら戻ってから次に既に存在するキーかどうかを順に調べていくようにすれば上手くいくのかも。

といいつつ、修正はまた次の周に挑戦することにして、今は先に進めてとりあえずは最後まで辿り着くことを優先することに。