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

Route 477



2008-01-19

[biwascheme] クロージャを実行するような関数をjsレベルで定義できるようにした

BiwaSchemeでは、基本的にライブラリは全てJavaScriptで書くことにしている。

が、ここで問題になるのが、mapのように中でSchemeのクロージャを呼ぶような関数だ。 クロージャが実行中にスタックを参照することもあるので、単純に新しいインタプリタを起動するわけにはいかない。

とすると動的に中間コードを生成する方法が思い浮かぶが、単純にクロージャを実行する中間コードを返してはいおしまい、というわけにもいかない。 mapのようにクロージャを何回も呼ぶ場合があるからだ。

悩んだ末に、こんな感じに書けるようにしてみた。

  define_libfunc("map", 2, null, function(ar){
    var proc = ar[0], ls = ar[1];
    var a = [];
    
    if(ls == nil)
      return nil;
    else{
      return new Call(proc, [ls.car], function(ar){
        a.push(ar[0]);
        ls = ls.cdr;
        if(ls == nil)
          return a.to_list();
        else
          return new Call(proc, [ls.car], arguments.callee); //無名再帰。JavaScriptは便利である
      })
    }
  })

まず、ライブラリ関数の中で、呼びたいクロージャ、それへの引数、クロージャを呼んだあとの処理(after)をまとめたオブジェクト (Callというクラスのインスタンス)を作り、それをreturnで返してやる。

インタプリタは、ライブラリ関数がCallを返したら、「クロージャを実行したあと、その結果を引数にして afterを呼び出す」という処理を表す中間コードを生成し、それを実行することにする。

これで、今のところちゃんと動いているようだ。

(let1 a 1
  (map (lambda (x) a) '(1 2 3)))  ;=> (1 1 1)

考えること:

  • これで本当に大丈夫か?おかしくなるケースはないか?
  • JavaScriptで書けるっていうけど、必ずCPS形式で書かんといかんよね?それはもうSchemeで書いた方が楽では?w
  • 変数のスコープとか大丈夫か?そのaが外から破壊されることはないか?
  • スタック溢れたりしない?
    • Callを返す→そのafterを呼ぶ→Callを返す→afterを…なので、after自体がネストして呼ばれるわけではない。ので大丈夫。

[biwascheme] BiwaScheme 0.3をリリースしました

びわこ開発合宿#2に来ています。本当は修論書きを頑張るはずだったんですが… どうしちゃったんでしょう。

0.2からだいぶ機能が増えたので、BiwaScheme 0.3をリリースしました。 ダウンロードはこちらから→BiwaScheme

変更点は以下です。

new

  • 関数が増えた
    • $ (getelemと同じ、($ "hoge")とか)
    • vector関係
    • 文字関係
    • リスト関係(append, list?, for-each, write/ss, equal?)
    • map系、for-each系(まだ複数のリストは未対応)
  • 構文展開を実装し、構文が増えた
    • and, or, let*, when, unless, let1, letrec, letrec*(このへんちょっとあやしい)
  • quasiquote, unquote (vectorはまだ)
  • ポートの導入
    • 文字列ポート(open-output-string, get-output-string)とか

change

  • ディレクトリ構成を変更 (lib/, test/)

fix

  • caarからcadddrまでの実装が逆になってた(cadrがcdarの意味になってた^^;)のを修正
  • to_scmという変な関数を、to_writeとto_displayに分離(それぞれwrite/display的に文字列化)

気がついたら、R6RSの標準関数が8割くらい実装できていました。 そろそろ標準ライブラリにも手を出すかなぁ。Chapter 3 List utilitiesとか。

[misc] ソリティアとマインスイーパーにつぎ込まれる労力を有効活用できないか

風呂場で、「現実逃避にソリティアとかついやっちゃいますよねー」という話をしたんですが。

ruby-minisatというライブラリがあります。

数独などのパズルの盤面を、SATという単純な問題に落とし込むことで、SAT用の高速なソルバがそのまま利用できてウマーというものです。 SATをパズル問題の中間言語として使うわけですね。

ということは、SETI@home などで必要な計算をSATに変換して、さらにそれをマインスイーパーの問題に落とし込めば、 ゲームで遊びながらSETI@homeに協力することが可能なのではないでしょうか?

ってもちろん、人間がマインスイーパーを解くより、コンピュータがSATの解を見つける方がはるかに速いので、 できたところであまり意味はないんですが(^^;。

でも画像認識のように人間の方が優れている問題もあるので、うまくそういう問題に変換することができたら…。 「マインスイーパーを解き続けるだけの簡単なお仕事です」なんてバイトができる時代になるかも。

cf. エ□グリッドコンピューティング