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

部分継続チュートリアル

ラベル:

この文書について

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

resetとshiftという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)

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

もっと洗練された例を挙げましょう。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)))))

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

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

これはshiftとresetを使ってもっとずっと簡単に表現できます：

(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)という手続きを使うこともできますが、簡潔さとカラム幅、それから一般的な使い方で一行に収まるようにそうしませんでした。 controlとprompt——このページのほとんどの例で同じ結果になるもう一対のよく知られた制御演算子——もあることを覚えておいて下さい。

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

(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氏によるshiftとresetの実装は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...
コメントを投稿
続きを読む

Perl の新 class 構文を使ってみる

Perl 5 のオブジェクト指向機能は基本的には Python の影響を受けたものだが、データを名前空間 (package) に bless する機構だけで Perl 4 以来の名前空間とサブルーチンをそのままクラスとメソッドに転換し第一級のオブジェクト指向システムとした言語設計は驚嘆に価する。 実際この言語のオブジェクトシステムは動的型付言語のオブジェクト指向プログラミングに要求されるおよそあらゆる機能を暗にサポートしており、CPAN には Moose を筆頭とした屋下屋オブジェクトシステムが複数存在しているがその多くは Pure Perl ライブラリである。つまり「やろうと思えば全部手書きで実現できる」わけである。 そういうわけで Perl のオブジェクト指向プログラミングサポートは機能面では (静的型検査の不在という現代的には極めて重大な欠如を除けば) 申し分ないのだが、しかし Moose その他の存在が示しているように一つ明らかな欠点がある。記述の冗長さだ。 コンストラクタを含むあらゆるメソッドは第一引数としてレシーバを受ける単なるサブルーチンとして明示的に書く必要があるし、オブジェクトのインスタンス変数 (a.k.a. プロパティ / データメンバ) は bless されたデータに直接的ないし間接的に プログラマ定義の方法 で格納されるためアクセス手段は実装依存である。これはカプセル化の観点からは望ましい性質だが、他者の書いたクラスを継承するときに問題となる。ある日データ表現を変更した親クラスがリリースされると突然自分の書いた子クラスが実行時エラーを起こすようになるわけだ。 そうならないためにはインスタンス変数へのアクセスに (protected な) アクセサを使う必要があるのだが、そのためには親クラスが明示的にそれらを提供している必要があるし、そもそも Perl にはメソッドのアクセス修飾子というものがないので完全な制御を与えるならばオブジェクトの内部状態がすべて public になってしまう。 そのような事情もあり、特にパフォーマンスが問題にならないようなアプリケーションコードでは Moose のようなリッチな語彙を提供するオブジェクトシステムを使うことが 公式のチュートリアルでも推奨 されてきた。Perl コアのオブジェクトシステムの改良は...
コメントを投稿
続きを読む

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 の ...
コメントを投稿
続きを読む

OCaml で Web フロントエンドを書く

要旨 フロントエンド開発に Elm は堅くて速くてとても良いと思う。昨今の Flux 系アーキテクチャは代数的データ型と相性が良い。ところで工数を減らすためにはバックエンドも同じ言語で書いてあわよくば isomorphic にしてしまいたいところだが、Elm はバックエンドを書くには現状適していない。 OCaml なら js_of_ocaml でエコシステムを丸ごとブラウザに持って来れるのでフロントエンドもバックエンドも無理なく書けるはずである。まず The Elm Architecture を OCaml で実践できるようにするため Caelm というライブラリを書いている。俺の野望はまだまだこれからだ (未完) Elm と TEA について Elm というプログラミング言語がある。いわゆる AltJS の一つである。 ミニマリスティクな ML 系の関数言語で、型推論を持ち、型クラスを持たず、例外機構を持たず、変数の再代入を許さず、正格評価され、代数的データ型を持つ。 言語も小綺麗で良いのだが、何より付属のコアライブラリが体現する The Elm Architecture (TEA) が重要である。 TEA は端的に言えば Flux フロントエンド・アーキテクチャの変種である。同じく Flux の派生である Redux の README に TEA の影響を受けたと書いてあるので知っている人もいるだろう。 ビューなどから非同期に送信される Message (Redux だと Action) を受けて状態 (Model; Redux だと State) を更新すると、それに対応して Virtual DOM が再構築されビューがよしなに再描画され人生を書き換える者もいた——という一方向の流れはいずれにせよ同じである。 差異はオブジェクトではなく関数で構成されていることと、アプリケーション外部との入出力は非同期メッセージである Cmd / Sub を返す規約になっていることくらいだろうか。 後者は面白い特徴で、副作用のある処理はアプリケーションの外で起きて結果だけが Message として非同期に飛んでくるので、内部は純粋に保たれる。つまり Elm アプリケーションが相手にしないといけない入力は今現在のアプリケーションの完全な状態である Model と、時系列イベ...
コメントを投稿
続きを読む

Perl のサブルーチンシグネチャ早見表

Perl のサブルーチン引数といえば実引数への参照を保持する特殊配列 @_ を手続き的に分解するのが長らくの伝統だった。これはシェルの特殊変数 $@ に由来する意味論で、おそらく JavaScript の arguments 変数にも影響を与えている。 すべての Perl サブルーチンはプロトタイプ宣言がない限りリスト演算子なので、この流儀は一種合理的でもあるのだが、実用的にそれで良いかというとまったくそうではないという問題があった; 結局大多数のサブルーチンは定数個の引数を取るので、それを参照する形式的パラメータが宣言できる方が都合が良いのである。 そういうわけで実験的に導入されたサブルーチンシグネチャ機能により形式的パラメータが宣言できるようになったのは Perl 5.20 からである。その後 Perl 5.28 において出現位置がサブルーチン属性の後に移動したことを除けば Perl 5.34 リリース前夜の今まで基本的に変わっておらず、未だに実験的機能のままである。 おまじない シグネチャは前方互換性を持たない (構文的にプロトタイプと衝突している) 実験的機能なのでデフォルトでは無効になっている。 そのため明示的にプラグマで利用を宣言しなければならない: use feature qw/signatures/; no warnings qw/experimental::signatures/; どの途みんな say 関数のために使うので feature プラグマは問題ないだろう。実験的機能を断りなしに使うと怒られるので、 no warnings で確信犯であることをアピールする必要がある。 これでプラグマのスコープにおいてサブルーチンシグネチャ (と :prototype 属性; 後述) が利用可能になり、 従来のプロトタイプ構文が無効になる。 使い方 対訳を載せておく。シグネチャの方は実行時に引数チェックを行うので厳密には等価でないことに注意: # Old School use feature qw/signatures/ 1 sub f { my ($x) = @_; ... } sub f($x) { ... } 2 sub f { my ($x, undef, $y) = @_...
コメントを投稿
続きを読む