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
