snow
なぜに?
Schemeを作るために実装の資料を探しているうちにこちらにたどり着きました。
いずこへ?
ゲームでも使えるリアルタイム性の高い組み込み用の実装を模索しています。
現在、自作のインタープリターを使い、起動コストの小さいIncremental GCの実験をしています。
- Shiro: おもしろそうなので、Scheme:組込み・リアルタイム用処理系 で語って下さい。
なぜ「Schemeなのか?」と問われれば、「男のロマンかな...」と答えることにしています(笑
謝辞
Schemeと出会ったのは大学4年のときです、10数年前になります。研究室の先輩がMac Plus用のMacSchemeという実装を持っていました。
先輩は「この言語はすぐれものだ」とか言っていたのですが...その時は聞き流していました^^;
ちなみに「オブジェクト指向」もそのとき聞いたのですが...やっぱり聞き流していました、ダメ学生だったので(涙)
でも、そのことが記憶に残っていたので今Schemeを書いています。先輩感謝です。
インタープリターを作ってみて思ふ
Schemeの仕様ってよく考えてあるな〜
参りました m(_ _)m
R5RS5かく語りき
internal defineはボディーの頭の部分にしか書いてはいけない
evalで新しい束縛を作ってはならない(interaction-enviromentは除く)
etc.
最初は「なんで?」と思ったけど、インタープリターを書いて見てなるほどと思った。
やっぱり新言語を作るにはセンスが必要なんだな〜
俺には無理なのか?...(涙)
野望
ところで、インタープリターを作っていて一番困ったのがテストであった...
最初はSCMのr4rstest.scmが通ればOKと思ったが全然甘かった^^;
で、あっちこっちの実装についているテストを片っ端からやって見ようとおもったのだが、テストがその処理系の固有機能を使って書いてあったり、最初がいきなり"define-syntax"だったり...そこまでつくってないっちゅ〜の(涙)
仕方が無いから、テストに必要な"define-macro"を作ったりテストルーチンを書き直したりするのだが....
それを動かすためにテストがひつようなんだよ〜ん(涙
というわけで、今の処理系が一通り動いたらスケーラブルでリッチなテスト用スイートを作ろうと策略している。これなら俺でも貢献できそうだしね(笑
そのときの為に、私の通ってきた道筋を書いておくことにする、皆のも教えてくれると嬉しいな〜(ここで捕まったとか...)
- まずGNUでSCM発見。
- SCMのソースを読む...わけわかんなくて挫折。
- mini-schemeを発見、ダウンロードして動かす。
- おお動く動く、continuationもdelayもforceも動く!
- お決まりのeightqueenでも.... 轟沈(注:答えはでるんだけどね^^;)
- mini-schemeがなぜに遅いのかを研究して第一号自作開始
- SCMの2.5倍くらいまで性能を上げる。(注:もちろん2.5倍遅い....)
- == さてここから本題 ==
- SCMのr4rstest.scmを通るまでデバッグ。これはインタープリターだしTRACE機能をつければ比較的簡単。continuationとforce, delayはmini-schemeの振る舞いと比較すれば動くようにできる(注:mini-schemeの実装は正確でない)。quasiquoteで捕まった。がしかしr4rstest.scmのサンプルは簡単なので通るようになった。
- 次にslibが動くようにデバッグ。loadの振る舞いが違っていたためチョット捕まる
- define-syntaxに挑むにあたりslibのmbeを動くように頑張るが、かな〜り捕まる。
- defmacroが必要なのでこれを作る...簡単(実際にはdefine-macroを作った)
- 正しくmacroが展開されない。その原因がquasiquoteにあることを発見
- quasiquoteのテストを探して片っ端からテスト
- 行き詰まったところでR5RSの英語ドキュメントを読む。
- 仕様の勘違いに気が付く....ほどなく動く->教訓:面倒がらずに原書を読め!(笑)
- slibを片っ端から動かす
- schelogでめちゃめちゃ捕まる
- continuationの再起動で問題が発生していることはすぐ判明
- ところがこいつのデバッグが難しい...なにしろcontinuationをちゃんと理解していないのだから...(涙
- continuation、それも変なやつを探して片っ端からテスト。これにはbiglooのテストがとても役に立った。書き換えの必要も少なくおまけにその他の大量のテストを行うこともできるようになった。
- わかってみれば簡単なことだったのだが、問題はlet等の初期値を評価する部分でcall/cc、これの再起動が繰り返されると...そのたびに新しい束縛がどんどん溜まる事が原因だった。Gaucheで引数フレームだけはstackにコピーバックしている理由がここでやっと理解できた気がした。がしかし一号機はstackを使っていない(SCMのECACHEに似た方法だった)....効率は悪いが別の方法でやり過ごすことにする。
- schelogが動き、slibが動くようになるとずいぶん楽になった。あとはbiglooのテストを端からクリアーしていく。
- === 一寸脱線 ===
- 本当はハイジェネマクロを実装してから書き直すつもりだったのだが...度重なるデバッグでソースがあまりに汚くなったので書き直すことにする。
- 2号機完成。SCMに全然かなわない(2倍くらいまで詰め寄ったが...)
- SCMがmemoizeという反則技(嘘)を使っていることに気が付き、変数の参照に同様な仕組みを作ってみるが...チビットしか改善しない。
- 遅い原因を調べ、また2号機の振る舞いから素のインタープリターでもcontrol stackを使った実装が可能と判断し3号機製作開始
- これよりハイジェネマクロに挑む。ここまでで4ヶ月...(涙)
- 力いっぱい捕まったので、マクロの勉強しながらGCを改良することにする(笑
- 3号機のGCがようやく安定した。CONSは他のシステムとの整合性を簡単に取りたいのでmark & sweep(後日mark & lazy-sweepにする予定)、で環境やコンティニュエーションなど外から直接アクセスする必要の無い部分にはCopyGCのハイブリッドだ。 これはイカスと思ったのだが....実装中に問題発生^^;....CPUのスタックに生きている環境を指すポインターが入っている場合、当然回収したい...しか〜し「生きている環境を指すポインター」って簡単にはわからな〜いってことに気が付いた。 これは環境は束縛を持っているので可変長であることに起因する。C/C++のGCとかでは当たり前の問題なんだけどね。いや〜気が付かなかったね〜、ばかな俺(涙。 一瞬"B"の字が走馬灯の様に脳みそに現れたが、よく考えれば「CPUのスタックだけに生きている環境へのポインターが存在する状況は新しい環境の作成時に限られる」のはず!。で注意深くコードを直してお守りのコメントを入れておく。 でテストテストテスト〜のつもりがイキナリrs4test.scmに門前返しを食らう。(SECTION 5 2 2)だ。「誰が書くんじゃ〜そんなコード」と突っ込みを入れても仕方ない。 原因は、こいつはヒープにセーブされた環境に束縛を追加しようとするからだった。コンパイラーには何でも無いこのコード(推定)も素のインタープリターには鬼門だ。このタイプのコードで(letとかはチット違う)は最後にlambdaでセーブされた環境に束縛が追加される。 今回環境用のヒープはCopyGCなので新しい環境は上から順番に埋まっていく。だからお尻を単純に延ばしてもOKのはずだった、はずだった、はずだった.....(涙 CopyGCで順番が入れ替わるのをかんがえていなかったのだ..ガ〜ン T_T 結局親には見せられない恥ずかしコードでこれを回避する。 気を取り直して次はincremental化だ。燃えるぜ〜(笑
雑感:現存するテストはOK、NGしか返さない。 「結果がコレなら原因はコレの可能性がある」といった情報の得られるテストがあったなら...もっと楽だったのに...と思ふ。
- テストがFailする理由を一発で知るのは一般的には無理、ってのは言えてると思います。XPのUnitTestのスタイルもそれに由来して、テストも(テスト対象物も)少しづつ成長させることで、"理由"を見失う時間を極力短くするようにしているわけで。
- 経験に基づいて傾向を把握する、ってのは可能かも知れません。つまりFailしたら原因を探すということを繰り返して統計(?)を取る。
- ただ、どっちかってーと自分でやるよりも「先人の膨大な記録」が欲しくなりそうです。それに処理系依存でその統計がフラつくなら、そもそも無意味だし。--戯
- snow「先人の膨大な記録」<-まさにそれが肝だと思います。「私は、このテストで失敗した、原因はこれこれだった」の羅列でも非常に役に立つと思います。たとえばGCでも「スタック上の環境をルートセットにしたが、バインドされたクロージャーの環境がそれにリンクしており、markしている最中に予期せぬ所で灰色を黒色に書き換えていた。ルートセットをすべてマークスタックに納めてからmarkを開始すると直った」といった情報です。でもこんな情報って作っている最中に書きためないと...忘れちゃうんですよね^^; そこが問題かも....
- 戯 ん。これは逆に面白いかも。Failした時点のソースを捨てずに保存し、Failから復帰するまでの更正記録(笑)を見ることで、何かが得られるかも。そう考えると益々、従来の一般的(XP含む)なソース管理方式と違って「下書き」を保存する価値が増してくるなあ…
- snow「先人の膨大な記録」<-まさにそれが肝だと思います。「私は、このテストで失敗した、原因はこれこれだった」の羅列でも非常に役に立つと思います。たとえばGCでも「スタック上の環境をルートセットにしたが、バインドされたクロージャーの環境がそれにリンクしており、markしている最中に予期せぬ所で灰色を黒色に書き換えていた。ルートセットをすべてマークスタックに納めてからmarkを開始すると直った」といった情報です。でもこんな情報って作っている最中に書きためないと...忘れちゃうんですよね^^; そこが問題かも....
- ただ、どっちかってーと自分でやるよりも「先人の膨大な記録」が欲しくなりそうです。それに処理系依存でその統計がフラつくなら、そもそも無意味だし。--戯
- てゆーか言語処理系の試験はUnitTestじゃなく全体Testだ罠。UnitTestより更に"知る"のが困難と思われ。
- snow:確かに言語処理系の完全性をテストすることを考えると....気絶しそうですね^^;そこまでは考えない様にします(笑
- 経験に基づいて傾向を把握する、ってのは可能かも知れません。つまりFailしたら原因を探すということを繰り返して統計(?)を取る。
Another something completely different - Monty Pythonより
モンティーパイソンといってもPythonの新しい実装かと思われそうな今日このごろですが(笑
- snow:今日「昭和二十七年」と「昭和二十八年」のギザつき十円玉をゲット〜〜〜〜 ジュースの自販機からツモリました!これが日常生活の中の「ささやかな幸福」ってやつでしょうか。私が趣味で実装を作るのも、やはり「ささやかな幸福」の味が忘れられないからのような気がします。だって新しい機能が動く度に幸せなんだもん。でも女房にはどちらも理解してもらえないです^^;
- 「いや〜二十年代を自販機から2つも出すとは驚きですね〜。この年代のはスリ減ったやつが多くてコインセレクター通らないのが多いからね〜。その自販機の近辺は要チェックだね〜。」by(財)日本ギザ付き十円玉保存会(嘘
- silk_warm_eel テストフレームワークを作ってしまいました。 もしよければ、参照ください。 私の名前のところからいけます。