テーブルから名前の検索

The Little Schemer

久しぶりにThe Little Schemer。
9章までは終わってたから、最終章の10章をば。


いろんな人が書いたレビューなどによると、この章ではSchemeを用いてScheme処理系を実装するのだそうだ。
The Little Schemerって、「この章の目標は○○が出来るようになる事ですよ」的なことがぜんぜん書いてないから、途中で「...ふーん。で、何が言いたいん？」って気持ちになることが多い。


さて、本題。


まず、2個のリストからなるリストのうち、最初のリストがセットで、かつ2つのリストの要素数が等しいものを「エントリー」と定義する。
セットに関しては111ページを参照のこと。
つまり、エントリーを例示すると

((One Two Three) (1 2 3))

や

((foo bar baz) (hoge hoge hoge))

や

((foo bar) ((this is) (a sample entry)))

など。

nameというセットとvalueというリストからエントリーを作成するには、以前作成したbuild関数が利用できる。
build関数の定義は119ページを参照。


さて、

(define name (quote bar))
(define entry (quote ((foo bar baz) (hoge fuga piyo))))

としたとき、

(lookup-in-entry name entry)

の値が

fuga

になるようなlookup-in-entry関数について考えてみようか、と。
つまり、セットからnameを探し出して、見つかったらリストの同じ位置にあるS式を返す関数ね。

もし、ここでnameの定義が

(define name (quote qux))

だったら、セットの中には見当たらない。こんなときに

(lookup-in-entry name entry)

が何に評価されるかはプログラマに任せたい、とのことだ。

んで、それをどうやって実現できるか？
答えは、引数を1個増やして、そいつで「見つからなかった場合に評価される関数」を渡してやる、という方法。
ちなみに、その「見つからなかった場合に評価される関数」は1つの引数をとる関数だそうな。
引数名がnameとか言ってるから、見つからなかったときのエラーメッセージかなんかに利用するのかな？


ここでlookup-in-entry関数の定義が示される。

(define lookup-in-entry
  (lambda (name entry entry-f)
    (lookup-in-entry-help name (first entry) (second entry) entry-f)))

first関数とsecond関数の定義は119ページ。
しかし、lookup-in-entry-helpは未定義。
lookup-in-entry-helpを実装しろ、と。

答えは

(define lookup-in-entry-help
  (lambda (name names vals entry-f)
    (cond
     ((null? names) (entry-f name))
     ((eq? name (car names)) (car vals))
     (else (lookup-in-entry-help name (cdr names) (cdr vals) entry-f)))))

だと。
lookup-in-entry-helpというヘルパをかますことで、何が嬉しいのだろうか。
ただ、ヘルパが無いとちょっと書きにくいな、ってことは分かる。


さて、ここでエントリーのリストを「テーブル」と定義する。
テーブルの例は

()

や

(((foo bar baz)
  (hoge fuga piyo))
 ((foo qux)
  ((this is) (a sample of table))))

など。

テーブルを拡大するextend-table関数は

(define extend-table cons)

と定義できる。

さっきはエントリーの中から名前を探して、それに対応するS式を取り出すlookup-in-entryを作ったけど、
今度はテーブルの中から探す関数を作ろう、と。
つまり、

(define name (quote entree))
(define table
  (quote (((entree dessert)
           (spaghetti spumoni))
          ((appetizer entree beverage)
           (food tastes good)))))

のとき、

(lookup-in-table name table table-f)

の値が

spaghetti

になるようなlookup-in-table関数。
この例だと、entreeは2箇所見つかるけど、最初に見つかった方を採用するから答えはspaghettiになる、と。

さて、定義は

(define lookup-in-table
  (lambda (name table table-f)
    (cond
     ((null? table) (table-f name))
     (else
       (lookup-in-entry
         name
         (car table)
         (lambda (name)
           (lookup-in-table name (cdr table) table-f)))))))

となるそうな。
lookup-in-entryの時と同じように、「テーブルに見つからなかったときに何をするか」を引数で渡している。

lookup-in-table関数で自分が難しいと感じた箇所は、

(lambda (name)
  (lookup-in-table name (cdr table) table-f))

の部分。
entry-fとしてこの無名関数を渡していて、この部分はいつ評価されるかというと、今見ているエントリーにnameが見つからなかった場合ね。
んで何をやっているか具体的にいうと、次のエントリーにlookup-in-entryを適用しているわけね。（もちろんnameとtable-fは不変）


今日はここまで。


次にやるべきことを引数で渡してやる、ってのは継続という考え方らしい。
僕の場合、継続と再帰が絡むと特に難しく感じる。