On Tue, Dec 30, 2008 at 5:53 AM, Rich Hickey <richhic...@gmail.com> wrote: > Could you provide an example of when you would need/use that? >
Sure.
Use Case #1: Implementing classic imperative algorithms
Consider the binary gcd algorithm on page 338 of The Art of Computer
Programmiing, volume 2. This is a very clever implementation of gcd
using only bit shifting and parity checking. Like many classic
algorithms, it is written in a very imperative style. The following
is a direct translation to Clojure:
(defn binary-gcd [a b]
(let [k (atom 0), u (atom a), v (atom b), t (atom 0),
algsteps {:B1 (fn [] (if (and (even? @u) (even? @v))
(do (atom-set k (inc @k))
(atom-set u (bit-shift-right @u 1))
(atom-set v (bit-shift-right @v 1))
:B1)
:B2)),
:B2 (fn [] (if (odd? @u)
(do (atom-set t (- @v)) :B4)
(do (atom-set t @u) :B3))),
:B3 (fn [] (atom-set t (bit-shift-right @t 1)) :B4),
:B4 (fn [] (if (even? @t) :B3 :B5))
:B5 (fn [] (if (> @t 0)
(atom-set u @t)
(atom-set v (- @t)))
:B6),
:B6 (fn [] (atom-set t (- @u @v))
(if (not (zero? @t)) :B3 (bit-shift-left @u @k)))}]
(loop [step :B1]
(let [next ((algsteps step))]
(if (number? next) next (recur next))))))
To test this code, I used the following implementation of atom-set:
(defn atom-set [a val]
(swap! a (constantly val)))
Now, the code would certainly be cleaner if Clojure had tail-call
optimization and letrec, because you could set each algorithmic step
up as a mutually recursive function, rather than storing the steps in
a hash table, and setting up a driver loop to handle the state changes
as in a state machine. Or if Clojure just had letrec, this could be
expressed using the new trampoline construct.
But that's not really the point. The point here is that this code
took me no effort to translate from the Knuth book, it worked on the
first run with no debugging needed, and anyone can easily compare this
code against the Knuth pseudocode, and see at a glance that this is a
correct implementation of that algorithm. There may be ways to
convert this to a functional style (and I encourage others to try it
as an interesting exercise), but with any such transformation, it will
be significantly more difficult to confirm that the program correctly
implements the algorithm.
About half of the atom-sets are updates that could use the swap!
function, but many of these are replacing the atom's contents with
something completely unrelated to its existing contents.
Use Case #2: setting up mutually referential data structures
A common way to set up mutually referential data structures is to
start them off with links that are set to nil, and then use imperative
setting to direct the links at the right things. As a quick example,
consider the cyclic-linked-list solution to the classic Josephus
problem. Here is one way to set up a cyclic ring of people:
(defn make-person [n]
{:id n, :link (atom nil)})
(defn link-people [p1 p2]
(atom-set (p1 :link) p2))
(defn ring-people [n]
(let [vec-people (vec (map make-person (range n)))]
(dotimes [i (dec n)] (link-people (vec-people i) (vec-people (inc i))))
(link-people (vec-people (dec n)) (vec-people 0))
(vec-people 0)))
Now depending on how this is going to be used, you could argue that
maybe you're better served by refs. But if the whole point of atoms
is to give power-users another, faster choice when no coordination is
needed, why not give the programmer a choice here? If I know for sure
that I'm just going to use this ring within a single thread, or use it
internally in a function that generates and uses the ring without ever
exposing the ring outside that function, then an atom may be the right
tool for the job.
--~--~---------~--~----~------------~-------~--~----~
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
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
-~----------~----~----~----~------~----~------~--~---
binarygcd.clj
Description: Binary data
josephus.clj
Description: Binary data
