[m-dev.] Generalizing STM

[Chris King]

Hi,

It seems to me that the STM constructs retry() and or_else are
extraneous in Mercury, and that more power can be had from relying on
Mercury's basic semantics.

I posit first that the STM log type, stm.stm, need not be unique but
merely mostly unique.  This follows from the fact that the STM log by
its very nature is backtrackable.  (Indeed, in the current
implementation, which writes on commit, I believe that the STM log
need not even be mostly unique; however it is desirable to maintain
that it is mostly unique should the underlying implementation change.)

Building on this, it can be seen that STM retry() can be replaced with
simple failure in the absence of negated contexts.  STM retry() is
supposed to "bubble up" to the outermost "atomic" block; this is
exactly what failure does in the absence of negated contexts.

Let's now look at what happens to a mostly unique STM log should it be
used inside a negated context.  Should the goal in the context
succeed, failure should propagate outward and the STM log will be
thrown away as expected.  Should the goal in the context fail, the STM
log (being mostly unique) will have its writes (NOT reads, which are
nondestructive and must be tracked for atomicity to hold) backtracked
to outside the negated context, whereupon execution of the transaction
will continue without the failed writes.

Putting this in the context of an if/then/else, a failed "if" goal
will cause backtracking of writes and subsequent execution of the
"else" goal -- in other words, we get "or_else" for free.

Furthermore, we gain added expressivity -- any code in the "then" goal
will be atomically executed if the "if" goal succeeds, but failure of
the "then" goal will not trigger the "else" goal.  This is not
possible with merely an "or_else" construct without setting an
auxiliary flag.

Over the course of the next few weeks I will work on reworking
Mercury's STM implementation to treat failure-as-retry.  This should
result in great simplification of the STM expansion code in the
compiler as it will no longer need to deal with the "or_else"
construct.

The only caveat I see is that removal of the explicit "retry" function
will make it harder to spot atomic blocks which could deadlock.  One
possibility is to only allow failure-as-retry in STM blocks marked
with an explicit flag (say "can_block").  Suggestions are welcome.

Thoughts?

- Chris
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at csse.unimelb.edu.au
Administrative Queries: owner-mercury-developers at csse.unimelb.edu.au
Subscriptions:          mercury-developers-request at csse.unimelb.edu.au
--------------------------------------------------------------------------