5 ms·

From zero to cooperative threads in 33 lines of Haskell

135 points by lelf 13y ago

dons 13y ago
See also Koen Claessen's "Poor Man's Concurrency Monad", http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8039 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8...
- drstrangevibes 13y ago
  I hate the fact that they make me pay for this! Where would society be if Pythagoras or Turing had charged for their ideas?
jokoon 13y ago
33 lines of haskell is like 2000 lines of C
- DanWaterworth 13y ago
  I don't know if this is true, but when I'm writing things in Haskell, it feels like there's a better than linear decrease in line count compared to C. i.e. the larger the program, the larger the proportion of gain.
  - dons 13y ago
    Abstraction power doesn't scale linearly in the number of tokens.
- qb45 13y ago
  At my university OS course we once had to implement a usermode threading library in C. Not cooperative, but preemptive (signals), with all the required locking, signal masking, atomic_t's and so on. Mine was about 300 lines of C.
  - stouset 13y ago
    Georgia Tech?
boothead 13y ago
There are some amazing things you can do with free monads, although I must confess to not having my head completely wrapped round them yet: There are some great links in this SO answer: http://stackoverflow.com/questions/6941904/recursion-schemes-for-dummies http://stackoverflow.com/questions/6941904/recursion-schemes... Especially Tim William's talk here: https://github.com/willtim/recursion-schemes/raw/master/slides-final.pdf https://github.com/willtim/recursion-schemes/raw/master/slid...
- dons 13y ago
  See also free applicatives. We use these extensively at work. E.g. http://gergo.erdi.hu/blog/2012-12-01-static_analysis_with_applicatives/ http://gergo.erdi.hu/blog/2012-12-01-static_analysis_with_ap... Amazing when entire DSL programs turn into 1 line calls.
  - boothead 13y ago
    Funny coincidence - In the place I work this is done with a bajillion lines of python. The entire DSL turns into a bowl of spaghetti with worms hidden throughout!
- MichaelAza 13y ago
  "I must confess to not having my head completely wrapped round them yet" My thoughts exactly. That's the thing about Haskell. I love the elegance and enjoy the mathematics but it seems it takes me months at a time before something clicks. One reason why I haven't used it for any "real" project.
  - Martijn 13y ago
    You don't really need to understand all these things in order to build "real" things with it. Just build something without caring too much whether an experienced Haskell programmer would find it elegant enough. Most of the "clicks" I've had is when I'd already built something in a naive way (that worked perfectly) and someone showed me an alternative, more elegant way in which it could be written.
tikhonj 13y ago
I think this is a perfect example of one of the main ideas behind lazy functional programming: we can reify computations as simple data structures. This thread system? It's just a large lazy tree. This lets us implement all the logic in a straight-forward way, just by operating on the data type; since the language is lazy, everything ends up being evaluated at the right time. To me, this was one of the bigger revelations with Haskell. Stop thinking about lists as lists, and consider them more like loops. Just loops that you can pattern match against and manipulate in a truly first-class way. Then extend this to computations of any other "shape" by thinking about other lazy structures. Free monads are in some ways the ultimate example of this in action: you can use do-notation--which clearly looks like a computation--to just produce a data structure. Then you're free to consume it however you like. Monads usually represent computations, perhaps with effects, but here we have an extremely general one that is just an algebraic data type! This works because we can decouple defining the data structure from evaluating it. We can build up our tree with a sequence of calls to fork and so on, in the order of our program flow. Then we can actually evaluate it in the order of our scheduler! This is one of the core ideas behind laziness.
- tetha 13y ago
  Reasoning similar to this enabled me to write a rather powerful test recently. We had a queue that was behaving strangely and we didn't reallz know how to tackle this. Thus I just went ahead and realized: If we take enqueue and dequeue as parenthesis open and parenthesis close, then a balanced string of opening and closing parenthesis will leave the queue empty. And furthermore, if the queue is thread safe, I can execute multiple such execution sequences in parallel and the queue will still be empty in the end and no execution sequence will be infinitely blocked. The threads might steal some elements back and forth, but no thread will ever starve, because for every stolen dequeue, and enqueue will be orphaned and thus, stolen in retaliation. From there, I could just write myself an execution sequence generator based on the CFG for balanced parenthesis trees, execute a number of these things in parallel and check if the queue was empty in the end. This test failed and it appears to be highly sensitive and precise.
blueblob 13y ago
Is it just me, or does it seem like using fork to implement thread is kind of overkill. The point of fork is that you want the context of the calling process (and the required overhead) and implementing threads on top of fork seems to defeat the purpose. Note: I have not programmed in Haskell and am unfamiliar with it's fork function.
- kenko 13y ago
  That fork function was defined in the library.
tux1968 13y ago
The article starts off with the English problem description, but it seems very clear that wasn't the logical starting point. It was framed in Haskell first and then worked back to the English. There's nothing wrong with that. But I think it's a bit disingenuous for the author to say he started with the English first. Who would describe cooperative threads that way without having a deep understanding of how they were about to implement them in Haskell?

135 points by lelf 13y ago

dons 13y ago

See also Koen Claessen's "Poor Man's Concurrency Monad", http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8039 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8...

drstrangevibes 13y ago
I hate the fact that they make me pay for this! Where would society be if Pythagoras or Turing had charged for their ideas?

jokoon 13y ago

33 lines of haskell is like 2000 lines of C

DanWaterworth 13y ago
I don't know if this is true, but when I'm writing things in Haskell, it feels like there's a better than linear decrease in line count compared to C. i.e. the larger the program, the larger the proportion of gain.
- dons 13y ago
  Abstraction power doesn't scale linearly in the number of tokens.
qb45 13y ago
At my university OS course we once had to implement a usermode threading library in C. Not cooperative, but preemptive (signals), with all the required locking, signal masking, atomic_t's and so on. Mine was about 300 lines of C.
- stouset 13y ago
  Georgia Tech?

boothead 13y ago

There are some amazing things you can do with free monads, although I must confess to not having my head completely wrapped round them yet: There are some great links in this SO answer: http://stackoverflow.com/questions/6941904/recursion-schemes-for-dummies http://stackoverflow.com/questions/6941904/recursion-schemes... Especially Tim William's talk here: https://github.com/willtim/recursion-schemes/raw/master/slides-final.pdf https://github.com/willtim/recursion-schemes/raw/master/slid...

dons 13y ago
See also free applicatives. We use these extensively at work. E.g. http://gergo.erdi.hu/blog/2012-12-01-static_analysis_with_applicatives/ http://gergo.erdi.hu/blog/2012-12-01-static_analysis_with_ap... Amazing when entire DSL programs turn into 1 line calls.
- boothead 13y ago
  Funny coincidence - In the place I work this is done with a bajillion lines of python. The entire DSL turns into a bowl of spaghetti with worms hidden throughout!
MichaelAza 13y ago
"I must confess to not having my head completely wrapped round them yet" My thoughts exactly. That's the thing about Haskell. I love the elegance and enjoy the mathematics but it seems it takes me months at a time before something clicks. One reason why I haven't used it for any "real" project.
- Martijn 13y ago
  You don't really need to understand all these things in order to build "real" things with it. Just build something without caring too much whether an experienced Haskell programmer would find it elegant enough. Most of the "clicks" I've had is when I'd already built something in a naive way (that worked perfectly) and someone showed me an alternative, more elegant way in which it could be written.

tikhonj 13y ago

I think this is a perfect example of one of the main ideas behind lazy functional programming: we can reify computations as simple data structures. This thread system? It's just a large lazy tree. This lets us implement all the logic in a straight-forward way, just by operating on the data type; since the language is lazy, everything ends up being evaluated at the right time. To me, this was one of the bigger revelations with Haskell. Stop thinking about lists as lists, and consider them more like loops. Just loops that you can pattern match against and manipulate in a truly first-class way. Then extend this to computations of any other "shape" by thinking about other lazy structures. Free monads are in some ways the ultimate example of this in action: you can use do-notation--which clearly looks like a computation--to just produce a data structure. Then you're free to consume it however you like. Monads usually represent computations, perhaps with effects, but here we have an extremely general one that is just an algebraic data type! This works because we can decouple defining the data structure from evaluating it. We can build up our tree with a sequence of calls to fork and so on, in the order of our program flow. Then we can actually evaluate it in the order of our scheduler! This is one of the core ideas behind laziness.

tetha 13y ago
Reasoning similar to this enabled me to write a rather powerful test recently. We had a queue that was behaving strangely and we didn't reallz know how to tackle this. Thus I just went ahead and realized: If we take enqueue and dequeue as parenthesis open and parenthesis close, then a balanced string of opening and closing parenthesis will leave the queue empty. And furthermore, if the queue is thread safe, I can execute multiple such execution sequences in parallel and the queue will still be empty in the end and no execution sequence will be infinitely blocked. The threads might steal some elements back and forth, but no thread will ever starve, because for every stolen dequeue, and enqueue will be orphaned and thus, stolen in retaliation. From there, I could just write myself an execution sequence generator based on the CFG for balanced parenthesis trees, execute a number of these things in parallel and check if the queue was empty in the end. This test failed and it appears to be highly sensitive and precise.

blueblob 13y ago

Is it just me, or does it seem like using fork to implement thread is kind of overkill. The point of fork is that you want the context of the calling process (and the required overhead) and implementing threads on top of fork seems to defeat the purpose. Note: I have not programmed in Haskell and am unfamiliar with it's fork function.

kenko 13y ago
That fork function was defined in the library.

tux1968 13y ago

The article starts off with the English problem description, but it seems very clear that wasn't the logical starting point. It was framed in Haskell first and then worked back to the English. There's nothing wrong with that. But I think it's a bit disingenuous for the author to say he started with the English first. Who would describe cooperative threads that way without having a deep understanding of how they were about to implement them in Haskell?