From zero to cooperative threads in 33 lines of Haskell

http://www.haskellforall.com/2013/06/from-zero-to-cooperative-threads-in-33.html

by lelf • 13 years ago

135 17 13 years ago

dons3• 13 years ago

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

jokoon• 13 years ago

33 lines of haskell is like 2000 lines of C

DanWaterworth• 13 years 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.

dons3• 13 years ago

Abstraction power doesn't scale linearly in the number of tokens.

qb45• 13 years 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• 13 years ago

Georgia Tech?

boothead3• 13 years 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...

Especially Tim William's talk here:

https://github.com/willtim/recursion-schemes/raw/master/slid...

dons3• 13 years ago

See also free applicatives. We use these extensively at work. E.g. http://gergo.erdi.hu/blog/2012-12-01-static_analysis_with_ap...

Amazing when entire DSL programs turn into 1 line calls.

boothead3• 13 years 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• 13 years 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• 13 years 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.

boothead3• 13 years ago

My approach is to measure my progress by how much less stupid I feel the n+1th time I read the material again. I hope if I just keep chipping away it will enter my brain by a process of osmosis.

tikhonj• 13 years 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• 13 years 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• 13 years 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• 13 years ago

That fork function was defined in the library.

tux1968• 13 years 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?

From zero to cooperative threads in 33 lines of Haskell

Related Stories