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

[Ryan Ingram]

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