Racketの継続プリミティヴ

Racketの継続がどうなっているのか，Racketのドキュメントを読みつつ分かったことをまとめる．
(注意: この記事は継続の解説ではない．寧ろ継続自体は大体分かっている前提で進める)
まず，主な継続プリミティヴについて簡単に説明する．次に，組み合わせたときの動作を例を出しつつ示す．さらに，これらの継続プリミティヴを使って shift / reset や他の演算子が実装できることを確認する．

Racketの主な継続プリミティヴ

(call-with-continuation-prompt proc [prompt-tag handler] arg ...)

略称 call/prompt

継続に区切り(継続プロンプト)を付けて proc を呼ぶ．区切られた継続の部分を継続フレームと呼ぶ(多分)．継続プロンプトは prompt-tag で識別される．

reset はこれのラッパマクロである．

handler は，後述の abort/cc によってこの call/prompt 呼び出しへ脱出してきた時に呼び出される．handler には abort/cc に渡した残りの引数が渡される．handler のデフォルト値は，(lambda (abort-thunk) (call-with-continuation-prompt abort-thunk prompt-tag #f)) である．

残りの引数は単に proc に渡される．

(abort-current-continuation prompt-tag v ...)

略称 abort/cc

現在の継続を破棄する．破棄されるのは，prompt-tag に対応する直近の継続プロンプトまでである．残りの引数は call/prompt のハンドラへと渡される．

(make-continuation-prompt-tag [sym])

新しいプロンプトタグを作る．

(default-continuation-prompt-tag)

プロンプトタグを指定しない時に使われるデフォルトプロンプトタグを得る．

(call-with-current-continuation proc [prompt-tag])

略称 call/cc

直近の継続プロンプトまでの継続を取り出す．この継続を起動すると現在の継続の一部を破棄する: 起動しようとする継続と現在の継続で継続フレームを共有している場合は，そのような最初の継続フレームまでが破棄される．さもなくば，直近の継続プロンプトまでの継続が破棄される．

(call-with-composable-continuation proc [prompt-tag])

略称 call/comp

直近の継続プロンプトまでの継続を取り出す．この継続を起動しても現在の継続は破棄されない．

(continuation-prompt-available? prompt-tag [cont])

((省略時は)現在の)継続において prompt-tag で識別される継続プロンプトが有効なら #t ，さもなくば #f を返す．

(dynamic-wind before body after)

基本的にR5RSのと同じだが，継続プロンプトによって継続を区切り，切り取ることができるので，ちょっと様子が異なる．dynamic-wind による動的ハンドラは，継続フレームにくっついている(多分)ので，継続プロンプトによって区切られ，call/cc 等で捕捉される継続に含まれない継続フレームに相当する部分の動的ハンドラは保存されない．

Racketの継続プリミティヴの相互作用

call/prompt + call/comp

(cons 'a (reset (cons 'b (call/comp (lambda (k) (cons 'c (k '()))))))) ; => (a b c b)

call/comp の呼び出しから reset (即ち call/prompt) に戻るまでの継続に k が束縛される．

call/prompt + call/cc

call/comp と同様に call/cc の呼び出しから reset に戻るまでの継続を捕捉するのだけど，この継続は起動したときに現在の継続の一部を破棄する性質を持つ．

(cons 'a (reset (cons 'b (call/cc (lambda (k) (cons 'c (k '()))))))) ; => (a b)

k を起動すると，まず現在の継続のうち reset までが破棄される．つまり (cons 'b ... (cons 'c <>) ...) の部分が破棄される．そして (cons 'a (reset <>)) の部分は残る．次に k に保存されていた継続を復元し，継続は (cons 'a (reset (cons 'b <>))) となる．
この場合は，継続フレームが共有されているので，そのような最初の継続フレームまでが破棄されるパターンである．
以下のように，継続の起動を別の継続フレームにしても，根元の継続フレームが共有されているので同じ結果になる．

(cons 'a (reset (cons 'b (call/cc (lambda (k) (cons 'c (reset (k '())))))))) ; => (a b)

次の例は，継続フレームを共有していないパターン．

(let ((k #f))
  (cons 'a (reset (cons 'b (call/cc (lambda (k1) (set! k k1) '())))))
  (cons 'c (reset (cons 'd (k '()))))) ; => (c b)

k には (cons 'b <>) の部分しか含まれていないので，この例は継続フレームを共有していないパターンになる．k 起動時の継続からは (cons 'd <>) の部分だけが破棄され，k に保存されている (cons 'b <>) に挿げ替わることになる．

call/prompt + dynamic-wind + x の準備

簡単のために

(define d displayln)
(define (d$ x) (lambda () (d x)))
(define (%dw x thunk) (dynamic-wind (d$ `(,x before)) thunk (d$ `(,x after))))
(define-syntax dw (syntax-rules () ((_ x body ...) (%dw x (lambda () body ...)))))

と定義しておく．
出力例

(dw 0 (d 'body))
;; (0 before)
;; body
;; (0 after)

(d (let/cc return (dw 0 (return 42))))
;; (0 before)
;; (0 after)
;; 42

call/prompt + dynamic-wind + abort/cc

call/prompt のデフォルトのハンドラがサンクを受け取るようになっているのは，(多分) shift 等の限定継続演算子を実装する時に都合がいいから．shift の「脱出してから本体を実行する」という流れが，abort/cc に本体を包んだサンクを渡すことで実現できる．

(reset (dw 0 (abort (d 'foo))))
;; (0 before)
;; foo
;; (0 after)

(reset (dw 0 (abort/cc (default-continuation-prompt-tag)
                       (lambda ()
                         (d 'foo)))))
;; (0 before)
;; (0 after)
;; foo

abort/cc に渡されるサンクは動的環境を巻き戻した後に呼び出されることになる．
abort は

(define (abort . args)
  (abort/cc (default-continuation-prompt-tag)
            (lambda ()
              (apply values args))))

と定義できる．

call/prompt + dynamic-wind + call/comp or call/cc

(let ((k #f))
  (dw 0 (reset (d (call/comp (lambda (k1) (set! k k1) 'a)))))
  (dw 1 (k 'b)))
;; (0 before)
;; a
;; (0 after)
;; (1 before)
;; b
;; (1 after)

継続 k に保存される継続フレームには (dw 0 ...) の呼び出しでインストールされた動的ハンドラ(以下 dw0 と呼ぶ)は含まれていない．間で reset によって区切られているからである．よって k は，dw0 の内側で捕捉されたにもかかわらず，呼び出しても dw0 は呼び出されない．
また call/comp によって捕捉された継続の呼び出し時には脱出を伴わない(=現在の継続は破棄されない)ため，(1 after) は k の呼び出しから返ってきた後で出力される．

(let ((k #f))
  (dw 0 (reset (d (call/cc (lambda (k1) (set! k k1) 'a)))))
  (reset (dw 1 (k 'b))))
;; (0 before)
;; a
;; (0 after)
;; (1 before)
;; (1 after)
;; b

一方 call/cc で捕捉した継続では，呼び出し時に脱出を伴う(=現在の継続が破棄される)ので，そのタイミングでafter thunkが実行される．

タグ付き限定継続

プロンプトタグを指定した場合，そのプロンプトタグによって識別される継続プロンプト以外の継続プロンプトは存在しないかのように扱われる(はず．でないと未知の継続プロンプトに干渉されることになるし，それを防ぐためのタグだよね)．
以下，

(define t1 (make-continuation-prompt-tag 't1))
(define t2 (make-continuation-prompt-tag 't2))

と定義しておいて，

(reset-at t1 (cons 'a (reset-at t2 (cons 'b (call/comp (lambda (k) (k '()))
                                                       t1))))) ; => (a b a b)
(reset-at t1 (cons 'a (reset-at t2 (cons 'b (call/comp (lambda (k) (k '()))
                                                       t2))))) ; => (a b b)

とすると，タグに対応する継続プロンプトまでの継続が捕捉される．

(let ((k #f))
  (reset-at t1 (cons 'a (reset-at t2 (cons 'b (call/cc (lambda (k1) (set! k k1) '())
                                                       t1)))))
  (reset-at t1 (cons 'c (reset-at t2 (cons 'd (k '())))))) ; => (a b)
(let ((k #f))
  (reset-at t1 (cons 'a (reset-at t2 (cons 'b (call/cc (lambda (k1) (set! k k1) '())
                                                       t2)))))
  (reset-at t1 (cons 'c (reset-at t2 (cons 'd (k '())))))) ; => (c b)

call/cc で捕捉した継続を起動したときも同様で，どの継続プロンプトまでの継続を破棄するかはタグで識別される．

dynamic-wind は(恐らく)継続フレームに関連付けられるもので，タグの識別はない．

限定継続演算子を使って他の限定継続演算子を実装する

reset-at + call/cc で call/prompt + abort/cc

(define *current-prompt-alist* (make-parameter '()))

(define (abort/cc tag . args)
  (apply (cdr (assoc tag (*current-prompt-alist*))) args))

(define call/prompt
  (case-lambda
   ((proc tag handler . args)
    (let* ((tag (or tag (default-continuation-prompt-tag)))
           (handler (or handler
                        (lambda (thunk)
                          (call/prompt thunk tag #f)))))
      (reset-at tag
        (call/cc
          (lambda (return)
            (handler
             (call/cc
               (lambda (abort)
                 (parameterize ((*current-prompt-alist*
                                 (cons (cons tag abort) (*current-prompt-alist*))))
                   (return (apply proc args))))
               tag)))
          tag))))
   ((proc tag)
    (call/prompt proc tag #f))
   ((proc)
    (call/prompt proc #f #f))))

call/cc と継続プロンプトを設置するだけの reset-at で，ハンドラ機能のついた call/prompt と abort/cc が実装できた(はず)．ついでに1引数の continuation-prompt-available? もすぐに実装できると思う．call/cc の取り出す継続はその call/cc 自体の継続と同じだけど，隙の生じぬ二段構えで call/prompt のように普通にリターンしてくるのと脱出してくるのを区別できる．

parameterize の所これでいいのかちょっと不安だけど実は大丈夫…？

call/comp + abort/cc で call/cc

(define call/cc
  (case-lambda
   ((proc tag)
    (call/comp
     (lambda (k)
       (define call/cc-tag (make-continuation-prompt-tag 'call/cc))
       (reset-at call/cc-tag
         (proc
          (lambda args
            (if (continuation-prompt-available? call/cc-tag)
                (abort/cc call/cc-tag
                          (lambda ()
                            (apply values args)))
                (abort/cc tag
                          (lambda ()
                            (apply k args))))))))
     tag))
   ((proc)
    (call/cc proc (default-continuation-prompt-tag)))))

call/cc で捕捉された継続を起動すると，その継続に入る前に脱出する．継続の中身自体は call/comp と同じはず．abort/cc を使うと丁度トランポリンできるので，そこで call/comp で捉えた継続を呼び出すようにすればいいみたい．
起動する継続と現在の継続で継続フレームを共有している場合，つまりその call/cc の動的寿命の中にいるときは，その call/cc 呼び出しまで脱出する必要がある．ある継続フレームの動的寿命の中にいるかどうかは，reset-at と continuation-prompt-available? で判定できる．そして call/cc-tag を作っておいて一先ずそれで脱出する．でその後再び abort/cc を使って(継続フレームを共有していない場合と同様に) (abort/cc tag (lambda () (apply k args))) してもいいんだけど，ここで破棄しようとしている継続は k と同じなので，ここは単に (apply values args) でいい．

call/prompt + call/comp + abort/cc で shift

(define (call-with-shift proc)
  (call/comp
   (lambda (k)
     (abort/cc (default-continuation-prompt-tag)
               (lambda ()
                 (proc (lambda args (reset (apply k args)))))))))

(define-syntax shift
  (syntax-rules ()
    ((_ k e ...)
     (call-with-shift (lambda (k) e ...)))))

shift のやることは，「限定継続を捕捉→脱出→限定継続を継続プロンプトで包んで本体に渡す」なので，call/prompt と call/comp と abort/cc があればすぐできる．
多分包みの reset を抜けば control も同様に実装できる．shift0 / reset0 は reset0 側でハンドラがトランポリンするときにプロンプトを再設定しないようにすればいいんじゃないかな．control0 / prompt0 も同様．

考察

call/prompt call/comp abort/cc の三つを基本にして call/cc や shift 等を構成すると考えるのが素直かなと思った．何故なら，継続フレームについて考えるなら call/cc は複合的な演算子ということになるから．

call/cc しか提供しない世界観では，call/cc は単純な単一の操作を行う手続き(を生成する手続き)なんだけど，継続フレームという概念とともに reset を導入すると，call/cc はより細かいいくつかの手続きに分解できる複合的な演算子に見えるようになる．
(4/8 追記等)