限定継続を使えばジェネレーターが簡単に実装できます。
シリーズの記事です。
- call/cc でジェネレーターを実装する
- 限定継続でジェネレーターを実装する ← この記事
限定継続
限定継続は範囲を限定した継続です。
この記事では Scheme 処理系として GNU Guile で動作確認しています。限定継続を扱うにはモジュールを読み込む必要があります。
(use-modules (ice-9 control))
簡単な例で継続と挙動を比較します。
継続
> (* 2 (+ 1 (call/cc (lambda (k) (+ 2 (k 5))))))
12
(k 5) で call/cc から 5 が返され、(* 2 (+ 1 5)) が計算されて 12 となります。
限定継続
限定継続では reset で範囲を限定して、その中で shift によって継続を取り出します。ラムダ式は不要なため、shift だけで call/cc とラムダ式に対応します。継続で呼び出した計算は reset まで到達すると呼び出し元に返ります。
> (reset (* 2 (+ 1 (shift k (+ 2 (k 5))))))
14
(k 5) で shift から 5 が返され、(* 2 (+ 1 5)) が計算されて 12 となる所までは同じです。
1 (reset (* 2 (+ 1 (shift k (+ 2 (k 5))))))
2 (reset (* 2 (+ 1 5)))
3 (reset (* 2 6))
4 (reset 12)
12 が reset に渡ると (k 5) の戻り値となり、計算が続行されます。
※ call/cc では飛ばされた (+ 2 ...) の計算が行われます。
5 (reset (* 2 (+ 1 (shift k (+ 2 12)))))
6 (reset (* 2 (+ 1 (shift k 14))))
14 が shift に渡ると reset の戻り値となり、計算は完了します。
説明の引用
ここまでの例を踏まえた上で、Wikibooks から説明を引用します。
shift / reset は部分継続（partial continuation, 限定継続 delimited continuation）を使うための構文である。 call/ccにより渡される継続と異なり、続きの計算全てを表す継続ではなく、resetのある途中位置までの継続を表し、終わりまで達したならば継続の呼び出し元へ返る。呼び出し元へ返るという点では部分継続は普通の関数と同じように扱うことができる。
ジェネレーター
限定継続は呼び出し元に返るため、ジェネレーターが簡単に実装できます。
(define (yield x) (shift k (cons x k)))
(define (g) (reset
(yield 1)
(yield 2)
(yield 3)
))
(define (next it) ((cdr it)))
(define it (cons '() g))
(set! it (next it))
(display (car it)) (newline)
(set! it (next it))
(display (car it)) (newline)
(set! it (next it))
(display (car it)) (newline)
1
2
3
shift に (cons x k) が渡ると reset から抜けて呼び出し元に返されます。
※ reset と shift は実行時のフローで関連付けられるため、コード上でネストさせておく必要はありません。
比較
前回の記事での継続による実装では、呼び出し元に戻るため next でも継続を取り出して cc-out を更新する必要がありました。
(define (g cc-out)
(define (yield x) (set! cc-out (call/cc (lambda (cc-in) (cc-out (cons x cc-in))))))
(yield 1)
(yield 2)
(yield 3)
)
(define (next it) (call/cc (cdr it)))
限定継続では呼び出し元に戻ることができるため継続を保存しておく必要がありません。yield は外部の変数を参照しないためジェネレーターの外で定義できます。next は継続の取り出しが不要なため (cdr it) を直接呼び出せば済みます。
(define (yield x) (shift k (cons x k)))
(define (g) (reset
(yield 1)
(yield 2)
(yield 3)
))
(define (next it) ((cdr it)))
このようにジェネレーターは限定継続のシンプルな応用となります。