algo.monads

continuation monad can easily overflow stack

Details

  • Type: Defect Defect
  • Status: Resolved Resolved
  • Priority: Minor 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/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

Activity

Konrad Hinsen made changes -
Field Original Value New Value
Resolution Declined [ 2 ]
Status Open [ 1 ] Resolved [ 5 ]

People

Vote (0)
Watch (0)

Dates

  • Created:
    Updated:
    Resolved: