12 ms·
Structured Concurrency in High-Level Languages
- yxhuvud 8y agoGreat follow up to the original argument. I certainly hope some language designers start to look really hard at these arguments. Off the top of my head: * Cancel all threads in the bundle. * Block until all threads in the bundle exit. * Block until at least one thread in the bundle exits. Cancel all the other threads. I think there also is one 'restart any exiting thread' and a variant of the block until all rule where only failed threads are restarted. Hmm, actually - perhaps there should be variants specifying the behavior of failed threads in all cases?
- zzzcpan 8y ago> perhaps there should be variants specifying the behavior It feels like Erlang/OTP is being reinvented right here again. Once you get deep enough into concurrency the ideas start to converge on killable isolated processes with asynchronous message passing and programmable behaviors. Because with shared memory killing a thread has unpredictable consequences, you need to either enforce isolation or avoid consequences in some other way, like by not having multithreading and using an event loop. Isolated processes need to communicate with other processes somehow. You need message passing. But it has to be asynchronous to make it possible to implement various waiting behaviors. With event loops you get there via cancellable contexts and higher order programming, but on a single cpu. Getting into multi core or distributed systems yet again requires asynchronous message passing. At the end it's all actors everywhere.
- pacala 8y agoWhat would be some usecases for which synchronous is insufficient and one has to reach for the hard to reason about asynchronous?
- dnautics 8y agoLet's say you are writing a parallel crypto hasher... Which if you're part of a pool is the case at the nacro level, the first to get to the answer should probably cancel the rest (though strictly speaking it's not necessary)
- toast0 8y agoSynchronous messaging is insufficient for making multiple requests at once and waiting for the responses. Also asynchronous messaging allows for optimistic notifications -- for example to clear a cache when coherency isn't required. With asynchronous messaging it's simple to build synchronous interactions if desired --- send a message and wait for a response; but you can't build asynchronous interactions on top of synchronous messages.
- dnautics 8y ago> It feels like Erlang/OTP is being reinvented right here again. I thought the same thing. There are some cases like low message passing computational tasks where you can get away with simple async futures + fetch_future (being a computationally oriented language Julia encourages this model) but in the end actors are pretty great at generalizing concurrency.
- CodeArtisan 8y agoOz's declarative concurrency is worth taking a look at. In Oz, a thread implicitly goes into sleep or wake up on data dependency. for example, declare FOO BAR % FOO and BAR are not bound to any value yet. in thread {print FOO} % the thread blocks here until FOO is bound to a value. BAR = 456 % Binds BAR which wake up any thread waiting for it. end thread FOO = 132 % Binds FOO which wake up any thread waiting for it. {print BAR} % the thread blocks here until BAR is bound to a value. end Because of this, ordering of operations is easy.
- TeMPOraL 8y agoThis sounds like an easy recipe for race conditions. Consider: declare FOO BAR % FOO and BAR are not bound to any value yet. in thread {print FOO} % the thread blocks here until FOO is bound to a value. BAR = 456 % Binds BAR which wake up any thread waiting for it. end thread {print BAR} % the thread blocks here until BAR is bound to a value. FOO = 132 % Binds FOO which wake up any thread waiting for it. end I swapped the instructions in the second thread. Does Oz detect that, or otherwise protect programmer from such mistakes?
- CodeArtisan 8y agoIt would deadlock but there is a debugger that shows the state of any thread and where it is blocked.
- smaddox 8y agoSo it's race free.... If you test every single possible system state, and remove all the race conditions. No thanks.
- ghkbrew 8y agoA race condition is a situation where the result depends on the ordering/interweaving of threads. And that example isn't actually one. It's a deadlock which are also bad but much more deterministic and easier to debug.
- noelwelsh 8y agoIsn't this really well trodden ground? Coroutines were known by the 60s, according to Wikipedia, and I have a really hard time believing that just about everything worth saying about them hasn't been said. I feel a little bit of scholarship would help avoid creating problems that have already been solved.
- ashleyn 8y agoIn my experience, there's an academic world, and a practical world, and never the 'twain shall meet. The academic world knew without experience that higher-level structured concurrency was the way to go. It took the practical industry decades of unmaintanable pthread messes to learn the same lesson, but they ultimately learned it.
- rumcajz 8y agoAny interesting links to academic research of higher-level structured concurrency?
- noelwelsh 8y agoHere's one interesting paper: http://www.csc.kth.se/~phaller/doc/haller16-scala.pdf http://www.csc.kth.se/~phaller/doc/haller16-scala.pdf Here's the general algorithm: 1. Find something interesting 2. Chase the references and read them. 3. Chase the citations (use Google Scholar) and read them, if they're relevant. You'll pretty soon have an understanding of the general approaches and issues. (If you throw "coroutine concurrency" into Google Scholar you'll very quickly find citations from the 80s discussing this model.)
- UncleEntity 8y agoIsn't this the same as Notes on structured concurrency, or: Go statement considered harmful[0] except using c rather than python? One has a "nursery" while the other has a "bundle" with both hoping to control the lifetime of coroutines. [0]https://news.ycombinator.com/item?id=16921761 https://news.ycombinator.com/item?id=16921761
- yxhuvud 8y agoDid you read the preface? It is a direct follow-up to that post written by one of the people that inspired it in the first place. The post goes through some parts in a bit more depth than what the previous post you are referring to did. But yes, the author has a very similar approach to the problem.
- deleted 8y ago[deleted]
- samatman 8y agoA proposal: what's being referred to as a 'bundle' or a 'nursery' should be called a 'loom'. A loom has the precise relation to actual warp threads as a virtual loom would to software (green) threads.
- sparkie 8y agoThe idea of looking at things as a call tree (or graph) rather than a plain old stack is how Schemers think about things. We specifically avoid terminology like "stack frame" and refer to them as "continuation frames" because we don't tie the abstract feature to how it is implemented. A branch in the tree is an invocation of call/cc. These recent complaints about structured concurrency in popular languages to appear to shadow the complaints about call/cc vs delimited continuations. More info here: http://okmij.org/ftp/continuations/against-callcc.html http://okmij.org/ftp/continuations/against-callcc.html.
- Animats 8y agoThe control flow issues mentioned there have been addressed many times. Coroutines and their discontents are well known. But the author has some good points about cancellation. Cancellation isn't well-studied. It has two main cases - canceling a wait, and interrupting actual computation. The first case comes up more often. If anything that can wait can be aborted, then things unwind better. Language support for this needs to be block-structured, as in Python's Lock lok; with lok : (do something) Python uses exceptions, so the appropriate mechanism there would be to indicate lock failure with an exception, and not execute the "with" block. In error code languages, the locking block should return an error code. Once a thread/coroutine/whatever is in cancellation, all waits should abort. So you rapidly fall through the code until the concurrent construct reaches its exit point. Unwinding still takes place. Non-blocking concurrency primitives should be allowed in this mode, so you can add things to a list, but can't wait on I/O. RAII things like file-closing on block exit have to be done that way, because the canceled construct can't wait for them. QNX real-time messaging works something like this. QNX's basic interprocess communication primitive is MsgSend, which sends a message and waits for a reply. MsgSend can be canceled, or can time out; an error code is returned. All I/O requests are MsgSend operations and thus can be canceled. In QNX, everything that can block can be timed out or canceled. This is used to place upper bounds on how long things can take. Canceling a compute loop is harder. If the compute loop is operating only on local data, it's not so bad. You need some data flow analysis to determine that the function being forced to error out doesn't have non-local side effects. If, say, you're inverting a matrix, and that needs to be aborted, you need to be sure that the matrix is never looked at again. This is probably easier in functional languages. Once wait cancellation under control, so the thing you're canceling can't block, having to wait for the other thread/coroutine/whatever to reach its join point isn't so bad. You don't need to kill it; you can wait for it to unwind. So solving cancellation moots the problem of how to handle thread joins for failed threads.
- KirinDave 8y agoFor those interested in various approaches in this space that are very interesting, may I recommend: * Haskell and in particular Marlow's async library. * The Erlang language's Actor system along with the OTP framework as a different way of thinking about orphaned processes (via supervision trees). * The Pony language, which can safely pass ownership of objects (and thusly coroutines) around.