Scheme/継続の種類と利用例 - Wikibooks
Introduction[編集] このセクションでは、継続を用いたプログラムを実際に動かしてみる。教科書の例題を解くためだけでなく、制御処理の仕組みを継続を活用して作ったり、既存のライブラリの動作をカスタマイズすることで実用的なプログラミングに応用できるようになることを目指す。また、処理系における実装の方法についても触れ、継続呼び出しのパフォーマンスについても考察する予定。 call/cc[編集] 導入[編集] call/ccは、(call/cc proc) 式を評価した後すべき計算を、継続オブジェクトとして proc に渡す手続きである。 この継続オブジェクトは、C言語で考えると (call/cc proc) を評価した後の処理へgotoするマクロ、もしくは (call/cc proc) を評価したときに setjmp() によってマークした地点に longjmp() によって移動する関
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
Continuation-passing style (継続渡し)、Haskell のリストと差分リストから、あと米田の補題 - Qiita
Continuation-passing style (継続渡し)、Haskell のリストと差分リストから、あと米田の補題Haskell圏論継続リスト はじめに 前回の投稿から少々考えていたのだが、やや理解が固まったので書いてみる、ただ中身は前回から少しも増えていない。 何を考えていたかというと、リストから差分リストへ変えたことで効率が上がったが、これはたまたまこの場合のみ使えるテクニックなのかあるいは何か背景があるのか？という疑問である。 これの答えはある程度肯定的であって、普通のリストと差分リストの間のような関係がもっと一般的に存在することが分かった、しかもその間を結ぶのが（お気に入りの）米田の補題である、なんと。 つまり、ある種の最適化問題はデータあるいは関数の型を継続渡しスタイルというのに変えるということに帰着していて、かつこれは必ず実行可能である、ということらしい。 元ネタはこ
The Continuation Passing Transform and the Yoneda Embedding | The n-Category Café
The Continuation Passing Transform and the Yoneda Embedding Posted by John Baez Guest post by Mike Stay 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? Assume A and B are types; the continuation passing transform takes a function (here I’m using C++ notation) B f(A a
call/cc 入門 (Coroutine with call/cc) - MAYAH
call/cc を使って簡単な Coroutine を作ります。call/cc 入門だと思ってもらえれば幸いです。 coroutine とは ここでは coroutine を「実行の途中でリターンでき、さらにそこ(実行の途中)から再開することが出来る何か」の意味で使用します。適当な疑似言語で書くと次の通り。関数の途中でのリターンを suspend(), 途中からの再開を resume() で表すことにします。 ここでは、これを scheme の call/cc を用いて表すことを目指します。 call/cc とは call/cc とは、call-with-current-continuation という scheme の関数で、「現在の継続(current continuation)を生成し、それを関数に渡してその関数を実行する」ものです。読者の殆どは「継続」についてよく知っているかもしれ
Peirce's law - Wikipedia
In logic, Peirce's law is named after the philosopher and logician Charles Sanders Peirce. It was taken as an axiom in his first axiomatisation of propositional logic. It can be thought of as the law of excluded middle written in a form that involves only one sort of connective, namely implication. In propositional calculus, Peirce's law says that ((P→Q)→P)→P. Written out, this means that P must b
Asymmetric CoroutinesによるOneshot Algebraic Effectsの実装 - lilyum ensemble
Asymmetric CoroutinesによるOneshot Algebraic Effectsの実装 Dec 9, 2018 src tag: { Lua Coroutines Algebraic Effects 言語実装 Advent Calendar } Tweet こんにちは､びしょ〜じょです｡ これは言語実装Advent Calendar 2018の9日目の記事です｡ 最初は "変数が全部箱の言語の設計と実装" と題して全部optionにくるまれてる参照とかそういう感じの何かを作ろうとしたけど多分面白くなくなって筆者の熱も醒めると思ったのでやめた｡ またそうこうしてるうちに良い感じのものが作れたので､論理的背景を整理するためにも内容を再考して今回のような内容となりました｡ ほならね早速いってみましょう｡ 1. はじめに Algebraic effects and handler
制御の逆転 〜 OchaCaml と限定継続でイベンドハンドラをダイレクトスタイルで書く - keigoiの日記
昔、こういう記事を書いた： OchaCamlで限定継続/answer type modificationを勉強する - keigoiの日記 もっと shift/reset で何か身の回りの例を書いてみたい。そこで限定継続を使って、イベントハンドラをコールバックではなくダイレクトスタイルで書けるようにする、ということをやってみる。 ユースケース 例がとても古くて恐縮だが、たとえば古きよきショッピングカートの web アプリを作るときは、普通はページのルーティングを書いて、クリックの度に発行される GET か POST リクエストに反応するイベントドリブンで構成することになる： /* /item_list アイテム一覧ページ */ Page onItemList(); /* /confirm 注文の確認ページ */ Page onConfirm(Cart); /* /thankyou 支払い完
Forking and ContT (I)
Introduction This is the first article in a series about continuations, forking, and monad transformers. Next article. Motivation When using StateT or ReaderT over IO, we sometimes would like to fork and still remain in this “monadic context”, but alas: main = flip evalStateT (0 :: Int) $ do modify (+1) liftIO $ forkIO $ do s <- get -- ^ type error: we are in IO, -- no state to `get`. d'oh! print
Continuations From the Ground Up
06 June 2017 It’s difficult to learn functional programming without hearing about continuations. Often they’re mentioned while talking about boosting the performance of pure functional code, sometimes there’s talk of control flow, and occasionally with ‘time-travel’ thrown in there to make it all seem more obscure. It’s all true, but let’s start from the beginning. This post was generated from a L
Continuations all the way down
Here are the slides for my Lambda Jam talk, "Continuations all the way down." It was originally going to be a collection of "why is it fast" anecdotes from popular Hackage libraries, since I know of several that observed significant improvements via CPS. When this happens, it could be due to the elimination of some incidentally complicated internal expression, either by something akin to fmap fusi
継続こわくない（RubyでFiberを使ったコードをcallccで書きなおしてみた） - 方向
Fiberに関するこんな記事をみて、 そういえば以前30分でわかるcallccの使い方で、 callccの代表的な使い方は * (A) 処理の中断/再開 (generator, wait_ok) * (B) 処理のやり直し (amb, ppp) の2通りが挙げられる。 callccが危険なのは(B)ができてしまうからだ。じゃあ(A)の機能だけなら残してもいいかも？ということで、Ruby 1.9ではFiberという機能が検討されている。 と書いてあったのを思い出して、「Fiberはcallccの抽象化ってことか……じゃあFiberのコードはcallccで書き直せるのかな？」 と思い試してみました。 Fiberのコード はこべにっき#より、改変 require 'fiber' def count() n = 0 Fiber.new do loop do Fiber.yield n n += 1
call/ccと古典論理のカリー・ハワード対応 - 再帰の反復blog
「直観主義論理のカリー・ハワード対応」の続き。 call/ccと継続 call/ccというのは、gotoを強力にしたものだと思っておけば良い。ただしScheme以外のプログラミング言語では、あまり見かけない機能。 例えばブロック構造から抜け出すための命令がある言語を考える。どのブロックから抜け出すかはラベルで指定する。またラベルはギリシャ文字で表すことにする。とりあえず次のような感じになるだろう。jumpの部分を実行するとブロックから抜け出す。 :α{ ... ... jump α; ... // ここは実行されない }でも、ブロック自体が値を持っている(値を返す)ようにした方が汎用的になる。例えば、次のプログラムはflagが真ならxに1が代入され、偽なら2が代入される。 x = :α{ ... ... if (flag) { jump α 1; } ... 2; }値を返すにしても返さな
僕でもわかる継続と部分継続 - まめめも
callcc と shift/reset についてわかるとこだけ書いてみます。 継続 callcc という操作は、現在から実行終了まで、継続をまるごと取り出します。例題。 p [1] + callcc {|k| [2] + k.call([3]) } #=> [1, 3] callcc では callcc がリターンしてから実行終了するまでの継続 k が取り出せます。k.call([3]) で継続が呼ばれると、いきなり「callcc が [3] を返した瞬間」に実行が飛びます。つまりこんな感じ。 p [1] + [3] あとは自明ですね。"[2] +" のあたりは無視されます。 部分継続 shift という操作は、現在から reset まで、継続の一部だけを取り出します。この継続の一部を部分継続といいます。例題。 p [1] + reset { [2] + shift {|k| [3] +
icfp02.dvi
Final Shift for Call/cc: Direct Implementation of Shift and Reset Martin Gasbichler Michael Sperber Universität Tübingen {gasbichl,sperber}@informatik.uni-tuebingen.de Abstract We present a direct implementation of the shift and reset con- trol operators in the Scheme 48 system. The new implementation improves upon the traditional technique of simulating shift and reset via call/cc. Typical appl
shift/reset
限定継続という概念(制御構文)があって、これを使うと、バックトラックとかが簡単に実装できるのですが、その動作がやたらややこしい、という話のメモです。 限定継続では、shiftというオペレータとresetというオペレータを用いて、継続を扱います。shiftというオペレータは、継続の呼び出しです(Schemeのcall/ccのようなものです)。それに対して、resetは、その範囲を限定します。 例えば、以下のように使えます。 (+ 1 (reset (+ 10 (shift c (c 100))))) :;==> 111 ここでは、resetが継続の取得する範囲を区切って、shiftのcに渡します。ここで渡される継続は、(lambda (x) (+ 10 x))の処理です。このラムダ式は、resetが用意してくれるようなイメージです。shiftは、resetで渡された限定継続(= 10を足すと
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
モナドをつくろう
Background of call/cc | Lambda the Ultimate
Video on Continuations | Lambda the Ultimate
An Operational Foundation for Delimited Continuations in the CPS Hierarchy | Lambda the Ultimate