> It achieves this in ways that seem subtle to us-- clearly so, since it wasn't really discovered and applied until the late 2010's
I'm getting a little annoyed by the structured concurrency crowd ignoring the synchronous concurrency paradigm as a historical precedent. It has existed since the 1980s and as far as I can tell there is a huge overlap in concepts. The only major difference I'm seeing is the addition of scoped asynchronous concurrency on top of synchronous concurrency (meaning single-threaded concurrency). That's significant for sure, but also not so much that it's cool to ignore the existing previous work.
Here's Céu, a language from 2011 with scoped synchronous concurrency:
input int KEY;
par/or do
every 1s do
_printf("Hello World!\n");
end
with
await KEY;
end
(Prints the “Hello World!” message every second, terminating on a key press.)
And hey, since we're talking about Lua, maybe we can acknowledge LuaGravity, which has existed since 2009?
Don't get me wrong though, I'm glad structured concurrency is catching on and that new work is being done in this area.
I’d very much like to see an accessible source on synchronous languages in general—a review paper maybe? So far I’ve only seen language-specific tutorials, where the nice things about the approach as such are liberally diluted with the specifics of the language and general programming knowledge.
That said, from what I’ve seen Trio-style “structured concurrency” is somewhat less strict than the synchronous model: nurseries being tangible objects implies (1) you can spawn a dynamically-specified amount of cooperative threads, as you can just tell the nursery to spawn things in a loop; (2) you are not limited to strict nesting, as an ancestor thread can pass you a nursery closer to the root if it wishes.
The result of the second point is that you can maintain a tree of responsibility for e.g. error propagation without having a stack discipline where a parent thread’s dynamic extent must encompass all of its children’s (though there must be an ancestor with such a property). Yes, that means you’re free to have a single catastrophically-crashing root nursery where everybody spawns whatever they want, but you’re also free not to (and in fact there’s a sort of capability discipline for that, to the extent that the host language encapsulates things).
From the references of those papers it should be easy to find others, right?
And yes, you're absolutely right that the synchronous model is more restrictive - most synchronous languages follow the GALS principle: "globally asynchronous, locally synchronous". One benefit of the synchronous model is that it can essentially be compiled to a finite state machine with a memory overhead of mere bytes per "trail" (the synchronous analogue of a thread - the code snipped above has one synchronous "main" trail that splits into two synchronous trails in the "par/or" section).
The focus on this makes sense historically, since many synchronous languages were originally designed to target hard real-time embedded systems, where available memory is small, computational tasks are usually not very heavy, and the "asynchronous" part is interacting with the real world.
But that also suggests that synchronous and asynchronous concurrency could complement each other with the right language design.
I'm open, as always, to refining my understanding of what structured concurrency is, what various forms it takes on, and how it came about. I don't think it's so obvious that the article has misstated, however.
I was not-quite-intentionally using a broader notion of structured concurrency, including not only the initial concept (tie task hierarchy to code structure, propagate errors up the call + task stack), but also critical pieces that are built on top of that, notably cancel/timeout scopes [1]. I don't think these pieces had been assembled to form something powerful enough to make concurrency manageable, until about the time of Nathaniel J. Smith's articles and Python Trio.
I'm revising the text slightly, and adding a footnote:
> It achieves this in ways that seem subtle to us-- clearly so, since its utility didn't reach critical mass until around 2018†
> † While it's argued that the core concept of structured concurrency has existed in some libraries and languages prior to the recent boom, these lacked significant parts of the story for making concurrency manageable. One is powerful, ergonomic control of timeouts and cancellation-- itself dependent on structured concurrency. Another is striving for a program that follows structured concurrency as a whole, including direct and transient dependencies. Nathaniel J. Smith was first to piece this all together, with a set of articles, and corresponding Python Trio concurrency library.
Though I suspect this will welcome more controversy ;)
Hey I remember you, you wrote that thoughtful post on why you think Zig has function colors. Looking forward to see what you come up with, you clearly are putting a lot of thought into the subject!
Yes, I've put a lot of thought in, and I'd like to hear your feedback. If you don't want to provide any, please don't waste your time reading the rest of this comment.
The basic extension I would make to structured concurrency is explained in my comment at [1], but I'll make this comment self-contained.
My design is predicated on the fact that the coolest thing about Rust is the borrow checker; it's a fantastic idea that eliminates many sources of bugs. But it's expensive, and structured concurrency can almost give it to us for "free." My design changes structured concurrency enough to give code a borrow checker for "free" or at least low cost at compile time and low cost at runtime.
The change is this: change API's to "push" execution "down" the stack. (In this context, I'm thinking of the typical execution stack that grows downward in memory.)
For example, say there's an API that creates an object A that your code wants to use. Usual code may just return A, and in that case, escape analysis would probably set A's lifetime to the lifetime of the caller, and this works. But in more complex cases, that may not be possible.
However, if the API that creates A takes a function B to call with A instead, then A's lifetime could be tied directly to the function that created it, and the creator function can call B with a borrow of A. This is completely safe because B is guaranteed to return before A's lifetime ends.
And if the language has some way to have closures, then B could be a closure with data or pointers to data higher in the stack, thus allowing code to access any data anywhere in the stack while running B with access to object A. This is still safe because B will definitely return before that other data goes out of scope.
This is how pushing execution down the stack can easily ensure that lifetimes are automatically followed without needing a borrow checker. Honestly, I would suggest to the Rust people that they should adopt this style of programming; it would immensely useful in Rust.
Anyway, then you add structured concurrency, which itself ties the lifetime of threads to the execution stack. This fact makes it easy to generalize the idea above to work with multiple threads. With structured concurrency, you can spawn a thread, and you know that any data higher on the stack than the threadset/nursery will always exist while that thread is live, no borrow checking necessary.
So to extend my example, maybe the API creates multiple A objects and runs B on multiple threads, each one with a different instance of A. Even if B is a closure, with pointers to data higher in the stack, this is completely safe (assuming no mutation) because that data has a longer lifetime than all of the threads.
As for mutation, I think Rust has the right idea with its Send/Sync model. To generalize mutation across threads, I would use something similar. For the possibility of mutation in the same thread, I would just add a layer of indirection; for example, I have strings, which are immutable, and string builders, which are mutable, but hidden behind an opaque pointer so that mutation is safe in single-thread code. Adding Send/Sync to this model will make mutability safe across threads too.
That takes care of most cases, but there is still one case.
Perhaps a thread creates data, and other threads want to use it. We have already taken care of the case where those other threads are descendants of the creator thread, but what if there is a thread C that wants to use that data that is not a descendant of the creator thread?
Easy: create a thread that is a descendant of both the creator thread and thread C and push its execution down the stack like above.
There would be an API to do this; thread C would basically send a request to the creator thread with a closure/function D and block waiting for the creator thread to say that D is done executing. The creator thread would create a new descendant thread E to run D. Once D was done, E would be joined, and the creator thread would send a message to thread C, which would then pick up execution where it left off.
Of course, since the lifetime of thread E is smaller than the lifetime of both the creator thread and thread C, it is safe to use D, even though D might have references to data in both thread C and the creator thread.
This would extend structured concurrency; instead of a thread tree, it would be a thread directed acyclic graph.
All of this obviously requires RAII, but to make things work even better, forbid self-referential data structures (use a parent data structure that owns all items and have the items just refer to other items with indices or borrowed references, like in my implementation of linked lists [2] [3]). This ensures that reference cycles don't happen and eliminates that possible complexity.
Also, it may be necessary to restrict thread spawning to the outermost scope of a threadset, just to ensure lifetimes are safe. If that's too onerous a restriction, then some lifetime analysis/borrow checker would be necessary, but I think it would be simpler than Rust's.
However, this is not a free lunch; there are a few costs to this:
1. Extra memory for the extra thread stacks. This can be somewhat mitigated with compiler support for calculating the max stack size of each thread, but it can't be completely mitigated.
2. Extra memory for the extra thread data in the kernel. This cannot be mitigated.
3. Extra CPU time to start and stop extra threads. This cannot be mitigated, though there might be some performance improvements to be had on spawning threads. Nevertheless, there is still expensive context-switching that has to happen.
4. A paradigm shift about the same size as the one to adopt structured programming once `goto` was considered harmful.
Of those four costs, I think number 4 is the biggest problem. The software industry is much larger, by several orders of magnitude, than it was when the structured programming shift took place, so there is greater momentum to overcome. And it would require rewriting a lot of libraries, or writing new ones. (This is one reason I am creating a new language: a new language has no technical debt in its standard library and can get the design right from the outset.) This is not a trivial cost, and it will only be done gradually, if at all. It will only happen if the industry decides that this is a good idea.
The CPU cost is the other one that concerns me, but I think this could be mitigated a lot by having a system call to spawn several threads at once.
The other mitigation would be to use thread pools: spawn threads when necessary, but when they finish, keep them around in a paused state and reuse them as much as possible. There would need to be a way to properly dispose of them in low-memory situations, but I think this could be done.
And maybe it won't matter much if people only spawn threads to do heavy work, which would amortize the cost of spawning the threads.
As for the memory costs, I think minimizing stacks for each thread is not going to matter much; stacks are already tiny compared to available memory. I don't think the extra kernel memory is going to be a problem either; it's a fixed cost and smaller than the cost of a thread stack.
Anyway, that's my design so far. What do you think?
One-sentence answer: sounds sensible, I think I'd need to play with it to get a good feeling for how it holds up in practice.
(btw, since one of the comments of [1] mentions Erlang, have you seen Pony? It's actor based but has a lot of interesting recent compsci theory behind it: https://www.ponylang.io/discover/. Who knows, there might be something interesting in there for you to steal)
Thank you, and I agree; it needs to be played with.
I've actually got a public "Show HN" scheduled for November 1, but it won't have any of the concurrency stuff then. (I don't have much time to work on it.) I hope concurrency won't be far behind.
But the concurrency MVP is implemented in C, and the compiler/interpreter already uses it. It's promising.
I've seen Pony before, but I haven't taken a deep look. I will now, thank you.
Even Python's Trio (which asserts that it is structured concurrency) uses await. But even Ada didn't use `await` (most languages didn't) and has had something very close to structured concurrency since 1983 (first published spec).
One of the important parts of structured concurrency is that if you have something like this:
a
spawn(b)
spawn(c)
`a` cannot terminate until after `b` and `c` have terminated (or it has to terminate them), at least not without moving the tasks or spawning them inside a nursery that will survive `a`'s scope. That's been baked into Ada since its first spec 40 years ago (along with many other elements of structured concurrency).
I'm getting a little annoyed by the structured concurrency crowd ignoring the synchronous concurrency paradigm as a historical precedent. It has existed since the 1980s and as far as I can tell there is a huge overlap in concepts. The only major difference I'm seeing is the addition of scoped asynchronous concurrency on top of synchronous concurrency (meaning single-threaded concurrency). That's significant for sure, but also not so much that it's cool to ignore the existing previous work.
Here's Céu, a language from 2011 with scoped synchronous concurrency:
(Prints the “Hello World!” message every second, terminating on a key press.)And hey, since we're talking about Lua, maybe we can acknowledge LuaGravity, which has existed since 2009?
Don't get me wrong though, I'm glad structured concurrency is catching on and that new work is being done in this area.
[0] https://en.wikipedia.org/wiki/Synchronous_programming_langua...
[1] http://ceu-lang.org/
[2] https://fsantanna.github.io/luagravity/