---
title: Clojureで相互再帰最適化
tags: []
categories: ["Programming", "Lisp", "Clojure"]
date: 2010-03-23T16:38:59Z
updated: 2010-03-23T17:34:42Z
---

そろそろClojureでのloop/recurによる末尾再帰最適化に慣れてきたんじゃないでしょうか。<br />Clojureでは相互再帰も最適化されません。例えばこんな例

    ;; ちょっと変わったみんな大好きFizzBuzz
    (declare fizz buzz)
    
    (defn fizz-buzz [n]
      (when (> n 0)
        (print n " = ")
        (fizz n)))
    
    (defn- fizz [n]
      (if (zero? (rem n 3))
        (print 'fizz))
      (buzz n))
    
    (defn- buzz [n]
      (if (zero? (rem n 5))
        (print 'buzz))    
      (println)
      (fizz-buzz (dec n)))

<p>
<br />
<img src="/upload/00013/uploaded-3478352419553.png" /><br />
<br />
このような再帰もスタックを消費します。手元の環境では<code>n = 2000</code>で<code>java.lang.StackOverflowError</code>が発生しました。
</p>
<p>
このような状況を最適化するために用意されている関数は。。。<code>trampoline</code>です。<br />
プログラミングClojureをお持ちの方はP.149を開いてください。さらっと説明されていますｗ
</p>
<h3>trampolineで最適化したコード</h3>
<code>trampoline</code>化させるには返り値の括弧の前に<code>#</code>をつけてクロージャ(closureの方)を返すように修正します。

    (declare fizz buzz)
    
    (defn fizz-buzz [n]
      (when (> n 0)
        (print n " = ")
        #(fizz n)))
    
    (defn- fizz [n]
      (if (zero? (rem n 3))
        (print 'fizz))
      #(buzz n))
    
    (defn- buzz [n]
      (if (zero? (rem n 5))
        (print 'buzz))    
      (println)
      #(fizz-buzz (dec n)))

<p>呼び出すときは<code>(trampoline f & args)</code>です。</p>
<pre class="prettyprint lang-cl">
user> (trampoline fizz-buzz 2000) ; これでjava.lang.StackOverflowErrorが発生しなくなりました!
</pre>
<h3>部分適用でインタフェース改善</h3>
<p>このままだと使うとき毎回<code>trampoline</code>を書かなくてはいけなくて面倒ですね。本来渡したいのfizzbuzzの引数だけです。こんなときのために<code>partial</code>部分適用があります！
<br />
プログラミングClojureをお持ちの方はP.146を開いてください。<code>trampoline</code>の第一引数が<code>fizz-buzz</code>である新しい関数を作っちゃいます。
</p>

    (declare fizz buzz)
    
    ;; rename
    (defn- fizz-buzz-1 [n]
      (when (> n 0)
        (print n " = ")
        #(fizz n)))
    
    (defn- fizz [n]
      (if (zero? (rem n 3))
        (print 'fizz))
      #(buzz n))
    
    (defn- buzz [n]
      (if (zero? (rem n 5))
        (print 'buzz))    
      (println)
      #(fizz-buzz-1 (dec n)))
    
    ;; 部分適用
    (def fizz-buzz (partial trampoline fizz-buzz-1))

<pre class="prettyprint lang-cl">
user> (fizz-buzz 2000) ; これでもともと期待していたインタフェースで最適化できました!
</pre>
<p>
面白いですねClojure!<br />まだプログラミングClojureを買っていない人はぽちりましょう！<br />
<a href="http://www.amazon.co.jp/exec/obidos/ASIN/4274067890/ikam-22/ref=nosim/" name="amazletlink" target="_blank"><img src="http://ecx.images-amazon.com/images/I/51rZIaR6A-L._SL160_.jpg" alt="プログラミングClojure" style="border: none;" /></a>
</p>