Personal tools

Talk:SantaClausProblem

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(I/O: You still need to use locks.)
 
(25 intermediate revisions by 12 users not shown)
Line 1: Line 1:
 
= Beautiful concurrency =
 
= Beautiful concurrency =
   
I am writing a chapter for a book called "Beautiful code", edited by Greg Wilson. My [http://research.microsoft.com/~simonpj/tmp/beautiful.ps draft chapter] is about Software Transactional Memory in Haskell.
+
I have written a chapter for a book called "Beautiful code", edited by Greg Wilson. The chapter is a tutorial about Software Transactional Memory in Haskell. The book is aimed at a general audience of programmers, <em>not</em> Haskell geeks, so I have tried to explain everything necessary as I go along.
   
I would welcome any comments or questions you have on the paper, or constructive suggestions for improving it; the more concrete the better.
+
You can find the paper itself, and the code download [http://research.microsoft.com/~simonpj/papers/stm here]. This Wiki talk-page is a place to contribute any post-publication thoughts or observations about the paper, if you wish.
 
The book is aimed at a general audience of programmers, <em>not</em> 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.
 
 
If you give your real name somewhere in your text (or email it to me), I'll add you to the acknowledgements at the end of the chapter.
 
   
 
----------
 
----------
Line 9: Line 9:
 
[[User:Simonpj|Simonpj]] 14:26, 22 December 2006 (UTC) To add a note, begin with four tilde signs <nowiki>~~~~</nowiki>; the Wiki will fill in your user name and date.
 
[[User:Simonpj|Simonpj]] 14:26, 22 December 2006 (UTC) To add a note, begin with four tilde signs <nowiki>~~~~</nowiki>; the Wiki will fill in your user name and date.
   
----------
+
[[User:Croach|Croach]] 17:10, 21 February 2007 (UTC)I just wanted to mention that it appears there is a small typo in the example code on page 2 of the paper. In the code you have a synchronized method called "withdraw" which you use again in the non-synchronized "deposit" method, only here you call the "withdraw" method "withdrawn". By the way, absolutely wonderful paper. I've been trying to learn everything I can about both Haskell and STM in the past few months and not only did this paper greatly increase my knowledge of STM, but it also helped increase my understanding of the basics of Haskell, which I already assumed I had a good grasp on. So, thank you for this work, it was an absolute joy to read.
 
[[User:ArthurVanLeeuwen|ArthurVanLeeuwen]] 16:25, 22 December 2006 (UTC) (SLPJ: done) 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").
 
 
[[User:NeilMitchell|Neil Mitchell]] 16:28, 22 December 2006 (UTC) (SLPJ: done) Sect 1, Para 2. If we want to write parallel program[s] - missing s.
 
 
 
[[User:Steven807|Steven807]] 17:14, 22 December 2006 (UTC) (SLPJ: there is in fact, in 2.4; but it needs a backward ref.) There is no definition or description of '''check'''
 
 
[[User:Tibbe|Tibbe]] 18:33, 22 December 2006 (UTC); (SLPJ: done)The footnote on page 2 now has a incorrectly capitalized T in hPutSTr.
 
 
[[User:Fanf|Fanf]] 18:51, 22 December 2006 (UTC) (SLPJ: done)page 1 para 2 "as well shall see" should be "as we shall see"
 
 
[[User:Fanf|Fanf]] 18:51, 22 December 2006 (UTC) (SLPJ: done)page 3 "a bit like *t in C" should be "a bit like t* in C" since t is a type
 
 
[[User:Garious|Garious]] 18:56, 22 December 2006 (UTC) (SLPJ: done) page 10 "at which point An elf" should be "at which point an elf"
 
 
[[User:Garious|Garious]] 18:58, 22 December 2006 (UTC) (SLPJ: done) page 10 "Here, then is a possible" should be "Here then, is a possible"
 
 
[[User:Garious|Garious]] 19:16, 22 December 2006 (UTC) (SLPJ: done) 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."
 
 
[[User:Garious|Garious]] 19:16, 22 December 2006 (UTC) (SLPJ: done) 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!"
 
 
[[User:Rycee|Rycee]] 20:46, 22 December 2006 (UTC) (SLPJ: done) Page 4. You probably want to change "... the action a does ..." to "... the action act does ..."
 
 
[[User:Rycee|Rycee]] 20:46, 22 December 2006 (UTC) (SLPJ: done) 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?
 
 
[[User:MichalPalka|MichalPalka]] 22:32, 22 December 2006 (UTC) (SLPJ: hard to konw what is "familiar" to a random reader. For a reader unfamiliar with SQL and triggers, referring to that might just make it more confusing. What do others think?) 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.
 
 
[[User:DavidHouse|DavidHouse]] 22:55, 22 December 2006 (UTC) (SLPJ: done) 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'.
 
 
[[User:DavidHouse|DavidHouse]] 23:04, 22 December 2006 (UTC)(SLPJ: done) Bottom of Page 4, "Then 'atomically act' grabs the lock, performs the action 'at',". Missing 'c' out of 'at'.
 
 
[[User:DavidHouse|DavidHouse]] 23:23, 22 December 2006 (UTC) (SLPJ: done) 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.
 
 
[[User:DavidHouse|DavidHouse]] 23:40, 22 December 2006 (UTC) (SLPJ: done at defn of hEchoLine) Page 9, you probably want to mention that ++ is string concatenation.
 
 
[[User:DavidHouse|DavidHouse]] 23:45, 22 December 2006 (UTC) (SLPJ: done)Page 10, I would expect to see the type signatures for the Gate interface rewritten alongside their definitions.
 
 
[[User:DavidHouse|DavidHouse]] 23:47, 22 December 2006 (UTC) (SLPJ: difficut to do this crisply, but I take the point) 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?
 
 
[[User:DavidHouse|DavidHouse]] 23:57, 22 December 2006 (UTC) (SLPJ: done) 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."
 
 
[[User:Dalejordan|Dalejordan]] 02:15, 23 December 2006 (UTC) (SLPJ: done) 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).
 
 
[[User:Brecknell|Brecknell]] 03:29, 23 December 2006 (UTC) (SLPJ: done) 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.
 
 
[[User:Brecknell|Brecknell]] 03:29, 23 December 2006 (UTC) (SLPJ: done) 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.
 
 
[[User:Brecknell|Brecknell]] 05:04, 23 December 2006 (UTC) (SLPJ: done) 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.
 
 
[[User:Mvanier|Mvanier]] 19:21, 23 December 2006 (UTC) (SLPJ: done) 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.
 
 
[[User:ChrisKuklewicz|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.
 
 
[[User:Conal|Conal]] 16:39, 25 December 2006 (UTC) (SLPJ: done) Page 11, first full paragraph, "then waits to the TVar to be decremented to zero." Replace "waits to" with "waits for".
 
 
[[User:Brecknell|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.
 
 
[[User:Gaal|Gaal]] 08:20, 27 December 2006 (UTC) (SLPJ: done) 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)
 
   
[[User:Fernando|Fernando]] 14:11, 29 December 2006 (UTC) In page 3, in the definition of incRef, the last line should probably read, writeIORef var (val+1), instead of writeIORef (val+1). The latter version won't compile.
 
   
[[User:Prb|PaulRBrown]] 07:11, 2 January 2007 (UTC) It would be convenient if the download link for the source code were active. (Otherwise, reviewers have to cut and paste the fragments in by hand.)
+
[[User:CloudiDust|CloudiDust]] 16:24, 25 February 2007 (UTC) Thanks very much for this wonderful paper! I'm gaining a lot from it now as both a newbie to Haskell and one to concurrency. Here are the typos I have found:
   
[[User:Prb|PaulRBrown]] 07:11, 2 January 2007 (UTC) I had trouble with the motivation for the Santa Claus example, and I ended up resorting to scratch paper to sketch out the problem and the model. That section would benefit from some additional introduction, perhaps a diagram. (Something schematic with "(n of m) || (p of q)" would be nice.) You could also explain it in terms of concurrency APIs that people are familiar with, e.g., count-down semaphores in Java's concurrency package. In fact, the additional development of the counting barrier prior to the Santa Claus problem would help overall clarity.
+
A. There is no "Int" but "int" in java. (I suppose they are java codes. :)
   
: [[User:DavidHouse|DavidHouse]] 10:30, 2 January 2007 (UTC) I actually had trouble with this one too. I think even the addition of a sentence like the following would help a great deal: "We want to model this setup in Haskell, where 'sleeping' is blocking and 'waking up' is doing something."
+
B. In the code at the beginning of Page 3, there seems to be a semicolon missing after "to.unlock()".
   
[[User:EricWilligers|EricWilligers]] 12:43, 4 January 2007 (UTC) Page 4: As page 14 currently contains a leap in difficulty with the definition of choose, perhaps foldr1 could be introduced before the last paragraph of 2.1, with an example call. This would also be an opportunity to introduce [ ] in a type signature - it does appear with regards to "sequence" but is easy to miss as the return value isn't discussed. A simple example would avoid (op) notation and would make no sense for empty lists. e.g. max_n values = foldr1 max_2 values
+
C. In the Footnote 2 in Page 5, the sentence "That’s because Haskell supports currying, which can you can ..." seems to duplicate a "can", and there seems to be a right parenthesis missing after "e.g. [13]".
   
[[User:EricWilligers|EricWilligers]] 12:43, 4 January 2007 (UTC) Page 10: Missing closing ) at the end of useGate
+
I'm now busy translating this paper into Chinese, and will feedback as often as I can. I wonder whether I can put my translation on the net and if so which license could I use? Many thanks again!
   
[[User:EricWilligers|EricWilligers]] 12:43, 4 January 2007 (UTC) Page 12: elf_group => elf_gp, rein_group => rein_gp
+
[[User:TuukkaH|TuukkaH]] 22:07, 23 June 2007 (UTC) What can we say about the relation to message passing: [http://www.cs.otago.ac.nz/staffpriv/ok/santa/index.htm Solving the Santa Claus Problem in Erlang]?
   
[[User:EricWilligers|EricWilligers]] 12:43, 4 January 2007 (UTC) Page 13: elf-gp 1 => elf_gp 1
+
[[User:ChrisKuklewicz|ChrisKuklewicz]] 14:08, 25 June 2007 (UTC) In response to [[User:TuukkaH|TuukkaH]], I have posted code at [[Santa]] which is just a short adaptation of the Erlang to Haskell using just Chan and TChan (to get orElse).
   
[[User:EricWilligers|EricWilligers]] 12:43, 4 January 2007 (UTC) Page 14 and page 8 claim all the code is presented. To meet this claim:-
+
[[User:TuukkaH|TuukkaH]] 14:33, 5 July 2007 (UTC) Thanks ChrisKuklewicz! I interpret that as Haskell supporting message passing better than Erlang, and it actually being a subconcept in STM too.
Perhaps the following can appear on p9, just before "Since IO actions are first-class, ..."
 
<haskell>
 
deliverToys :: String -> IO ()
 
deliverToys s = putStr (s ++ " delivering toys\n")
 
</haskell>
 
Perhaps the following can appear on p13, just before "Working inside-out, ..."
 
<haskell>
 
reindeer :: Group -> Int -> IO ()
 
reindeer gp id = forkIO (forever (reindeer1 gp id))
 
</haskell>
 
Alternately, perhaps deliverToys and reindeer could appear in section 3.5 so they don't affect the flow in 3.1 and 3.3.
 
   
[[User:Brianh|Brian Hulley]] 22:06, 4 January 2007 (UTC) Page 5: Trivial typo "be execute simultaneously" should be "execute simultaneously" or "be executed simultaneously". I spent ages trying to understand why the 'brutal lock' method wouldn't ensure isolation then I realised it was that I'd just assumed all other threads would be stopped dead in their tracks while the atomic block was running whereas if I'd read the text more carefully I'd have seen that the lock indeed only applies to actions wrapped in <hask>atomically</hask>. I think if you said something like "if a thread is accessing an IORef while holding the <hask>atomically</hask> lock there is nothing to stop a *different* thread from accessing the same IORef directly at the same time" it would help emphasise the fact that other threads can still be running even though only one thread can be in an atomic block at any given time.
+
[[User:Alisezgin|Alisezgin]] 12:59, 31 December 2007 (UTC) it was a good read. i will have to look into a more detailed exposition pretty soon. but one quick question:
   
[[User:Brianh|Brian Hulley]] 09:49, 5 January 2007 (UTC)
+
from what i understand, an atomic block can only have side effects on stm variables. what if i want to have a block of io instructions (like launchmissiles) that need to be executed with no intervening instructions/threads, that is, atomically? this is of course assuming that rolling back will not be needed for this specific block. is this something that is fundamentally disallowed because it is poor programming practice? admittedly, i am no concurrent programmer so i am not familiar with what might come up while designing a concurrent system.
* Page 6: re-execution: this looks like you could end up in an infinite loop since if thread A needs to do something complicated in an atomic block while thread B just sits in a tight loop continuously incrementing the same TVar (used by A) then A would probably always have an invalid view of memory by the time it was ready to validate. Does the implementation address this problem?
 
* Page 10: No definition for <hask>check</hask>. Section 2.4 only defines <hask>retry</hask> so perhaps section 3.2 should include:
 
<haskell>
 
check c = if not c then retry() else return ()
 
</haskell>
 
(to avoid introducing yet another Haskell function <hask>unless</hask>)
 
* Page 12: Use of <hask>sequence</hask> and list comprehensions seems more complicated than something like:
 
<haskell>
 
mapM_ (elf elf_gp) [1..10]
 
</haskell>
 
* Page 16: Section 5 on locks. It seems to me that STM solves these problems by just conceptually using a single lock (the 'brute force' lock on <hask>atomically</hask>) but a clever thing about STM is that it gets the simplicity of just having a single global lock without the performance penalty due to the use of logging (ie the global lock is only held for the duration of the validate and commit instead of for the whole duration of the atomic block).
 
These are just minor points though - I thought it was a really good intro to STM - I've never used/looked at STM before now and yet after reading just this one chapter I feel I've got enough understanding to start using it - Thanks.
 
   
[[User:EricWilligers|EricWilligers]] 01:02, 7 January 2007 (UTC) (Disclaimer: I tested using GHC 6.4.2, was hoping to test with 6.6 but haven't.) I needed to change elf and reindeer due to a compilation error - Expected type: IO (), Inferred type: IO ThreadId. Each of the following worked:-
+
[[User:Cjs|Cjs]] 08:12, 6 January 2009 (UTC) For I/O, you need to use locks. STM isn't a pancea. The reason the whole rollback thing works so well for STM in Haskell (it's a major problem in most non-Haskell STM implementations) is because the code run in the STM monad is pure (i.e., can't do I/O).
<haskell>
 
elf :: Group -> Int -> IO ()
 
elf gp id = do { _ <- forkIO (forever (elf1 gp id)) ; return () }
 
</haskell>
 
<haskell>
 
elf :: Group -> Int -> IO ThreadId
 
elf gp id = forkIO (forever (elf1 gp id))
 
</haskell>
 
<haskell>
 
elf gp id = forkIO (forever (elf1 gp id))
 
</haskell>
 
The last option avoids the need to mention ThreadId.
 

Latest revision as of 08:12, 6 January 2009

[edit] Beautiful concurrency

I have written a chapter for a book called "Beautiful code", edited by Greg Wilson. The chapter is a tutorial about Software Transactional Memory in Haskell. 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.

You can find the paper itself, and the code download here. This Wiki talk-page is a place to contribute any post-publication thoughts or observations about the paper, if you wish.


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.

Croach 17:10, 21 February 2007 (UTC)I just wanted to mention that it appears there is a small typo in the example code on page 2 of the paper. In the code you have a synchronized method called "withdraw" which you use again in the non-synchronized "deposit" method, only here you call the "withdraw" method "withdrawn". By the way, absolutely wonderful paper. I've been trying to learn everything I can about both Haskell and STM in the past few months and not only did this paper greatly increase my knowledge of STM, but it also helped increase my understanding of the basics of Haskell, which I already assumed I had a good grasp on. So, thank you for this work, it was an absolute joy to read.


CloudiDust 16:24, 25 February 2007 (UTC) Thanks very much for this wonderful paper! I'm gaining a lot from it now as both a newbie to Haskell and one to concurrency. Here are the typos I have found:

A. There is no "Int" but "int" in java. (I suppose they are java codes. :)

B. In the code at the beginning of Page 3, there seems to be a semicolon missing after "to.unlock()".

C. In the Footnote 2 in Page 5, the sentence "That’s because Haskell supports currying, which can you can ..." seems to duplicate a "can", and there seems to be a right parenthesis missing after "e.g. [13]".

I'm now busy translating this paper into Chinese, and will feedback as often as I can. I wonder whether I can put my translation on the net and if so which license could I use? Many thanks again!

TuukkaH 22:07, 23 June 2007 (UTC) What can we say about the relation to message passing: Solving the Santa Claus Problem in Erlang?

ChrisKuklewicz 14:08, 25 June 2007 (UTC) In response to TuukkaH, I have posted code at Santa which is just a short adaptation of the Erlang to Haskell using just Chan and TChan (to get orElse).

TuukkaH 14:33, 5 July 2007 (UTC) Thanks ChrisKuklewicz! I interpret that as Haskell supporting message passing better than Erlang, and it actually being a subconcept in STM too.

Alisezgin 12:59, 31 December 2007 (UTC) it was a good read. i will have to look into a more detailed exposition pretty soon. but one quick question:

from what i understand, an atomic block can only have side effects on stm variables. what if i want to have a block of io instructions (like launchmissiles) that need to be executed with no intervening instructions/threads, that is, atomically? this is of course assuming that rolling back will not be needed for this specific block. is this something that is fundamentally disallowed because it is poor programming practice? admittedly, i am no concurrent programmer so i am not familiar with what might come up while designing a concurrent system.

Cjs 08:12, 6 January 2009 (UTC) For I/O, you need to use locks. STM isn't a pancea. The reason the whole rollback thing works so well for STM in Haskell (it's a major problem in most non-Haskell STM implementations) is because the code run in the STM monad is pure (i.e., can't do I/O).