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

部分継続チュートリアル

この文書について

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

コメント

このブログの人気の投稿

Perl 7 より先に Perl 5.34 が出るぞという話

Perl 5 の次期バージョンとして一部後方互換でない変更 (主に間接オブジェクト記法の削除とベストプラクティスのデフォルトでの有効化) を含んだメジャーバージョンアップである Perl 7 がアナウンスされたのは昨年の 6 月 のことだったが、その前に Perl 5 の次期周期リリースである Perl 5.34 が 5 月にリリース予定 である。 現在開発版は Perl 5.33.8 がリリースされておりユーザから見える変更は凍結、4 月下旬の 5.33.9 で全コードが凍結され 5 月下旬に 5.34.0 としてリリース予定とのこと。 そういうわけで事前に新機能の予習をしておく。 8進数数値リテラルの新構文 見た瞬間「マジかよ」と口に出た。これまで Perl はプレフィクス 0 がついた数値リテラルを8進数と見做してきたが、プレフィクスに 0o (zero, small o) も使えるようになる。 もちろんこれは2進数リテラルの 0b や 16進数リテラルの 0x との一貫性のためである。リテラルと同じ解釈で文字列を数値に変換する組み込み関数 oct も` 新構文を解するようになる。 昨今無数の言語に取り入れられているリテラル記法ではあるが、この記法の問題は o (small o) と 0 (zero) の区別が難しいことで、より悪いことに大文字も合法である: 0O755 Try / Catch 構文 Perl 5 のリリース以来 30 年ほど待たれた実験的「新機能」である。 Perl 5 における例外処理が特別な構文でなかったのは予約語を増やさない配慮だったはずだが、TryCatch とか Try::Tiny のようなモジュールが氾濫して当初の意図が無意味になったというのもあるかも知れない。 use feature qw/ try / ; no warnings qw/ experimental::try / ; try { failable_operation(); } catch ( $e ) { recover_from_error( $e ); } Raku (former Perl 6) だと CATCH (大文字なことに注意) ブロックが自分の宣言されたスコープ内で投げられた例外を捕らえる

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 の

多分週刊チラシの裏 (Mar 23, 2021 - Mar 27, 2021)

Intel プロセッサのマイクロコードを変更する非公開命令が発見される 今日のプロセッサは複雑な命令を単純な回路で実装したりバグの修正を容易にするため、1 個の命令でも実際にはプロセッサ内部に格納されたマイクロプログラムを実行するようになっていることが多い。 かつて浮動小数点演算器のバグで Pentium をリコールする羽目になった Intel も例外ではないのだが、Intel が電子署名したマイクロコードでなくとも適用できる非公開命令が発見されたという報告。 ただし無条件ではなく、命令自体はユーザモードでもデコードされるがプロセッサが特定の “Unlocked State” にないときは未定義命令として処理されるらしい。 MSKK の週休三日トライアルで生産性が四割向上 2019 年の記事。週休三日制を導入する事業所は中小を中心に増加しているが、Microsoft の日本法人であるマイクロソフト株式会社 (MSKK) が “Work Life Choice Challenge” と称して 2019 年夏に実施した金曜日を休日とする試験的措置において、前年同月比 40 % の生産性向上が見られたとのこと。 同施策は休日の追加に加えて会議時間短縮の奨励、またメッセージングアプリによる会議自体の代替なども含んでいる。 2015 年の電通における過労自殺事件に国際的な耳目が集まって以降、日本は「過労死」に象徴される長時間労働の是正に取り組んでおり、MSKK のこの措置は将に時節を得たものであったと言える。 r/WallStreetBets からゴリラ保護基金へ多額の寄付 「みんなで株価吊り上げて食い付いたヘッジファンド釣ろうぜ」という一種の祭で GameStop の株価が高騰したのは今年の 1 月だが、その震源地であった Reddit の WallStreetBets (WSB) コミュニティからマウンテンゴリラ保護のための基金である The Dian Fossey Gorilla Fund International に 350,000 USD の寄付があったとのこと。 ところで何故ゴリラかというと「猿の惑星」に倣って WSB コミュニティ内で同志を猿 (ape) と称していたからとか。異説に「猿みたいに株を買うのにキーボードを連打しているから」とも。

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 と、時系列イベ

多分週刊チラシの裏 (Feb 28, 2021 - Mar 22, 2021)

JavaScript 開発者が如何にして TypeScript 嫌いから TypeScript ファンになったか 気軽な読み物。型宣言の冗長さとジェネリクスなどの複雑性を嫌って (選択肢にあれば) JavaScript の方を選んできた筆者が TypeScript しか選べない職場に移って数ヶ月後にはすっかりファンになっていたという話。 理由は月並で「『不可能な状態を不可能にする』Union Type と網羅性チェック」「コンパイル時型検査によるエラーの早期検出」「リッチな IDE 支援」の 3 本。理由がそれだけなら個人的には Flow か Elm を進めたいところではある。 NASA の最新火星ローバーが搭載するプロセッサは 1998 年の iMac と同じ NASA が Mars 2020 ミッションのために送り出し、先月火星表面に着陸した最新かつ過去最大のローバーである Perseverance の話。 2021 年に活動を開始したこのハイテク・ガジェットのメインプロセッサは PowerPC 750 であるとのこと。1998 年発売の初代 iMac が搭載していた “G3” プロセッサといえば分かり易いだろう。 もちろん民生品そのものではなく、-55 - 125 ℃ の気温と 200,000 - 1,000,000 Rad の放射線に耐える特別仕様の BAE Systems RAD750 である。ちなみに「火星で自撮り」という快挙を成し遂げたのち現在も活動中の先代 Curiosity も同じものを搭載している。動作周波数 110 - 200 MHz、価格は $200,000 程度とのこと。 Internet Archive Infrastructure 過去の Web サイト、書籍、ビデオに音楽からクラシックソフトウェアまでインターネットに公開されたあらゆるデータを収集・保存する Internet Archive のインフラ紹介ビデオ。 クラウドは一切使っておらず、自前のベアメタルサーバ 750 台に接続されたストレージはシステム全体で 200PB とのこと。保存されるデータは現在のところ年 25 % 以上増大しており、四半期で 5 - 6 PB 規模だという。 Semantic Versioning はお前を救わない 「ある API