[Haskell-cafe] Stronger STM primitives needed? Or am I just doing it wrong?

[Tim Harris (RESEARCH)]

Hi,

I think this could be a nice addition.

What do you think about a slight change:

   readTVarWhen :: TVar a -> (a -> bool) -> STM a

This would retry until the (a->bool) function returns true (and, of course, as with a normal "retry", the implementation would need to watch all of the TVars that have been read).

This would avoid replicating the condition in the control flow of the program and the parameter to retryUntil, and avoid the possibility that the two conditions might be inconsistent (or can you see any examples where it might be useful to have different conditions)?

Do you have a program where the basic implementation with "retry" is performing badly?  If you're OK distributing it then could we add it to the STM benchmark suite that the group at Barcelona Supercomputing Center are developing?

Thanks,

Tim




-----Original Message-----
From: haskell-cafe-bounces at haskell.org [mailto:haskell-cafe-bounces at haskell.org] On Behalf Of Ryan Ingram
Sent: 22 April 2008 14:49
To: haskell-cafe at haskell.org
Subject: [Haskell-cafe] Stronger STM primitives needed? Or am I just doing it wrong?

How can I implement the following operation efficiently in STM?  Given
a TVar "now",

waitFor t0 = do
    t <- readTVar now
    if (t < t0) then retry else return ()

This naive implementation has the problem that the transaction gets
restarted every time "now" gets updated, even if the new value is
still less than t0.

One primitive that would be strong enough is this:
retryUntil :: TVar a -> (a -> Bool) -> STM ()

although it would still do some computation every time "now" changed.

The thought I originally had was to register the "waitFor" time with
some helper which kept track of the current time and fired off a
notice when it was ready.  But the problem with that is that "retry"
undoes all the work of setting that up; the goal is still to block,
but I want a stronger blocking primitive.

Does anyone have any ideas?

  -- ryan

Here's the background:  I'm following along with Conal's excellent FRP
paper at http://conal.net/papers/simply-reactive/

In his implementation of futures, Conal uses a race primitive which
spawns two threads each computing a value that (if successful) is
guaranteed to agree.  I was (and still am) sure that an implementation
using STM could avoid needing to race, with careful use of orElse &
retry.

Here's the datatype I'm using for Future:

> -- semantic type for future
> -- t = type of Time, an instance of Bounded.  a = value type
> type F t a = (t, a)
> force :: Future t a -> F t a

> data Future t a = Fut
>     { waitFor :: t -> STM ()
>     , value :: STM (t, a)
>     }


> firstFuture :: Future t a -> Future t a -> Future t a
> -- with semantics:
> -- force (firstFuture f1 f2) = (min t1 t2, if t1 <= t2 then v1 else v2)
> --   where
> --     (t1, v1) = force f1
> --     (t2, v2) = force f2

Each future lives in some universe; imagine you have the following:
] type Universe t -- abstract
] P :: Bounded t => Universe t -- universe of pure values
] R :: Universe Time -- universe of the real world
] univ :: Future t a -> Universe t
] now :: Universe t -> STM t
] -- now P = return maxBound
] -- now R = current time

The main thrust of this is that each universe has its own idea of what
time it is; but when combining futures, we get a new universe which
tracks the later of the times in the two universes.  The problem is
combining two futures:

Lets say we have:
anyKey :: Future Time () -- fires when the user first presses a key
thousand :: Num t => Future t () -- fires at tick 1000
thousand = exactly 1000 ()

and we are evaluating
  force (firstFuture anyKey thousand)

Now, "clock" is going to fire at tick 1000; we know this because it
lives in the pure universe and its value is always available.  So
firstFuture can get the following:

   x1 <- maybeSTM (value anyKey)
   -- x1 = Nothing
   x2 <- maybeSTM (value clock)
   -- x2 = Just (1000, ())
   ...
     -- synchronize P with R at tick 1000
     waitFor anyKey 1000 -- if nothing has changed before tick 1000
     return (1000, ())

-- converts a possibly-retry-calling STM into one that never fails
maybeSTM m = fmap Just m `orElse` return Nothing

So if we use the naive implementation for "waitFor" in terms of "now",
the whole transaction will get re-evaluated every tick.  I only want
it to get re-evaluated if the user presses a key (changing some TVar
evaluated in "value anyKey"), or tick 1000 passes, whichever comes
first.  Is there a way to do this?  Is my choice of "waitFor" as the
basic "universe synchronization" operation too weak?
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe at haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe