continuationとは？わかりやすく解説

計算機科学における継続（けいぞく、continuation）とは、プログラムを実行中のある時点において、評価されていない残りのプログラム（the rest of the program）を表現するものであり、手続き（procedure）あるいは関数（function）として表現されるものである^[1]。

継続に相当する概念は1960年代初頭から存在しており、Algol 60のコンパイラの実装^[2]などの文献にたびたび登場していたが、継続の利用に関する最も早い記述は、1964年のアドリアン・ファン・ワインハールデン (en:Adriaan van Wijngaarden) によるものである^[1]。

概要

計算一般における継続

Schemeによる次の式を考える：

(+ 4 (+ 1 2))

この式を評価する際、まず (+ 1 2) が計算され、すなわち 1+2 が計算され、次にその結果に4を足して全体の計算結果が求められる。(+ 1 2) の評価が行われた段階での「残りの計算」を表現すると、

(lambda (v) (+ 4 v))

のようになる^[3]。この式はすなわち、値 $v$ を引数に取り、それに4を足した値を返す関数である。実際、この後 (+ 1 2) の計算結果が $v$ に代入されて、4を足した値が最終的に計算結果が求められるため、この関数は確かに (+ 1 2) を評価する段階での「残りの計算」の表現である。

call/cc

Schemeの call-with-current-continuation (call/cc と省略される) は、その時点での継続を引数として関数を呼び出す手続きである。Schemeの言語仕様書（R7RS^[4]）には「もっとも単純な例」として次のコードが載っている：

(define list-length
  (lambda (obj)
    (call-with-current-continuation
      (lambda (return)
        (letrec ((r
              (lambda (obj)
                (cond ((null? obj) 0)
                  ((pair? obj)
                    (+ (r (cdr obj)) 1))
                  (else (return #f))))))
          (r obj))))))