Entropy

新着

Programming Clojure, Third Edition › 怠け者になろう

Properties2
descriptionフィボナッチ数列を単純な再帰、末尾再帰、recur、遅延シーケンスで実装して比べ、シーケンスの現実化を遅らせることと、シーケンスの先頭への参照を保持しないことを学ぶ
tagsbook-chapter, clojure

TL;DR

  • 単純な再帰も末尾再帰も、JVM が末尾呼び出し最適化を行えないので、大きな入力でスタックオーバーフローを起こす。recur を使えばスタックを消費しない。
  • 複数の値が必要なときは、lazy-seq やシーケンスライブラリで遅延シーケンスを返し、必要な範囲の取り出しを呼び出し側に委ねる。
  • 遅延シーケンスは var に束縛せず、シーケンスを返す関数として定義する。先頭への参照を保持すると、不要な要素が GC されない。

内容

再帰的定義

FP は再帰的定義を多用する。再帰的定義は 2 つの部分からなる。

  • 基底: シーケンスのいくつかの要素を明示的に列挙した部分
  • 帰納: シーケンスの残りの要素を、すでに判明している要素を組み合わせて作り出すルール

再帰的定義をコードへ変換する手法

この節のテーマは再帰的定義をコードへと変換することである。これにはいくつか方法がある。

  • 単純な再帰: 関数が自分自身を何らかの方法で呼び出して、帰納のステップを実装するもの
  • 末尾再帰: 関数が自分自身を呼び出すのを、本体の実行パスの末尾の位置に限ったもの。末尾再帰は重要な最適化を可能にする
  • 遅延シーケンス: 直接の再帰を行わず、後で必要になった時点で値を計算するもの

再帰では、正しいアプローチを選ぶのが重要である。誤った方法で実装すると、パフォーマンスが低かったり、スタックオーバーフローやヒープオーバーフローを引き起こしたりする可能性がある。Clojure では、遅延評価が最良のアプローチであることが多い。

フィボナッチ数列によるサンプルコード

上に挙げたすべてのアプローチを、フィボナッチ数列を例に試してみる。フィボナッチ数列は再帰的定義を使えば簡単に書ける。

  • 基底: 0 番目のフィボナッチ数 は 0、1 番目のフィボナッチ数 は 1 である
  • 帰納: のとき、 は である

この定義を使うと、最初の 10 個のフィボナッチ数は次のようになる。

(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

単純な再帰

まずは、単純な再帰を使って実現する。

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

小さな n を与えて、動作を確認する。

(stack-consuming-fibo 9) ; 34

うまく動作しているが、大きな n を与えると問題が起きる。

(stack-consuming-fibo 1000000) ; java.lang.StackOverflowError

再帰により、 に対する 1 回の関数呼び出しは、さらに 2 回の関数呼び出しを引き起こす。JVM レベルでは、これらの呼び出しは Java のメソッドになり、呼び出しごとにスタックフレームというデータ構造がアロケートされる。stack-consuming-fibo は n に比例した深さのスタックフレームを作るので、すぐに JVM のスタックを使い尽くし、StackOverflowError を引き起こす。また、作られるスタックフレームの総数は n に対して指数的に増えるので、スタックオーバーフローを引き起こさなかったとしても、パフォーマンスは著しく低い。

Clojure の関数呼び出しは常にスタックフレームを作り、スタック領域を使っていくので、スタック消費型と呼ばれる。このため、Clojure では stack-consuming-fibo のようなスタックを消費する再帰は絶対に避けるべきである。

末尾再帰

FP では、末尾再帰でスタック消費の問題を解決できる。

末尾再帰関数は再帰的な定義を持つが、再帰呼び出しが関数の末尾に制限されている。この末尾とは、関数の返り値を計算する式を指す。言語処理系は末尾呼び出し最適化（TCO: tail-call optimization）によって、末尾再帰をスタックを消費しない繰り返しに変換できる。

単純な再帰のコードは、stack-consuming-fibo を 2 回呼び出した後で + を呼び出すので、末尾再帰ではない。末尾再帰にするには、帰納を進める上で必要な情報をすべて引数で受け取る関数を定義すればよい。こうすると、再帰の結果を受け取った後で加算する必要がなくなるので、再帰呼び出しを末尾に置ける。

具体的には、次のように定義できる。

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

ここでは letfn マクロを使っている。

(letfn fnspecs & body) ; fnspecs => [(fname [params*] exprs)+]

letfn は let と似ているが、ローカル関数を定義するためのマクロである。letfn で定義された関数は、自分自身や、同じ letfn ブロックで定義されたローカル関数を呼び出せる。定義したローカル関数 fib は、current（現在のフィボナッチ数）、next（次のフィボナッチ数）、n（ステップ数）という 3 つの引数を取る。

この関数は小さな n では動くが、大きな n では動かない。

(tail-fibo 9) ; 34N
 
(tail-fibo 1000000) ; java.lang.StackOverflowError

この原因は JVM にある。Haskell のような関数型言語は簡単に TCO を行えるが、JVM は関数型言語向けには設計されていないので、現状は自動的には行えない。したがって、JVM 上で直接走る言語で、自動的に TCO を行える言語は存在しない。

Clojure はいくつかの代替方法を提供している。

  • recur: 明示的な自己再帰
  • 遅延シーケンス
  • trampoline: 明示的な相互再帰

recur を使った自己再帰

Clojure では、自分自身を末尾で呼び出している関数を、recur を使った明示的な自己再帰として書き直せる。たとえば、末尾再帰のサンプルコードは次のように書き直せる。

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

これで、フィボナッチ数を計算するのにスタックを消費せず、（辛抱強く待ってさえいれば）巨大な n に対しても を返せる。

(recur-fibo 9) ; 34N
(recur-fibo 1000000) ; 195 ... 208,982桁省略 ... 875N

recur-fibo は 1 つのフィボナッチ数を計算したが、次にいくつかのフィボナッチ数が必要なケースを考える。たとえば recur-fibo を何度も呼び出す方法は、結果が次に使われることなく捨てられてしまうので無駄である。結果をその都度キャッシュするとしても、いくつの値を、どの値をキャッシュするかを考える必要がある。しかし、これは関数を実装する側ではなく、呼び出し側に委ねるべきである。

理想的には、シーケンスを使って、必要な値の範囲というものを気にしなくて済む API を提供する。そして呼び出し側は必要な範囲を take と drop で取り出せばよい。これを実現するのが、遅延シーケンスである。

遅延シーケンス

lazy-seq マクロ

遅延シーケンスは lazy-seq マクロで作る。lazy-seq は、必要になったときに初めて body を実行する。そして、後で呼ばれたときのために値をキャッシュする。

(lazy-seq & body)

このマクロを使うと、フィボナッチ数列は次のように定義できる。

(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))))))

引数を取らない本体は、基底となる [0 1] と、2 つの引数を渡して残りの値を計算する部分とをくっつけて返す。

([] (concat [0 1] (lazy-seq-fibo 0N 1N)))

2 つの引数を取る本体は、次のフィボナッチ数 n を計算し、その値と数列の残りとを cons する。

(let [n (+ a b)]
	(lazy-seq
		(cons n (lazy-seq-fibo b n))))

重要なのは、lazy-seq で本体の実行を遅延評価している箇所である。これがないと、本体内の lazy-seq-fibo の呼び出しがすぐに行われ、スタックオーバーフローを起こすまで再帰する。

小さな値を入れて、動作を確認する。

(take 10 (lazy-seq-fibo))
; (0 1 1N 2N 3N 5N 8N 13N 21N 34N)

大きな値も入れて確認してみる。

(rem (nth (lazy-seq-fibo) 1000000) 1000) ; 875N

シーケンスライブラリを使う

lazy-seq-fibo は、「要素数が可変または巨大なシーケンスを作るときは遅延評価を使う」という 3 つ目のガイドラインに従っている。

ただし、シーケンスライブラリを使えば、直接 lazy-seq を呼び出さなくても済む場合もある。たとえば、iterate 関数を使って、次のようにフィボナッチ数列を実装できる。

(take 5 (iterate (fn [[a b]] [b (+ a b)]) [0 1]))
; ([0 1] [1 1] [1 2] [2 3] [3 5])
 
(defn fibo []
  (map first (iterate (fn [[a b]] [b (+ a b)]) [0N 1N])))

map と iterate はそれぞれ遅延シーケンスを返すので、fibo が返すのも遅延シーケンスである。

遅延シーケンスも、スタックとヒープをまったく消費しないわけではない。しかし重要なのは、シーケンスの全体の長さに比例したリソースを消費しない点である。どのくらいのリソースを使うかは、シーケンスを使う側が選ぶことである。

シーケンスの現実化

現実化はできる限り遅らせる

遅延シーケンスは現実化されるときに、実際にメモリ上にインスタンス化される部分だけがリソースを消費する。Clojure は本当に必要となるまで、できる限りシーケンスの現実化を遅らせようとしている。

たとえば take は遅延シーケンスを返すので、それ自身は現実化をまったく行わない。

(def lots-of-fibs (take 100000000 (fibo)))
; #'user/lots-of-fibs

実際に値を必要とする関数を呼び出したときに初めて、Clojure はそれらの値を計算する。その場合でも、必要な値しか計算されない。

(nth lots-of-fibs 100) ; 354224848179261915075N

REPL は遅延評価しない

ただし、REPL は遅延評価しない。REPL が使っている print ルーチンは、デフォルトではコレクションの要素をすべて表示しようとする。そのため、先ほどは lots-of-fibs を定義して、REPL に表示させないようにした。

; 実行してはいけない
(take 100000000 (fibo))

REPL で遅延シーケンスを試すための Tips

遅延シーケンスを試すときは、*print-length* の値をセットして、出力する要素数に制限をかけておくとよい。

(set! *print-length* 10) ; 10

これを実行すると、10 個より多くの要素を持つシーケンスは最初の 10 個だけが表示され、残りは … で表示されるようになる。

(take 100000000 (fibo))
; (0N 1N 1N 2N 3N 5N 8N 13N 21N 34N ...)
 
(fibo)
; (0N 1N 1N 2N 3N 5N 8N 13N 21N 34N ...)

1 億個のフィボナッチ数だろうが、すべてのフィボナッチ数だろうが実行できる。

頭を抱えない — シーケンスの先頭への参照を保持しない

結論: 遅延シーケンスを作るときは var に束縛するのではなく、遅延シーケンスを返す関数として定義する。

遅延評価で気をつけるべきは、シーケンスの中のもう使わない部分への参照を保持してしまうケースである。これが一番起こりやすい典型的なケースは、シーケンスの先頭への参照を保持してしまうケースである。前節でいくつかの方法でフィボナッチ数を計算したときも、これを避けるために、直接シーケンスを計算するのではなく、いずれもシーケンスを返す関数として実装した。

シーケンスを直接定義して、トップレベルの var に束縛することもできなくはない。

(def head-fibo (lazy-cat [0N 1N] (map + head-fibo (rest head-fibo))))

lazy-cat マクロは concat と似ているが、引数は必要になったときに初めて評価される。この定義は「フィボナッチ数列の各要素」と「フィボナッチ数列を 1 つずらした列の各要素」の和の形で再帰を表現している。

; (concat (0 1) (map + (0 1 ...) (rest (1 ...))))
; (concat (0 1) (map + (0 1 1 ...) (rest (1 1 ...))))
; (concat (0 1) (map + (0 1 1 2 ...) (rest (1 1 2 ...))))
; (concat (0 1) (map + (0 1 1 2 3 ...) (rest (1 1 2 3 ...))))
; (concat (0 1) (map + (0 1 1 2 3 ...) (rest (1 1 2 3 ...))))
; (concat (0 1) (map + (0 1 1 2 3 5 ...) (rest (1 1 2 3 5 ...))))

この定義は小さなフィボナッチ数に対しては動作する。

(take 10 head-fibo) ; (0N 1N 1N 2N 3N 5N 8N 13N 21N 34N)

しかし、大きなフィボナッチ数ではエラーになる。

(nth head-fibo 1000000)
; java.lang.OutOfMemoryError: GC overhead limit exceeded

これはトップレベルの var である head-fibo がシーケンスの先頭部分の参照を保持していることが原因である。これにより、シーケンスの先の方に進んでも、不要なはずの要素が GC されない。一度でも使われたフィボナッチ数は head-fibo から参照されているので、ずっとキャッシュされ続けることになる。

通過した部分をキャッシュしておく必要がないならば、シーケンスの先頭への参照を持ち続けてはならない。head-fibo の例が示すように、遅延シーケンスを作るときは直接 var に束縛するのではなく、作られたシーケンスを返す関数とするべきである。

キーワード

自分の理解

ある種の再帰について自動で TCO を行う言語を実装することは可能だが、すべての再帰について行うのは不可能である。そこで Clojure は、プログラマが明示的に再帰を示す方法を選んだ。もし JVM で汎用的な TCO が使えるようになれば、Clojure もそれをサポートする可能性がある。

グラフビュー

バックリンク