On Dec 30, 2008, at 6:29 PM, Mark Engelberg wrote:
> 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.
>
>
I don't see these as being compelling arguments for atom-set. You can
do these things with Java arrays or other Java things like
clojure.lang.Box.
OTOH, atom-set just invites the read-modify-write race conditions
swap! was meant to avoid.
There's simply no value for Clojure to add to a simple mutable box.
Clojure does provide the tools for low-level mutation - access to
Java. You can wrap that in whatever functions/macros you like.
Rich
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
