Simon Peyton Jones: Beautiful concurrency

I am writing a chapter for a book called "Beautiful code", edited by Greg Wilson. My draft chapter is about Software Transactional Memory in Haskell.

I would welcome any comments or questions you have on the paper, or constructive suggestions for improving it; the more concrete the better.


The book is aimed at a general audience of programmers, not Haskell geeks, so I have tried to explain everything necessary as I go along. So if you are not a Haskell expert, your input would be particularly valuable to me.

You can post your comments on the Haskell wiki.

STM was discussed here many time before, of course. For me the original papers were easier to follow, but some may prefer the style of presentation used here.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

interesting book

Sounds like an interesting book, anyone know the subject of other chapters?

Sounds interesting

I'd be quite interested to read this. I don't suppose it might become available on a more mainstream format? PDF or HTML, say? I just spent the last 1/2 hour or so wrestling with Ghostscript to no avail. Sigh.

Use the Google...

...select the 'View as Text' option on Google Search page.

You probably want install

You probably want install Ghostview. If you are interested in following links to papers from LtU, you should probably get used to postscript.

PS error?

Actually, the PS file showed only blank pages for me, whereas they're usually no problem, and I had to convert it to a PDF with ps2pdf.

Ghostview opens the file ok

Ghostview opens the file ok here.

or buy a mac

sorry for being so obnoxious ;-)

Postscript experience

Yeah, the experience of opening the document was pretty painless on my Mac.

(sorry, see my other post below for "on-topic" discussion)

converting postscript to PDF

A bit off-topic, but...

http://www.ps2pdf.com/convert/index.htm is good if you only need this sort of thing occasionally.

You can also use Ghostscript to do the same thing.

When you install Ghostscript for Windows, you should get a batch file called 'ps2pdf' with it. (I accepted the defaults and it ended up in "C:\Program Files\gs\gs8.54\lib\").

Then make an environment variable called GSC that holds the full path to gswin32.exe (this file is part of Ghostscript too -- my copy ended up as "c:\Program Files\gs\gs8.54\bin\gswin32.exe"), and create a shortcut to 'ps2pdf' in your 'Send To' folder. You can then easily convert PS files from Windows Explorer from the context menu. The new PDF file ends up in the same folder as the postscript one.

Can we stop talking about file formats now?

Here's a PDF version. Enjoy, it's good.

Anyone care to discuss the

Anyone care to discuss the paper, or are we going to keep discussing the file format ;-)

Trying to "get it"

Speaking as a non-Haskell person, I had the following thoughts: The problem Peyton is referring to seems to be synchronizing of threads. One way around this is "messaging" in one form or another. In MFC there is a built in message system. This leads to an outrageous thought about Haskell. Can we think about monads as components processing messages. Typically the monad receives a message and returns a message. If this is a valid interpretation how does one interpret the three monad laws in this context?

Messaging

Isn't messaging how Erlang handles concurrency?

A message monad..

Specifically, "components processing messages" would be equivalent to "programs processing monads".

If this is what you are talking about--the message-passing model (basically), then yes, ala metaphor:

message-passing model<~>functional model
Message<~>Monad
Actor/Object<~>Program
Send-Recieve transaction<~>Monad application

Basically, if we were to implement a message-passing model, monads would be the data structure that stores "command" or "action" messages.

Melikesnot

I wish he'd chosen a more interesting example problem and that the STM primitives would suggest the solution.

Also nice if the URL for the source code worked :-)

motivation for monads?

If I understand it correcly, transactions can be re-tried only because Haskell differentiates between computations that have side effects and those that don't. In other words, "y=launchMissle()" is not something that can be 're-tried,' whereas "x=head(someList)" can be done/undone for ever.

Does that mean that if languages such as Java/C#/Python/etc. want to use transactional memory, they must learn to differentiate betweeen purely functional vs. side effect producing functions? Does that mean that it would be beneficial to provide Monads in those languages?

Erlang experience

The Mnesia database in Erlang uses a similar retry strategy but informally relies on the programmer to avoid side-effects in transactions. The practical experience is that some programmers are careful to always do the right thing and others aren't.

The situation in Erlang isn't ideal but I don't think monads and static types would be an appropriate solution there. More realistic would be for side-effects within transactions to cause a runtime exception (crash). I think the important thing is to avoid having incorrect programs that "seem to work" most of the time (like C programs with buffer-overrun vulnerabilities).

Is that what we call the "ST Monad"?

Is that what we call the "ST Monad"? The paper explains nicely why it is different from the IO monad (and why you can use STM inside the IO monad but not vice-versa). It does not a very good job of telling which one to use, mentioning "convenience" as a factor. There is a word about composability and maybe that should have been developed more.

Also, like for another reviewer the Santa Claus example passed over my head. It started nicely with a bank account, why not use that in the complete example?

STM != ST

I believe you may be confusing the ST monad with the STM monad. The ST monad is used for self-contained stateful computations. Suppose you want to write an imperative GCD function in Haskell for some perverse reason; you could write this monstrosity:

import Control.Monad.ST
import Data.STRef

gcd :: Integer -> Integer -> Integer
gcd a b = runST (imperativeGCD a b)
    where imperativeGCD a b =
            do aRef <- newSTRef a
               bRef <- newSTRef b
               tRef <- newSTRef 0  -- Temporary variable
               gcdLoop aRef bRef tRef
          gcdLoop aRef bRef tRef =
              do a <- readSTRef aRef
                 b <- readSTRef bRef
                 writeSTRef tRef b
                 writeSTRef bRef (a `mod` b)
                 t <- readSTRef tRef
                 writeSTRef aRef t
                 a <- readSTRef aRef
                 b <- readSTRef bRef
                 if (b /= 0) then gcdLoop aRef bRef tRef else return a

The thing about this is that, although it uses an imperative version of Euclid's algorithm, the function gcd is purely functional. That's what the ST monad is for. The STM monad is meant to carry out side-effects on variables that may be shared between threads, and it can't escape the IO monad.

Does that help, or did I misinterpret your post?

Re: STM != ST

Thanks, that clears things up.

I like your "monstruosity" :-)

Haskell seems to be a breeding ground for all kinds of programming concepts, without allowing them to tarnish its elegance. Too bad I still can't reconcile myself with functional-style programs (for more than a few lines). I should really look into a functional syntax that does not bend my head.

Anyone have the code?

As Luke Gorrie mentioned previously, the link in the paper isn't working and I've apparently done something seriously wrong typing it in---I'm getting a deadlock and I cannot figure out why. :-) (See http://www.crsr.net/files/Santa.hs for my sad version.)

Like Luke, I am not in love with the presentation---Section 3 feels forced and rather disorganized, and I wish he had gone from the bottom up rather than from the middle out. For example, the discussion of operateGate is broken into a brief mention where it is defined and a longer paragraph on why it is done the way it is at the end of that section.

Haskell and Erlang back-to-back

There's a comment on the chapter, as well as the Haskell
code and a comparable Erlang version, on this web page:
Solving the Santa Claus Problem in Erlang.

courtesy Richard O'Keefe

BR,
Ulf W

bug, not deadlock

I don't think STM ever claimed to eliminate bugs completely. :)

There's a typo in joinGroup: you're writing the out gate (g2) back to the TVar twice instead of g1 and g2.

http://liyang.hu/crap/Santa.hs

V2

There's now a version 2 of the paper, and a version 2 wiki page.

Error in the code?

Is it possible that the code for the incRef on page 3 contains an error? It seems like the first argument for the writeIORef is missing:


incRef :: IORef Int -> IO ()
incRef var = do { val <- readIORef var ; writeIORef (val+1) }

It seems to me that the last statement in the do construct should be writeIORef var (val+1). In any case, I cannot get the code to typecheck otherwise.

I have been looking at the pdf Peter Scott posted, btw.