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

部分継続チュートリアル

ラベル:

この文書について

これは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氏のオンラインで公開されている論文)。

コメント

コメントを投稿

このブログの人気の投稿

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

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

Perl 5.42 が出たので perldelta を読んだ

去る2025年7月2日に Perl 5.42 がリリースされた。ので例によって perldelta を一通り眺めた。 このバージョンは実験的機能である組込みのクラス構文の実装が進展した。 他にもパフォーマンスの改良、組み込み関数・演算子・C レベル API の追加、多数のバグ修正があるが劇的な変化ではなく、発見・修正された脆弱性もかなり限定的な問題なので刺さる機能がなければ急いで移行する必要はあまりないように思われる。 以下主だった新機能の抜粋。 source::encoding プラグマ ソースコードが特定の文字エンコーディングで記述されていることを宣言するプラグマ。サポートされているエンコーディングは ASCII と UTF-8 のみである。 use source::encoding 'ascii' が宣言された字句的スコープにおいて非 ASCII 文字を記述するとコンパイル時エラーが発生するようになる。 use source::encoding 'utf8' は単に use utf8 のシノニムである。 Perl 5 は 2000 年にリリースされたバージョン 5.6 から UTF-8 によるソースコード記述をサポートしているが、後方互換性のため既定では ASCII を前提としており、 utf8 プラグマを使わない限り文字列リテラルや RegExp リテラルはバイト列として解釈されるし、識別子にも英数字および '_' しか使うことができない。 識別子はともかく「リテラルは既定でバイト列である」という意味論は極めて誤用しやすい。Unicode 文字列のつもりで渡した値が意図せずバイト列であったために実行時警告・エラーを得た経験は非英語圏のプログラマなら一度ならずあるだろう。 このプラグマはそのような初歩的なバグをコンパイル時に検出することで、Perl プログラムの最も頻出するエラーの一つを実質的に解消しようとしている。 ちなみに use v5.42 すると自動で use source::encoding 'ascii' も有効になるので、今まさに警告を吐いているようなアプリケーションをアップグレードする際は注意が必要である。 any / all 演算子 実験的...
コメントを投稿
続きを読む

Project Euler - Problem 42

問題 原文 By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t 10 . If the word value is a triangle number then we shall call the word a triangle word. Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words? 日本語訳 単語中のアルファベットを数値に変換した後に和をとる. この和を「単語の値」と呼ぶことにする. 例えば SKY は 19 + 11 + 25 = 55 = t 10 である. 単語の値が三角数であるとき, その単語を三角語と呼ぶ. 16Kのテキストファイル word.txt 中に約2000語の英単語が記されている. 三角語はいくつあるか? 解答 42問目! ちょっと拍子抜けするほど簡単です。三角数を片っ端から計算して連想配列に入れておき、文字列の値を計算して照合するだけです。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/sum/; sub word_value($) { my $offset = ord('A') - 1; sum map { ord($_) - $offset } split //, uc shift; } sub tri_num($) { my $n = shift; $n * ($n + 1) / 2...
コメントを投稿
続きを読む

Project Euler - Problem 38

問題 原文 What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1? 日本語訳 整数と(1,2,...,n) (n > 1) との連結積として得られる9桁のPandigital数の中で最大のものを答えよ. 解答 乗数が1, 2, ..., n (n > 1)で桁数は9なので、被乗数mは1から9999の範囲です。 範囲が分かれば後は簡単で、m×1から順に積を連結していって、丁度9桁となったときにPandigital数であればいいわけです。 Pandigital数 を定義通り考えれば「1から9のすべての数字が1回以上現れる数」ですが、この問題では桁数の制約からいずれの数字も1回ずつしか現れないため、「同じ数字が重複して出現せず、0が現れない数」に読み替えることができます。Perlだとこちらの方が正規表現マッチングが高速でした。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/max/; say max map { my $cat = ''; for (my $mul = 1; length $cat < 9; $cat .= $_ * $mul++) {} (length $cat == 9 and $cat !~ /0/ and $cat !~ /(\d).*\1/) ? $cat : () } 1 .. 9999;
コメントを投稿
続きを読む

Perl 5 to 6 - 列挙型

これはMoritz Lenz氏のWebサイト Perlgeek.de で公開されているブログ記事 "Perl 5 to 6" Lesson 16 - Enums の日本語訳です。 原文は Creative Commons Attribution 3.0 Germany に基づいて公開されています。 本エントリには Creative Commons Attribution 3.0 Unported を適用します。 Original text: Copyright© 2008-2010 Moritz Lenz Japanese translation: Copyright© 2011 SATOH Koichi NAME "Perl 5 to 6" Lesson 16 - 列挙型 SYNOPSIS enum bit Bool <False True>; my $value = $arbitrary_value but True; if $value { say "Yes, it's true"; # 表示される } enum Day ('Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun'); if custom_get_date().Day == Day::Sat | Day::Sun { say "Weekend"; } DESCRIPTION 列挙型は用途の広い獣です。定数の列挙からなる低レベルのクラスであり、定数は典型的には整数や文字列です(が任意のものが使えます)。 これらの定数は派生型やメソッド、あるいは通常の値のようにふるまいます。 but 演算子でオブジェクトに結びつけることができ、これによって列挙型を値に「ミックスイン」できます: my $x = $today but Day::Tue; 列挙型の型名を関数のように使うこともでき、引数として値を指定できます: $x = $today but Day($weekday); ...
コメントを投稿
続きを読む