STM in Clojure vs Haskell, why no retry or orElse?

[Tom Hall]

A few months ago I reread Simon Peyton Joneses article on STM in the
Beautiful Code book and decided to try and translate it into clojures
STM

See the paper here http://research.microsoft.com/pubs/74063/beautiful.pdf

He says 'Atomic blocks as we have introduced them so far are utterly
inadequate to coordinate concurrent programs. They lack two key
facilities: blocking and choice' so I guess the implication is
Clojures STM is inferior, any thoughts?

I had to use a constraint on a ref and try/catch to get the same
effect (though I hate using exceptions for control flow it does seem
to work)

https://github.com/thattommyhall/santa-claus/blob/master/src/santa/core.clj

I think a better solution might be had using watchers, how would you do it?
Any good links explaining differences in the STMs?

Cheers,
Tom

[vemv]

You can increase the chances of generating discussion by boiling down both the relevant content of paper and your program to a minimal, self-contained form.

Cheers - Victor

[Tom Hall]

OK, I guess the essence is:
Why does Clojure not need retry or orElse when another implementer of
STM considers them essential?
I'm guessing it's because clojures in MVCC but would like confirmation
and perhaps links to comparisons between STMs and maybe a guide to
Clojures.

How would you solve the Santa Claus Problem in Clojure?
I suggested watchers might be a good idea but am curious what others would do.
The original paper has a 2 page description of the problem if the
version I linked to is too verbose for people,
http://www.crsr.net/files/ANewExerciseInConcurrency.pdf


Cheers,
Tom

> --
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your
> first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to the Google Groups
> "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to clojure+u...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Philip Potter]

On 18 February 2013 12:30, Tom Hall <thatto...@gmail.com> wrote:
> OK, I guess the essence is:
> Why does Clojure not need retry or orElse when another implementer of
> STM considers them essential?

What are retry and orElse? What do they do?

> I'm guessing it's because clojures in MVCC but would like confirmation
> and perhaps links to comparisons between STMs and maybe a guide to
> Clojures.
>
> How would you solve the Santa Claus Problem in Clojure?
> I suggested watchers might be a good idea but am curious what others would do.
> The original paper has a 2 page description of the problem if the
> version I linked to is too verbose for people,
> http://www.crsr.net/files/ANewExerciseInConcurrency.pdf

Following links creates inertia, particularly when the links are pdfs
and when people are reading the list on mobile devices. For reference,
here is a one-paragraph description I found on google:

"Santa repeatedly sleeps until wakened by either all of his nine
reindeer, back from their holidays, or by a group of three of his ten
elves. If awakened by the reindeer, he harnesses each of them to his
sleigh, delivers toys with them and finally unharnesses them (allowing
them to go off on holiday). If awakened by a group of elves, he shows
each of the group into his study, consults with them on toy R&D and
finally shows them each out (allowing them to go back to work). Santa
should give priority to the reindeer in the case that there is both a
group of elves and a group of reindeer waiting."

Phil

[Tom Hall]

>> Why does Clojure not need retry or orElse when another implementer of
>> STM considers them essential?
> What are retry and orElse? What do they do?

I had hoped to get a reply from someone with experience of both, as
the quote suggests they are for blocking and choice (The article was
the first time I'd seen STM so am absolutely not an expert)

From the Haskell docs:
retry :: STM a
Retry execution of the current memory transaction because it has seen
values in TVars which mean that it should not continue (e.g. the TVars
represent a shared buffer that is now empty). The implementation may
block the thread until one of the TVars that it has read from has been
udpated. (GHC only)
(this is what made me think of watchers in clojure,
http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/add-watch)

orElse :: STM a -> STM a -> STM a
Compose two alternative STM actions (GHC only). If the first action
completes without retrying then it forms the result of the orElse.
Otherwise, if the first action retries, then the second action is
tried in its place. If both actions retry then the orElse as a whole
retries.

> "Santa repeatedly sleeps until wakened by either all of his nine
> reindeer, back from their holidays, or by a group of three of his ten
> elves. If awakened by the reindeer, he harnesses each of them to his
> sleigh, delivers toys with them and finally unharnesses them (allowing
> them to go off on holiday). If awakened by a group of elves, he shows
> each of the group into his study, consults with them on toy R&D and
> finally shows them each out (allowing them to go back to work). Santa
> should give priority to the reindeer in the case that there is both a
> group of elves and a group of reindeer waiting."

I think it's a shame he wrote the article around Christmas and chose a
less well known problem, I have looked at several Clojure Barbershop
Problem solutions so have a better idea now what an idiomatic solution
to this sort of problem might be.

Cheers Phil,
Tom

[Philip Potter]

On 18 February 2013 21:41, Tom Hall <thatto...@gmail.com> wrote:
>>> Why does Clojure not need retry or orElse when another implementer of
>>> STM considers them essential?
>> What are retry and orElse? What do they do?
>
> I had hoped to get a reply from someone with experience of both, as
> the quote suggests they are for blocking and choice (The article was
> the first time I'd seen STM so am absolutely not an expert)
>
> From the Haskell docs:
> retry :: STM a
> Retry execution of the current memory transaction because it has seen
> values in TVars which mean that it should not continue (e.g. the TVars
> represent a shared buffer that is now empty). The implementation may
> block the thread until one of the TVars that it has read from has been
> udpated. (GHC only)
> (this is what made me think of watchers in clojure,
> http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/add-watch)
>
> orElse :: STM a -> STM a -> STM a
> Compose two alternative STM actions (GHC only). If the first action
> completes without retrying then it forms the result of the orElse.
> Otherwise, if the first action retries, then the second action is
> tried in its place. If both actions retry then the orElse as a whole
> retries.

They sound like very interesting features. They also sound lower-level
than Clojure's STM -- if a Clojure STM transaction fails, it will
automatically retry until it succeeds (or hits
LockingTransaction/RETRY_LIMIT, currently 10000, when it throws an
exception.) Is this the case in Haskell?

Clojure automatically detects the conditions under which a transaction
is considered to have failed (modulo the need to avoid write skew with
the #'ensure fn) -- does Haskell provide this or are you expected to
do all the checking yourself and call retry directly? Does Haskell
provide a way to easily achieve Clojure's auto-retrying behaviour?

Given the behaviour, I don't think it would be possible to implement
retry or orElse without significant modifications to
LockingTransaction.java and possibly exposing a different set of
abstractions as STM primitives -- the retrying behaviour is written
into the java source:

https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/LockingTransaction.java#L252

>> "Santa repeatedly sleeps until wakened by either all of his nine
>> reindeer, back from their holidays, or by a group of three of his ten
>> elves. If awakened by the reindeer, he harnesses each of them to his
>> sleigh, delivers toys with them and finally unharnesses them (allowing
>> them to go off on holiday). If awakened by a group of elves, he shows
>> each of the group into his study, consults with them on toy R&D and
>> finally shows them each out (allowing them to go back to work). Santa
>> should give priority to the reindeer in the case that there is both a
>> group of elves and a group of reindeer waiting."
>
> I think it's a shame he wrote the article around Christmas and chose a
> less well known problem, I have looked at several Clojure Barbershop
> Problem solutions so have a better idea now what an idiomatic solution
> to this sort of problem might be.
>
> Cheers Phil,
> Tom
>

[Ben Wolfson]

On Tue, Feb 19, 2013 at 2:28 AM, Philip Potter
<philip....@gmail.com> wrote:
>
> They sound like very interesting features. They also sound lower-level
> than Clojure's STM -- if a Clojure STM transaction fails, it will
> automatically retry until it succeeds (or hits
> LockingTransaction/RETRY_LIMIT, currently 10000, when it throws an
> exception.) Is this the case in Haskell?

I don't know if there's a limit, but transactions retry automatically,
and transaction failure is detected automatically. I'm confused by the
characterization of orElse as lower-level than Clojure's STM: it's a
way of combining two independent STM actions and thus strikes me as a
higher-level operation.

Here's the way "retry" is introduced in "Beautiful Concurrency":

"""
Atomic blocks as we have introduced them so far are utterly inadequate to
coordinate concurrent programs. They lack two key facilities: blocking and

choice. In this section I’ll describe how the basic STM interface is elaborated
to include them in a fully-modular way.

Suppose that a thread should block if it attempts to overdraw an account (i.e.
withdraw more than the current balance). Situations like this are common in
concurrent programs: for example, a thread should block if it reads from an
empty buffer, or when it waits for an event. We achieve this in STM by adding
the single function retry, whose type is

retry :: STM a

Here is a modified version of withdraw that blocks if the balance would go
negative:

limitedWithdraw :: Account -> Int -> STM ()
limitedWithdraw acc amount
= do { bal <- readTVar acc
; if amount > 0 && amount > bal
then retry
else writeTVar acc (bal - amount) }
"""

So it isn't really about restarting failed transactions because (e.g.)
someone else has written to the ref while we've been executing, but
detecting a case within an otherwise successful transaction---where
"successful" means "we can read and write to all these refs with no
problem"---where we actually want to start over and wait until some
values have changed.

--
Ben Wolfson
"Human kind has used its intelligence to vary the flavour of drinks,
which may be sweet, aromatic, fermented or spirit-based. ... Family
and social life also offer numerous other occasions to consume drinks
for pleasure." [Larousse, "Drink" entry]

[Mark Engelberg]

On Mon, Feb 18, 2013 at 1:41 PM, Tom Hall <thatto...@gmail.com> wrote:

I think it's a shame he wrote the article around Christmas and chose a
less well known problem, I have looked at several Clojure Barbershop
Problem solutions so have a better idea now what an idiomatic solution
to this sort of problem might be.

I wrote a Clojure solution to the Santa Claus problem several years ago for my own edification.  I haven't thought about the problem in a while, but in case the code is useful to you, here it is:
https://gist.github.com/Engelberg/4988711