Details

Type: Defect

Status: Resolved

Priority: Minor

Resolution: Declined

Affects Version/s: None

Fix Version/s: None

Component/s: None

Labels:None
Description
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/mreduce, but it has a
;; wierdly unuseful type.
(defmonadfn foldm
[f a xs] (reduce (fn [macc x] (mbind macc #(f % x))) (mresult a) xs))
(defn add [s]
(runcont
(withmonad contm
(callcc
(fn [k]
(foldm (fn [a n]
(if (== n 8888) (k 1)
(mresult (+ a n))))
0 s))))))
(add (range 1 10000)) ;; stack overflow
Can be worked around with a trampoline:
(defmonad conttrampm
[mresult mresultcont
mbind mbindcont])
(defn callcctramp [f]
(fn [c] [(f (fn [v] (fn [_] [c v ::cont]))) c ::cont]))
(defn runconttramp [cont]
(loop [cv (cont identity)]
(if (and (vector? cv)
(= ::cont (nth cv 2)))
(recur ((first cv) (second cv)))
cv)))
(defn add2 [s]
(runconttramp
(withmonad conttrampm
(callcctramp
(fn [k]
(foldm (fn [a n]
(if (= n 8888)
(k 1)
(mresult (+ a n))))
0 s))))))
(add2 (range 1 1000000)) ;; > 1
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.