5 ms·

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

by 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.

by tikhonj 13y ago

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.