限定継続 (delimited continuation) の動作を理解する

Kink Scheme

限定継続のオペレータであるshift/resetおよびcontrol/promptについて、その動作が腑に落ちたので、以下にまとめます。

継続とは

継続とは、呼び出されると「この後の計算」を実行する関数です。

Schemeにはcall/ccという関数が存在し、プログラムの任意の箇所で「この後の計算」が取り出せます。たとえば次のプログラムでは、gobackにcall/ccを呼び出した箇所の継続が束縛されます。gobackを呼び出すことで、call/cc呼び出しのところに制御が戻るため、1ずつ値を足しながら無限ループします。

(let ((pair (call/cc (lambda (cont) (list 0 cont)))))
  (let ((n (car pair)) (goback (cadr pair)))
    (print n)
    (newline)
    (goback (list (+ n 1) goback))))

; => 1 2 3 4 5 ....

仮にKinkで書くとこんな感じです。Kinkにcallccは無いけれど。

[:N :goback] = callcc{(:cont)
  [0 $cont]
}
print_line(N)
goback(N + 1 $goback)
# => 1 2 3 4 5 ...

call/ccによって取り出される継続は、呼び出されると、呼び出し元に戻ってくることがありません。「この後の計算」はその実行文脈（スレッドとか）が終わるまで続き、終わったらその実行文脈はおしまいです。つまり、returnのあるcallではなく、jumpです。

限定継続とは

限定継続とは、「この後の計算」の範囲に区切りをつけた (delimit) 継続です。限定継続は呼び出されると、区切りのところまで処理を進めて、呼び出し元に戻ります。

限定継続を扱うオペレータとしては、reset（区切りをつける）とshift（継続を取り出す）のペア、prompt（区切りをつける）とcontrol（継続を取り出す）のペアなど、いくつかの組み合わせが提唱されています。

shift/resetの使い方については、次の記事が分かりやすいです。

shit/resetの応用例として、ジェネレータ（イテレータ）を手続き的に生成する例を挙げます。実装言語はKinkです。

ジェネレータは2つの関数on_itemとon_endを引数に取って、要素が無ければon_endを呼び、要素があればon_item(現在の要素 次の要素以降のジェネレータ)を呼ぶ関数だ、ということにします。ジェネレータについて、eachやmapは次のように定義できます。

:map = {(:gen :trans)
  {(:on_item :on_end)
    gen(
      {(:V :next_gen)
        on_item(trans(V) map($next_gen $trans))
      }
      $on_end
    )
  }
}

:each = {(:gen :consume)
  gen(
    {(:V :next_gen)
      consume(V)
      each($next_gen $consume)
    }
    {}
  )
}

ベクタの要素を列挙するジェネレータは次のように定義できます。

:vec_gen = {(:Vec)
  {(:on_item :on_end)
    Vec.empty?.then(
      $on_end
      { on_item(Vec.first vec_gen(Vec.drop(1))) }
    )
  }
}

:nums = vec_gen([10 20 30])
:doubled_nums = map($nums {(:N) N * 2 })
each($doubled_nums $print_line)
# => 20 40 60

ベクタのような単純なデータ構造ならともかく、木やグラフのような複雑なデータ構造を扱う場合、上記のvec_genのように、ジェネレータを関数的に定義するのは困難です。ここで限定継続 (shift/reset) を使うと、Pythonのジェネレータのように、手続き的にジェネレータが定義できます。次のプログラムのcogenは、手続き的にジェネレータを作るための関数です。

:cogen = {(:fun)
  :yield = {(:V)
    shift{(:k) ['yielded' V $k] }
  }
  _make_cogen{
    reset{
      fun($yield)
      'returned'
    }
  }
}

:_make_cogen = {(:enter)
  {(:on_item :on_end)
    enter.switch(
      ['yielded' :V :k] {
        :reenter = { k 'returned' }
        on_item(V _make_cogen($reenter))
      }
      'returned' $on_end
    )
  }
}

10, 20, 30を列挙するジェネレータは次のように作れます。

:nums = cogen{(:yield)
  yield(10)
  yield(20)
  yield(30)
}

:doubled_nums = map($nums {(:N) N * 2 })
each($doubled_nums $print_line)
# => 20 40 60

Kinkには現在shift/resetがないので、上記のプログラムは動きません。入れるとしたら、下述するタグ付き限定継続を入れるので、どっちにしろ上記はそのままでは動かないはずです。

Oleg Kiselyov氏は An argument against call/cc という記事で、call/ccが扱いづらく危険であること、むしろ言語処理系は限定継続をプリミティブとして提供するべきであることを主張しています。確かに、call/ccによる継続はいわばgotoですから、危険であることは納得できます。

しかしながら限定継続のオペレータは、構成要素が多いだけに動作が微妙であり、直感的に把握しづらいという難点があります。微妙なところとは、たとえば、限定継続の処理自体がresetの中で実行されるのか、shiftのbody部の処理はresetの中で実行されるのか、などです。次の節で見るように、shift/resetとcontrol/promptは、このような微妙な動作が異ります。

各オペレータの動作

shift/reset, control/promptを、実装してみることで動作を理解します。

実装には、Schemeから派生した言語であるRacketを使います。Racketでは、プリミティブな継続オペレータとして、make-continuation-prompt-tag, call/prompt, call/comp, abort/ccという関数が提供されています。これらを組み合わせることで、shift/reset, control/prompt, それにcall/ccも実現できます。

  • (make-continuation-prompt-tag sym): Racketでは複数種類の継続区切りが区別できます。make-continuation-prompt-tagは、区切りを区別するためのタグを作ります。
  • (call/prompt thunk tag on-abort): tagで指定されたタグについて、継続を区切ってthunkを呼びます。thunkの中でabort/ccが呼ばれたときには、on-abortを呼びます。on-abortは継続区切りの外で呼ばれます。
  • (call/comp proc tag): tagで指定されたタグについて、一番内側の区切りまで計算する限定継続を引数としてprocを呼びます。
  • (abort/cc tag v ...): tagで指定されたタグについて、一番内側の区切りまで飛んで戻ります。v ...は、call/promptで指定したon-abortに渡す引数です。

Racketの継続まわりのリファレンスは次のページです。

これらのプリミティブであれば、それぞれ実装を想像するのはなんとか可能です。call/promptはスタックに区切りのフレームを積んでthunkを呼ぶのでしょう。call/compはスタックを最内の区切りまで切り取っておいて、呼び出されるとスタックの切れ端を現在のスタックに乗っけて評価をはじめるような関数を作るのでしょう。abort/ccは、最内の区切りまでのスタックを切り捨ててからon-abortを呼ぶのでしょう。

Racketの継続プリミティブを組み合わせて、私家版のshift/resetを作ってみます。

#lang racket
(require racket/control)

(define my-tag (make-continuation-prompt-tag 'my-tag))

(define (*my-reset thunk)
  (call/prompt
    thunk
    my-tag
    (lambda (abort-thunk) (abort-thunk))))

(define (*my-shift fun)
  (call/comp
    (lambda (k)
      (let ((kk (lambda (v) (*my-reset (lambda () (k v))))))
        (abort/cc my-tag (lambda () (*my-reset (lambda () (fun kk)))))))
    my-tag))

(define-syntax my-reset
  (syntax-rules ()
                ((_ body ...)
                 (*my-reset (lambda () body ...)))))

(define-syntax my-shift
  (syntax-rules ()
                ((_ k body ...)
                 (*my-shift (lambda (k) body ...)))))

promptはresetの別名ですが、shiftとcontrolの実装は異ります。具体的には、shiftに渡される限定継続の処理がresetの中で実行されるのに対して、controlに渡される限定継続の処理はpromptの外で実行されます。

#lang racket
(require racket/control)

(define *my-prompt *my-reset)

(define (*my-control fun)
  (call/comp
    (lambda (k)
      (abort/cc my-tag (lambda () (*my-prompt (lambda () (fun k))))))
    my-tag))

(define-syntax my-prompt
  (syntax-rules ()
                ((_ body ...)
                 (my-reset body ...))))

(define-syntax my-control
  (syntax-rules ()
                ((_ k body ...)
                 (*my-control (lambda (k) body ...)))))

Olivier Danvy's puzzleの理解

実装すれば理解できたと言えるのか。もちろんそんなことはない。

限定継続のパズルとして、Olivier Danvy's puzzleというコードがあるのだそうですが、このcontrol/prompt版がまるで分からない。

Racketで書き下すと次のとおりです。

#lang racket
(require racket/control)

(reset
  (shift k1 (cons 1 (k1 #f)))
  (shift k2 (cons 2 (k2 #f)))
  '())
; => '(1 2)

(prompt
  (control k1 (cons 1 (k1 #f)))
  (control k2 (cons 2 (k2 #f)))
  '())
; => '(2 1)

shift/resetの結果は直感的ですが、control/promptの結果は実行順序がテレコになっているように見えます。

なんでこんなことになるのか。段階的な項変換で理解してみます。まずはcontrol/promptから。

#lang racket
(require racket/control)

; (1) 初期状態
(prompt
  (control k1 (cons 1 (k1 #f)))
  (control k2 (cons 2 (k2 #f)))
  '())

; (2) 最初のcontrolに突入
(prompt
  (let ((k1 (lambda (ignored)
              ignored ; 元々最初のcontrolがあったところ
             (control k2 (cons 2 (k2 #f)))
             '())))
    (cons 1 (k1 #f))))

; (3) k1を簡約
(prompt
  (cons 1 (begin
            #f
            (control k2 (cons 2 (k2 #f)))
            '())))

; (4) beginの次の#fは不要なので消しとく
(prompt
  (cons 1 (begin
            (control k2 (cons 2 (k2 #f)))
            '())))

; (5) 二番目のcontrolに突入
(prompt
  (let ((k2 (lambda (ignored)
              (cons 1 (begin
                        ignored ; 元々二番目のcontrolがあったところ
                        '())))))
    (cons 2 (k2 #f))))

; (6) k2を簡約
(prompt
  (cons 2 (cons 1 (begin
                    #f
                    '()))))

; (7) beginの結果は単に'()である
(prompt (cons 2 (cons 1 '())))

; (8) promptの中身がリストのリテラルにできる
(prompt '(2 1))

; (9) controlのないpromptは単にbodyの結果を返す
'(2 1)

続いてshift/reset。

#lang racket
(require racket/control)

; (1) 初期状態
(reset
  (shift k1 (cons 1 (k1 #f)))
  (shift k2 (cons 2 (k2 #f)))
  '())

; (2) 最初のshiftに突入
(reset
  (let ((k1 (lambda (ignored)
              (reset
                ignored
                (shift k2 (cons 2 (k2 #f)))
                '()))))
    (cons 1 (k1 #f))))

; (3) k1を簡約
(reset
  (cons 1 (reset
            #f
            (shift k2 (cons 2 (k2 #f)))
            '())))

; (4) resetの次の#fは不要なので消しとく
(reset
  (cons 1 (reset
            (shift k2 (cons 2 (k2 #f)))
            '())))

; (5) 二番目のshiftに突入
(reset
  (cons 1 (reset
            (let ((k2 (lambda (ignored)
                        (reset
                          ignored
                          '()))))
              (cons 2 (k2 #f))))))

; (6) k2を簡約
(reset (cons 1 (reset (cons 2 (reset #f '())))))

; (7) shiftが無いので順々にresetを外していく
(reset (cons 1 (reset (cons 2 (reset '())))))
(reset (cons 1 (reset (cons 2 '()))))
(reset (cons 1 (reset '(2))))
(reset (cons 1 '(2)))
(reset '(1 2))
'(1 2)

これで違いが見て取れるようになりました。control/promptでは、k1, k2の呼び出しがpromptを作らないので、その中でcontrolが呼ばれると、k1, k2の外側のprompt内の処理が限定継続に束縛されてabortされるので、処理がテレコになって見えるわけです。一方shift/resetでは、k1, k2の呼び出し自体がresetを作るので、その中でshiftが呼ばれても、k1, k2の外側の処理がabortされることはありません。

どちらが良いかは難しいところです。shift/resetの方が分かりやすいのですが、余計にスタックフレームを積むので、末尾呼び出しの最適化が掛からなくて困ることがあるのかもしれません。ここらへんは使いこなしてみないと分からなそうです。