Remove first item from Clojure vector atom and return it

Question

I have an atom wrapping a vector of items:

(def items (atom [1 2 3 4]))

I want to atomically remove the first item and return it. This code illustrates the logic:

(let [x (first @items)]
  (swap! items #(subvec % 1))
  x)

But the above code is not correct when many threads are contending with each other. There is a race condition between reading and updating.

As stated nicely in this answer, atoms are for uncoordinated synchronous access. I was hoping this could be done with an atom instead of a ref, because the atom is simpler.

Is there a solution that uses only atoms, not refs? (I'm going to try using watches and see how that goes.) If your answer insists that a ref is needed, could you please explain why a ref is needed even though refs are suggested when one wants "Coordinated Synchronous access to Many Identities" (same link as above).

This is different from other related questions such as How do I update a vector element of an atom in Clojure? and Best way to remove item in a list for an atom in Clojure because I want to update a vector atom and return the value.

Answer 1

A spin loop with compareAndSet is used to swap! an atom. Clojure also provides a lower level compare-and-set! for atoms that you can use to do your own spin loop and return both the old and new value.

(defn swap*!
  "Like swap! but returns a vector of [old-value new-value]"
  [atom f & args]
  (loop [] 
    (let [ov @atom 
          nv (apply f ov args)]
      (if (compare-and-set! atom ov nv)
        [ov nv]
        (recur)))))

(defn remove-first-and-return [atom]
  (let [[ov nv] (swap*! atom subvec 1)]
    (first ov)))

Answer 2

If you need to use an atom, use a locally encapsulated atom to store the first element of the in-transaction value of the winning transaction.

(let [f-atom (atom nil)]
  (swap! items-atom #(do (reset! f-atom (first %)) 
                         (rest %)))
  @f-atom)

Alternatively, achieve the same with a ref and a dosync transaction block:

(dosync
  (let [f (first @items-ref)]
    (alter items-ref rest)
    f)))

Here, in case the transaction fails because a parallel write operation succeeded, the transaction does not return or have effect on the ref until it could have been retried so that the read and write operations were performed without interruption by another write operation.

Answer 3

My go-to solution for this is storing whatever return value is needed in the metadata of the contained value. I don't know how idiomatic that is and it obviously only works for classes that implement the IMeta interface.

(defn pop-head!
  [a]
  (-> (swap! a #(with-meta (subvec % 1) {:head (% 0)}))
      (meta)
      :head))

This profits from the fact that swap! returns the now-stored value of the atom. Let's try it:

(def a (atom [1 2 3 4]))
(pop-head! a) ;; => 1
(pop-head! a) ;; => 2
(pop-head! a) ;; => 3
(pop-head! a) ;; => 4
(pop-head! a) ;; => IndexOutOfBoundsException...

Yeah, you might want to handle that case. ;)

Answer 4

This is not a solution for this use case, but might be for some others.

You can create a watch on the atom with add-watch which will send an event with both the old and new values.

Answer 5

Since the addition of swap-vals! in Clojure 1.9, you can use (ffirst (swap-vals! items rest)) to return the first element from the vector and update the atom in a single operation.