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
