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
I neglected to include mresultcont and mbindcont for the conttrampm call!
(defn mresultcont [v] (fn [c] [c v ::cont]))
(defn mbindcont [mv f] (fn [c] [mv (fn [v] [(f v) c ::cont ]) ::cont]))