lisp - プロジェクト Euler 72 (lisp) に関する奇妙な質問

Question

これに対する出力に明らかなパターンがあることを認識しています.52を超えるものを実行しようとすると、lispboxのREPLが中止される理由を知りたいだけです.また、コードを改善するための提案は大歓迎です. ^-^

(defun count-reduced-fractions (n d sum)
  (setf g (gcd n d))
  (if (equal 1 d)
      (return-from count-reduced-fractions sum)
      (if (zerop n)
          (if (= 1 g)
              (count-reduced-fractions (1- d) (1- d) (1+ sum))
              (count-reduced-fractions (1- d) (1- d) sum))
          (if (= 1 g)
              (count-reduced-fractions (1- n) d (1+ sum))
              (count-reduced-fractions (1- n) d sum)))))

私が電話するときに私が得るすべて

(count-reduced-fractions 53 53 0)

は

;評価は中止されました

それより下のすべての数値で実行され（そして正確な結果が返される）、頭、紙、または1行で（必要に応じて）53を実行できることを考えると、私にはあまり意味がありませんLispで一度に。53 に固有のものではないことを確認するために、53 より大きいさまざまな数値でテストしました。何も機能しません。

Answer 1

この動作は、末尾呼び出しの最適化が欠落していることを示唆しているため、再帰によってスタックが破壊されます。考えられる理由は、デバッグの最適化を宣言したことです。

ちなみに、を明示的に呼び出す必要はありませんreturn-from。sumは自己評価記号なので、この行を変更できます

(return-from count-reduced-fractions sum)

に

sum

編集：提案された変更の説明：「sum」はそれ自体の値に評価されます。これは「if」ステートメントの戻り値になり、（これはdefunの最後のステートメントであるため）関数の戻り値になります。

編集：宣言された最適化の説明：トップレベルに以下を追加できます：

(declaim (optimize (speed 3)
                   (debug 0)))

または同じものを使用しますが、関数の最初のステートメントとしてではdeclareなくを使用します。declaimうまくいかない場合は、（スペース3）と（安全0）を試すこともできます。

末尾呼び出しの最適化とは、戻り値が直接返される関数呼び出しが（スタックアップではなく）スタック上のフレーム置換に変換され、再帰関数呼び出しをループに効果的に「フラット化」し、再帰関数呼び出しを排除することを意味します。これにより、デバッグが少し難しくなります。これは、期待する場所に関数呼び出しがないためです。再帰の「深い」ところでエラーが発生するかどうかはわかりません（最初にループを作成したかのように）。ご使用の環境では、TCOを有効にするためにオーバーライドする必要のあるデフォルトのデクラメーションが作成される場合があります。

編集：この質問を再検討するだけです、何gですか？私はあなたが実際にしたいと思います

(let ((g (gcd n d)))
  ;; ...
  )

Answer 2

私の推測では、lispbox には組み込みのスタック深度制限があると思います。Common Lisp は、末尾再帰関数が一定のスタック スペースを使用することを保証しないため、count-reduced-fractions を呼び出すたびにスタックに別のレイヤーが追加される可能性があります。

ちなみに、SBCL はこのアルゴリズムを問題なく実行します。

* (count-reduced-fractions 53 53 0)
881

* (count-reduced-fractions 100 100 0)
3043

Answer 3

スタイルの問題として、d と sum をオプションにすることができます。

(defun test (n &optional (d n) (sum 0)) .. )

Answer 4

おそらくスタックオーバーフローです（へー）。