最近、Clojureに入門しようとしていて、『プログラミングClojure』を読んでいる。

関数型言語では再帰をよく使うことになるはずだが、JVMで動く言語をほとんど書いたことがない(Javaのテストコードを書いたことがある程度)ので、JVMがスタックをどう扱うのかよくわかっていない。いくつかフィボナッチ数を求める例を挙げる。

(defn stack-consuming-fibo [n]
(cond
(= n 0) 0
(= n 1) 1
:else (+ (stack-consuming-fibo (- n 1))
(stack-consuming-fibo (- n 2)))))

予想どおりだが、nが大きくなるとStackOverflowErrorになる。

sample.core=> (stack-consuming-fibo 10000)StackOverflowError clojure.lang.Numbers$LongOps.combine (Numbers.java:419)

Clojureの関数呼び出しは常にスタックフレームを作りスタック領域を使うので、スタック消費型と呼ばれる。スタックフレームはnに対し指数的に増加するので、nが大きいとJVMのスタックを使い尽くす。

(defn tail-fibo [n]
(letfn [(fib
[current next n]
(if (zero? n)
current
(fib next (+ current next) (dec n))))]
(fib 0N 1N n)))

良さそうに見えるが、JVMはtail-call optimizationしないので、nが大きくなるとStackOverflowErrorになる。

sample.core=> (tail-fibo 10000)StackOverflowError   clojure.lang.BigInt.add (BigInt.java:148)

『プログラミングClojure』の第2版によると、今のところ、JVM上で動くプログラミング言語で、自動でtail-call optimizationする言語は存在しないようだ。

(defn recur-fibo [n]
(letfn [(fib
[current next n]
(if (zero? n)
current
(recur next (+ current next) (dec n))))]
(fib 0N 1N n)))

詳細は理解できていないが、明示的にrecurと書けばJVMが最適化し、先程までStackOverflowErrorが出ていた大きさのnでも結果が返ってくる。

複数のフィボナッチ数を求めたい場合、計算途中をキャッシュしておきたくなる。値をいくつキャッシュするか、あるいはどの値をキャッシュするかは関数を実装する側ではなく、呼び出し側に責務があるべきである。呼び出し側が必要な範囲を取得する例を遅延シーケンスで実践してみる。

(defn lazy-seq-fibo
([]
(concat [0 1] (lazy-seq-fibo 0N 1N)))
([a b]
(let [n (+ a b)]
(lazy-seq
(cons n (lazy-seq-fibo b n))))))

lazy-seqマクロで遅延シーケンスが生成させる。この関数が呼ばれて初めて(cons n (lazy-seq-fibo b n))が実行されるという意味である。下の例は10番目のフィボナッチ数を求めたものである。

sample.core=> (nth (lazy-seq-fibo) 10)
55N

遅延シーケンスもスタックやヒープを消費しない訳ではないが、シーケンス全体の長さに比例したリソースを消費することはないという点が重要である。

Software engineer