Conrad Barski の本「The Land of Lisp」から Lisp を学んでいます。今、私は最初のつまずきにぶつかりました。ここで、著者は次のように述べています。
このように自分自身を呼び出すことは、Lisp で許可されているだけでなく、しばしば強く推奨されます
リスト内のアイテムをカウントする次のサンプル関数を示した後:
(defun my-length (list)
(if list
(1+ (my-length (cdr list)))
0))
my-length100 万個の項目を含むリストでこの関数を呼び出すと、スタック オーバーフロー エラーが発生します。したがって、Lisp でそれほど長いリストを持つことを期待することは決してないか (したがって、私の使用例は役に立たないかもしれません)、またはそのような長いリスト内の項目をカウントする別の方法があります。これに光を当てることができますか？(ちなみに、私は Windows で GNU CLISP を使用しています)。
Chris Taylorの例を使用したCLISPのTCO（末尾呼び出しの最適化）：
[1]> (defun helper (acc list)
(if list
(helper (1+ acc) (cdr list))
acc))
(defun my-length (list)
(helper 0 list))
HELPER
今それをコンパイルします：
[2]> (compile 'helper)
MY-LENGTH
[3]> (my-length (loop repeat 100000 collect t))
*** - Program stack overflow. RESET
現在、上記は機能しません。デバッグレベルを低く設定しましょう。これにより、コンパイラーはTCOを実行できます。
[4]> (proclaim '(optimize (debug 1)))
NIL
再度コンパイルします。
[5]> (compile 'helper)
HELPER ;
NIL ;
NIL
[6]> (my-length (loop repeat 100000 collect t))
100000
[7]>
動作します。
Common LispコンパイラがTCOを実行できるようにすることは、ほとんどの場合、デバッグレベルによって制御されます。デバッグレベルが高い場合、コンパイラは関数呼び出しごとにスタックフレームを使用するコードを生成します。このようにして、各呼び出しをトレースでき、バックトレースで表示されます。デバッグレベルが低い場合、コンパイラは末尾呼び出しをコンパイル済みコードのジャンプに置き換えることができます。これらの呼び出しはバックトレースには表示されません。これにより、通常、デバッグが困難になります。
末尾再帰を探しています。現時点では、関数は次のように定義されています
(defun my-length (list)
(if list
(1+ (my-length (cdr list)))
0))
my-length自身を呼び出した後、その値を呼び出し元の関数に渡す前に、結果に 1 を追加する必要があることに注意してください。値を返す前に値を変更する必要があるということは、呼び出しごとに新しいスタック フレームを割り当てる必要があることを意味します。使用されるスペースはリストの長さに比例します。これが、長いリストでスタック オーバーフローを引き起こす原因です。
ヘルパー関数を使用するように書き直すことができます
(defun helper (acc list)
(if list
(helper (1+ acc) (cdr list))
acc))
(defun my-length (list)
(helper 0 list))
ヘルパー関数は、これまでのリストの長さを格納する蓄積パラメーター と、長さを計算しているリストであるリストの 2 つのパラメーターを取ります。acclist
重要な点は、helpertail が再帰的に記述されていることです。つまり、自分自身を呼び出すことは最後に行うということです。これは、関数がそれ自体を呼び出すたびに新しいスタック フレームを割り当てる必要がないことを意味します。最終結果はとにかくスタック フレームのチェーンをずっと遡って渡されるため、古いスタック フレームを上書きする必要がなくなります。新しいものを使用すると、再帰関数が一定のスペースで動作できるようになります。
この形式のプログラム変換 - 再帰的 (ただし末尾再帰ではない) 定義から、末尾再帰ヘルパー関数を使用した同等の定義への変換は、関数型プログラミングの重要なイディオムです。これは、少し時間をかけて理解する価値があります。
再帰的なデータ構造を操作するための再帰的な関数を作成することは、Lisp では確かに有効です。また、(lisp の) リストは再帰的なデータ構造として定義されているので、問題ありません。
ただし、経験したように、再帰を使用して100万項目の深さのデータ構造をトラバースすると、スタックに100万フレームも割り当てられ、ランタイム環境に大量のスタックスペースを割り当てるように特に要求しない限り、スタックオーバーフローが予想されます（gnu clispでこれを行うことができるかどうか、またはどのように行うかはわかりません...）。
まず第一に、これはリストデータ構造が実際にはすべてに最適ではないことを示していると思います.この場合、別の構造の方が良いかもしれません. )
もう 1 つのことは、このような大規模な再帰が効果的であるためには、コンパイラは末尾再帰を最適化し、反復に変換する必要があるということです。clisp にこの機能があるかどうかはわかりませんが、関数を実際に最適化できるように変更する必要があります。（「末尾再帰の最適化」が意味をなさない場合は、お知らせください。いくつかの参考文献を掘り下げることができます）
反復の他の方法については、以下をご覧ください。
または他のデータ構造:
(DEFUN nrelem(l)
(if (null l)
0
(+ (nrelem (rest l)) 1)
))