Cで継続渡し(末尾最適化バージョン) - ヒビノキロク
Cで継続渡しを書いてから、もう少しがんばれば末尾最適化もできそうだということに気付いて、やってみたらなんとかできた。しかも、絶対にアセンブラが必要だろうと思っていたんだけど結果的にはアセンブラに頼らずにCの範囲内で実現することができた。さすが高級アセンブラ。 fib2.c #include <stdio.h> #include <stdlib.h> #include "obj.h" int main(int argc, char *argv[]) { // 汎用レジスタのつもり void *r1; void *r2; closure_t c = newClosure(0); c->func = (func_t) &&fib_cps_0; for (int i = 1; i < 10; i++) { addRef((object_t) c); // printf("Fibonacci(%d)
継続渡しとコンパイル - ヒビノキロク
実装はまだ先だが、継続渡しに変換してからコンパイルする方法がなんとなく分かった。 継続渡しへの変換 継続渡しへの変換は、簡単な例で示すと以下のようになる。 次の式を評価するためには、まず(g)を評価して、その戻り値を使って(f # x)を評価する。 (f (g) x)つまり以下の式と等価。 ((lambda (v) (f v x)) (g))ここで関数gの引数を一つ増やして、１引数の関数kを取れるようにしたg_cpsを考える。この関数g_cpsは、本来のgの計算を行った後で、戻り値を返す代わりに渡された関数を呼び出す（呼ばれた関数から戻ってこないので、呼び出すというよりジャンプすると言った方が正しい）。 (g_cps (lambda (v) (f v x)))このときの増えた引数が継続。 (擬似)バイトコードへのコンパイル 具体例で考える。 (define (fact n) (if (>
継続渡しとコンパイル(2)〜末尾再帰の場合 - ヒビノキロク
前のエントリでループの度にヒープにクロージャを生成しているのが無駄だと思う人がいるかもしれないが、それは例に挙げた関数が末尾再帰になっていないからだ。継続渡しは末尾再帰の時に最も真価を発揮する。 というわけで階乗計算の末尾再帰版。 (define (fact_tailrec n) (define (fact-aux n r) (if (> n 1) (fact-aux (1- n) (* n r)) r)) (fact-aux n 1))これを継続渡しスタイルにしたものがこれ。 (define (fact_tailrec_cps n k) (define (fact-aux n r k) (if (> n 1) (fact-aux (1- n) (* n r) k) (k r))) (fact-aux n 1 k))さらにこれを前のエントリと同様の規則で変換すると、 fact_tailre
末尾再帰と継続（メモ） - ヒビノキロク
レキシカルスコープと継続ができたので、あとSchemeに必要なものとしては末尾再帰の最適化がある。せっかくだからこれも実装したい。 どうやって実装すればいいか。最初はインタプリタではなくコンパイラを作らないといけないと思ったが、ひょっとすると継続を使えば自然に実装できるかもしれない。今は継続をバカ正直に毎回生成しているが、等しい継続(同じクラスで参照しているオブジェクトも同じ)は、振る舞いも同じはずなので、既に同値の継続オブジェクトが存在していたらそれを使うようにすると、繰り返しだろうが再帰だろうが有限の継続だけで済んでしまうような気がする。 ただ、もしそうなるとちょっとした問題があって、オブジェクトが循環参照するようになるので、最早オブジェクトの寿命をガベージコレクタに任せきりにはできないかもしれないということ。Javaのガベージコレクタってそこまで賢くなかったよなあ。となると自分で何と
続・継続 - ヒビノキロク
昨日の時点ではまだバグがあったが、そのバグも直った。たぶんこれで完成したと思う。最終的にはスタックですらなく、単に現在の継続を覚えておくだけで良くなった。これは継続自身に次に処理を渡すべき継続の参照を持たせることにしたためで、こうしないと継続を再利用した時に問題が出る。 昨日は結果しか書かなかったので、継続について少し解説を。 > (+ (call/cc (lambda (x) (x 1) 2)) 3) ==> 4この例では、xにcall/ccの外側への継続が束縛されているので、xを呼ぶと(call/cc ...)全体がその引数と置き換わり、全体としては(+ 1 3)を計算することになる。いわゆる大域脱出の例。 別の例： (define cont #f) ==> #f (+ (call/cc (lambda (x) (set! cont x) 1)) 2) ==> 3 (cont 5) =
継続(Continuation) - ヒビノキロク
なんかゴニョゴニョやってるうちに出来たみたい。 > (+ (call/cc (lambda (x) (x 1) 2)) 3) ==> 4 以下のページなども参考にしつつ、継続スタックを自前で管理することで実現した。継続に対応させるために、プリミティブ関数の実装がとても力業になってしまった。 Schemeを作ろう 第3回 http://www.jah.ne.jp/~naoyuki/Writings/VScheme3.html それと、レキシカルスコープは意外に簡単に実装できた。要するにオブジェクトの値を求める時に、評価するときの環境じゃなくて定義した時の環境を使えばいい。定義する場所と評価する場所が異なるのは関数オブジェクト(==lambda式)の中だけだから、結局は関数に定義した時の環境を持たせておくだけでよくて、わずか数行の書き換えで実現できてしまった。 継続に対応するコードの例 参考ま
sumiiの日記 - call/ccが「副作用」である理由
http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3acall%2fcc%e3%81%a8%e5%89%af%e4%bd%9c%e7%94%a8 (via http://d.hatena.ne.jp/flappphys/20061119#p2) おお、これは正確でわかりやすい議論ですね。call/ccが参照透明性を破壊する（ややトリッキーな）実例としては、前にちらっと書いた > (define x (call-with-current-continuation call-with-current-continuation)) > x #<system continuation> > (x 123) > x 123も、その筋ではよく知られているようです。元のcomp.lang.schemeの議論をちゃんと読んでいないので既出かもしれませ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
