Gist updated to use watchers for table state reporting, instead of coupling the reporting with the transaction.
Also, as cgrand pointed to me, note that this implementation using the STM is somehow related to the "Monitor solution" described in : http://en.wikipedia.org/wiki/Dining_philosophers_problem#Monitor_solution https://gist.github.com/759364 Feedback appreciated, -- Laurent 2010/12/30 Laurent PETIT <[email protected]> > of course there's a little rampant bug, (take) should read (take (count > phils) ..) not (take (* 3 (count phils)...), gist updated. > > > 2010/12/30 Laurent PETIT <[email protected]> > >> And here's the gist, if it's more readable : >> https://gist.github.com/759364 >> >> 2010/12/30 Laurent PETIT <[email protected]> >> >> Here's my attempt at providing a simple solution to this problem: >>> >>> 18 lines of code, not too bad if it's not buggy ;-) >>> >>> ;;; Dining philosophers. Solution using Clojure STM. >>> ;;; What are our identities? >>> ;;; The problem talks about forks, and philosophers. >>> ;;; Conceptually, forks have a "taken-by" property which can have one >>> ;;; of three values: :left-philosopher, :righ-philosopher, :nobody. >>> ;;; Conceptually, philosophers have a "state" property which can be >>> ;;; :eating or :thinking. >>> ;;; Note that with an approach using STM for getting both forks at once >>> ;;; atomically or none, and synchronizing the philosopher's value, we >>> ;;; will always have the "taken-by" property of the forks and the >>> "state" >>> ;;; property of the philosopher synchronized. >>> ;;; So we can altogether get rid of the fork concept, use refs for >>> ;;; representing philosophers, and allow the change of the state of a >>> ;;; philosopher to :eating by ensuring that his neighbours have the >>> ;;; :thinking value in the same transaction >>> ;;; For simulating true concurrent independent philosophers, we will have >>> >>> ;;; one thread per philosopher. Using "future" is just an easy trick >>> for >>> ;;; starting a new thread, and we do not really want to use "future" >>> beyond >>> ;;; its "will run the code in a separate thread" feature. >>> ;;; Implementation notes: >>> ;;; * philosopher "behaviour" is basic : thinks for a while, tries to >>> eat, >>> ;;; thinks for a while, stops eating, thinks for a while, tries to >>> eat, >>> ;;; thinkgs for a while, etc. >>> ;;; * could be enhanced for graceful shutdown of the dinner, etc., but >>> this >>> ;;; would clutter with no real value to the essence of the solution >>> >>> (def phils (repeatedly 5 #(ref :thinking))) >>> >>> (defn snapshot [] (->> phils (map deref) doall dosync)) >>> >>> (def printer (agent nil)) >>> >>> (defn react [val neighbours-vals] >>> (cond >>> (= :eating val) :thinking >>> (some (partial = :eating) neighbours-vals) val >>> :else :eating)) >>> >>> (defn phil-fn [p neighbours] >>> (Thread/sleep (rand-int 100)) >>> (dosync >>> (let [old @p >>> new (alter p react (map deref neighbours))] >>> (when-not (= old new) (send printer (fn [_] (prn (snapshot)))))))) >>> >>> (defn start-lunch [] >>> (doseq [[left-phil phil right-phil] (take (* 3 (count phils)) >>> (partition 3 1 (cycle >>> phils)))] >>> (future (while true (phil-fn phil [left-phil right-phil]))))) >>> >>> ;(start-lunch) >>> >>> 2010/12/29 Laurent PETIT <[email protected]> >>> >>> Hi Todd, >>>> >>>> 2010/12/29 Todd <[email protected]> >>>> >>>> Thanks Ken, Mark, David and Alex for your comments regarding Binary >>>>> Search trees. I've read that thread several times, and ordered Okasaki's >>>>> Purely Functional Data Structures, too. I'll return to this a bit later. >>>>> >>>>> Meanwhile, I decided to tackle learning Clojure from a different >>>>> angle...in this case, implementing a solution for the Dining Philosopher >>>>> problem. >>>>> >>>>> I've posted my code here: >>>>> >>>>> https://gist.github.com/757925 >>>>> >>>>> General comments/questions: >>>>> >>>>> 1. I suppose it's from years of OO programming, but it still feels so >>>>> weird not to be creating objects and then hanging methods off those >>>>> objects. >>>>> In fact, my first approach was to create protocols and records for each of >>>>> the 'objects': chopsticks, philosophers, even the table. But this started >>>>> to >>>>> get painful, so I shifted gears... >>>>> >>>>> 2. I'm using a number of symbols (:tablestate, :seats, :chopsticks, >>>>> :servings, etc). Shouldn't these be defined somewhere? It feels like I'm >>>>> driving w/o a seatbelt. I'm so used to encapsulating this sort of thing in >>>>> an enum or something, and then relying on java typing to enforce the >>>>> allowed >>>>> values. >>>>> >>>>> 3. Starting a thread with (future ... This couldn't be easier. Very >>>>> cool. >>>>> >>>>> 4. I tried making the table an agent instead of a ref. Then I was >>>>> sending methods to the table like, start-tableservice or >>>>> stop-tabelservice... I'll investigate further, but is it idiomatic to >>>>> start >>>>> threads within the agent? >>>>> >>>>> (BTW - Chapter 6 on State Management of Practical Clojure was >>>>> particularly helpful to me for figuring out the syntax for refs and >>>>> agents.) >>>>> >>>>> Anyone feel like tearing my code apart? I'd like to make it as clean >>>>> and clojure-ish as possible. >>>>> >>>> >>>> Not tackling the problem "at heart", here are some notes on your clojure >>>> code : >>>> >>>> * print-table: its body is in a dosync. And its intent is to emit >>>> printfs. This seems wrong. Side effects should be avoided inside >>>> transactions, since they could be retried by the STM. One solution could be >>>> to have print-table write in a memory location by rebinding >>>> clojure.core/*out* to a StringWriter, and `print` the result outside the >>>> dosync. >>>> >>>> * (+ 1 ph-index) : can be written as (inc ph-index) >>>> >>>> * create-table: you could take advantage of the fact that everything >>>> is an expression : >>>> instead of : >>>> (let [ch (zipmap (range seats) (map ref (take seats (repeat :table)))) >>>> ph (zipmap (range seats) (map ref (take seats (repeat >>>> :thinking)))) >>>> servings (zipmap (range seats) (map ref (take seats (repeat >>>> 0))))] >>>> {:seats seats :chopsticks ch :philosophers ph :tablestate (ref >>>> :dinnertime) :servings servings}) >>>> you could directly have : >>>> {:seats seats >>>> :chopsticks (zipmap (range seats) (map ref (take seats (repeat >>>> :table)))) >>>> :philosophers (zipmap (range seats) (map ref (take seats (repeat >>>> :thinking)))) >>>> :tablestate (ref :dinnertime) >>>> :servings (zipmap (range seats) (map ref (take seats (repeat 0))))} >>>> >>>> * create-table: zipmaps could be simplified, instead of (zipmap >>>> (range seats) (map ref (take seats (repeat :table)))), you could just write >>>> (zipmap (range seats) (repeat (ref :table))) >>>> >>>> * all functions : you're placing the docstring in the wrong place. >>>> Should be right after the name of the function >>>> >>>> * consider not having, at the end of your namespace full of functions, >>>> direct calls to the functions, but rather encapsulate it in a function >>>> named >>>> main or -main. And let people call this main manually or via their favorite >>>> tool. >>>> >>>> I do not have time to deeply analyse the algorithm of your code, but >>>> some 10,000 feets notes about it: >>>> * lots of uses of indices. Feels weird. Maybe it's necessary, but my >>>> guess is that there's a better solution : without indices at all, but (but >>>> maybe not) in the function initializing the states. >>>> * or maybe the use of indices could be lessened by not propagating >>>> this to helper functions (at least) >>>> >>>> HTH, >>>> >>>> -- >>>> Laurent >>>> >>>> >>> >> > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to [email protected] Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/clojure?hl=en
