スキップしてメイン コンテンツに移動

部分継続チュートリアル

この文書について

これはCommunity Scheme Wikiで公開されているcomposable-continuations-tutorial(2010年09月30日版)の日本語訳です。

誤字脱字・誤訳などがありましたらコメントあるいはメールで御指摘いただけると幸いです。

本訳は原文のライセンスに基づきCreative Commons Attribution-ShareAlike 2.0 Genericの下で公開されます。

Original text: Copyright© 2006-2010 Community Scheme Wiki

Japanese translation: Copyright© 2011 SATOH Koichi

本文

部分継続(Composable continuation)は継続区間を具象化することで制御を逆転させるものです。 ウンザリするほど複雑な概念を表す長ったらしいジャーゴンのように聞こえますが、実際はそうではありません。今からそれを説明します。

resetshiftという2つのスペシャルフォームを導入するところから始めましょう[1](reset expression)は特別な継続を作るなりスタックに目印を付けるなりしてからexpressionを評価します。簡単に言えば、expressionが評価されるとき、あとから参照できる評価中の情報が存在するということです。 実際にはshiftがこの情報を参照します。(shift variable expression)は目印のついた場所、つまりresetを使った場所にジャンプし、その場所からshiftを呼び出した場所までのプログラムの断片を保存します; これはプログラムの区間を「部分継続」として知られる組み合わせ可能な手続きに具象化し、この手続きにvariableを束縛してからexpressionを評価します。

組み合わせ可能(Composable)という語はその手続きが呼び出し元に戻ってくるため、他の手続きと組み合わせられることから来ています。 Composable continuationの別名として例えば限定継続(Delimited continuation)や部分継続(Partial continuation)もありますが、ここでは一貫して「組み合わせ可能」という用語を使います(訳注: 日本語では「部分継続」が訳語としてメジャーなので、この語を用いることにします)。 組み合わせ可能という特性はcall-with-current-continuatonが生成する「脱出継続」と違う部分です。 脱出継続は戻ってきません——というより、制御をプログラムの別の場所に戻す効果があります——が、部分継続は戻ってきます。

部分継続を呼び出すと、制御をshiftが呼ばれた場所に戻します。 しかしresetに渡された式が評価された位置に制御が続けて戻るときは、resetが呼ばれた位置に戻るのではなく、部分継続手続きが呼び出された位置に戻るのです!

別の説明としてコード変形を示してみます[2]:

(reset (...A... (shift V E) ...B...))
; -->
(let ((V (lambda (x) (...A... x ...B...))))
  E)

(reset E)
; -->
E

一連の例が意味を理解するのに役立つでしょう。 まず最初に、shiftがない(reset expression)は末尾再帰を考えなければexpressionの評価と同じです。

(+ 1 (reset (+ 2 3)))
;Value: 6

(cons 1 (reset (cons 2 '())))
;Value: (1 2)

次にshiftを加えます。shiftで作られた部分継続を呼び出さなければ、shiftは自身とそれを動的スコープで内包しているresetの間の一切を捨てる効果があります。

(+ 1 (reset (+ 2 (shift k
                   ;; Kは無視
                   3))))
;Value: 4

(cons 1 (reset (cons 2 (shift k
                         ;; kは無視
                         (cons 3 '())))))
;Value: (1 3)

問題: もし(reset ... shift)内でkを適用したらどうなるでしょう?

次に部分継続を使ってみましょう。これは(lambda (x) (+ 2 x))(lambda (x) (cons 2 x))と同じになります; これはresetに渡した式のshift呼び出しをすべて引数xで置き換えた1引数関数を作ることで確認できます。これこそが「制御の逆転」の意味するところです: プログラムの評価の一部が関数として具象化されているのです。

(+ 1 (reset (+ 2 (shift k
                   (+ 3 (k 4))))))
; -->
(+ 1 (let ((k (lambda (x) (+ 2 x))))
       (+ 3 (k 4))))
; -->
(+ 1 (+ 3 (+ 2 4)))
;Value: 10

(cons 1 (reset (cons 2 (shift k
                         (cons 3 (k (cons 4 '())))))))
; -->
(cons 1 (let ((k (lambda (x) (cons 2 x))))
          (cons 3 (k (cons 4 '())))))
; -->
(cons 1 (cons 3 (cons 2 (cons 4 '()))))
;Value: (1 3 2 4)

さらに、部分継続は複数回呼び出すこともできます; プログラムの一部を実行する単なる関数であり、何度も同じ部分を実行することができます。

(+ 1 (reset (+ 2 (shift k
                   (+ 3 (k 5) (k 1))))))
; -->
(+ 1 (let ((k (lambda (x) (+ 2 x))))
       (+ 3 (k 5) (k 1))))
; -->
(+ 1 (+ 3 (+ 2 5) (+ 2 1)))
;Value: 14

(cons 1 (reset (cons 2 (shift k
                         (cons 3 (k (k (cons 4 '()))))))))
; -->
(cons 1 (let ((k (lambda (x) (cons 2 x))))
       (cons 3 (k (k (cons 4 '()))))))
; -->
(cons 1 (cons 3 (cons 2 (cons 2 (cons 4 '())))))
;Value: (1 3 2 2 4)

これらの例は多分恣意的で、実用的ではないように見えるでしょう。実際これらの例は恣意的ですが、その目的はshiftresetを簡潔な方法で説明するところにありました。 式変形は手作業で行うこともできますが、shiftresetの威力は全体的なコード変形を必要としない点にあります。 shiftresetは抽象の境界を越えて、字句的に手が届かないスコープの動的な制御をも逆転させることができます; つまり、部分継続はプログラムの様々な点を把握せずとも、その一部を関数に詰め込むことができるということです 。

もっと洗練された例を挙げましょう。for-eachのような手続があったとして、for-eachやその類の手続が受け付けるようなコレクションを受け取ってその要素の遅延ストリームを返す手続を作りたいとします。これはcall-with-current-continuation3つとset!を使って作ることができます。胃腸や心臓が弱い方は見ないほうが良いでしょう。

(define (for-each->stream-maker for-each)
  (stream-lambda (collection)
    (call-with-current-continuation
      (lambda (return-cdr)
        (for-each
          (lambda (element)
            (call-with-current-continuation
              (lambda (return-to-for-each)
                (return-cdr
                  (stream-cons element
                    (call-with-current-continuation
                      (lambda (return-next-cdr)
                        (set! return-cdr return-next-cdr)
                        (return-to-for-each))))))))
          collection)
        (return-cdr stream-null)))))

明らかにこれは不細工です。コードが入れ子の深みに降りていくのに合わせてインデントが素敵なスロープを描いていますが、このコードを考えているときに思い浮かぶことは優雅さという概念についての考えだけでしょう。 しかしながら、このパターンはshiftresetが抽象化しているものによく似ています。

return-cdrresetで評価される式の継続を表しています; これにはコレクションを走査する間、連続した出力ストリームのcdrを返すためにreturn-next-cdrが代入されます。shift同様、保存しておきたいプログラムの一部に入った時点で継続を具象化―—return-to-for-each——し、次のresetする位置、つまりreturn-cdrに脱出しています。 保存した一部を使いたくなったら、あたかも部分継続を呼び出すように継続——これはストリームが次に返すcdrの継続——をreturn-next-cdrとして具象化し、それをreturn-cdrに代入してプログラムの一部が次にどこに戻れば良いか分かるようにしてから、return-to-for-eachを呼び出してプログラムの一部をもう一度実行しています。

これはshiftresetを使ってもっとずっと簡単に表現できます:

(define (for-each->stream-maker for-each)
  (stream-lambda (collection)
    (reset (begin
             (for-each (lambda (element)
                         (shift k
                           (stream-cons element (k))))
                       collection)
             stream-null))))

脚注

[1] スペシャルフォームの代わりに(reset thunk)(shift receiver)という手続きを使うこともできますが、簡潔さとカラム幅、それから一般的な使い方で一行に収まるようにそうしませんでした。 controlprompt——このページのほとんどの例で同じ結果になるもう一対のよく知られた制御演算子——もあることを覚えておいて下さい。

[2] この変形は厳密には正しくありません、本当はもう少しresetを置く必要があります。 詳細はこの文書の範囲から外れる上、入れ子になったshiftresetを使うときしか関係のないことです。 が、完備性のため、必要ならここに完全な変形を示しておきます:

(reset (...A... (shift K E) ...B...))
; -->
(let ((K (lambda (x) (reset (...A... x ...B...)))))
  (reset E))

(reset E)
; -->
E

(ラムダ式の内側のresetだけがshift/reset演算子とcontrol/prompt演算子の相違点です)

実装

Riastradh氏によるshiftresetの実装call-with-current-continuationに基づいており、非常に重く実用には低速ですが、可搬性があります。

Oleg氏によるバージョンは継続が必要とする部分だけをキャプチャするのにトランポリンを使っています。これはメモリリークがないという利点を持ちますが、このトランポリンは「空の」継続の中に置くべきで、また期待する動作のためにcall/ccを変更する必要があります。

PLT Scheme(訳注: Racketに改名しています)のscheme/controlライブラリにはshift/resetやその他多数の制御演算子が論文へのリンク付きで収録されています。

GasbichlerとSperber両氏による論文「Final Shift for Call/cc: Direct Implementation of Shift and Reset」は様々な実装技術の詳細を掘り下げています(Sperber氏のオンラインで公開されている論文)。

コメント

このブログの人気の投稿

C の時間操作関数は tm 構造体の BSD 拡張を無視するという話

久しぶりに C++ (as better C) で真面目なプログラムを書いていて引っかかったので備忘録。 「拡張なんだから標準関数の挙動に影響するわけねえだろ」という常識人は読む必要はない。 要旨 time_t の表現は環境依存 サポートしている時刻は UTC とプロセスグローバルなシステム時刻 (local time) のみで、任意のタイムゾーン間の時刻変換を行う標準的な方法はない BSD / GNU libc は tm 構造体にタイムゾーン情報を含むが、tm -> time_t の変換 ( timegm / mktime ) においてその情報は無視される 事前知識 C 標準ライブラリにおいて時刻の操作に関係するものは time.h (C++ では ctime) ヘッダに定義されている。ここで時刻を表現するデータ型は2つある: time_t と tm である。time_t が第一義的な型であり、それを人間が扱い易いように分解した副次的な構造体が tm という関係になっている。なので標準ライブラリには現在時刻を time_t として取得する関数 ( time_t time(time_t *) ) が先ずあり、そこから time_t と tm を相互に変換する関数が定義されている。 ここで time_t の定義は処理系依存である。C / C++ 標準はそれが算術型であることを求めているのみで (C11 からは実数型に厳格化された)、その実体は任意である。POSIX においては UNIX epoch (1970-01-01T00:00:00Z) からのうるう秒を除いた経過秒数であることが保証されており Linux や BSD の子孫も同様だが、この事実に依存するのは移植性のある方法ではない。 一方で tm は構造体であり、最低限必要なデータメンバが規定されている: int tm_year : 1900 年からの年数 int tm_mon : 月 (0-based; 即ち [0, 11]) int tm_mday : 月初からの日数 (1-based) int tm_hour : 時 (Military clock; 即ち [0, 23]) int tm_min : 分 int tm_sec : 秒 (うるう秒を含み得るので [0...

js_of_ocaml の使い方

js_of_ocaml (jsoo) は Ocsigen が提供しているコンパイラである。その名の通り OCaml バイトコードから JavaScript コードを生成する。 これを使うことで OCaml で書いたプログラムを Web ブラウザや node.js で実行することができる。 インストール 単に OPAM を使えば良い: $ opam install js_of_ocaml js_of_ocaml-ocamlbuild js_of_ocaml-ppx バージョン 3.0 から OPAM パッケージが分割されたので、必要なライブラリやプリプロセッサは個別にインストールする必要がある。 とりあえず使うだけなら js_of_ocaml と js_of_ocaml-ppx の二つで十分。後述するように OCamlBuild でアプリケーションをビルドするなら js_of_ocaml-ocamlbuild も入れると良い。 これで js_of_ocaml コマンドがインストールされ、OCamlFind に js_of_ocaml 及びサブパッケージが登録される。 コンパイルの仕方 以下ソースファイル名は app.ml とし、ワーキングディレクトリにあるものとする。 手動でやる場合 一番安直な方法は、直接 js_of_ocaml コマンドを実行することである: $ # バイトコードにコンパイルする。js_of_ocaml.ppx は JavaScript オブジェクトの作成や操作の構文糖衣を使う場合に必要 $ ocamlfind ocamlc -package js_of_ocaml,js_of_ocaml.ppx -linkpkg -o app.byte app.ml $ # 得られたバイトコードを JavaScript にコンパイルする $ js_of_ocaml -o app.js app.byte OCamlBuild を使う場合 OCamlBuild を使う場合、.js 用のビルドルールを定義したディスパッチャが付属しているので myocamlbuild.ml でこれを使う: let () = Ocamlbuild_plugin . dispatch Ocamlbuild_js_of_ocaml . dispatcher $ # app.ml -...

macOS で GUI 版 Emacs を使う設定

macOS であっても端末エミュレータ上で CLI 版 Emacs を使っているプログラマは多いと思うが、端末側に修飾キーを取られたり東アジア文字の文字幅判定が狂ってウィンドウ描画が崩れたりなどしてあまり良いことがない。 それなら GUI 版の Emacs.app を使った方がマウスも使える上に treemacs などはアイコンも表示されてリッチな UI になる。 しかし何事も完璧とはいかないもので、CLI だと問題なかったものが GUI だと面倒になることがある。その最大の原因はシェルの子プロセスではないという点である。つまり macOS の GUI アプリケーションは launchd が起動しその環境変数やワーキングディレクトリを引き継ぐので、ファイルを開こうとしたらホームディレクトリ ( ~/ ) でなくルートディレクトリ ( / ) を見に行くし、ホームディレクトリなり /opt/local なりに好き勝手にインストールしたツールを run-* 関数やら shell やら flycheck やらで実行しようとしてもパスが通っていない。 ワーキングディレクトリに関しては簡単な解決策があり、 default-directory という変数をホームディレクトリに設定すれば良い。ただし起動時にスプラッシュスクリーンを表示する設定の場合、このバッファのワーキングディレクトリは command-line-default-directory で設定されており、デフォルト値が解決される前に適用されてしまうので併せて明示的に初期化する必要がある: (setq default-directory "~/") (setq command-line-default-directory "~/") 次にパスの問題だが、まさにこの問題を解決するために exec-path-from-shell というパッケージがある。これを使うとユーザのシェル設定を推定し、ログインシェルとして起動した場合の環境変数 PATH と MANPATH を取得して Emacs 上で同じ値を setenv する、という処理をやってくれる。MELPA にあるので package-install するだけで使えるようになる。 このパッケージは GUI ...

BuckleScript が ReScript に改称し独自言語を導入した

Via: BuckleScript Good and Bad News - Psellos OCaml / ReasonML 文法と標準ライブラリを採用した JavaScript トランスパイラである BuckleScript が ReScript に改称した。 公式サイトによると改称の理由は、 Unifying the tools in one coherent platform and core team allows us to build features that wouldn’t be possible in the original BuckleScript + Reason setup. (単一のプラットフォームとコアチームにツールを統合することで従来の BuckleScript + Reason 体制では不可能であった機能開発が可能になる) とのこと。要は Facebook が主導する外部プロジェクトである ReasonML に依存せずに開発を進めていくためにフォークするという話で、Chromium のレンダリングエンジンが Apple の WebKit から Google 主導の Blink に切り替わったのと似た動機である (プログラミング言語の分野でも Object Pascal が Pascal を逸脱して Delphi Language になったとか PLT Scheme (の第一言語) が RnRS とは別路線に舵を切って Racket になったとか、割とよくある話である。) 公式ブログの Q&A によると OCaml / ReasonML 文法のサポートは継続され、既存の BuckleScript プロジェクトは問題なくビルドできるとのこと。ただし現時点で公式ドキュメントは ReScript 文法のみに言及しているなど、サポート水準のティアを分けて ReScript 文法を優遇することで移行を推進していく方針である。 上流である OCaml の更新は取り込み、AST の互換性も維持される。将来 ReScript から言語機能が削除されることは有り得るが、OCaml / ReasonML からは今日の BuckleScript が提供する機能すべてにアクセスできる。 現時点における ReScript の ...

Project Euler - Problem 27

問題 しばらく止まってましたが今日から再開。 原文 Considering quadratics of the form: n 2 + an + b, where |a| < 1000 and |b| < 1000 Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0. 日本語訳 |a| < 1000, |b| < 1000 として以下の二次式を考える (ここで|a|は絶対値): n 2 + an + b n=0から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数a, bの積を答えよ. 解答 最大探索範囲は-999 <= a <= 999、-999 <= b <= 999なので、およそ4,000,000通りの係数の組合せを試すことになります。組合せ毎に数列を生成して、それが素数か判定するわけですからたまりません。簡単な検討を加えて範囲を絞りましょう。 与えられた二次式をf(n)とおくと、f(0) = b、f(1) = a + b + 1です。 f(n)が長さ2以上の素数列を生成するならこれらは素数ですから、次のことがいえます: bは素数である a + b + 1は素数である b = 2のとき、aは偶数である それ以外のとき、aは奇数である 素数判定関数 is_prime には同じ引数が与えられることがよくあるのでメモ化しています。 #!/usr/bin/perl use strict; use warnings; use feature qw/say/; sub prime_seq_len($$) { my ($coeff_a, $coeff_b) = @_; my $len = 0; my $n = 0; $len++, $n++ while is_prime($n * ($n + $coeff_a) ...