SICP 読み (109) 3.3.3 表の表現

とりあえず、例示されている手続きを試験してみる事で理解してみる事に。
とりあえず微妙ですが、make-table から

#!/usr/bin/env gosh

(use test.unit)
(require "3.3.3")

(define-test-suite "3.3.3"

  ("table"
   ("make table"
    (assert-equal '(*table*) (make-table))
    )
   )
  )

実装は以下で、試験は無論パス。

(define (make-table) (list '*table*))

次は insert! を試験。の前に assoc を確認しておいた方が良さげか。基本的な呼び出し方としては

(assoc key (cdr table))

みたいな感じ。backbone を cdr しながら key をチェックしてマッチしたら対を戻しているように見える。という事で以下の試験をでっち上げてみた。
# ちなみに最初、(cdr t) するのを忘れてました (log

  ("assoc"
   ("assoc no-elements"
    (let ((t (make-table)))
      (assert-false (assoc 'a (cdr t))))
    )

    ("assoc match (1)"
     (let ((t (make-table)))
       (set-cdr! t (cons (cons 'a 1) '()))
       (assert-equal '(a . 1) (assoc 'a (cdr t))))
     )

    ("assoc match (2)"
     (let ((t (make-table)))
       (set-cdr! t (cons (cons 'a 1) '()))
       (set-cdr! (cdr t) (cons (cons 'b 2) '()))
       (assert-equal '(b . 2) (assoc 'b (cdr t))))
     )
   )

試験はパス。assoc は対を戻す。次は insert! の確認を。とりあえず、リストとしてはこんなカンジになるのでしょうか??

  ("insert!"
   ("insert 'a 1"
    (let ((t (make-table)))
      (assert-equals 'ok (insert! 'a 1 t))
      (assert-equals '(*table* (a . 1)) t))
    )
   )

うう。ソレのクセでつい assert-equals ってやってしまう。正しくは以下。

  ("insert!"
   ("insert 'a 1"
    (let ((t (make-table)))
      (assert-equal 'ok (insert! 'a 1 t))
      (assert-equal '(*table* (a . 1)) t))
    )
   )

ツマラんコトしてるなぁ。(とほほほ
あるいは 2 件追加するとどうなるか、というと先頭側に追加。このあたりは p.157 に記述あり。リスト処理という部分において非常にアレなつくりになっております。

   ("insert (a . 1) & (b . 2)"
    (let ((t (make-table)))
      (assert-equal 'ok (insert! 'a 1 t))
      (assert-equal 'ok (insert! 'b 2 t))
      (assert-equal '(*table* (b . 2) (a . 1)) t))
    )

あるいは、既存のキーに対して insert! するとどうなるか、というと

   ("insert (a . 1) & (b . 2) after insert (a . 3)"
    (let ((t (make-table)))
      (assert-equal 'ok (insert! 'a 1 t))
      (assert-equal 'ok (insert! 'b 2 t))
      (assert-equal '(*table* (b . 2) (a . 1)) t)
      (assert-equal 'ok (insert! 'a 3 t))
      (assert-equal '(*table* (b . 2) (a . 3)) t))
    )

置き換わる、と。で、最後は lookup ですが作ったばかりの表に検索かけても #f が戻ってくる。

  ("lookup"
   ("lookup empty"
    (let ((t (make-table)))
      (assert-false (lookup 'a t)))
    )
   )

あるいは、正常だと値が戻ってくる。

   ("lookup is normal"
    (let ((t (make-table)))
      (insert! 'a 1 t)
      (assert-equal 1 (lookup 'a t)))
    )

あるいは、表に存在しない key でも #f が戻る。

   ("lookup by invalid key"
    (let ((t (make-table)))
      (insert! 'a 1 t)
      (assert-false (lookup 'b t)))
    )

先頭要素の car が '*table* になってるのも意味があるのか。深いのぅ。注釈によれば、こうするお陰で insert! が void な (戻りナシな) 手続きにできる、と。成程。