Scheme:call/ccと副作用
c.l.sで興味深い議論が進行していたのでメモ。 purely functional Lisp + call/cc = ? 発端は、Nils M Holmの 「Purely functionalなマイLispにcall/ccをつけてみたよ」 という投稿。 それに対し、Schemeの大御所達から 「call/ccは、副作用を生じるよ」 と突っ込みが入る。 言い替えれば、「set!などの明示的な副作用オペレータを一切持たない purely functionalなLispに、call/ccを導入すると、それはもはや purely functionalではなくなる」ということ。 実例 これは簡単な例によって示すことができる。szgygによる例： (let ((f (lambda (x) (call/cc (lambda (k) k))))) (cons (f 0) (f 0))) (f 0)の2回
Scheme:使いたい人のための継続入門
使いたい人のための継続入門継続渡し形式call/ccは普通の関数call-with系関数call-with-procedurecall-with-continuation-procedurecall-with-current-continuation評価順序と継続call/ccパズルお手元マルチスレッド部分継続reset/pcとcall/pc環境破壊と部分継続部分継続の使用法PRINT-AND-NEXT-REPL議論質問お手元マルチスレッドのサンプルプログラムについて 使いたい人のための継続入門 とりあえず殴り書き。 くどかったり冗長な文章になってたり、重複してたり、間違ってたり、 おおいなる勘違いをしてたり、恥をカいてたりするかもしれないけどご愛敬。 藁をもつかみたい気持ちで継続を使えるようになりたい人は読んでみてください。 ただし所詮は藁です。(ｗ 継続渡し形式 例によって階乗fact
Re: call/cc 勉強会 - higepon blog
call/cc勉強会 - 日記を書く[・ _ゝ・]はやみずさん 面白そうですね。 自分が分かるのは call/ccを処理系に実装する方法 一部 call/cc の使うシチュエーション コルーチン・ファイバ・ユーザースレッドの実装 大域脱出(Goto) return の代わりに (find の実装で使うとか 例外処理の実装 あたりかなあ。 これは！というかっこいい使い道が知りたいです。
CPS（継続渡し方式）変換をJavaScriptで説明してみるべ、ナーニ、たいしたことねーべよ - 檜山正幸のキマイラ飼育記 (はてなBlog)
久々にThe n-Category Cafeを見たら、Mike Stayによる"The Continuation Passing Transform and the Yoneda Embedding"なんて記事がありました。 米田埋め込みは圏論ではお馴染み。継続渡しへの変換はコンピュータ・プログラミングではお馴染み。 この2つは、実は同じものなんだよ。なんで、誰もこのことを言わないんだろうね？ The Yoneda embedding is familiar in category theory. The continuation passing transform is familiar in computer programming. They're the same thing! Why doesn't anyone ever say so? Mike Stayのこの記事、面白いのだ
Scheme:なぜSchemeにはreturnが無いのか
あるいは、なぜcall/ccがプリミティブなのか、に関する一考察 (Shiro: 「なんでも継続」に入れようかと思ってたネタだけど、 あっちがいつ書けるかわからんので、忘れないようにこっちにまとめとく) (話の流れがあるので、誤りの修正以外のコメントは途中ではなく、一番下にお願いします) returnはどこだ? Aliceは、リストlisと述語手続きpredを取り、lisの各要素に順にpredを適用して、 predが真の値を返したら直ちにその要素を返すような関数findを 書くことを考えた。 (findは便利なので、実はsrfi-1に定義されてるけど、 Aliceはまあ自分の勉強のために書いてみることにしたと思いねえ)。 AliceはPerlなら良く知っている。Perlならこんな感じで書けるはず。 sub find { ($pred, $lis) = @_; foreach $elt (@
Scheme 入門 16. 継続
1. 初めに 今回は Scheme の特徴的なデータ型である継続について説明します。 このデータ型は他のプログラミング言語には無いので理解するのは易しくないかもしれません。 とりあえず、感じをつかんでいただければ結構です。 この文書では、まず一般的な継続について説明し、それから Scheme の継続について説明します。 多くの解説書ではまず Scheme の継続について説明してから、継続渡しスタイルについて説明していますが、 先に継続渡しスタイルについて説明したほうが、なぜ Scheme に継続というデータ型があるのかがわかりやすいと思います。 2. 継続とは 継続とはトップレベルに戻ってくるまでにしなければならない計算です。 実は、継続は計算過程において普遍的に存在しますが、明示的に扱われることが少ないため、 なじみのない概念になっています。例えば、[example 1] を見てみると、
Scheme:CPS
pitecan.comへの移転のためか、増井さんちのWiki掲示板は以前のコンテンツがなくなっているようなので、Google cacheから転載します。-- SHIMADA (2003/07/26 05:41:15 PDT) 転載ここから ---- 「普通の奴らの上を行け」の追記文に出てくる、WebBasedアプリケーションと継続について。 継続と聞くとSchemeのcall/ccを連想するかもしれませんが、むしろここで重要なのは、「継続渡しスタイル(Continuation Passing Style, CPS)」です。CPSそのものは、 PerlでもRubyでもJavaでも書けます。どっちかというと、普通の手続き指向から考え方を変えるのがポイントなんで。 CPSのポイント。手続きは呼び出したら戻ってきません。行ったっきりです。ですから、その手続きの後で何か別のことをやりたいなら、「その
継続を渡してチェーンすること - 檜山正幸のキマイラ飼育記 (はてなBlog)
「Erlangメッセージによる割り込み -- 継続への入り口として」において、Erlangで実際に使われている継続渡しっぽい手法を紹介しました。 それで、なーんか似たようなことをやったような、、、と、はるか昔の記憶が刺激されて、あーあー思い出したよ。 むかし、僕、MS-DOSのバッチファイルでテキストエディタ作ったことがあるんですよ（って、どんだけバカだったかが分かる）。それをASCIIネットのjunk.testにアップロードしましたね（って、どんだけ昔かが分かる）。 今はcallでサブバッチファイルを呼び出せるのですが、昔はそんなのなくて、バッチフィルからバッチファイルを呼び出すのは無理でした。チェーンならできるんですけどね。呼び出しじゃなくてチェーンて何？って人は次を実行してみてください。 main.bat @echo off echo main 1 sub echo main 2 s
Erlangメッセージによる割り込み -- 継続への入り口として - 檜山正幸のキマイラ飼育記 (はてなBlog)
Erlangにはシステムメッセージというものが定義されていて、これを使って走行中のプロセスを中断して介入することができます。とは言っても、システムメッセージは何ら特殊なものではなくて、普通のErlangメッセージに過ぎません。{system, From, Request}という形のメッセージが来たらどう行動すべきかの約束があるだけなのです。 したがって、システムメッセージの規約を守らないプロセスの中断・再開はできません。この点で、OSカーネルがサポートする割り込みとは違います。でも、規約による割り込みのメカニズムが面白いので、単純化した例で紹介します。 実例：カウンター まずは、実例のコード。 -module(counter). -export([start/1, loop/1]). start(N) when is_integer(N) -> spawn(?MODULE, loop, [
call/cc - Scheme VM のお勉強 - higepon blog
(call/cc (lambda (c) 3)) =>(frame () (conti (argument (close (c) (constant 3 (return)) (apply))))) call/cc を見ていく。 論文には call/cc は closure の特殊な場合だよと書いてあるが分からなかったので処理を追う。 frame は昨日書いた通り、current value rib を空にし、指定された next expression とその時点での env/rib/stack を stack に保存する。 conti では closure を作成する。 closure は (body e vars) のようなリスト構造なのだけど、conti では body => ('nuate stackレジスタ 'v) e => 空 vars => (v) のような closure 。
On Lisp --- 継続
継続とは，動作中に凍結したプログラムだ． すなわち計算処理の状態を含んだ一つの関数的オブジェクトだ． 保存された計算処理は，それが中断された時点から再開する． プログラムの状態を保存し，後に再開できる能力は，ある種の問題解決に素晴しい威力を発揮する． 例えば並列処理では，中断されたプロセスを継続で表すのが便利だ． 非決定的探索問題では，継続は探索ツリーのノードを表現できる． 継続の理解は難しいかも知れない． この章ではその話題に2段階で取り組む． この章の前半では継続の組込みサポートのあるSchemeでの用例を見る． 継続の振舞を説明し終わったら，後半ではCommon Lispプログラムで継続を生成するマクロの使い方を示す． 第22--24章のいずれでも，ここで定義したマクロを利用する． Schemeの継続 Common Lispでシンボルの「シンボル値」と「シンボル
Route 477(2007-06-20)
■ [ruby][event] Ruby勉強会＠関西-16「30分でわかるcallccの使い方」 先週末のRuby勉強会＠関西で、Rubyにおけるcallccの使い方について発表させていただきました。 スライド： pdf ppt 継続の説明については「なんでも継続」がよく参照されるんだけど、 ちょっと説明がボトムアップすぎると思うので(僕も最初に読んだときは全然分からなかった)、「callccで何ができるか」という応用面から攻める 構成にしてみました。 最初は「継続かわいいよ継続」「それをすてるなんてとんでもない」と思ってたんだけど、 いろいろ調べてるうちになんでcallccが嫌われるのかが理解できてしまった。callccはかわいいけど、非常に手のかかる奴らしい。 しかも、面白い利用例はいっぱいあるけど実用的な例があんまりないんだよね^^;。 callccが無くなるとRubyの「かっこよさ
継続を利用した疑似マルチスレッドをコーディング中 - 2 - higepon blog
call/cc を用いた Coroutine の実装。 http://www.shido.info/lisp/scheme_cc.html を参考に単純化してやってみる。 中断するときに、call/cc で継続を取り出して queue に入れて、queue から次の処理を取り出して実行という形。 理解できた。 自前インタプリタでも動いた。当り前か。 (define queue (cons '() '())) (define (enqueue! process) (if (null? (car queue)) (set-car! queue process) (set-cdr! queue process))) (define (dequeue!) (let ((p (cdr queue))) (set-cdr! queue (car queue)) (set-car! queue '())
継続マラソン - 継続渡しスタイル - higepon blog
継続渡しスタイルを熟読し、必要時には写経。 写経。 (define (fact/cps n cont) (if (= n 0) (cont 1) (fact/cps (- n 1) (lambda (a) (cont (* n a)))))) 結果。 (fact/cps 4 (lambda (a) a)) => 24 引数で、継続手続きを受けとる感じ。 (define (hige-even n even-proc odd-proc) (if (even? n) (even-proc n) (odd-proc n))) あまり意味のない手続きだけど、継続渡しスタイルだと、hige-even がどういう結果を返すかを外から制御できるってのがメリットっぽい。 (hige-even 5 (lambda (a) 'even) (lambda (a) 'odd)) => odd ふむふむ。 うーん。こ
setjmp/longjmpとローカル変数 - sumiiのブログ
call/ccが出てきたので、ついでに： #include <setjmp.h> int main() { int x, y; jmp_buf k; x = 123; y = setjmp(k); if (y == 0) { x = 45; longjmp(k, 1); } return x + y; } はいくつを返すか、という話。 > gcc jmp.c -o jmp > ./jmp > echo $status 46 > gcc -O3 jmp.c -o jmp > ./jmp > echo $status 124xにvolatileをつけ忘れると、こういうこと↑になります… Cf. > (let ((x 123)) (let ((y (call-with-current-continuation (lambda (k) (set! x 45) (k 1))))) (+ x y)))
404 Blog Not Found:perl - to goto or not to goto, that's the continuation
2007年04月18日06:45 カテゴリLightweight Languages perl - to goto or not to goto, that's the continuation Perlでもgotoを使えば、本当の継続(continuation)が可能であることを示す。 継続ってなんのことだかさっぱりわからない一は、以下にあらかじめ目をとおしておいていただきたい。 なんでも継続 なんでも継続、Perl で。 : torus solutions! 404 Blog Not Found:継続は力なり Tociyuki::Diary - Perl 5.8 で似非継続 Perl 5のgotoには、3種類ある。 goto LABEL こちらはCなどで見られるgotoと等価である。 goto END; print "Hello\n"; END: print "Goobye\n"; G
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Continuation passing as a reflection
call-with-values / values - higepon blog
dynamic-wind の仕様を読みつつ理解しよう - higepon blog
call/cc - higepon blog