リリカル☆Lisp開発日記

数日前から言っていますが、はてなようせいさんが可愛いです。
あまりに可愛かったので、わけの分からないものを作ってしまいました。
はてなようせいとまなぶ Schemeの形式的意味論
昨日の夜、はてなようせいで何か作ろうと思い立ち、
今日の朝からずっと書きはじめました。
気が付いたら夜でした。

dynamic-windが多分できました。
「多分」と付いてるのは、あんまり試してないからです。
そもそも本物のSchemeでdynamic-windなんて使ったことがありませんし(笑)
まずは、dynamic-windの途中で脱出する例。

?- eval([store,[[hoge,0]],
[call_cc,
[lambda,[k],
[dynamic-wind,+,
[lambda,[],[k,3]],
[lambda,[],[set,hoge,789]] ]] ]], X).
X = [store, [[hoge, 789]], [values, 3]] ;
No

非常に読みづらいですが、S式に直すと、大域環境が「hoge=0」の時に、

(call/cc
(lambda (k)
(dynamic-wind +
(lambda () (k 3))
(lambda (set! hoge 789)))))
=> 3 (大域環境は「hoge=789」)

ということです。
dynamic-windを途中で脱出していますが、
第三引数であるサンクがちゃんと適用されているのが分かります(hogeに値が設定されている)。
次に、dynamic-windに再突入する例。

?- eval([store,[[cont,0],[hoge,0]],
[dynamic-wind,
[lambda,[],[set,hoge,[+,hoge,1]]],
[lambda,[],[call_cc,[lambda,[k],[set,cont,k],0]]],
+] ], X).
X = [store, [[cont, [throw, '#:G866', [begin0|...]]], [hoge, 1]], [values, 0]] ;
No
?- eval([store, [[cont, [throw, '#:G866', ... ]], [hoge, 1]], [cont,333]], X).
X = [store, [[cont, [throw, '#:G866', [begin0|...]]], [hoge, 2]], [values, 333]] ;
No

またも、死ぬほど読みにくいのでS式に直すと、大域環境が「cont=0, hoge=0」の時に

(dynamic-wind
(lambda () (set! hoge (+ hoge 1)))
(lambda () (call/cc (lambda (k) (set! cont k) 0)))
+)
=> 0 (大域環境は「cont=継続オブジェクト, hoge=1」)
(cont 333)
=> 333 (大域環境は「cont=継続オブジェクト, hoge=2」)

dynamic-windの第二引数のサンクに再突入していますが、
第一引数のサンクが適用されているのが分かります(hogeがインクリメントされている)。
本当は、もっと複雑な例も試すべきなんでしょうが、
評価をしてステップごとの結果を追うのが非常に疲れるのでこれだけで勘弁してください。
多分上手く動いていると思います。

dynamic-windの作成中に大きな問題が発生した。
それは、
「筆記体が読めない！」
R6RSのA.10にあるFigure A.10にある関数定義の並びですが、
真ん中の関数名は恐らくKだと思います。
そう考えると上はJではないのかと推測できるんですが、
下もJのように見えます。そもそもどっちもJじゃない気もします。
文字が読めずに行き詰る、自分のあまりの頭の悪さに泣きました。
あと、はてなようせいが可愛いです。

とある方からの勧めで、「Three Implementation Models for Scheme」を読み始めました。
180ページもあって「うげー」という感じだったのですが、1ページあたりの文字の量が少なく、
また、内容もソースが多くて読みやすかったのでむしろ「ほへー」という感じでした。
—
4章まで読み終わったので、適当なまとめを書いておきます。

• Schemeは関数と継続がfirst class objectで末尾呼出、代入のサポートも必要
  => 従来のコンパイラ/インタプリタの手法が使いにくい
• 全てをヒープにおくことによってコンパイラとVMを作ることができる
  => ただし、動作が遅い
• スタックを使えば速い(変数などもスタックに入れる)
  => first classの関数、継続、末尾呼出、代入はそのままではサポートできない
• スタックを継続オブジェクトに丸ごとコピーすることで継続を実装
  => もちろん遅いが、継続の作成はそう頻繁には起こらないと仮定すれば大丈夫
• Display Closureに関数とその自由変数の値(のコピー)を持たせてヒープに置く
  => これにより関数をfirst classにできる
• 以上の手法を使うと、継続と関数の持つ変数の値はコピーであるため、代入に対応できない
  => set!を使う変数だけを特別扱いして対処(MLの参照型のようにする)
• set!を使う変数は値をヒープにもち、変数自体にはヒープへの参照を持たせる
  => 変数のコピーも同じ領域を指すので代入に対応できる
• 末尾呼出の最適化はスタックの使い方を工夫すればできる
• あと色々工夫すればさらに速くできる

たぶんこんな感じです。
英語が良く分からなくてもソースさえ読めれば結構分かるので、
英語が苦手な方にもお勧め。

～前回のあらすじ～

やる夫：
「世の中は広いお…
本を出したり、すごいモノつくってる人たちの中に混じって、
ゆとり世代の大学生がgauche.nightに出るのは
無理があったかもしれないお…」
先輩：
「大丈夫だってヴぁ！　秘策があるってヴァ！」
やる夫：
「先輩、助かります！」
（この先輩は色々とすごいひとだお！きっといい案があるに違いないお！）
先輩：

～以上あらすじ～
で、ここで出てきたTシャツ(以後「ゆとりTシャツ」)ですが、本当につくってgauche.nightで着ます。
ゆとり世代っぽいTシャツを着てる人がいれば私と思ってください。
ゆとりTシャツイメージ図

六角形はゆとりの嗜み^(*1)である
「円周率 = およそ3」
の象徴です。
Rの意味はレーシングラグーン^(*2)をやればきっとわかるはずです。
(*1)ゆとりの嗜み
「円周率 = およそ3」という素晴らしいものは、テレビなどでさんざん聞きましたが、
実際にそれで授業を受けたという人は聞いたことがありません。
私の学校ではむしろ「えー、この内容は君達の年からは範囲外になりましたがやります。」
という風に国の方針を無視した教師の方が多かったぐらいでした。
(*2)レーシングラグーン
ファイナルファンタジーシリーズで有名なスクウェアが販売した
「High Speed Driving RPG」
という独特すぎるジャンルのゲーム。
ちなみに、このRPGは”Racing Poem Game”の略という説が有力。
登場するキャラクタはみんな異常に詩人であり、語りだすと台詞が妙に長く、
1)やたらとアルファベットを使う、2)三点リーダ「…」を多用する、
3)語尾は「○○さ……」、4)台詞の最後には「……冗談じゃねえ……」
を基本とする。以上条件を満たすしゃべり方を「ラグーン語」「ラグーニッシュ」などといい、
レーシングラグーンのファンの間では日常的に使用されている。
ラグーニッシュの例:
「……KYOTO……」
「毎日……この街で
　朝と夜が繰り返される」
「今の俺には街がNightなのかMidNightなのかも分からないのさ……」
「こんな俺を……最速の彼方に送ってくれた
　SQUAREさんにＲを捧げさせてもらうさ……」
「時間なんて、関係ないな……」
「サガフロやFinalFantasy流に言えば
　プレイ中に現実の時間を気にしないことに近い」
「……冗談じゃねえ……」

わーい ＼（＾o＾）／ Prologで書いたSchemeインタプリタにcall/ccが付いたよー！

?- eval_step([store,[], [+, [call_cc, [lambda,[k], [k,99], 1 ]], 1] ], X).
[store, [], [[lambda, [#:G1716], [+, #:G1716, 1]],
[call_cc, [lambda, [k], [k, 99], 1]]]]
[store, [], [[lambda, [#:G1716], [+, #:G1716, 1]],
[[lambda, [k], [k, 99], 1],
[throw, #:G1730, [[lambda, [#:G1716], [+, #:G1716, 1]], #:G1730]]]]]
[store, [], [[lambda, [#:G1716], [+, #:G1716, 1]],
[[lambda, [], [[throw, #:G1730, [[lambda, [#:G1716], [+, #:G1716, 1]], #:G1730]], 99], 1]]]]
[store, [], [[lambda, [#:G1716], [+, #:G1716, 1]],
[begin, [[throw, #:G1730, [[lambda, [#:G1716], [+, #:G1716, 1]], #:G1730]], 99], 1]]]
[store, [], [[lambda, [#:G1716], [+, #:G1716, 1]], [values, 99]]]
[store, [], [[lambda, [#:G1716], [+, #:G1716, 1]], 99]]
[store, [], [[lambda, [], [+, 99, 1]]]]
[store, [], [begin, [+, 99, 1]]]
[store, [], [+, 99, 1]]
[store, [], 100]
[store, [], [values, 100]]
X = [store, [], [values, 100]] ;
No

式”(+ (call/cc (lambda (k) (k 99) 1)) 1)”の評価を行っています。
注目すべきは2ステップ目。
call/ccによって継続オブジェクトが作られていますが、
その内容は「何かを受け取って1を足す “(lambda (#:G1716) (+ #:G1716 1))”」であり、
これはまさに最初の式のcall/ccの箇所を別のものに変えた関数です。
見事なまでに現在の継続が作られています。
あとはdynamic-windの規則を作れば完全なcall/ccとなるはずです。

昨日の続き。
誤字かと思っていたところは誤字ではなかったようです。
quoteを含まないと書いてある非終端記号procが
proc ::= pp | null | ‘sym | sqv | (make-cond string)
と定義されており、思いっきりquoteを含んでるから、これはsymの間違いと思ったのですが、
sym ::= [variable except dot]
x ::= [variable except dot and keyword]
とあり、もしquoteを外すと、シンボルと変数が区別できなくなり、
おまけにquoteの評価の規則を見ると、
‘sym -> ‘sym
であり、シンボルに付いているquoteは外さないようです。
つまり、クォートが付いていればシンボル、付いていなければ変数。
最終結果にも平気でquoteが付いたままになります。
……こんな定義でいいのか? R6RS。

R6RSのAppendix AにはSchemeのサブセットの形式的意味論が載っています。
形式意味論というからには、しっかりと定義してある。
しっかりと定義してあるからには、論理的に正しい。
論理的に正しい、ということはPrologで書くことができる。
という謎の発想が生まれたのでPrologでこの形式的意味論に沿った
Schemeインタプリタを書いてみることにしました。
言い訳をしておきますが、Prologをまともに使うのは初めてです^(*1)。
まだ、作っている途中なのですが、ある程度動いたので、
とりあえず、先に実行結果とソース(つくりかけで非常に汚い)を載せておきます。

?- gen_atom(seed).
Yes
?- eval([store,[], [begin, 1, 2]], X).
X = [store, [], [values, 2]] ;
No
?- eval([store,[], [if, [+,1,2], [+,3,4], [+,5,6]]], X).
X = [store, [], [values, 7]] ;
No

ソース
入力/表示形式がPrologのリストで非常に見づらいですがお許し下さい。
最初の gen_atom はユニークなアトムを得るための述語(Lispで言うところのgensym)の初期化。
入力においての [store, X, Y] はXが抽象マシンのストア(メモリ)の内容、Yが評価すべき式。
出力においてはYが得られた式の値となります。
(詳しくはR6RSのAppendix Aを読んでください。)
未束縛の変数を気軽に扱ったりできて、Prologって楽しいですね。
しかし、今回に関してはなんといっても、
簡単なBNFを写して、 即 パース♪
といった感じでした。
遊びなので効率は気にしない方向で。
けど、評価文脈に沿って評価を行うというのが非常に辛かったです。
評価文脈の穴が三種類(通常用、多値用、単一値用)あるということを無視して放置していたら、
あとで、評価文脈関連の述語全てに引数を一つ付け足す羽目になったり、
あと、実行結果がおかしいと思ったら、原因がR6RSの誤字^(*2)だったり。
(*1)「リストをアペンドするプログラムくらいなら書いたことあります。」という程度。
(*2)Figure A.2aのnoprocの ‘sym は恐らく sym の誤り。

「コンピュータプログラミングの概念・技法・モデル」という本で、
Ozというプログラミング言語の説明を見ていたら、驚かされる記述がありました。
それは、ただの、素朴なmapの定義です。

fun {Map Xs F}
case Xs
of nil then nil
[] X|Xr then {F X} | {Map Xr F}
end
end

独特な記法の言語なので、Schemeで書き直すと、次のようなものです。

(define (map xs f)
(cond ((null? xs) '())
(else (cons (f (car x))
(map (cdr x) f)))))

このプログラムですが、末尾再帰に書き直されて、
反復構造になるらしいです。
リストを構成する途中で再帰呼び出しをしているため、
普通は末尾再帰の形に直らないだろうと思っていたのですが、
Ozの場合、このプログラムが以下のように直せるようです。

proc {Map Xs F Ys}
case Xs of nil then nil
else case Xs of X|Xr then
local Y Yr in
Ys = Y|Yr
{F X Y}
{Map Xr F Yr}
end
end
end

procは手続きの定義で、第三引数Ysは参照渡しで結果が格納されます。
『Ys=Y|Yr』とすることにより、CAR部がY、CDR部がYrのコンスをYsに格納しますが、
この時点でYとYr(という識別子の指す変数)は束縛されていません。
しかし、これはOzの上では全く問題ありません。
続く、二つの手続き呼び出しにより、YとYrに値が格納され、
結果として、Ysにも値が入っているという仕組みらしいです。
これはかなり衝撃的でした。
痺れる……

昨日から読んでた「ふつうのHaskell」ですが、大体読み終わりました。
モナドについては、正直よく分かりませんでした。
ちゃんと勉強すると時間がかかりそうなので、後回しにしておきます。
で、Haskellそのものですが、なんだかあまり好きになれない感じでした。
どこが気に入らなかったのか自分でも良く分からないのですが。
ひょっとしたら単純に(変数に)型のない言語の方が好きなのかも知れません。
(好きな言語を考えてみると、Cを除いたら型のない言語ばかりだった(笑))