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

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

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

2014.08.20 : 一部修正