[ALGOM-5] continuation monad can easily overflow stack Created: 10/Sep/12 Updated: 05/Feb/14 Resolved: 05/Feb/14
|Reporter:||ben wolfson||Assignee:||Konrad Hinsen|
The continuation monad uses tail calls, and because they aren't optimized out it's vulnerable to stack overflows for large computations:
;; there is a function clojure.algo.monads/m-reduce, but it has a
(defn add [s]
(add (range 1 10000)) ;; stack overflow
Can be worked around with a trampoline:
(defn call-cc-tramp [f]
(defn run-cont-tramp [cont]
(defn add2 [s]
(add2 (range 1 1000000)) ;; -> 1
|Comment by ben wolfson [ 10/Sep/12 12:01 PM ]|
I neglected to include m-result-cont and m-bind-cont for the cont-tramp-m call!
(defn m-result-cont [v] (fn [c] [c v ::cont]))
(defn m-bind-cont [mv f] (fn [c] [mv (fn [v] [(f v) c ::cont ]) ::cont]))
|Comment by Konrad Hinsen [ 05/Feb/14 6:14 AM ]|
It is true that the continuation monad can easily overflow the stack. I don't see any solution within the constraints imposed by the JVM (no tail call optimization).
A different implementation based on a trampoline is a useful workaround. Unfortunately I cannot use your code because you are not on the list of people who have signed a Contributor Agreement.