Details
-
Type:
Defect
-
Status:
Open
-
Priority:
Minor
-
Resolution: Unresolved
-
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/m-reduce, but it has a
;; wierdly unuseful type.
(defmonadfn fold-m
[f a xs] (reduce (fn [macc x] (m-bind macc #(f % x))) (m-result a) xs))
(defn add [s]
(run-cont
(with-monad cont-m
(call-cc
(fn [k]
(fold-m (fn [a n]
(if (== n 8888) (k 1)
(m-result (+ a n))))
0 s))))))
(add (range 1 10000)) ;; stack overflow
Can be worked around with a trampoline:
(defmonad cont-tramp-m
[m-result m-result-cont
m-bind m-bind-cont])
(defn call-cc-tramp [f]
(fn [c] [(f (fn [v] (fn [_] [c v ::cont]))) c ::cont]))
(defn run-cont-tramp [cont]
(loop [cv (cont identity)]
(if (and (vector? cv)
(= ::cont (nth cv 2)))
(recur ((first cv) (second cv)))
cv)))
(defn add2 [s]
(run-cont-tramp
(with-monad cont-tramp-m
(call-cc-tramp
(fn [k]
(fold-m (fn [a n]
(if (= n 8888)
(k 1)
(m-result (+ a n))))
0 s))))))
(add2 (range 1 1000000)) ;; -> 1
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]))