リリカル☆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!を使う変数は値をヒープにもち、変数自体にはヒープへの参照を持たせる
  => 変数のコピーも同じ領域を指すので代入に対応できる
• 末尾呼出の最適化はスタックの使い方を工夫すればできる
• あと色々工夫すればさらに速くできる

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

わーい ＼（＾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を除いたら型のない言語ばかりだった(笑))

『ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門』を買いました。
Haskellの本を買うのは初めてなんですが、私がHaskellに抱いていたイメージとして
「インデントでブロックを表す言語」というものがありまして、まあ、実際その通りなんですが、

「{ }」と「;」を使うと、複数の式を束ねる構文がインデントを使わずに記述できます。
(7.2節 レイアウト)

とあり、実は

main = do {
cs <- getContents;
putStr cs
}

こんな書き方もできるようです。
ああ、これなら読みやすい……と一瞬思ったのですが、
Haskell使ってる方は使ってないような気がします。
(使ってたら、逆にインデントの話の方がマイナーな話になるだろうし。)
だとしたら、あまり使わない方がいいですね。
とりあえず、最初の方は大体読んだので、
たのしみにしていたモナドの説明は明日にでも読めそうです。
ワクワクして寝れなくなったら今日中に読むかもしれませんが(笑)
話は変わりますが、
「car/cdrを使っていたらCommonLispを使う職場で笑われて、
それ以降はfirst/restを使うようにした」
なんて記事を読んだことがあるのですが、そんなもんなんですかね。
本しか読んでないとその言語の常識ってのがいまいち分からないです。