これはフォーラムの投稿者が示した例です。このテールが最適化されているかどうかはわかりません。また、テールを最適化したバージョンが通常のバージョンよりも優れている方法について、素人の説明を誰かが与えることができますか.
(defun mylength (s)
(labels ((mylength-inner (s x)
(if (car s) (mylength-inner (cdr s) (+ x 1)) x)))
(mylength-inner s 0)))
テール最適化されていないバージョンですか？
(defun l (s) (if (car s) (+ 1 (l (rest s))) 0))
関数は、それ自体への直接呼び出しを返すか、それ自体への呼び出しを返さない場合、最適化された末尾呼び出しにすることができます。関数 mylength-inner は または のいずれxかを返す(mylength-inner (cdr s) (+ x 1))ため、テール最適化できます。
これは、関数を再帰的に呼び出す代わりに、コンパイラがそれをループに変えることができることを意味します。x を返すか、(cdr s) を s に代入し、x をインクリメントして、最初からやり直します。(Scheme 標準では、実装がこの最適化を実行できる必要がありますが、Common Lisp 標準では実装に任せています。もちろん、この最適化は非常に便利なので、ほとんどの実装で実行されます。)
最適化されていないバージョンでは、l は単に l の呼び出しを返すのではなく、l の呼び出しに 1 を加えた結果を返します。これは、ループに直接変換できないことを意味するため、すべての関数呼び出しを行う必要があります。
コンパイラーが l をループにしたいとします。(rest s) を s に代入するのは問題ありませんが、? はどこに置くの(1 + ...)ですか?
FWIW、CL は末尾呼び出しを最適化することを保証しません。それは実装に依存します。SBCL はそれをサポートします。これは、コンパイラがテール コールを削除することを仕様で要求する Scheme とは異なります。それをしなければ、あなたはスキームではありません。
また、末尾再帰は、CL ではかなり非慣用的です。loopマクロがありますので、それを使用してください:)
テール呼び出しは、コール スタックに余分なスペースを必要としないように最適化できます。また、関数の最後の操作が再帰呼び出しである必要があります。これは、フォーラム ソースの例に当てはまるようです。非末尾バージョンの最後の操作は追加であるため、再帰呼び出しには独自のスタック フレームが必要です。
これは単純なパターンに従い、外部関数の引数に加えてアキュムレータ引数を取る内部関数を定義し、答えを累積します。最後までたどり着いたら累積値を出します。
おそらくここにもっと良い説明があります：
http://mitpress.mit.edu/sicp/full-text/book/book-ZH-11.html#%_sec_1.2.1
リストの長さのSchemeの「教科書」の例は次のようになります。http ：//www.scheme.com/tspl3/start.html#./start：h8 「長さ」を検索します。