loop/recurで相互再帰(Clojure)

 Clojureのtrampolineを使った相互再帰の例として, even/odd関数が有りますが, しかし,  簡単な相互再帰なら, trampolineよりloop-recur内に自分でディスパッチさせる処理を書いたほうがわかりやすいような気がします.

 例えば, even/oddならこんな感じ.

(defn even-odd? [even-or-odd n]
  (loop [status even-or-odd n n]
    (cond
     (= status :even)
     (if (= n 0)
       true
       (recur :odd (dec n)))
     (= status :odd)
     (if (= n 0)
       false
       (recur :even (dec n))))))

こう書いておいて,

user> (even-odd? :odd 9)

と呼び出すとか. cond節が冗長になりますが, declare, defnと書いて, 無名関数で囲って, trampolineで待ち受けさせるのと大差ないかなと....思ったのですが, 比べてみると, やっぱり読みにくい. trampoline版のほうがシンプルですね.

(declare my-odd?)

(defn my-even? [n]
  (if (= n 0)
    true
    #(my-odd? (dec n))))

(defn my-odd? [n]
  (if (= n 0)
    false
    #(my-even? (dec n))))

適当に測ってみると少し早くなった程度.

user> (time (trampoline my-even? 10000000))
"Elapsed time: 2127.23756 msecs"
true
user> (time (even-odd? :even 10000000))
"Elapsed time: 1781.678006 msecs"
true

しかし, 相互再帰を書く時の選択肢としてはありかなと思ったりしてます.

trampolineでバックトラックパーサを作る

shift/resetと、(fnで囲った)closure/trampolineは、なんとなく似てます。

trampoline

trampolineは、末尾再帰をエミュレートする為の関数です。

clojureは、末尾再帰ができないので、loop-recur特殊形式で
ループを記述するのですが、これは、ほとんどJavaやCのwhile文か、
それ以下の表現力しかありません。
なので、相互再帰とか、複雑な末尾再帰は表現できません。

その代替手段としてtrampolineという関数があります。
以下のように使います。

1. まず、普通に末尾呼出形式で関数型言語風のプログラムを書きます。
2. 次に、その末尾呼出を全部無名関数で囲ってクロージャにします。
3. トランポリン関数の上で、相互再帰の関数を呼び出します。

トランポリンは、与えられた関数とその引数を起動して、関数を実行します。
関数の実行結果として、

1. クロージャが戻ってきたら、(それは、末尾呼出なので)そのクロージャを再び実行。
2. それ以外の値が戻ってきたら、終了。

これで、スタックを消費せずに、末尾再帰が、特に相互再帰のような
複雑な末尾再帰も実現できるという事で、非常にめでたいのですが。

この末尾呼出で戻ってきたクロージャってもしかして、
trampolineが終了するまでの残りの計算　 ... .... (限定)継続!?

というわけで、概念的に、というか理論的にどうなのかはわかりませんが、
直感的には、かなり似たものだという印象です。

trampolineがresetに対応していて、
「shiftが呼ぶ限定継続」が、「末尾再帰で送り出されるレキシカルクロージャ」に対応している、
と、考えます。

その証拠というか、例として、shift/resetの得意なバックトラックを
trampolineを使って簡単に書くことができます。
その例として、パーサ(構文解析器)を書きました。

バックトラックパーサ

バックトラックとは、その名の通り(?)後戻りをする機構のことです。構文解析とは、結局のところ、文法法則を(終端)記号列に対してうまく当てはまるかどうかを試すアルゴリズムに過ぎません。なので、当てはまりそうだったら、適当に当てはめてみて、ダメだったら、元に戻すというやり方でもOKなのです。(もちろん、それ相応の計算量がかかりますが。)
なので、適当にパターンマッチを繰り返して、辻褄があわなくなったらその時点まで戻るようなパーサを書くことができます。それがバックトラックパーサです。
で、今回のこの末尾呼出のクロージャを限定継続に見立てて、パターンマッチに失敗したら、この限定継続もどきを呼び出すことでバックトラックを実現します。

次の文法をParseするプログラムにしました。

E → T '+' E
T → F '*' T
E → T
T → F
F → num

backtracparser.clj


実行結果と利用例は、こんな感じ。
ちゃんと構文解析しています。
parse-with-stack-traceで、バックトラックしていることも確認出来ます。

user=> (load-file "backtrackparser.clj")
#'user/parse-with-stack-trace
user=> (parse [[:num] [:+] [:num] [:*] [:num] [:$]])
[:E :+ [:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:T [:F [:num]]]]
user=> (parse-with-stack-trace [[:num] [:+] [:num] [:*] [:num] [:$]])
[]
([:num])
([:F [:num]])
... ...
([:$] [:E [:T [:F [:num]]]] [:*] [:F [:num]] [:+] [:T [:F [:num]]])
back track !!
([:T :* [:T [:F [:num]]] [:F [:num]]] [:+] [:T [:F [:num]]])
([:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:+] [:T [:F [:num]]])
([:E :+ [:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:T [:F [:num]]]])
([:$] [:E :+ [:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:T [:F [:num]]]])
[:E :+ [:E [:T :* [:T [:F [:num]]] [:F [:num]]]] [:T [:F [:num]]]]

うーん、gistとブログの色合いが微妙......

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

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

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