Personal tools

Talk:SantaClausProblem

From HaskellWiki

Revision as of 08:20, 27 December 2006 by Gaal (Talk | contribs)

Jump to: navigation, search

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 email me directly (simonpj@microsoft.com), or add Wiki talk notes below.


Simonpj 14:26, 22 December 2006 (UTC) To add a note, begin with four tilde signs ~~~~; the Wiki will fill in your user name and date.


ArthurVanLeeuwen 16:25, 22 December 2006 (UTC) There's a couple of typos in the paper as it is now. More importantly, the footnote on page 2 has (hGetLine h "hello") where it should state (hPutStr h "hello").

Neil Mitchell 16:28, 22 December 2006 (UTC) Sect 1, Para 2. If we want to write parallel program[s] - missing s.


Steven807 17:14, 22 December 2006 (UTC) There is no definition or description of check

Tibbe 18:33, 22 December 2006 (UTC); The footnote on page 2 now has a incorrectly capitalized T in hPutSTr.

Fanf 18:51, 22 December 2006 (UTC) page 1 para 2 "as well shall see" should be "as we shall see"

Fanf 18:51, 22 December 2006 (UTC) page 3 "a bit like *t in C" should be "a bit like t* in C" since t is a type

Garious 18:56, 22 December 2006 (UTC) page 10 "at which point An elf" should be "at which point an elf"

Garious 18:58, 22 December 2006 (UTC) page 10 "Here, then is a possible" should be "Here then, is a possible"

Garious 19:16, 22 December 2006 (UTC) page 11 "Again, we define Group is declared" whaaa? maybe: "Group is declared as a data type with constructor MkGroup. MkGroup is passed the Group's capacity, and a TVar containing the number of current members and the Group's two Gates."

Garious 19:16, 22 December 2006 (UTC) page 11 "Creating a new Group is simply..." Is a process of three somewhat-abstract steps simple enough to say 'simply'? Instead, maybe show the code and let the reader think, "Hey, that's simple!"

Rycee 20:46, 22 December 2006 (UTC) Page 4. You probably want to change "... the action a does ..." to "... the action act does ..."

Rycee 20:46, 22 December 2006 (UTC) Page 8. Typographic nitpick: The space after "i.e." looks wide, perhaps you forgot to write "i.e.\ " to force a regular (non sentence ending) space in LaTeX?

MichalPalka 22:32, 22 December 2006 (UTC) You could add a reference to SQL and triggers. They are similar in that it is programming with transations and seeing familiar names will make applied programmers feel more comfortable.

DavidHouse 22:55, 22 December 2006 (UTC) Page 3, "That is, return v is a function that, when performed, does no side effects and returns v." Your use of 'that is' implies that you could deduce the fact that it does no side effects from the type signature just given, which isn't true. It's an auxiliary property of 'return'. Maybe just miss out the 'that is'.

DavidHouse 23:04, 22 December 2006 (UTC) Bottom of Page 4, "Then 'atomically act' grabs the lock, performs the action 'at',". Missing 'c' out of 'at'.

DavidHouse 23:23, 22 December 2006 (UTC) Page 5, "Then 'withdraw' is an STM action that adds amount to the balance in the account." 1) For consistency with the rest of the paper, it should be "Then 'withdraw account ammount'..." 2) withdraw subtracts, not adds, to the amount in the account.

DavidHouse 23:40, 22 December 2006 (UTC) Page 9, you probably want to mention that ++ is string concatenation.

DavidHouse 23:45, 22 December 2006 (UTC) Page 10, I would expect to see the type signatures for the Gate interface rewritten alongside their definitions.

DavidHouse 23:47, 22 December 2006 (UTC) Page 9/10, algebraic datatypes are a little weird for the non-initiated, especially with constructors that don't appear to do anything ("Where do you define MkGate?" etc.). You might want to liken them to C's structs, and explain the constructors as tags?

DavidHouse 23:57, 22 December 2006 (UTC) Page 13, I don't think you sufficiently explain 'sequence'. You may wish to add a sentence along the lines of "'sequence' is a function that takes a list of IO actions and returns the action that, when executed, runs each of the actions you passed it in turn."

Dalejordan 02:15, 23 December 2006 (UTC) For the sake of us newbs you might mention in Section 2.1 how all these actions ever get performed. Also, in your description of nTimes I think it would be clearer to say it creates a composite action that performs its argument action n times, rather than say it performs it (directly) n times, even though the value of n is not yet known. Another example of the "beauty" of first class actions (and recursion).

Brecknell 03:29, 23 December 2006 (UTC) Page 7: withdraw should subtract, not add amount to the balance (sadly). Also, since this withdraw has different semantics to the version on p5, you may want to consider giving it a different name.

Brecknell 03:29, 23 December 2006 (UTC) Page 8, towards the end of section 2.4: Two instances of "withdraw" should be "withdraw2", one in the function definition and one in the comment.

Brecknell 05:04, 23 December 2006 (UTC) In the problem definition, "Santa repeatedly sleeps until wakened...", but with the definition of "forever" given in the text, and without some sort of asynchronous signalling, it looks to me like Santa will sleep for at least as long as his random number generator tells him to. Perhaps move the sleep out of forever and into elf and reindeer, then Santa will just sleep in awaitGroup.

Mvanier 19:21, 23 December 2006 (UTC) In section 3.3, "sequence" might as well just be "sequence_". It's confusing to return a list of unit values and not do anything with them. In section 5, I think that the problem with composing lock-based concurrent functions could be explained better; the statement "instead we must expose the locking protocol" could be expanded to show why this is the case.

ChrisKuklewicz 22:17, 24 December 2006 (UTC) In learning Haskell STM back in October of 1995 I had written a solution to the same Santa problem. The main suggestion I have is that the elf and reindeer are given two actions (use Gate inGate) and (useGate outGate) and are required to properly bracket their actual action between these two. If the (joinGroup group) call returned a single scoping combinator (bracket_ (useGate inGate) (useGate outGate)) then the concurrency model for the elf and reindeer would be even to get correct (and beautiful?). Furthermore they could be passed (joinGroup group) instead of (group). This prevents the elf and reindeer from calling any other group functions.

Conal 16:39, 25 December 2006 (UTC) Page 11, first full paragraph, "then waits to the TVar to be decremented to zero." Replace "waits to" with "waits for".

Brecknell 03:41, 27 December 2006 (UTC) This was my first exposure to STM, and I found it clear and easy enough to follow. However, I think it is mainly the discussion of bank accounts that conveys the "beauty" of STM, since that's where the important concepts are demonstrated: composability of transactions, implicit locking and deadlock avoidance, etc. In the Santa Claus problem, those concepts are somewhat obscured. I think the Santa Claus problem is still useful for demonstrating how STM can handle a tricky concurrency scenario with relative ease, but it didn't give me the sense of clarity that the discussion of bank accounts did. Maybe the Santa Claus solution needs more focus on the abstractions possible in STM, how they can help modularise concurrent programs, and why STM is better for solving concurrency problems than the concurrency primitives available elsewhere.

Gaal 08:20, 27 December 2006 (UTC) The binding and usage of the reindeer group on page 12 are inconsistent:

 ; rein_gp <- newGroup 9
 ; sequence [ reindeer gp n | n <- [1 .. 9]]
                    -- ^^
 ; forever (santa elf_group rein_group)