<< Back to previous view

[ALGOM-5] continuation monad can easily overflow stack Created: 10/Sep/12  Updated: 05/Feb/14  Resolved: 05/Feb/14

Status: Resolved
Project: algo.monads
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: ben wolfson Assignee: Konrad Hinsen
Resolution: Declined Votes: 0
Labels: None


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]
(with-monad cont-m
(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)))

(defn add2 [s]
(with-monad cont-tramp-m
(fn [k]
(fold-m (fn [a n]
(if (= n 8888)
(k 1)
(m-result (+ a n))))
0 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.

Generated at Tue Jan 23 22:19:57 CST 2018 using JIRA 4.4#649-r158309.