<< Back to previous view

[ALGOM-13] Update links to Jim Duey's tutorial Created: 17/Feb/14  Updated: 21/Feb/14  Resolved: 21/Feb/14

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

Type: Enhancement Priority: Major
Reporter: Jim Duey Assignee: Konrad Hinsen
Resolution: Completed Votes: 0
Labels: None

Attachments: Text File README.patch    
Patch: Code

 Description   

I provided an updated link to the beginning of the monads tutorial on my blog.



 Comments   
Comment by Konrad Hinsen [ 21/Feb/14 8:12 AM ]

Done: https://github.com/clojure/algo.monads/commit/c7754d6cdf0721cce4a3c89790bc2c0fb83ecaa7





[ALGOM-12] Add new monad tutorial links to README Created: 14/Feb/14  Updated: 21/Feb/14  Resolved: 21/Feb/14

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

Type: Enhancement Priority: Major
Reporter: Leonardo Borges Assignee: Konrad Hinsen
Resolution: Completed Votes: 0
Labels: documentation, enhancement

Attachments: Text File 0001-Add-new-monad-tutorial-links.patch    
Patch: Code

 Description   

This patch adds the monad tutorials I wrote a while back.

It was requested by a user in this tweet: https://twitter.com/JakeGoulding/status/434309278329872384

Since he doesn't have a CA on file, I just created the patch myself.



 Comments   
Comment by Konrad Hinsen [ 21/Feb/14 8:15 AM ]

Done: https://github.com/clojure/algo.monads/commit/11429c1c05c2c0aa4d4befd783efa66748a40b1b





[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


 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



 Comments   
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 Sep 30 08:56:47 CDT 2014 using JIRA 4.4#649-r158309.