Scheme/継続

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を自由に導入できるので、n-inの手続きであっても次のように「1-in手続きのつながったもの」に加工できます)

 (define (f x y) (* x y))

 (lambda (X)
   (lambda (Y)
      (f X Y)))

---

1-in/1-out手続きf,g,hを考えると、あらゆる1-Schemeプログラムは本質的に次のような形をもつと考えられます。

(h (g (f 入力)))  => 結果

つまり前の手続きの出力が次の手続きの入力として渡され、それが連なって最終結果が導かれるわけです。パイプラインに似ていますね。

ところで、これは次のように図式化できます。

入力 => [ f => g => h ] => 結果

ここで少し細工をして

入力 => [ f => 1 => h ] => 結果

としたらどうでしょうか。つまりgで計算をする替わりに前後の脈絡なく1をhに渡してしまうわけです。考えて見れば、これは部品の差し替えが起こるだけでプログラム全体の進行には大して影響がないことが分かります。それどころか、「特別な場合にgの計算を省略したい」といったニーズにたいへん便利に見えます。

こういう差し替えを行うにはパイプラインを監視すればよさそうです。つまり「基本的には前の手続きの入力を次に渡すのだが、必要なら替わりの値を流し込んでもいい」というルールがあれば部品の差し替えと同じことが実現できます。これはつまり図式の => にアクセスする手段があるということになります。

=> とはなんでしょうか。

まず

• 前の値を受け取って次の手続きに渡す何か

であることが分かります。よく考えるとこれは1-in/1-outの手続きそのものです。そして「前の値」とは、ある手続きの計算結果のことですから、

• ある手続きを呼び出すとき、その後ろに必ず => が一つある

ということが言えます。最後に流し込みのルールを追加します。

• 何もしなければ => はその手前の手続きの結果を受け取るが、必要なら任意の値を渡してもいい

このような性質を持った => を「継続手続き」といいます。そして、ある手続きを呼び出す時に、すぐ後ろの継続手続を取り出す手段がSchemeには用意されているのです。これはcall-with-current-continuationあるいは省略してcall/ccと呼ばれています。

継続

Schemeの仕様書R5RSによれば、継続の正確な定義はこうです。

Whenever a Scheme expression is evaluated there is a continuation waiting the result of the expression. The continuation represents an entire (default) future for the computation.

[訳] Schemeの式が評価される時、そこには評価の結果を待つ継続が一つ待機している。継続は計算の(デフォルトの)未来全体を表している。

デフォルトの未来全体とは、ずいぶん持って回った言い方です。

これは継続手続きが連なるパイプラインの先を何であれ継続と考える、ということを意味します。実行型プログラムであればプログラムの終了までですし、対話環境なら「次の入力を受け取ってそれを解釈しまた次の・・」という繰り返しを(少なくとも概念上)継続全体としてとらえます。

ここで注意しなければならないのは、一端取り出した継続手続きは、他の手続きとなんら変わるところがない、ということです。再び上の例を考えます。

上の例を字句通りに書くと次のようになります。

(h
  (call/cc
    (lambda (cont-proc) ;; 継続手続きをとり出す
       (let ((v (f 入力)))
         (cont-proc 1)      ;; 継続手続きに1を渡す
         (g v)                    ;; ここでgを呼び出しているが、
      ))))                         ;; 直前の継続手続きで脱出してしまうため、実際には実行されない

=> (h 1)

ここでcont-procは単なる手続きなので、適当な変数に代入すれば後から再利用できてしまうのです。

(define reuse #f)
(h
  (call/cc
    (lambda (cont-proc)
      (let ((v (f 入力)))
       (set! reuse cont-proc)
       (g v)                  ;; 今度はcont-procを呼び出していないので普通に手続きは終了する
     ))))

=> (h (g v))

その後適当なタイミングでcontを呼び出すことができます。

(reuse 1)
=> (h 1)

このような場合、単に再開手続きを呼ぶだけではあまり意味がないので、脱出用の継続手続きを同時に用意して処理の中断を行うケースが多いでしょう。

(define (re-entrant stop-cont)
  (call/cc
    (lambda (continue)
      (stop-cont continue))) ;; 再開用の手続きを渡して一端終了
  (continued-body)            ;;continueが呼び出されると実行される
  ...
)

以上をまとめると、継続の基本的な作用は次の二つになります。

• 手続き呼び出しの直前にcall/ccを使うことで、替わりの脱出経路を取り出せる
• 継続を保存することで処理の再開ができる

Schemeと継続

Schemeの継続は基本的に「一入力の手続き」です。ただし真の多値であるvalues手続きをもつ関係上、「call-with-valuesの直下で呼び出されたcall/ccはn入力の継続手続きを生成する」と規定されています。

「継続」という概念は必ずしもScheme固有のものではないのですが、Schemeとワンセットで扱われることが多いようです。理由は色々ありますが、

• ラムダ算法あっての継続ということ(全ての操作がlambda手続きと見なせるから、あらゆる状況で正しく継続を取り出せる)
• 動的型(継続に任意の値を渡せる)
• 一方で副作用をもつ(レキシカルクロージャと組み合わせることで威力を発揮する)

などが考えられます。

継続の応用例

• 脱出継続
• ツリー探索
• コルーチン
• バックトラック
• 協調的マルチタスク(call/cc軽量スレッド)
• 例外処理