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

Sterling Clover s.clover at gmail.com
Thu Apr 24 14:06:27 EDT 2008

> broken2 = atomically $ do
>   (v1, v2) <- expensive_computation :: STM (TVar Int, TVar Int)
>   retryUntil v1 (> 50)
>   x <- expensive_computation2 :: STM Int
>   retryUntil v2 (> x)

Ah. I think I see now. I had thought you were trying to give more power to
the primitive than you are.

But I'm still finding the example confusing, in that expensive_computation2
is in STM, and thus isn't pure. The point, I suppose, would rather be to
assert that retryUntil v2 (> x) depends on what v2 depends on, and what x
depends on, but *not* on what v1 depends on, and thus to retry only when the
appropriate portion of the dependency tree changed.

However, in this case, that still doesn't buy you anything, I think, because
from the information given, one can't disentangle what v1 and v2 depend on?

I hope I'm somewhat closer to the mark here.

On 4/23/08, Ryan Ingram <ryani.spam at gmail.com> wrote:
> On 4/23/08, Sterling Clover <s.clover at gmail.com> wrote:
> > But expensive_computation2 is in STM. This means that it *should* be
> rerun,
> > no? Between the first run and the retry, the result of
> > expensive_computation2 may well have changed.
> Ah, but that's not true; the main "good thing" about retry is that you
> don't have to keep running the computation; instead you wait until
> something that you accessed in your transaction log changes and -then-
> you rerun it.  Right now the transaction log for "retry" only contains
> "read from variable X" (for some list of variables).  But it could
> instead contain "read from variable X" and "read from variable X using
> retryUntil with predicate p which gave result True".  Then we have a
> "smarter" log which can use the pure predicate p to give more
> information about whether or not the whole transaction can run or
> whether it is just guaranteed to fail again.  If we know a transaction
> is guaranteed to fail, we can skip running it because we know it will
> not commit.
> Given the semantics of retryUntil, it is impossible that changing v1
> affects the results of running this STM computation -unless- it or
> something else prior in the computation read from v1, or the result of
> the predicate changes.
> No spooky-action-at-a-distance is possible.  David's more general
> "subatomically" primitive would achieve the same results; the proof is
> that
> (1) no side effects can be caused by the subatomic action, that is, no
> writes happen which could change future reads.
> (2) the result of the computation is ignored -except- for whether it
> retries or returns, that is, it can't affect the control flow of the
> rest of the transaction.
> So, if have a transaction T that is waiting inside "retry" for a
> variable that it read to change, and a variable that is only accessed
> in a "subatomic" part of T is changed, we can try running the
> subatomic computation first.  Here are the four cases:
> 1) The subatomic computation succeeded before and still succeeded.
> Then we know the end result of the computation is unaffected, and will
> still retry.  No need to do anything.
> 2) The subatomic computation succeeded before and now fails (calls
> 'retry' or retryRO').  Then we know that the computation will now fail
> at this earlier point.  Mark the change to "fail" in the transaction
> log and leave the computation in the "waiting for retry" state.
> 3) The subatomic computation failed before and still fails.  See (1)
> 4) The subatomic computation failed before and now succeeds.  The
> result of the entire computation can change, we should now re-run the
> entire computation.
> -- ryan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080424/4a70c561/attachment.htm

More information about the Haskell-Cafe mailing list