Route 477(2007-11-19)

2007-11-19

■ [event] LiveCoding#5に参加します

http://cotocoto.jp/event/2936

12/1に大阪で行われるLiveCodingというイベントに参加させていただくことになりました。今回はLiveCoder側です。何作ろうかなぁ。

定員が少ないらしいので、申し込みはお早めにどうぞ。

■ [javascript][scheme] BiwaSchemeを公開しました

Javascriptで書かれたScheme処理系「BiwaScheme」を公開しました。

Kent Dyvbigの「Three implementation models for scheme」の4章を参考に作られています。スタックベース・中間言語方式で、call/cc、set!が実装されています。マクロはまだありません。構文もまだ基本的なものしか用意されていません。

コア部分はブラウザに依存しないので、SpiderMonkey等のコマンドラインの処理系でも動作します。 IE6.0, Firefox2.0, SpiderMonkey1.6.1, CScript(WSH5.6)で動作を確認しています。

デモ

実行の様子のダンプ
ユニットテスト (JSSpec)
インタラクティブな評価(REPL)
Hello World
- OreScript精神に則り、scriptタグの中にS式を書くだけで実行されるようにしてみました :-)

                <script src="biwascheme.js">
                (display "Hello, World!")
                </script>

- 参考：
  - OreScript時代の幕開け - yukobaの日記
  - JS オレオレ言語ブーム - IT戦記

他の処理系について

jsScheme
- Javascriptで書かれたものとしては、現時点で一番完成度の高い処理系です。R5RSにほぼ準拠しています。call/cc、マクロ、JITコンパイル等の機能があります。パーザ部分をそのまま流用させていただいてます。
WebScheme
- 卒論のときにいじっていたもので、上のjsSchemeにWeb関連の機能を加えたものです。実行速度があまり速くないのと、JITと継続の相性が悪いことが、今回の再実装の動機になりました。
id:gnarlさんのやつ
- 言語開発合宿の時に(隣の席で)作られていたものです。同じドキュメントを参考に作られていますが、4章ではなく3章がベースになっているようです。
地獄Scheme
- 京都の若きLisper、zickさんによる処理系です。ソースがなんとなくCっぽいです。BiwaSchemeのソースはSchemeっぽいかもしれません(元がScheme in Schemeなので)。CodeZineの記事のアップグレード版のようです。
id:higeponさんのやつ(C++)
- こっちは4章ベースなので、実はBiwaSchemeと一番似た構造になっているはずです。が、向こうはどんどん実装が進むので、こっちも追いつかねばという気にさせられて開発が進みました(笑)。ありがとうございます。

今後の予定

APIの拡張: とりあえずWebScheme相当の機能は載せる予定。
構文の拡張: condとかまだ実装してない構文を。
関数の拡張: jsSchemeがR5RSベースなので、こっちはR6RS準拠を目指すことにします(笑)。
パーザを自前のものに: #0等の記法に対応したい。

■ [biwascheme] メモ

higepon版(←そろそろなんか名前をつけてほしいな)との違いとか、もう少し詳しく。

コンパイラ部分の実装言語
- BiwaSchemeはコンパイラ部分もJavascriptで実装している(というか、Scheme版を作ろうとはしたんだけどうまく動かなかったんで、選択肢が無く…。ほとんどコピペするだけなのに…。)
ライブラリの実装言語
- BiwaSchemeは、ライブラリ関数もなるべくJavascriptで書く予定です。高速化のために。
- …しかし本当に速くなるんだろな。まぁ関数によるか。
- mapとか、高階関数をどうするか考え中。
ライブラリのarity
- jsSchemeはエラーチェックがほとんど無かったので、その辺をもうちょっとなんとかしたい。
- とりあえずライブラリ関数は「引数の最小個数」「引数の最大個数(無限の場合はnull)」をデータとして持つようにした。
- というのを実装するために、apply命令の引数を一つ増やした(渡された引数の数)。
関数のarity
- 可変長引数はまだ実装してないんだけど、そろそろ実装しないとな。
- 「もはや誰向けの記事だか分かったものではない」と書かれているけど、俺が参考にしますｗ
正規表現
- どうしようかなぁ。
命令コードの定数化
- これはすごいｗｗｗ
- やりたいけど、デバッグとか大変にならないかなぁ。デバッグ時だけ命令コードを文字列で出力すればいいのか。
- どれくらい高速化できるかわからんので、もうちょっと動かしたいコードの規模が大きくなってからでいいかな。
read
- Gaucheのが使いまわせるのは正直うらやましいｗ
letとかbeginとか(1, 2)
- 今のところ、リスト操作のコードをJavascriptで書いて対処している。
- jsSchemeはこのへんを「Schemeで書いた処理をJITコンパイルしたコード」で行ってて、結構時間を食ってたような。
- まぁリスト操作とかSchemeの方が100倍楽なのは明らかなんだが。変換にかかるコード量がそんなに多くないので今のところおｋ。
数値演算を組み込み命令に
- どうしようかなぁパート2。
- これももっと大きくなってから検討するか。
global
- jsSchemeにはTopEnvとCoreEnvという2種類のグローバル環境があって、TopEnvはユーザ用、CoreEnvは標準ライブラリ用と分かれていた。
- ので、BiwaSchemeも最初はrefer-topenvとrefer-coreenvとか作ってたんだけど、よく考えると分ける必要が分からないのでrefer-globalに統一した。
命令の引数順序
- frameの第二引数と第三引数を入れ替えたりした。こうすると、ダンプしたときに frame→関数→残りの処理という順序になる(実行順序と見た目が一致する)ので分かりやすい。
define
- (define a (lambda () b)) (define b 1) (display (a)) みたいなコードってvalidなんですよね。嫌だなぁ…(笑)。
- あとでやる。
jsSchemeとの違い(気をつけているところ)
- 速度を気にする。
- 名前空間を汚さない。
- コンソールでも動く。
- デバッガ(←というほどのものでもない)を頑張る。
  - HTML+Javascriptは画面を作るのがとても簡単で良いです。やっぱりログに色付けしたりレイアウトできるのは大きいなぁ。
  - デバッガが楽しいと開発も楽しい。
ユニットテスト
- 「これが通ったらR6RS認定！」みたいなテストケースがどっかに落ちてないものか。
行程
- 9月前半：印刷したまま放置してあった3imp.pdfを(超適当に)流し読みした。
- 9月後半：KMCのコーディング合宿があったので、3章のヒープベースのを実装してみる。というのが言語開発合宿でid:gnarlさんと思いっきり被って焦ったｗ。
- 10月前半：ヒープベースのが一応動く。が、下手にオリジナリティを加えたせいで3.5の改良ができないことに気付く。なんとなく放置。
- 10月後半：酔った勢いで(LiveEatingの日ですね)、スタックベースも動かしたくなる。4章をひたすらjsにコンバートする(酔っているのでコードの意味は理解していない)。
  - 変数の型がないので四苦八苦しつつデバッグする。
  - 前回の経験を生かし、できるだけ原点に忠実に移植。
  - 構造は違えど、作業としては2回目なので楽。2回目いいよ2回目。
- 11月前半：「4章を真面目に読まないとどうしようもない」という結論に達する。そりゃそうだろjk。
  - setと書いてあるのに追加順序に意味があることに気付き愕然とする。孔明の罠か。
  - collect_freeはSetを引数に取るべきなのに、Pairを渡していたことが(ようやく)発覚。リストの長さを求めるコードが動いた。
  - call/ccとset!を実装した。第4章完。
- 11月後半：構文や関数を追加したりなんだり←いまここ

■ [biwascheme] あーあと

http://b.hatena.ne.jp/todesking/%e8%a8%80%e8%aa%9e%e3%81%ae%e5%ae%9f%e8%a3%85/ が参考になるという噂。

http://noncopyable.hp.infoseek.co.jp/soft01/make_cps.html とか凄いな。すごすぎるな(笑)。C++怖い。

// ありがちな関数内再帰関数（こういうのが C++ での CPS 変数となるらしい）
int s_expr_tail(vector<var_t>& _){
  struct __  : boost::noncopyable {
    int ___; __() : ___(0) {} typedef vector<var_t> ____;
    int _____(____& ______) {
      ______.push_back(regist_num(___++));    // 式の終点にレジスタを置く
      ____::iterator _______(______.begin()),________(______.end());
      for(;_______!=________;++_______){
        if(var_t::type_num<____>() == _______->which() ){
          (void)_____(get<____>(*_______));
        }
      }
      return ___;
    }
  } _________;
  return _________._____(_); // 下バー使いまくり
}

[ツッコミを入れる]

トップ «前の日記(2007-11-18) 最新次の日記(2007-11-20)» 編集

Route 477