3 ms·

I do not know of any case studies or examples. However, my own code could be considered non-trivial because it's a full build system, or will be. After writing

I do not know of any case studies or examples. However, my own code could be considered non-trivial because it's a full build system, or will be. After writing only enough to get it bootstrapped, I'm now going through and redoing a lot to make it use all structured concurrency. Nevertheless, I don't think it's useful as an example, or rather, it won't be useful once the transformation is done. > It'd also be interesting to know if all of the behaviour that was expressed in the original structureless concurrency code could be ported across to structured concurrency, or if it was still necessary to use structureless concurrency in a few places as the corresponding behaviour was not expressible. I have a firm belief that the equivalence of structured and unstructured concurrency is exactly the same as the equivalence of structured and unstructured programming. It has been proven that you can express any possible unstructured program as a structured program. [0] (There is a bit of controversy over the original proof, but as far as I can tell, it has been proven as long as multi-level loop breaks/continues exist. See [1]. This is one reason why my language will have multi-level breaks/continues.) I personally believe that such a proof exists for structured vs. unstructured concurrency and that it just needs to be found. Part of that belief is founded on [2], which does an excellent job of showing how the `go` statement is really a multi-branch `goto` statement. Perhaps I'll try to discover the proof and write it in a blog post. (As a first dirty attempt, imagine all of the possible ways you could have more than one concurrent thread of execution. It should be simple to show how to turn every possible use of a `go`-like statement into an opening of a threadset that launches two tasks and waits on them before continuing. I'm not sure how any way of splitting a thread of execution into more than one thread of execution could not possibly be simulated with that. I could be wrong, though.) Oh, and I just found out that Swift has structured concurrency! [3] This is great! And I think it is the first mainstream programming language with it. I think this is awesome because it means that structured concurrency is going mainstream. I hope it helps structured concurrency win against async/await, which I believe is a poor model. So if you want a case study, I'd watch the Swift community; someone is going to rewrite their code using structured concurrency and write a blog post about it. [0]: https://en.wikipedia.org/wiki/Structured_program_theorem https://en.wikipedia.org/wiki/Structured_program_theorem [1]: http://www.cs.cornell.edu/~kozen/Papers/BohmJacopini.pdf http://www.cs.cornell.edu/~kozen/Papers/BohmJacopini.pdf [2]: https://vorpus.org/blog/notes-on-structured-concurrency-or-go-statement-considered-harmful/ https://vorpus.org/blog/notes-on-structured-concurrency-or-g... [3]: https://github.com/apple/swift-evolution/blob/main/proposals/0304-structured-concurrency.md https://github.com/apple/swift-evolution/blob/main/proposals...

zozbot234 5y ago
I don't think this can be made to work. Concurrent systems are usually modeled using things like e.g. Petri nets that are not really "highly structured" by your definition. They may be more structured than a goto statement, but they aren't nearly as simple as the pure fork-join model that's often regarded as the typical case of "structured" concurrency. Even the first diagram in OP has free interleaving of main() with quux() then foo() that's not well described by a "tree" of fork-join "tasks". (The second diagram is similarly complex in that foo() may want to transfer ownership of bar() to main(), in order to cleanly terminate and allow main() to proceed prior to waiting for bar().)
- gavinhoward 5y ago
  You're probably right that my rough sketch for a proof wouldn't work. That said, first of all, I don't think structured concurrency has to be a tree. I think it can be a DAG. See my comment at [0]. To solve the main(), quux(), foo() problem, just have main() open a threadset, spawn quux(), then call a function while the threadset is still open, and in that function, open another threadset that spawns foo(). The main(), foo(), bar() problem is a problem of cancellation. In that one, I believe that foo() should not return until bar() does. And if you need to cancel, use deadlines. That is why my code has cancellation built-in, with timers to implement deadlines. (Well, it's still alpha, but the rough shape of it is there.) [0]: https://lobste.rs/s/8msejg/notes_on_structured_concurrency_go#c_wkxbvb https://lobste.rs/s/8msejg/notes_on_structured_concurrency_g...

zozbot234 5y ago

I don't think this can be made to work. Concurrent systems are usually modeled using things like e.g. Petri nets that are not really "highly structured" by your definition. They may be more structured than a goto statement, but they aren't nearly as simple as the pure fork-join model that's often regarded as the typical case of "structured" concurrency. Even the first diagram in OP has free interleaving of main() with quux() then foo() that's not well described by a "tree" of fork-join "tasks". (The second diagram is similarly complex in that foo() may want to transfer ownership of bar() to main(), in order to cleanly terminate and allow main() to proceed prior to waiting for bar().)

gavinhoward 5y ago
You're probably right that my rough sketch for a proof wouldn't work. That said, first of all, I don't think structured concurrency has to be a tree. I think it can be a DAG. See my comment at [0]. To solve the main(), quux(), foo() problem, just have main() open a threadset, spawn quux(), then call a function while the threadset is still open, and in that function, open another threadset that spawns foo(). The main(), foo(), bar() problem is a problem of cancellation. In that one, I believe that foo() should not return until bar() does. And if you need to cancel, use deadlines. That is why my code has cancellation built-in, with timers to implement deadlines. (Well, it's still alpha, but the rough shape of it is there.) [0]: https://lobste.rs/s/8msejg/notes_on_structured_concurrency_go#c_wkxbvb https://lobste.rs/s/8msejg/notes_on_structured_concurrency_g...