Scheme手習い 第10章 このすべての値は何だ
この章ではSchemeによるSchemeインタープリタを実装します。実装するインタープリタがサポートするSchemeの仕様はこの本に出て来るSchemeの仕様です。
ノート：
entry
連想配列相当。ペアのリストではないのはキーがユニークな集合である必要があるから。
new-entryは二つのリストをペア（ドットペアではない）にするだけなので既出のbuildと全く同じ。実際に評価すると：
> (new-entry '(appetizer entree beverage) '(patee beouf vin)) ((appetizer entree beverage) (patee beouf vin)) > (new-entry '(appetizer entree beverage) '(beer beer beer)) ((appetizer entree beverage) (beer beer beer)) > (new-entry '(beverage dessert) '((food is) (number one with us))) ((beverage dessert) ((food is) (number one with us))) >
lookup-in-entry
見つからなかった時に呼び出す（継続？）関数entry-fを引数に取る。ヘルパー関数lookup-in-entry-helpを引数、name、キー集合、値リストとみつからなかった時の関数に適用する。
lookup-in-entry-helpは
- キー集合が空の場合はentry-fを適用する
- 最初のキーがnameと一致する場合、最初の値
- 最初のキーがnameと一致しない場合、残りのキー集合、残りの値リストから捜す
１つの引数nameを取るべきだと思いますが、なぜでしょう。
と言う問いに対する答えは出て来ない。最初から後出のlookup-in-tableで使うつもりであればnameすら要らない筈。
実際に評価してみる。
> (lookup-in-entry 'entree (new-entry '(appetizer entree beverage) '(food tastes good)) (lambda (name) (display name) (display ": not found") (newline))) tastes > (lookup-in-entry 'dessert (new-entry '(appetizer entree beverage) '(food tastes good)) (lambda (name) (display name) (display ": not found") (newline))) dessert: not found >
lookup-in-table
entryのリストを検索する。見つからなかった時に呼び出す関数が重要。それぞれのlookup-in-tableは(car table)しか検索しない。見つからなかった時に直ぐにtable-fを適用するのではなく、(cdr table)から捜す『続き』の関数を作って渡す。見つからないままtableが空になればtable-fが適用される。
> (lookup-in-table 'entree '(((entree dessert) (spaghetti spumoni)) ((appetizer entree beverage) (food tastes good))) (lambda (name) (display name) (display ": not found") (newline))) spaghetti > (lookup-in-table 'appetizer '(((entree dessert) (spaghetti spumoni)) ((appetizer entree beverage) (food tastes good))) (lambda (name) (display name) (display ": not found") (newline))) food > (lookup-in-table 'main-dish '(((entree dessert) (spaghetti spumoni)) ((appetizer entree beverage) (food tastes good))) (lambda (name) (display name) (display ": not found") (newline))) main-dish: not found >
value
６章でのvalueは引数のS式で表された数式を解釈（計算）する関数だったが、
(value e)は何ですか。ここでeは(car (quote (a b c)))です。
の答えがaなので、valueは引数のS式を解釈（評価）する関数になる。
eのタイプは何ですか。ここでeはconsです。
アトムとしてのconsは*const。
(value e)は何ですか。ここでeはcar。
アトムとしてのcarを評価すると(primitive car)と言うS式になる。
*identifierはプリミティブ以外で定義された名前。*lambdaは関数定義。*applicationは関数が先頭にあり評価可能なS式。*condは特殊構文。
expression-to-action
引数のS式を解釈し、アクションと呼ばれる関数を決める関数。
atom-to-action
補助関数atom-to-action。
アトムに対応するアクション関数を決める。
アトムは定数か#t、#f、基本関数（組み込み関数）か名前。名前は変数でアクションとしては*identifierを対応付けるが、それ以外は全て*constと対応付ける。defineが無いので*identifierとして登場するのは仮引数のみ。
add1?とsub1?はタイポ。
list-to-action
補助関数list-to-action。
S式がリストの場合その先頭要素によってアクション関数を決める。
quote、lambda、condは特殊構文としてそれぞれのアクションを対応付ける。それ以外は*applicationと対応付ける。
アクション
全てのアクションは評価するべきS式と識別子表を引数に取る。*constでは基本関数は(primitive x)と言うS式に評価される。*quoteはS式の第２要素をそのまま返す。
initial-tableは識別子表に名前（識別子）が見つからなかった時に呼ばれる。空リストのcarは取れないので結局エラーとなる。
> (car '()) . . car: expects argument of type <pair>; given () >
アクション*lambdaの結果は、(non-primitive 引数リスト 関数本体）と言うリスト。
meaningはまずeに対してexpression-to-actionを適用してアクションを決める。ここではlist-to-actionが適用されて*lambdaが返る。meaningではそのアクションをeとtableに適用する。*lambdaにeとtableが渡り(non-primitive 識別子表 lambdaの本体）と言うリストが作られる。
evconはcond文を解釈する。
条件式を最初から順番に解釈する
- 条件部分（question-of）がelseであればその式部分（answer-of）の意味する。
- 条件部分を評価して#tが返ればその式部分を意味する。
- 条件部分を評価して#fが返れば、条件式の残りの部分の意味となる。
空リストが渡った時の対処が無いが、この章（この本？）全てにおいてエラーは無い事が前提。evconに関しては必ずどれかの条件が真を返すか、elseがある事が前提となる。
evlisは関数を適用する前に、引数リストの各要素を解釈する関数。
- 引数リストが空であればその意味も空。
- それ以外は最初の要素の意味（meaning (car args) table）と残りのリストを解釈したリスト(evlis (cdr args table)を結合した物を意味する。
*applicationはリストeの最初の要素にmeaningを適用して関数を取り出して、evlisで引数をすべて解釈して、applyを適用する。
applyはmeaningで解釈した関数がprimitiveかnon-primitiveかでその後の解釈の関数を分けている。
apply-primitiveは関数の定義ではなくアトムとしての基本関数名がnameとして入って来る。ほぼそのまま対応するSchemeの関数の適用を意味する事になる。
defineは無いのでprimitiveではない関数は全てクロージャ。
『apply-closureはテーブルを拡張することになります。』とはlambdaに続く仮引数（formals）とvalsとして渡される実引数（values）を対応付けてテーブルに登録する事を意味する。
手続き的に解釈すると：
- new-entryで仮引数のリストと実引数のリストをentryとして纏め
- それをextend-tableでclosureとして渡されて来たテーブルに追加
- そのテーブルを使ってmeaningでclosureのbodyを解釈する
例の解釈を追うと；
クロージャはテーブル、仮引数、定義をリストにしたもの。
テーブル：( ( (u v w) (1 2 3) ) ( (x y z) (4 5 6) ) )
仮引数：(x y)
定義：(cons z x)
実引数は( (a b c) (d e f) )。
仮引数と実引数で新しいentryを作り：( (x y) ( (a b c) (d e f) )
それをテーブルに追加する：( ( (x y) ( (a b c) (d e f) ) ) ( (u v w) (1 2 3) ) ( (x y z) (4 5 6) ) )
定義部分を解釈する。
- meaningにeとして(cons z x)が渡り、tableとして上記のテーブルが渡る。
- expression-to-actionではeはアトムではないのでlist-to-actionでアクションを決める。
- list-to-actionではeの先頭要素がcondなので*applicationをアクションとする。
- eとtableに*applicationを適用する。
- meaningにeとしてcons、tableはそのまま
- consとtableに*constを適用する。
- (*applicationに戻って）(z x)とtableを引数にevlisを適用する
- (*applicationに戻って）(primitive cons)と(6 (a b c))にapplyを適用する。
- (primitive cons)はプリミティブなのでconsと(6 (a b c))にapply-primitiveを適用する。
- apply-primitiveではSchemeの組み込み関数としてのconsを6と(a b c)に適用する。
- 結果として(6 (a b c))とその意味が決まる。
- (primitive cons)はプリミティブなのでconsと(6 (a b c))にapply-primitiveを適用する。
残念ながらこのインタープリタではquoteが使えないので、a、b、cが定義出来ず、上記の例を単純に評価している事は出来ない。
前の章のlengthをYコンビネータで評価すると：
> (value '(((lambda (h) ((lambda (mk-length) (mk-length mk-length)) (lambda (mk-length) (h (lambda (l) ((mk-length mk-length) l)))))) (lambda (length) (lambda (l) (cond ((null? l) 0) (else (add1 (length (cdr l)))))))) '(a b c d e))) 5 >
ノート終わり。
本書のテーマ『再帰』を徹底して勉強しました。C、C++、Javaの世界では再帰関数を書く機会はほぼ皆無ですが、効率云々を度外視すれば整数の演算も再帰で定義出来るし、リストの処理はループで考えるより先頭の要素にのみ着目して関数を考え、残りは再帰処理として考える方が寧ろ形としては自然な気がしてきました。最初は本文でもやっている様にひとステップ毎にトレースして『手続き的』に関数を理解していましたが、段々再帰の形が手に馴染んで来ると一般形としての漸化式の様な関数定義と基底部の定義と言った具合に『宣言的』な理解に頭の中がシフトして行く様な感覚でした。実際にプログラムを作る際にはfilterやmapと言ったより抽象化された道具を使い生の再帰を書く事はないのかも知れませんが、根底にこの感覚を持っている事が肥やしになってくれると期待します。
最後は『あとがき』ではなくで『幕間』と言う事なので、このまま第二幕のScheme修行に突入します。
*1:éが化けてしまうので、ここでは普通にeを使います。
