#:g1: trivial-tcoの紹介

Posted 2014-02-23 15:00:00 GMT

(LISP Library 365参加エントリ)

 LISP Library 365 の55日目です。

trivial-tcoとはなにか

 trivial-tcoはRalph Möritz氏作の末尾再帰の最適化が効くようにオプションを設定したフォームを提供するものです。

パッケージ情報

パッケージ名trivial-tco
Quicklisp
Quickdocshttp://quickdocs.org/trivial-tco

インストール方法

(ql:quickload :trivial-tco)

試してみる

 どんな関数があるかは、Quickdocsで確認できます。
といってもwith-tail-call-optimization1つだけですが。

 Schemeの心で末尾再帰で書いてもスタックが溢れてしまうのがCommon Lisp。
大抵の処理系は末尾呼び出しを最適化しますが、Schemeより最適化を邪魔するもの(スペシャル変数など)が多いので扱い難いものとなります。
とりあえず、そういう邪魔になるものは考えなければ、コンパイラは最適化オプションによって呼び出しをジャンプに変換します。
trivial-tcoは処理系ごとのオプションの違いを吸収するマクロで、定義もこれだけです。

(defmacro with-tail-call-optimization ((&optional treat-warnings-as-errors) &body body)
  #+ (or sbcl allegro)
  `(let ()
     (declare (optimize (speed 3)))
     ,@body)
  #+ (or lispworks ccl)
  `(let ()
     (declare (optimize (debug 0)))
     ,@body)
  #- (or cmu sbcl ccl lispworks allegro)
  (let ((msg "Proper tail-call optimization is not available."))
    (if treat-warnings-as-errors
        (error msg)
        (progn 
          (warn msg)
          `(progn
             ,@body)))))

 使い方もシンプルで、とりあえず最適化されて欲しいフォームを囲むだけです。
以前紹介した、そのままではスタックが溢れてしまうletrecが丁度良いので例として組み合せてみます。
まずは、素の再帰でのループ

(defun foo ()
  (letrec:letrec ((iter (lambda (n)
                          (if (zerop n)
                              :done
                              (iter (1- n))))))
    (iter 1000000)))

(foo) ;!!>Control stack exhausted (no more space for function call frames). ;!!>This is probably due to heavily nested or infinitely recursive function ;!!>calls, or a tail call that SBCL cannot or has not optimized away.

スタックが溢れます。
次にwith-tail-call-optimization付き

(defun foo ()
  (tco:with-tail-call-optimization ()
    (letrec:letrec ((iter (lambda (n)
                            (if (zerop n)
                                :done
                                (iter (1- n))))))
      (iter 1000000))))

(foo) ;=> :DONE

無事最適化されました。
なかなか良いねと思ったのですが、作者はClozure CLでしかテストしてないよとのことで、LispWorks/Allegro CLで試してみたところ設定オプションが違うようで最適化が効かないようです。SBCLでは最適化は効きましたが、今後に期待しましょう。

末尾呼び出しの最適化についての関連記事等

まとめ

 今回は、trivial-tcoを紹介してみました。
TCOのまとめを書いてる人が作成したのかと思い込んでいましたが、まとめ記事は、Marc Simpsonという方が書いているようなので別人でした。
今後trivial-tcoにもこのまとめの内容が盛り込まれると嬉しいですね。それとletで囲むんじゃなくて、locallyになると嬉しい。

comments powered by Disqus