Recursion in JVM

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

プログラミングClojure 第2版

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

1. 素朴な再帰

(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のスタックを使い尽くす。

2. 末尾再帰

(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する言語は存在しないようだ。

3. recurを使った自己再帰

(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でも結果が返ってくる。

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

4. 遅延シーケンス

(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

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