shift/reset

　限定継続という概念(制御構文)があって、これを使うと、バックトラックとかが簡単に実装できるのですが、その動作がやたらややこしい、という話のメモです。

限定継続では、shiftというオペレータとresetというオペレータを用いて、継続を扱います。shiftというオペレータは、継続の呼び出しです(Schemeのcall/ccのようなものです)。それに対して、resetは、その範囲を限定します。
例えば、以下のように使えます。

(+ 1 (reset (+ 10 (shift c (c 100)))))
:;==> 111

ここでは、resetが継続の取得する範囲を区切って、shiftのcに渡します。ここで渡される継続は、(lambda (x) (+ 10 x))の処理です。このラムダ式は、resetが用意してくれるようなイメージです。shiftは、resetで渡された限定継続(= 10を足すという処理)を受け取り、この継続をcにバインドします。call/ccで、継続をバインドするのと同じです。次にバインドされたcに対して、引数100を与えて評価するので、このshiftは、110を返します。その後、resetの外側にジャンプし、最後に1が足されて111と評価されます。
次に別の例です。

(+ 1 (reset (+ 10 (shift c 100))))
;;==> 101

ここでは、resetが継続の取得する範囲を区切って、shiftのcに渡します。 ここまでは、前の動作と同じです。今回も同じように、cに継続をバインドしているのですが、今回は、cを呼び出していないので、このcが切り捨てられます。つまり、10を足すという残りの処理がなくなります。shiftにより、resetのところまで、ジャンプし、結果、shiftが返す値100に1がたされて101と評価されます。
shift/resetが一組の場合は難しくないかと思われますが、shiftが2つ出てきたりすると一気にややこしくなります。
このような例です。

(+ 1 (reset (+ 10 (shift c (c 100)) (shift c 1000))))
;;==> 1001
(+ 1 (reset (+ 10 (shift c (c 100)) (shift c (c 1000)))))
;;==> 1111

上記の例の上の式では、(shift c 1000)が、ばっさりそれまでの式を切り捨てた上で1000と評価されるので、1001が帰ってきます。問題は、下の式ですが、継続渡しスタイルみたいになっているのが面白いですね。

こういうのって、手続き型言語風に書くとわかりやすかったりしますよね。なので、beginを使って表現してみました。Wikipediaの記事と似ていますが、そちらよりは若干原始的です。それぞれの動作とスコープが途切れる前後に数字を割り振っています。
1を出力 → reset → 2を出力 → shift → 3を出力 → 継続呼び出し → 4を出力 → shift終わり → 5を出力 → reset終わり → 6を出力というコードです。

(begin
    (display "1. before reset\n")
    (reset
     (begin
       (display "2. before shift\n")
       (shift cont
              (begin
                (display "3. before call-cont\n")
                (cont 0)
                (display "4. after call-cont\n")))
       (display "5. after shift\n")))
     (display "6. after reset\n"))

上記に対して、以下のような結果を出力します。

1. before reset
2. before shift
3. before call-cont
5. after shift
4. after call-cont
6. after reset

4と5が入れ替わっている以外は、順番どおりに実行されていることが確認できるかと思います。では、なぜ入れ替わったのかという点ですが、上記のプログラムにおいて継続が呼ばれたポイントに原因があります。3と4の間に継続が呼ばれています。なので、5が3と4の間に来ます。ただし、限定継続なので、resetで取得された範囲外にある6は、継続として呼ばれません。

ところで、限定継続は、ネイティブに固有の言語に実装されていません。shift/resetを文法として実装している言語なんてあるんでしょうか？　じゃあ使われてないじゃん、って突っ込まれたのですが、まあ、おそらくその通りかもしれません。ただし、SchemeでマクロとCall/cc(プリミティブの継続)を使えば、shift/resetを実装できるみたいです。『Final Shift for Call/cc: Direct Implementation of Shift and Reset』って、論文にその方法が書いてあります。
こんな感じです。

(define-syntax reset
  (syntax-rules ()
    ((reset ?e) (*reset (lambda () ?e)))))

(define-syntax shift
  (syntax-rules ()
    ((shift ?k ?e) (*shift (lambda (?k) ?e)))))

(define (*meta-continuation* v)
  (error "You forgot the top-level reset..."))

(define (*abort thunk)
  (let ((v (thunk)))
    (*meta-continuation* v)))

(define (*reset thunk)
  (let ((mc *meta-continuation*))
    (call-with-current-continuation
     (lambda (k)
       (begin
         (set! *meta-continuation*
               (lambda (v)
                 (set! *meta-continuation* mc)
                 (k v)))
         (*abort thunk))))))

(define (*shift f)
  (call-with-current-continuation
   (lambda (k)
     (*abort (lambda ()
               (f (lambda (v)
                    (reset (k v)))))))))

以上のコードを定義すると、Racket上でshift/resetの構文が使えるようになります。

上記のコードは、call/ccが多用されてて、読みにくいですが、resetとshiftの実際の使用例に照らし合わせて考えると読みやすくなります。例えば、shiftとresetのマクロですが、それぞれ、引数として渡されている処理をlambda式として囲い、関数形式の*shiftと*resetに渡しているだけです。

まず、*resetは、はじめに(普通の)継続が呼ばれています。ここで取得される継続はresetで囲った処理以降の計算で、それをkで表しています。そして、広域変数*meta-continuation*にresetの範囲が終わった後の処理を記述をset!しています。その処理とは、resetが再帰的に呼ばれることを想定した*meta-continuation*の値のリセットと、残りの計算を実行するようなlambda式です。set!の処理が終わった後、引数として与えられた限定継続の部分を実行します。

実際に実行するのが*abortの役割です。引数なし関数thunkを実行し、結果の値を*meta-continuation*関数に渡します。*meta-continuation*は、resetの後始末をしています。(ここで、let文が使われていて、一瞬、(*meta-continuation* (thunk))でもいいような気がしたのですが、気のせいでした。)

最後に*shiftですが、この*shiftの引数fは、(shift c 100)でいうところの、(lambda (c) 100)です。限定継続をバインドしたlambda式になります。つまり、(f (lambda (v) (reset (k v))))で与えられている、(lambda (v) (reset (k v)))が、限定継続だということです。そして(k v)の呼び出しにより、現在の継続を捨てるようです。この時、(k v)をresetで囲うことでこの時点の継続を*meta-continuation*の確保している継続に対して、上書きします。

数十行程度のコードだったのに、やけに重たかったのは気のせいでしょうか。これを使って実際にどんなバックトラックのコードが書けるのかは、また別の記事に書きます。

Clojureは継続渡しスタイルができない

　Clojureは、末尾再帰最適化ができない言語だというのは知っていましたが、まさか、継続渡しスタイルもダメだったとは。しかし、考えてみれば当然のことで、継続渡しスタイル自体が、末尾再帰最適化を期待している書き方なんですよね。

以下が、証拠のコードです。

(defn +& [a b cont]
  (cont (+ a b)))

(defn empty?& [a cont]
  (cont (empty? a)))

(defn cps-sum [sum ls cont]
  (empty?&
   ls
   (fn[empty]
     (if empty
       (cont sum)
       (+& sum (first ls)
           (fn[sum]
             (cps-sum sum (rest ls) cont)))))))

一見なんの変哲もない継続渡しスタイルのコードですが、スタックが消費されっぱなしになっているのは一目瞭然ですね。ちなみに、このコードは、wikipediaの記事を参考にしました。cps-sumは、引数に与えられたリストの合計値を計算するという、くだらない関数です。

上記のプログラムを実行すると、

user=> (cps-sum 0 (range 0 100) #(println %))
4950
nil
user=> (cps-sum 0 (range 0 10000) #(println %))
java.lang.StackOverflowError (NO_SOURCE_FILE:0)
user=>

こうなります。0～100の和を足している時は、正しい値を返しているのですが、0～1万の値の和を計算しようとすると、スタックオーバーフローになります。

このままでは、面白くないので、これを解決するようなアプローチを考えてみました。こんな感じになりました。

(defn +& [a b cont]
  #(cont (+ a b)))

(defn empty?& [a cont]
  #(cont (empty? a)))

(defn cps-sum [sum ls cont]
  (fn[] (empty?&
   ls
   (fn[empty]
     (fn[] (if empty
       (fn[] (cont sum))
       (fn[] (+& sum (first ls)
           (fn[sum]
             (fn[] (cps-sum sum (rest ls) cont)))))))))))

これを実行すると、

user=> (trampoline (fn[] (cps-sum 0 (range 0 10000) #(println %))))
49995000
nil

こうなります。ちゃんと動いてますね。

末尾呼び出しを全部無名関数で囲って、クロージャにして、トランポリンに送り込むような形にしただけです。オチは特にありません。