And here's the gist, if it's more readable : https://gist.github.com/759364
2010/12/30 Laurent PETIT <laurent.pe...@gmail.com> > 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 <laurent.pe...@gmail.com> > > Hi Todd, >> >> 2010/12/29 Todd <t.greenwoodg...@gmail.com> >> >> 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 clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
