vallog: continuation

ラベル continuation の投稿を表示しています。すべての投稿を表示

2011/01/11

継続の実装方針

fault on continuation (Gauche-devel-jp) - Gauche - SourceForge.JP

継続の実装は、何を重視するかでかなり違ってくるせいでしょうね。

full continuationの実装は、スタックエリアのコピーという観点
から見ると、次のように分類されます。

(1) 継続作成時にスタックからヒープへのコピーを行い、
継続呼び出し時にヒープからスタックへのコピーを行う

(2) 継続作成時にスタックからヒープへのコピーを行うが、
継続呼び出し時にはコピーを行わない

(3) 継続作成時にはコピーを行わず、
継続呼び出し時にコピーを行う

(4) 継続作成時にも継続呼び出し時にもコピーは行わない

guileやSCMは(1)のタイプです。このタイプは、CとSchemeの
スタックが自由にインターリーブできるのが特徴です(Scheme
ルーチンから呼んだCルーチンからさらにSchemeルーチンを
簡単に呼べる)。したがってC APIが単純になります。また、
スタックエリアのGCを必要としません。しかしコピーの回数が
多いため、継続は非常に重くなります。
SCMよりguileがかなり重いのは何故だかわかりません。

Gaucheは(2)の方法を利用しています。(1)と同様にスタック
エリアのGCが不要で、コピーの回数が少ないのが特徴です。
しかし、呼ばれない継続でも作られる時点でコピーする必要が
あるのであまり良い方法ではないです。将来、スタックエリア
のGCを実装できたら(3)か(4)に移りたいと考えています。

(3)はChez Schemeへの実装の論文があります。Petite Chez
Schemeで使われているかどうかは知りませんが、おそらく
使われているんではないでしょうか。スタックエリアのGCと、
スタックアンダーフローを検出する一種のバリアが必要です。
継続の作成はほぼノーコストです。継続の呼び出しには若干の
オーバヘッドがあります。

(4)は実装技術的にはさらに2つに分かれます。継続を全て
ヒープアロケートする方法と、スタックフレームをポップしない
方法です。完全なcontinuation passing styleなので、
継続の作成、起動ともに理論上ノーコストでできる方法です。
しかし、継続を全てヒープアロケートするのはメモリアクセスの
ローカリティが悪く、最近のCPUでは不利になります。
Chickenは後者の方法 (ポップしないスタックフレーム)を使って
います。理屈の上ではこれが一番良い方法のはずですが、スタック
エリアのGC回数が(3)よりずっと多くなるため、総合的な性能で
比較すると微妙なところです。

--shiro

2010/12/20

余談

面白かったのが

Island Life - returnを継続プリミティブにする話

経由で読んだこれ

「難しいのは継続ではないcallccだ…とすると、難しいのは限定継続ではなくshift/resetなのでは？」

これわかるような気がします。継続自体も難しいけど、call/cc がまた難しい。以前 let/cc はわかるけど call/cc がわからないという状態がありました。。今でも let/cc ベースで call/cc を認識しているわけですが・・・。（The Seasoned Schemer の影響もあり）

こんな感じで・・・

(let1 loop #f
  (let1 i 0
    ;; (let/cc c (set! loop c))
    (call/cc (^c (set! loop c)))
    (print i)
    (inc! i)
    (when (< i 10)
      (loop))))

let/cc - Gauche ユーザリファレンス: 6.17 制御

余談2

そういえば、継続といえば、amb カッチョイイですよね。

gist: 638160 - GitHub

（return の記事おもしろいなあ。。）

ついでみたいだけど

2010/05/26

syntax-rules: amb

非決定性というやつです。よく分からないので、写経してみました。動き気持ち悪いですね。。どうなってるんですかこれ。。
確か、On Lisp や SICP (計算機プログラムの構造と解釈)にも出てくるらしいですね。

http://people.csail.mit.edu/jhbrown/scheme/continuationslides04.pdf

わけわかめ。

追記

vallog: On Lisp 非決定性

syntax-rules: try

macroの方のPDFを一通り読み終えたので、continuationの方のPDFを読み始めました。

(PDF)Advanced Scheme TechniquesSome Naughty Bits

英語の方は、ほとんどわかりません。The Seasoned SchemerやThe Little Schemer, 4th Editionは雰囲気と勢いで読みました。

The Seasoned Schemerに出てくる try のことを思い出しました。

2010/05/24

call/cc sum1-n, reverse

(call/cc identity) が、なるほど！だったので。

各言語で作った簡易足し算器

2010/04/02

継続 continuation

お陰様で「継続」が少しずつわかってきました。

ごく簡単なコードについては

継続が見えるようになってきた
CPS（継続渡しスタイル）に書き換えることができるようになってきた
call/ccによる脱出が書けるようになってきた
継続呼び出しによる「脱出」が結果的にそう見えるだけで、厳密には「脱出」という表現は相応しくないのではないか、と思うようになった
call/ccが使われているコードに対する抵抗が減った

しかし

少し複雑になるだけで継続なんてちっとも見えやしない
厳密なCPSなんて全く書けやしない
call/ccが散在するコードを見ると目が回る

というような状態。抵抗が減っただけでも、大きな収穫だと思っています。理解の助けになるのは、やはり簡単な例で良いのでたくさん書いてみることだなーと、いまさら思いました。いや、そんなにたくさん書いていないので、もっとたくさん書かないといけないなーと思っているところでした。

2010/03/25

filter-break

リストlisと述語手続きpredを取り、lisの各要素に順にpredを適用して、 predが真の値を返したら直ちにその要素を返すような関数find

2010/03/24

find-fold

「プログラミングGauche」の継続のところをチラ見して。CPS難しいー。このコードの後、もっとCPSです。「厳密にCPS変換するとこうなるよ」ってのが載ってましたがギブ。

Re:filter*

vallog: filter*

こんな感じで↓。

お陰さまでかなりすっきりしました（笑）

2010/03/23

よくわかるcall/cc

「打ち消し線」すごくわかりやすい！

タンブラーとは - #9LISP 実は意図はこう言う事です。

内容に直接関係しないのですが、「スタックのコールバック」。@aharisuさんが言っていたのはたぶん「コールスタックの破棄」的なことだったかと。コールスタックごと吹き飛ばす的な。違ったかな。

継続あれこれ

眺めてたら途中で力尽きた。

継続 - Wikipedia

「ある時点での状態」を変数に束縛して、後からそこへ戻るといったことも可能になる。Schemeの継続は関数の形をとっており、これは「その関数を呼ぶことにより、そこに渡された引数をcall/ccで囲まれている式全体の値として継続に“注入”できる」と定義されている。

継続

プログラムの実行順序を制御する概念

継続

既に終了したスタックフレームを黄泉の国から引きずり出してスタックにぶちこめるわけである。

普通の人間が「おっ、ここはCall/CCを使えばカッコ良く実装できるね！」などと思いついたりすることはまずありえない

Scheme/継続 - Wikibooks

継続を用いれば大域脱出、コルーチン、疑似マルチタスク、バックトラックといった特殊な制御を必要とするプログラムを効率的に記述することができる

なんでも継続

「分かれば分かる」

継続は現在の計算を続行するための情報

どんなコードでも継続渡し形式として「見る」ことができる

Gauche ユーザリファレンス: 6.16 制御

現在の継続を手続き (継続手続き) にパッケージ化して、それを引数として procを呼び出します。procが戻ったら、その返り値がcall/ccの値となります。

Karetta|Gaucheプログラミング(立読み版)|継続

言語によっては、呼び出し元の関数が分からず呼び出したらもう戻ってこないものもあります。呼び出し元の関数に値が返ってくるのは、どこから自分を呼び出したのかという情報をどこかで管理し、呼び出された側はその情報を元に値を返すという決まりがあるからです。

Karetta|Gaucheプログラミング(立読み版)|call/cc

保存した継続を動かしてみましょう。

Karetta|Gaucheプログラミング(立読み版)|継続渡しスタイル

(* 2 (fact 10))という計算は、fact/cpsを使えば次の式と等価です。(fact/cps 10 (lambda (a) (* 2 a)))

継続渡し形式で書けば、現在実装中の関数が、どういう形で結果を返すのが良いかの設計を遅らせることが出来ます。

継続は保存してから呼び出されるまでの間、完全に休眠しており、その間にいかなる式の評価でもはさむことが出来ます。

(call/cc (lambda (return) ...)) は説明すると長くなるけど、まあ、 returnってラベルを定義してるもんだと思ってくれればいい。

2010/03/12

"再帰も"ループも使わずに配列を逆順にする：継続呼び出し編

先日は、「再帰は厳密にはループじゃないよね？」というノリで書きました。
ヒネリたくてもヒネれず、Y combinator で書くなどしました。

vallog: 流行ってるようなので「ループを使わずに配列の順序を逆にする」

今回は、The Seasoned Schemer で出てきた let/cc を用いてやってみました。

vallog: TSS rember-beyond-first, rember-up-to-last, let/cc, call/cc

（やっぱこれって「再帰じゃない」とは言い張れないような気がしてきました。うまいこと書けてないだけかな。）

取り合えず以下コード

ちなみに先日のものはこちら

追記

タンブラーとは - もっと大胆にやっても良いです。

いやー読んでもよくわからないっす・・・。力不足ですはい＾＾；

(define (my-reverse ls)
  (let/cc return
   (let ((r #f))
     (let ((l ls) (acc '()))
       (let/cc continue
        (set! r continue))
       (and (null? l) (return acc))
       (set! acc (cons (car l) acc))
       (set! l (cdr l))
       (r '())))))

よく読んだらなんとなくわかりました。継続呼び出しでジャンプ（というか無限ループ的なもの）、andは継続呼び出しによる終了（脱出）のための条件分岐、副作用で蓄積と減算ですか。うーん難しいぃー＾＾；

追記2

タンブラーとは - トリックはこう言う事です。

擬似コードも説明もわかりやすかったです。
追記で書いたように、だいたい思った通りの動きのようで安心しました。でもやっぱりなんか異物感のようなものがありますねー・・・。@cametan_001さんの仰るように関数型的でないからなのでしょうか。

兎に角もっと書いてみる方が良さそうだなーという印象でした。

2010/03/09

TSS intersectall (letcc, call/cc)

letcc の hop を catch, hop の呼び出しを throw だ、と言われると途端にイメージが出来上がった。しかし、たぶんC#なんかの catch, throw と同じようなことがもできるだけで、同じではない、ですよね。

未だに継続周り（呼び出しとか渡しとか）が、いまいちピンとこない。
説明やコードを読めば、その時は動きがわかるし、何をしてるかもだいたいわかる（つもり）。
見よう見まねで書ける。

でも消化不良（？）というか、ものにならないというか。
パラダイムシフトが起きてないってことなのかな。

で、それが起きないのはそれが起きるほどコードを書いてないから、だと思う。

「悟り体験」ってきっとパラダイムシフト。

この例の場合だと、最後のコードでも同様の結果・・・ですよね？
ネストが深い場合に、深部から一気に脱出するとなると継続呼び出しの方でないとできない・・・んだよねきっと。

2009/10/19

継続渡しスタイルCPS

1年くらいSchemeやってて継続（渡し、呼び出し）についても何度か読んだり書いたりしてるはずなのに未だに「どんなんだっけ？」となってしまう私です。

「なんでも継続」とか読んで少しだけ書いてみた。

普通の階乗

;; factorial
(define fact
(lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))

継続渡し階乗（Continuation Passing Style -> CPS）

(define fact/cps
(lambda (n cont)
    (if (zero? n)
        (cont 1)
        (fact/cps (- n 1)(lambda (x)
                           (cont (* n x)))))))

やっぱりイメージが沸かないので展開してみた

(fact/cps 5 (lambda (x) x))

(fact/cps (- 5 1)
(lambda (x)((lambda (x) x)(* 5 x))))

(fact/cps (- (- 5 1) 1)
(lambda (x)((lambda (x)((lambda (x) x)(* 5 x))) (* 4 x))))

(fact/cps (- (- (- 5 1) 1) 1)
(lambda (x)((lambda (x)((lambda (x)((lambda (x) x)(* 5 x))) (* 4 x))) (* 3 x))))

(fact/cps (- (- (- (- 5 1) 1) 1) 1)
(lambda (x)((lambda (x)((lambda (x)((lambda (x)((lambda (x) x)(* 5 x))) (* 4 x))) (* 3 x))) (* 2 x))))

(fact/cps (- (- (- (- (- 5 1) 1) 1) 1) 1)
(lambda (x)((lambda (x)((lambda (x)((lambda (x)((lambda (x)((lambda (x) x)(* 5 x))) (* 4 x))) (* 3 x))) (* 2 x))) (* 1 x))))

ということですか。わかりました。わかりません。毎度理解できたつもりですが、数日すると忘れるんだろうな。ということはつまりわかってないのな。

実行時のキャプチャーとか言いますよね、わかります。わかりません。セーブポイントみたいなもんだということですね？現在の環境ごとクロージャにぶち込んでほいほい渡していって必要になってから使うし使わなくても良いし、と。

scheme の「継続」の超てきとうな説明

超てきとうとは書いてありますがわかりややすかったです。「なんでも継続」の最初の方もわかりやすかった。

The Little Schemer のrember&coのところをもっかいやってみよう。というか丸ごと読み直そう。んでThe Seasoned Schemerもちゃんと読もう。

なんかピンとこないんですよね・・・。

あ、ついでにJavaScriptとC#も。改めて書く必要もなく同じコードなんですけどね。なんとなく。C#は気分でgoto使ってみた。

function factCps (n, cont)
{
return n === 0
? cont(1)
: factCps (n - 1, function(x){ return cont(n * x);});
};

factCps(5, function(x){ return x;});

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Diagnostics;

namespace SampleCallPassingStyle
{
    public class Program
    {
        public static void Main(string[] args)
        {
            Trace.Listeners.Add(new ConsoleTraceListener());
            Trace.WriteLine("Continuation Passing Style Factorial Start");

restart:

            try
            {
                FactCps(decimal.Parse(Console.ReadLine()), 0, i => { Console.WriteLine(i); return i; });
                goto restart;
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
                goto restart;
            }
        }

        public static decimal FactCps(decimal n, decimal nest, Func<decimal, decimal> cps)
        {
            return n == 0
                ? cps(1)
                : FactCps(n - 1, ++nest, i => { Console.WriteLine("i = {0}, n = {1}, cont({0} * {1}), nest = {2}", i, n, nest); return cps(i * n); });

            //return n == 0
            //    ? cps(1)
            //    : FactCps(n - 1, ++nest, i => cps(i * n));
        }
    }
}

The Little Schemer

posted with amazlet at 09.03.30

Daniel P. Friedman Matthias Felleisen
Mit Pr
売り上げランキング: 16078

おすすめ度の平均: 5.0

小さなScheme処理系で学ぶ数学基礎理論
Schemeが好きになります
英語であるのが苦痛にならない楽しさ
面白いスタイル

Amazon.co.jp で詳細を見る

The Seasoned Schemer

posted with amazlet at 09.03.30

Daniel P. Friedman Matthias Felleisen
Mit Pr
売り上げランキング: 18883

おすすめ度の平均: 5.0

Little Schemer とセットで