Hacker News Reader

Comment by oconnore | Hacker News Reader

    import Control.Concurrent.STM
    import Control.Monad
    import Data.Vector

    type VecInts = Vector (TVar Int)

    newVecInts :: Int -> STM (VecInts)
    newVecInts s = generateM s (\_ -> newTVar 0)

    modifyVI :: VecInts -> Int -> Int -> STM ()
    modifyVI vi pos val = do
      writeTVar (vi ! pos) val

    waitUntilEqual :: VecInts -> Int -> Int -> STM ()
    waitUntilEqual vi p1 p2 = do
      a <- readTVar (vi ! p1)
      b <- readTVar (vi ! p2)
      when (a /= b) retry

View on HN

I'm not familiar with the semantics of software transactional memory, but doesn't this violate the "don't busy-loop" requirement? Is the retrying logic smart enough to set up some kind of watch on the values, or does it just run continuously until satisfied?

> Is the retrying logic smart enough to set up some kind of watch on the values

Yes. It only retries when one of the referenced values is updated.

This does violate the rule "only use mutexes and condition variables", and perhaps the rule added at the end "you can't read the values" (comparing memory without reading from memory seems like quite a trick!).

The "you can't read the values" note is referring to the API exposed to callers, not internal restrictions on the implementation.

Are you sure? That doesn't seem to match with the wording:

> There's no way to read the values from the array, only to set them and compare them for equality

(emphasis mine). That seems to me to mean literally what it says; that you can query two values for equality, but, either way, have no information about what the values are.

EDIT: From the horse's mouth (https://news.ycombinator.com/item?id=9801189), I'm wrong.

My bad; Strilanc's interpretation is correct. I updated the wording to hopefully be a little clearer.

Thanks! While you're here, is oconnore (https://news.ycombinator.com/item?id=9800705 )'s solution legal according to your rules?

EDIT: Also, the wording

> There's no way to read the values from the array, only to set them and compare them for equality

seems unchanged.

The preceding sentence was changed to be more explicit that the bullet points are about the "user-facing API" being unrealistic. They're not implementation rules/constraints.

I think his solution is a little bit tongue in cheek - it shows how much easier it is to solve using transactional memory compared to low-level concurrency primitives. So it cheats by using very powerful techniques instead of the very weak ones that the post says to use. You couldn't use his solution in C++ for instance, because C++ doesn't come with garbage collection or transactional memory.

I see; I don't know enough about concurrency to recognise the tongue-in-cheek-ness (or whatever). Thanks for explaining!

I think the rule is that you can only compare the values for equality, not find out what they actually are. (How one would stumble upon such a restriction is a different matter, but at least it's not a paradoxical setup.)

EDIT: From the horse's mouth (https://news.ycombinator.com/item?id=9801189), I'm wrong.

Reply on news.ycombinator.com