読者です 読者をやめる 読者になる 読者になる

Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

Clojure :: recurが意味分からないという人のための簡単な再帰講座

 この記事は、Clojure Advent Calender 2013 (全部俺) 2日目です。

 定期的にClojureのタイムラインを見ていたりするのですが、どうやら皆が引っかかりやすい部分の一つとして、どうやらrecurという存在があるようです。recurとは、loopと対応して、再帰的な構造を擬似的に作り出すための構文です。例えば、1から100を出力するための関数を、looprecurで書くと、下のような構文になるでしょう。

(defn one-to []
  (loop [x 1]
    (if
    (> x 100) nil
    (do (println x) (recur (+ x 1))))))

 さて、このように強力なループを生成するlooprecurの構文なのですが、しかしどうやらClojureのタイムラインを見ていると、このrecurについて躓いてしまう人が多い印象を感じます。

 そこで、recur(doc recur)してみるとわかるのですが、だいたい下のようなことが書かれたりします。

Evaluates the exprs in order, then, in parallel, rebinds
the bindings of the recursion point to the values of the exprs.

 recurの文字は、実はrecursion、英語で直すならば「回帰・再帰」という意味であったりします。例えば、末尾再帰を英語に直した場合、tail recursionと書いたりします。つまり、この構文は「再帰」と非常に密接な関係にあると言えるでしょう。

 さて、この構文が、元々どのような経緯によってでてきたのか、という話に関しては、Clojureの公式ドキュメントを見るのがはやいでしょう。元の英文に関しては、上のリンクを読んでもらうとして、ここではざっとした訳をしたいと思います。

変更されるローカル変数が存在しないときに、ループやイテレーションをするとき、状態の変化をコントロールするためのコードを組み立てるか、言語に最初から存在している構文を使うかというフォームとは違うフォーム取る必要が有ります。関数型言語においては、ループやイテレーションは再帰的な関数呼び出しから、最適化したり、置き換えたりされます。多くのこのような言語では、関数呼び出しは、末尾の場所においては、スタックを使うのではなく、一定の再帰的なループに置き換わります。しかし、ClojureはJavaの呼び出し変換を使っているので、これができません。なので、同じような末尾再帰最適化を作り出すことができません。その代わり、recurという特別なオペレーターを提供します。これは、一定のスペースを使用する再帰的ループになり、そして、関数の枠組み、あるいは、ループが終わる直前でジャンプします。これは末尾再帰最適化を作り出すわけではないのですが、同じようなエレガントな構造を作りだすことができます。そして、recurは末尾の位置でだけ行えるように要請します。

 どういうことなのでしょうか。

 まず最初に、再帰には二つの種類があることを知ると良いでしょう。そこで、Creative CommonsであるStructure and Interpretation of Computer Programsから、関連する図を引用してみましょう。

f:id:nisemono_san:20131203000619p:plain

 この二つの図を、clojureで書き直すと、下のように書き直すことが出来ます。

(defn factorial [n]
  (if (= n 1)
      n
      (* n (factorial (- n 1)))))
(defn factorial [n]
  (fact-iter 1 1 n))

(defn fact-iter [product counter max-count]
  (if (> counter max-count)
     product
     (fact-iter (* counter product)
                (+ counter 1)
                (max-count))))

 さて、あえてSICPの訳にならって、前者を「線形再帰」、後者を「末尾再帰」とよぶことにしましょう。この二つの違いは、「線形再帰」が、その再帰が終わるまで、計算し続けるのに対して、「末尾再帰」は、そのつど、関数に結果を渡していくという違いがあります。このような、末尾再帰的な構造を、擬似的に最適化するための構文こそが、looprecurなのです。

 ですから、loopは単にそこでループ構造を作るための便利な構文だと思うと、痛い目を見てしまいます。あくまでもrecurが与えるのは、擬似再帰構造です。例えば、次のような関数を定義してみましょう。

(defn bad-loop []
  (loop [x 1]
  (if (< x 100) (recur (+ x 1)) nil)
  (println "Done")))

 これは、エラーになってしまいます。なぜなら、最後に再帰をしていないからです。しかし、下の場合はどうでしょうか。

(defn good-loop []
  (loop [x 1]
     (if (< x 100) (recur (+ x 1)) (println "Done."))))

 これは動きます。厳密に言うと、ifは特別な形式(special form)のためです。基本的には、ifで分岐しなかった場合のリストというのは無視されるためであり、この場合であるならば、xが100未満の場合、(println "Done.")は、とりあえずなかったことになります。

 初歩中の初歩ですが、意外と躓く人が多いように感じたので、拙い解説ではありますが、簡単に説明しました。これでrecurの使い方についてなんとなく理解してもらえれば幸いです。