[cl-stm-devel] Retry

[Hoan Ton-That]

Yesterday I gave an example of the operator `try'.
Today, you'll see how `retry' nicely complements
it.

The previous code tried to increment one of two
counters.  It didn't matter which one we incremented
as long as we incremented!  Lets generalize from
that example to increment any counter in a list of
counters:

(deftransaction increment-any (counters)
  (tif (trans (null counters))
       (retry)
       (try (increment     (car counters))
	    (increment-any (cdr counters)))))

Here `tif' is a macro just like `if', but it takes transactions
as its test and branches.  That's why the (null counters)
is wrapped up in a `trans'.  As you can infer, that means
the return value of `retry' and `try' are transactions.

Looking at the second clause tells us that this is a
standard car/cdr recursion.  We try to increment the
first counter, and if we fail, we try the rest of them.
The base case is where we call retry.  So if the list
is empty, the transaction is *aborted* and starts
from scratch again.  The transaction waits on all
the variables that have been read until `retry' was
called.  This guarantees that the transaction will
eventually commit.  Here is an example:

STM> (progn
       (defvar *c1* (new 'counter))
       (defvar *c2* (new 'counter)))
*C2*
STM> (acquire-lock (lock-of (count-of *c1*)))
T
STM> (acquire-lock (lock-of (count-of *c2*)))
T
STM> (perform (increment-any (list *c1* *c2*)))
[debugging output elided...]
STM> (values (value-of (count-of *c1*)) (value-of (count-of *c2*)))
0
0
STM> (release-lock (lock-of (count-of *c1*)))
NIL
STM> (unwait (count-of *c1*))
[debugging output elided...]
STM> (values (value-of (count-of *c1*)) (value-of (count-of *c2*)))
1
0

So that was just the same as yesterday.  But we can
do better.  `increment-any' is just a special case of
trying any transaction down a list, just like `map' is
a special case of apply a function down a list.  So
the equivalent would be:

(deftransaction try-list (transaction list)
  (tif (trans (null list))
       (retry)
       (try (funcall  transaction (car list))
	    (try-list transaction (cdr list)))))

And we could now define `increment-any' as:

(deftransaction increment-any (counters)
  (try-list #'increment counters))

Now running it gives us:

STM> (perform (increment-any (list *c1* *c2*)))
[debugging output elided...]
STM> (values (value-of (count-of *c1*)) (value-of (count-of *c2*)))
2
0

And indeed it works the same as before.  Indeed
we could even use `try-list' in many other situations,
like reading from a socket like Unix's select.

Now I am in a bit of a conundrum with regards to
the interface that CL-STM should have.  At the
moment I'm not happy with using all these new
macros like `progt', `progt1', `tif' and so on because
it means the programmer has to learn all these new
names that are just variations of the standard CL ones.
Its also a pain to figure out where to use `trans' and
`untrans'.

I've started some work on a code walker that transforms
CL forms into STM ones.  I have the equivalents of `tlet',
`progt' and `tif' implemented.  Even better is the code
walker handles macro expansion, so that `cond', and
`prog1' will be taken care of.  BTW, this code walker
will only traverse forms inside a `deftransaction'.

Ideally we'd like to write code without explicit `trans'
and `untrans'.  Even in the simple `increment-any'
example, we had to use `trans'.  It would be nice
if we could tell in advance whether or not a particular
expression is a transaction or not.  But Common Lisp
doesn't have a type system.  But here is what we know:

Forms like `(trans ...)' are transactions.

A form is a transaction if its car is a symbol defined with
`deftransaction'.  So (increment-any ...) is a transaction.

Assuming all transactions are take the form above,
we can infer that anything else is not a transaction.
So (null ...) is not a transaction, and thus the walker
can wrap it with `trans'.

The above analysis doesn't work for higher-order
functions.  It assumes incorrectly that (reduce ...)
is doesn't return a transaction.  But it could return
a transaction depending on the function passed
to it.  So the analysis only work on first-order
functions.

I'm wondering if this is the best we can do?  I've
still got more thoughts on this but now I'm asking
you.  What interface would you like?  Do you mind
writing `trans' and `untrans'?  Would you accept
a half-solution?  Whatever, just tell me whats on
your mind.  Did you have a good day?  Are you
following the world cup?

Hoan