4

私はchainl1の末尾再帰バージョンを実装しようとしていますが、loop-recurを使用しても、StackOverflowErrorがスローされます。それはどのように可能であり、それを変更するために何ができますか？

(defn atest [state]
  (when-not (and (= "" state) (not (= (first state) \a))) 
      (list (first state) (. state (substring 1)))))
(defn op [state]
  (when-not (and (= "" state) (not (= (first state) \a)))
    (list #(list :| %1 %2) (. state (substring 1)))))
(defn chainl1-helper [x p op]
  (fn [state]
    (loop [x x
           state state]
      (if-let [xs (op state)]
        (when-let [xs2 (p (second xs))]
          (recur ((first xs) x (first xs2)) (second xs2)))
        (list x state)))))

(defn chainl1 [p op]
  (fn [state]
    (when-let [[v s] (p state)]
      ((chainl1-helper v p op) s))))
(def test-parse (chainl1 atest op))
(defn stress-test [n] (test-parse (apply str (take n (interleave (repeat "a") (repeat "+"))))))
(stress-test 99999)
4

1 に答える 1

8

スタックを爆破する最終結果を出力するため、コードではなくREPLになります。

最後の行を次のように置き換えます

(count (stress-test 99999))

そしてそれは終わります

スタックトレースには、このパターンが何度も繰り返されています。

 13:    core_print.clj:58 clojure.core/print-sequential
 14:    core_print.clj:140 clojure.core/fn
 15:      MultiFn.java:167 clojure.lang.MultiFn.invoke

編集：LDomagalaは、この種のクラッシュに対する安全性として印刷レベルを指摘しました

user>  (set! *print-level* 20)
20
user> (stress-test 9999)
((:f (:f (:f (:f (:f (:f (:f (:f (:f (:f (:f (:f (:f (:f (:f (:f (:f (:f (:f # \a) \a) \a) \a) \a) \a) \a) \a) \a) \a) \a) \a) \a) \a) \a) \a) \a) \a) \a) "")
user>
于 2012-04-19T22:54:01.207 に答える