Twitterのどこかで「Contモナドを使わない継続の説明を書いてくれ」みたいな話を目にしたので書きました． この記事は，以下のような方を対象に書かれています． Haskellはなんとなく使える．モナドもなんとなくわかる． 息をするように新しいモナドを定義したりはできない． 継続が何かは全く分からない．Schemeとかを使ったこともない． 継続とは Haskell(に限らずほとんどの言語)では，以下のようなステップでプログラムを実行していきます． 何らかの関数に引数を与えて，その計算結果を受け取る． 受け取った計算結果を別な関数の引数に与える． 以下繰り返し． 例えばHaskellで，与えられた3つの数の平均を取る関数を(非常に冗長に)書いてみると，以下のようになるでしょう． module Cont where import Prelude hiding (div) add :: Num
A page about call/cc [ENS] [ENS students] [David Madore] [Mathematics] [Computer science] [Programs] [Linux] [Literature] [What's new?] [What's cool?] [Site map] Table of contents What is call/cc? What is this page? A first introduction Who invented call/cc? What does call/cc stand for? Which programming languages have a call/cc function? Outgoing-only continuations: exceptions Exceptions in C: se
There is one abstraction that can be used to implement such apparently diverse concepts as exceptions, generators, coroutines and even the backtracking mechanism present in Prolog. This article demonstrates how to use continuations to implement these constructs in a custom, small programming language. Then the implementation of an interpreter for that language is presented. Finally a Java servlet
モナドのすべての継続モナドのところが簡潔で、概念とかもあまり明示的に説明してなくて理解に苦労したので、ポイントをメモ。誤りなど、乞うご指摘。 newtype Cont r a = Cont { runCont :: ((a -> r) -> r) } instance Monad (Cont r) where return a = Cont $ \k -> k a (Cont c) >>= f = Cont $ \k -> c (\a -> runCont (f a) k) 概要的なこと 継続といいつつ、Contが表すのは継続というより、CPSな関数。*1 CPSな関数は、引数に関数をとり、自分の仕事の最後でその関数(継続)を呼ぶ。 CPSな関数に、継続として別のCPSな関数を渡す、その別のCPSな関数に継続としてさらに別のCPSな関数を渡す、…の連鎖（CPSな関数のネスト）が、全体として
再帰関数のスタックオーバーフローを倒す話を何回かに分けてします。 連載目次 再帰関数のスタックオーバーフローを倒す話 その1 ← 今回 CPSとCPS変換の話 再帰関数のスタックオーバーフローを倒す話 その1.5 F#での「末尾」についての話 再帰関数のスタックオーバーフローを倒す話 その2 .NETにおける末尾最適化の方法についての話 再帰関数のスタックオーバーフローを倒す話 その2.5 継続モナドと、F#の残念さの話 再帰関数のスタックオーバーフローを倒す話 その3 すべてをあきらめて再帰をwhileに書き直す方法の話 はじめに 継続渡しスタイルもしくは継続渡し形式(Continuation Passing Style、以降CPS)という言葉を聞いたことがあるでしょうか。 今日はCPSの話をします。 前提知識は、F#のみです。 継続とは CPSの前に、まずは継続の話です。 継続と言って
継続、continuationと来ればやはりSchemeの話になるのだろうか。一般社会で schemeと言えば「すきーむ（n）計画。陰謀。」であるがソフトウェア業界で Schemeと言ったらLispの一種のことだ。Lispには変種が腐るほど存在するが、 Common Lispと並んで有名なのがSchemeである。Common Lispが標準化の課程でゴテ ゴテと装備して巨大化したのに対し、Schemeは遥かにコンパクトでクリアな仕 様を持つ。またSchemeとは言語の一般名であり、その実装にはGaucheとか scmとかguileとかMIT Schemeなどがある。 さてCall/CC、正式名称Call with Current Continuation、について 説明しよう。Call/CCはちょっと見はsetjmp/longjmpと同じように見えるのだが、 スタックが深くなる方向にもジャ
Schemeは継続(continuation)という、たいへん強力で柔軟な制御機構を備えています。継続を用いれば大域脱出、コルーチン、疑似マルチタスク、バックトラックといった特殊な制御を必要とするプログラムを効率的に記述することができるのです。しかし一方でその抽象度の高さから、「継続は難しいもの」という印象も強いようです。 ここでは継続の正確な定義はとりあえず後に回し、直感的な観点から継続を導入してみたいと思います。 話を簡単にするため、今全ての手続きが1-in/1-outであるような1-Schemeというものを考えます。例えば： (define (double x) (* x x)) (double 2) => 4 (define (add1 x) (+ x 1)) (add1 2) => 3 のような手続きが1-Scheme手続きです。 (なおSchemeではlambdaを自由に導入で
2013-10-03 限定継続の(すごくわかりやすい(かもしれない))解説 ** この記事はmrubyで限定継続(shift/reset)を実装した話の一部です 限定継続とは一般化された継続のようなもので、切り取るスタックの底を指定できるcallccのようなものです。といってもこうやって言葉を並べているだけだと何を言っているか全くわからないと思うのでここから具体的に説明していきます。 限定継続にはいくつか種類があるんですが、とりあえず今はshift/resetという二つの演算子(二つで一つのペアです)を説明します。 説明で使っているAPI mruby-partcontの以下のAPIを使っています。 class Continuation self[*ret] -> value call(*ret) -> value Kernel.#reset Kernel.#shift reset rese
Shiro Kawai まだ下書き Schemeの特徴をあげるときに、「継続」や「call/cc」が出て来ないことはない。 でも、R5RSのcall/ccの項をいくら読んでも、どうもよくわからない。 call/ccを使えばC言語のbreakみたいなのとか、コルーチンとかいう スレッドもどきとかが書ける、というのはわかったけど、一体そういうのが書けて 何が嬉しいのか、そこんとこがピンと来ないんだ。 今、そこにある継続 プログラミングの世界の概念には、禅の公案のようなものがある。 それを説明する文章はほんの一文なのに、最初に目にする時、 その文は全く意味をなさない、暗号のように感じられる。 だがひとたびその概念を理解すると、 その概念の説明は確かにその一文で説明されているのがわかるのだ。 そんな、「分かれば分かる」という禅問答の中でも 「継続」は最も謎めいたものの一つと言えるだろう。 文献を紐
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く