星にゃーんのブログ

ほとんど無害。

Scheme 継続

もうひとつのScheme入門 16. 継続を写経した。

「継続」は、計算において必ず存在する。 しかし、明示的に扱われることが少ない。

例えば、

(* 3 (+ 1 2))

のような計算があるとき、(+ 1 2)を評価した後の残りの計算は、(* 3 _)である。 この部分を継続と呼ぶ。

継続渡しスタイル

継続は、第一級関数をもつ言語であれば、CPS(継続渡しスタイル)によってあつかうことができる。

これは、関数が値を返す部分に、計算結果をどんな関数に渡すのかを引数で指定する方法。

(define (id x)
  x)

(define (k+ a b k)
  (k (+ a b)))

(define (k* a b k)
  (k (* a b)))

この関数群を使って、先ほど示したコードを書くとこうなる。

(k+ 1 2 (lambda (x) (k* 3 x id)))

関数適用の順番が入れ替わっている。

再帰関数のCPS

(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

(define (kfact n k)
  (if (= n 1)
      (k 1)
      (kfact (- n 1) (lambda (x) (k (* n x))))))

一つ目が通常の階乗。二つ目がCPS階乗。 CPS版は末尾再帰になっている。 このように、再帰関数をCPS化することで、末尾再帰に変換できる。 Schemeは末尾再帰をループに最適化するので、とても嬉しい。

call/cc

call/ccを使うと、継続によるジャンプができる。

> (* 3 (call/cc (lambda (k) (+ 1 2))))
9 ;継続が呼ばれていないので、普通の式と同じ
> (* 3 (call/cc (lambda (k) (+ 1 (k 2)))))
6 ;継続kが呼ばれ、(* 3 2)を計算し、トップレベルに6が返る
(define cc)
(* 3 (call/cc (lambda (k)
                 (set! cc k)
                 (+ 1 2))))

> (+ 100 (cc 3))
9
> (+ 100 (cc 100))
300

継続を呼ぶと、その後の式を無視してトップレベルに戻る。

具体的な使用方法は後でまとめる。