Gauche:ImplicitFuture

Gauche:ImplicitFuture

Shiro(2010/05/13 02:15:14 PDT): d.y.d - 未来の国のアリス で紹介されてるimplicit futureがいいなと思ったのでちょっと考えてみた。

これは、ファーストクラスの値を「後で計算する」ことにしておける仕組み。 感覚としてはdelay/forceと似ているけれど、Schemeの場合、 promiseは値そのものとは別種のオブジェクトになってしまう。 implicit futureは値を使う側にはその仕組みの存在がまったく見えない。

そういう仕組みの必要性にというのは実際にあって、srfi-10記法 #,(...) の中で srfi-38記法 #n# が使われる場合がそうだ。 (Gauche:循環リストの読み書き)。

  #0=#,(myobject #0#)

みたいに循環されると、myobjectのコンストラクタに渡す値としてmyobjectの コンストラクタの戻り値が必要、という矛盾につきあたる。 今は仕方ないので、まだ確定していない値の参照をコンストラクタに渡す 時は #<read-reference> という特殊なオブジェクトを渡している。 myobjectのコンストラクタは 「#<read-reference> の値が決定した 時に呼ばれるコールバック」を登録することができて、 readが完了した時にはコールバックによって確定値が埋められる、という寸法だ。

ただ、全てのread time constructorで陽に#<read-reference>を チェックしないとならないし、コンストラクト時に引数の値が確定していないと ならないオブジェクトもあるので、万能ではない。なので今でもどうしようか 迷っててundocumentedにしてある。

もしシステムレベルでimplicit future(のようなもの)を扱えるなら、 #0#の箇所ではfutureを渡してやればいい。

(このケースではむしろ欲しいのはimplicit forceだけど。 両者の違いは、implicit futureでは値を見に行って決まってなかったら 誰か他の人が計算してれるまで自分は待つのに対し、 forceは既に計算されてなかったら自分で計算するってだけ。 どちらも、「値を見る」というアクションに対してシステム側で トラップがかけられることに依存しているという点では似たようなものだ)。

Gaucheでimplicit forceなりimplicit futureなりが実現できると とても面白いのだけれど、問題になっているのがCのインタフェース。 CレベルでSchemeの値を取り出すあらゆる箇所に、 その値がfutureやpromiseかどうかというチェックを入れる必要がある。 SCM_CAR みたいなごく基本的な動作でさえそうだ。 これは性能にもC APIの使い勝手にもえらい大きな影響を与えることになる。

ただ、背後にあるメカニズムの本質がアクセスへのトラップということならば、 トラップがかけられる場所にだけ仕込めるようにする、ってのは ありかな、とふと思った。

例えば、トップレベル変数へのアクセスはC APIでも必ず関数を通す。 エラーも発生し得る関数なので、SCM_CARほど軽いことは期待されてない。 もっと言えばローカル変数アクセスについてはC APIから直接触ることは 無いので、こちらもトラップを入れようと思えば何とかなる。 ということは、「値」そのものをfuture/promiseと考えるのではなく、「束縛」 をfuture/promiseと考える、というのはアリかもしれない。

んー、やっぱりだめかな。Schemeのstrictなセマンティクスだと 変数が引数に使われてた場合、呼び出しの前に変数から値を取り出す必要があるから、 その時点でforceせざるを得なくなるか。

中途半端だけど、アイディアとして書き付けとく。


Shiro(2011/07/04 14:37:33 PDT): もしかしてimplicit forceできるかも、と思った。 キーは、原則としてpromiseをforceするのをScheme -> Cの界面で やってしまう、ってとこ。

  (define-cproc foo (x::<pair>) ...)

のようなCで定義された関数(subr)があった場合、どうせSchemeからこのsubrに 入るところでSCM_PAIRPのチェックが入る。そこでチェックがミスったパスで、 promiseならforceしてもういちどチェックをかける、ってことはできる。これだと

ということになる。

ScmObjを取るようなsubrで、C側で型チェックをしている場合は、 何もしなければpromiseはwrong type argumentでエラーになる。

でも、これは「そういうもの」だと割り切ることもできる。つまり、implicit forceは いかなる場合でも動くわけじゃなくて、対応してないsubrではエラーになるんだけど、 対応してないsubrの数が十分に少なければ実用上問題無いんじゃないか、という考え。 なるべく型チェックをgenstub側にやらせるように移行してゆけば、将来的には ほぼimplicit forceとみなせるようになるんではないか。

ただ、渡されたデータが指す先にpromiseが現れる場合はちょいと厄介だ。 典型的なのは、リストを取るsubrで、subr中でSCM_CAR, SCM_CDRを呼んでるもの。 これはかなりたくさんあるので、それら全てをリストの途中でpromiseが出てきた 場合に対応させるのは面倒だ。

けれども、mapやfor-each等の基本関数は徐々にSchemeでの実装に置き換えてしまおうと 思ってるし、そうでないやつについても x::<list> と宣言されてたら その時点でリスト全部をforceしてしまうってことにすれば、Cレベルでの影響は あまりないかもしれない。

リストではなく木で、lazyに具体化されるものについてはもうちょい面倒。 define-cprocの宣言は x::<pair> なんだけど、実は ((a . b) (c . d)) の ようなツリーを期待してて、Cレベルでは SCM_PAIRP(SCM_CAR(x)) などとしてから SCM_CAAR(x) とかしてるパターン。

ここで (a . b) とか (c . d) のところがlazyになってると、 スタブジェネレータによる自動変換ではそこはforceされないので、 CレベルでSCM_PAIRPにひっかかってエラーになる。

けど、完全にlazyな言語と違って、 (delay (cons (cons 'a 'b) (cons 'c 'd))) とした場合、promiseは一番外側にしかかからないので、あまりそういうケースは 心配しなくても良いかもしれない。


もう一つ妥協案がある。 一般的なdelay/force全てをimplicitでサポートするのではなく、 「lazyなcons」という特殊な型を設けて、それのみimplicit forceをサポートする。

lazy consだけでも、lazyなシーケンスが作れるので、 Clojureくらいの感覚で遅延評価を扱えるようにはなるんではなかろうか。

統一性という意味ではちょっと劣るけど、もともとeagerな処理系にlazyを 混ぜようって話自体が統一性から外れたところにあるんだから、 現実的な線としてはありなんではないかって気がしてきた。

実際、srfi-40/srfi-41では事実上promiseのサブタイプを作っていて、 promiseなら何でも渡せるわけじゃない。

More ...