Talk:SantaClausProblemV2

From HaskellWiki
Jump to navigation Jump to search

Beautiful concurrency

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

After a lot of useful feedback, I have now completed Version 2 of the paper. The Haskell code is also available.

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 see what people said about version 1 on the version 1 talk page: Talk:SantaClausProblem .

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.

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. Notably, I'd like to acknowledge Steven807, Mvanier, Fernando, Gknauth, EngineerScotty, BoAdler, Schmitz, Genneth, Pitarou, Asilovy.

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.

Brecknell 13:38, 11 January 2007 (UTC) In Figure 1, retry should be STM a, not STM (). (SLPJ: done)

Sylvain 13:45, 11 January 2007 (UTC) small points: since you go through explaining that the do-notation is overloaded and works for STM as well as IO (page 8), you might want to tell the same for return on page 11 (return being given with a type a -> IO a on page 5). (SLPJ: done) There is also a double "Here is the code" at the bottom of page 17. (SLPJ: done)

Brecknell 13:59, 11 January 2007 (UTC) The rewrite of the paragraph at top of page 17 has left behind a fragment that I think just needs to be deleted: "just runs each of the actions in sequence".(SLPJ: done)

Brecknell 14:15, 11 January 2007 (UTC) Last sentence of page 18: "Here is another way approach that..." Delete either "way" or "approach". (SLPJ: done)

ArthurVanLeeuwen 14:27, 11 January 2007 (UTC) (SLPJ: done) minor stuff, really:

  • page 2, middle of page: syncrhonized -> synchronized
  • page 5, top of page: For example, here are two Haskell functions -> For example, here are the type signatures for two Haskell functions (the functions themselves may be primitives, after all)
  • page 5, second paragraph: do the parentheses around hPutStr serve more than to confuse? Especially given their absence for hEchoLine...
  • page 5, footnote 3: comma after effects
  • page 6: make discarding the return value of forkIO in the second example main more explicit, e.g. with a footnote
  • page 7, after Atomicity: This ensured -> This ensures

Brecknell 14:32, 11 January 2007 (UTC) I like the way you build up to the definition of "choose" in this new revision. I think this helps to convey how STM and actions as first-class values can improve modularity and composability in concurrent applications. So, if you like, you can consider my lsat comment on the previous revision "done", as well.

Maeder 14:38, 11 January 2007 (UTC) (SLPJ: done)

  • page 11, use subtract (+ -> -) in limitedWithDraw
  • page 22 (2nd line), the the -> the

Genneth 15:07, 11 January 2007 (UTC) p4: make analogy between () and void to help non-haskellers (SLPJ: done)

ArthurVanLeeuwen 15:10, 11 January 2007 (UTC) The bottom of page 17 has 'Here is his code:' in duplicate. (SLPJ: done)

ArthurVanLeeuwen 15:19, 11 January 2007 (UTC) The note 'The code for choose is brief, but a little mind-bending:' on page 19 is very short, for such a leap in required understanding. In just one single block of 7 lines you introduce both the concept of IO actions encapsulated inside STM actions as well as the concept of list comprehension. For a non-haskeller this is quite a lot. (SLPJ: True; but I'm not sure whether to say more, or less! Or just leave it)

Maeder 15:25, 11 January 2007 (UTC) maybe generalize nTimes on page 7 to type: Int -> (Int -> IO ()) -> IO () and use nTimes on page 16 instead of sequence_ and list comprehensions. (The function choose on page 19 is also higher order.) (SLPJ: I decide to leave it)

Malcolm 15:27, 11 January 2007 (UTC) (SLPJ: done)

  • Intro, para 2, "Sadly, parallel program[s] are" - missing plural
  • sec 2.1, para 3, "if two thread[s] call" - missing plural
  • sec 3.2, Atomicity, "This ensured that" -> "This ensures that"

Maeder 15:35, 11 January 2007 (UTC) maybe use putStrLn (hPutStrLn) instead of \n in the strings (SLPJ: actually this does not work well. When concurrent threads do putStrLns, the newlines can be separated form the lines they follow. This doesn't happen with putStr. In principle it could happen with putStr too; GHC makes no guarantees about interleaving. The Right Thing would be to use more locking etc, but I thought that was too big a distraction.)

Malcolm 16:07, 11 January 2007 (UTC) (SLPJ: done)

  • page 11, limitedWithdraw2 in type signature, is called simply withdraw2 in definition
  • sec 4.2 "remaining capactity" -> "remaining capacity" (x3)
  • sec 4.3 "newGate makes [a] new Gate" - missing article
  • top of page 17, orphan (non-)sentence ". just runs each of the actions in sequence."
  • sec 4.4, "futher" -> "further"
  • sec 4.4 "another way approach" -> "another approach"
  • sec 6 "exectued" -> "executed"
  • sec 6 "the the treatment" -> "the treatment"

Jmuk 04:14, 12 January 2007 (UTC) page 13, semicolons in helper1 are out of alignment (SLPJ: done)

Fanf 19:34, 12 January 2007 (UTC) (SLPJ: done) Minor nits:

  • p.2: need semicolon at end of last java statement in each function.
  • p.2: should you comment that the class has a withdraw method similar to the deposit method?
  • p.4 paragraph about locks: you introduce the word "compositional" here - perhaps better to stick with "modular"?
  • bottom of p. 4: should "can" be omitted, or should it read "we must explain"?
  • bottom of p. 7: inconsistent tense: began -> begins.
  • Should the layout of the do notation be more like normal C layout, to avoid freaking out the mundanes?
  • would openGate be a clearer name for operateGate?
  • footnote p. 14: mkGate -> MkGate
  • santa's code: perhaps a comment between two gates to note that the elves or reindeers do their things at that point.
  • limitedWithdraw: is the test (amount > 0) redundant?

Fanf 19:45, 12 January 2007 (UTC) (SLPJ: hmm... I'm re-using the description in earlier papers) Section 4 introduction: The description of the problem reads like a description of an implementation, and I think it should be more story-like. e.g.

Santa spends most of his time asleep. On Christmas Eve, his nine reindeer return from their holidays and wake up Santa. He harnesses each of them to his sleigh, delivers toys with them and finally unharnesses them, allowing them to return to their holidays. All year his ten elves are busy working to make toys, but every so often they will need to consult Santa about toy R&D in his study. Santa will only wake up and talk to three of them at a time, and of course their consultations are a lower priority than delivering toys.

  • p.13 perhaps "sleep" should be "delay" for consistency with the terminology in the code, and to avoid confusion with what santa does - the elves are making toys during the delay, not sleeping. (SLPJ: done)
  • Also, is it worth noting that the reindeer gates model the harnessing and unharnessing? (SLPJ: not sure. Anyone else?)

Justin Bailey 20:35, 12 January 2007 (UTC) Really interesting paper. I've only been exposed to Haskell (through a graduate Programming Languages course) for 4 or 5 months, but I found it very readable. My comments:

  • The introduction showing problems with locks and how atomically can be used in the bank account example is very well done.
  • Development of the gate operations is pretty clear. It would have helped if a short gloss on the connection between the whimsical problem statement and the opening/closing of gates was made. Re-reading, you do cover it in one paragraph on p.13. Sadly, I'd forgotten a lot of that by the time I got to reading about the implementation of Gates and Groups. Maybe make connections throughout that section?
  • I agree with ArthurVanLeeuwen above about the choose function. It's extremely mind-bending. I didn't event notice actions was a list until I saw the post - I just skimmed past that syntax trying to figure out the do portion. I also think the introduction of foldr1 would throw people not familiar with Haskell or functional programming. I still have trouble with it :)
  • p.14: "capacity" is misspelled "capactity" several times. (SLPJ: done)
  • p.17: "1000,000 microseconds" instead of "1,000,000 microseconds".(SLPJ: done)


LuciusGregoryMeredith 02:00, 13 January 2007 (UTC) Simon, lovely paper. Your first paragraph is very compelling. Let me quote it here.

  • "The free lunch is over [8]. We have grown used to the idea that our programs will go faster when we buy a next-generation processor, but that time has passed. While that next-generation chip will have more CPUs, each individual CPU will be no faster than the previous year’s model. If we want our program to run faster, we must learn to write parallel programs [9]."
  • What evidence does this paper offer that using STM will actually get my program to run faster? (SLPJ: none whatsoever. The only claims I'm trying to make are (a) we need to learn to write concurrent programs; and (b) if we want to write parallel programs, then STM is promising. In fact we need to write concurrent programs for all sorts of reasons, and performance is only one of them; I'm just using it as a convenient "way in". A bit sloppy perhaps.) For all i can see in this example, it may be a beautiful abstraction that when used at scale on interesting programs cannot actually take advantage of the multicore architecture. To be convinced, starting from this particularly motivating opening, i would like to see an example that begins with an algorithm that is not parallel. Then be shown a beautiful, STM-based parallel version that is demonstrably faster.
  • It would be particularly compelling to see just how a good implementation of STM for Haskell takes advantage of Intel and/or AMD multicore hardware.
  • It would be even more compelling to see the corresponding lock-based program and how it fairs relative to the STM version in terms of performance, usage of the hardware platform as well as program understandability and analysis.
  • Clearly, one of the real rubs is getting from current expressions of algorithms to parallel ones, especially parallel ones that map onto modern architectures. Perhaps your point is that STM helps one start to think and conceptualize computation as a concurrent activity -- which then offers some hope to the ordinary programmer to develop programs that will actually take advantage of today and tomorrow's architectures. If so, then the paper is an excellent start, but i would very much like to see this point made more explicit and central, especially if you only give some lipservice to the argument that STM can actually be made to take advantage of the multicore architectures. In particular, evidence for this sort of point might come in the form of a study of how long it takes an ordinary programmer -- not a Simon P-J -- to develop a beautiful solution like a solution to the Santa Clause problem.
  • Evidence against this sort of point would come in the form of people finding the basic constructs of the solution "mind-bending".

Pitarou 00:51, 15 January 2007 (UTC) In the definition of the function forever, there is the comment -- Repeatedly perform the action, taking a rest each time. I'm not sure what you mean by "taking a rest". (SLPJ: done)

Asilovy 16:43, 15 January 2007 (UTC) Page 1 first paragraph, last sentence : I'm not native english but I wonder if you would'nt write "If we want our programs..." with 's' since you use plurals elswhere. (SLPJ: done)

Asilovy 16:43, 15 January 2007 (UTC) Page 3 last sentence before 2.2 : Is'nt it "... on there being INsufficient..." rather than "sufficient" ?(SLPJ: done)

Asilovy 18:33, 15 January 2007 (UTC) Page 6, last sentence : Should'nt you write "...being explicit aboute SIDE effects..." and the same for the last sentence of the next paragraph (begin page 7) "This ability to make SIDE effects..." (SLPJ: done)

Asilovy 18:33, 15 January 2007 (UTC) Page 8 second paragraph : I can understand that, in some sense, atomocity and isolation are related (in fact 2 faces seen by different threads of the same problem) but you start by saying the model does not ensure atomicity and explain why finishing by "...thereby destroying the isolation guarantee". Sounds confusing.

Asilovy 18:33, 15 January 2007 (UTC) Page 10 code of limitedWithdraw : isn't it "writeTVar acc (bal - amount)" with a minus ? (SLPJ: done)

Asilovy 18:33, 15 January 2007 (UTC) Page 11 : name confusion in the code to limitedWithdraw2 (in the type signature), and withdraw2 in the definition and the comment (SLPJ: done)

Asilovy 18:33, 15 January 2007 (UTC) Page 15 firt line : maybe "The function newGate makes A new Gate..." ? (SLPJ: done)

Jeremygibbons 12:47, 22 January 2007 (UTC) "in reality" (p14) - I hate to break it to you, Simon, but I think "in the specification" would be more appropriate here. (SLPJ: ha ha; I think I'll leave it!) Also, on p19, "a atomic" should be "an atomic" and on p21, "sophisiticated" is misspelt. (SLPJ: done)

Norbertk 20:12, 12 February 2007 (UTC) (p4) I am a Haskell Newbie, so I don't understand at first read the different meaning of the '->' in the type signature. It separates the types of the input paramters and it separates the type of the result. Writing this I presume that the last token is always the result, isn't it ? Maybe a remark would be in order, saying that Haskell functions always return exactly one value.

Retrieved from "https://wiki.haskell.org/index.php?title=Talk:SantaClausProblemV2&oldid=11431"