News for hackers. Stuff that matters.
Re:Structured Concurrency by ghoward on Saturday March 19, 2022 @06:07PM (#30737983)
Just so you know, those of us who believe in structured concurrency often have slightly different meanings (which I believe will converge over time). My definition is at [0].

Beyond libdill, a rough version has now been implemented in C. (By me, sorry for shilling.)

An example of it in code is at [1].

Combine it with something I call a stackpool (basically a heap-allocated replacement for `alloca()`), and you can worry very little about managing memory manually, even in C.

In fact, both together can even serve the same purpose as Rust's borrow checker in C, if you are willing to write your code with a certain style.

Once I implement it as a first-class construct in a language (which I'm doing right now), it will look like this:

    threadset
    {
        // This starts a thread.
        go run_thread(arg1, arg2, etc);

        // The current thread does not leave
        // this block until all threads finish.
    }
I'm happy to answer questions.

[0]: https://gavinhoward.com/2019/12/structured-concurrency-defin...

[1]: https://git.yzena.com/Yzena/Yc/src/commit/30f4ae4e471cb5a500...

Re:Structured Concurrency by shoo on Saturday March 19, 2022 @07:37PM (#30738563)
Are you aware of any case studies / examples of applying structured concurrency to a nontrivial codebase, which illustrates the benefits and drawbacks of the approach?

It'd be great to see before & after comparisons of taking a codebase written without structured concurrency, and porting it to use structured concurrency constructs, then seeing the differences in terms of runtime overhead, number of weird defects in one implementation but not in the other, lines of code spent, etc.

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.

Appreciate getting a good case study might be challenging --- I've been exposed to oldschool fortran numerical code written in a pre-structured-programming style with heavy use of global variables and gotos, trying to port that across to use structured constructs and local variables can be a large amount of effort.

Re:Structured Concurrency by ghoward on Saturday March 19, 2022 @08:03PM (#30738717)
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

[1]: http://www.cs.cornell.edu/~kozen/Papers/BohmJacopini.pdf

[2]: https://vorpus.org/blog/notes-on-structured-concurrency-or-g...

[3]: https://github.com/apple/swift-evolution/blob/main/proposals...

Re:Structured Concurrency by zozbot234 on Saturday March 19, 2022 @10:57PM (#30739652)
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().)

Re:Structured Concurrency by ghoward on Saturday March 19, 2022 @11:57PM (#30739956)
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_g...

Re:Structured Concurrency by frankpf on Saturday March 19, 2022 @08:23PM (#30738805)
Would you say that Java's Loom[1] matches your definition of structured concurrency?

[1]: https://www.javaadvent.com/2020/12/project-loom-and-structur...

Re:Structured Concurrency by ghoward on Saturday March 19, 2022 @09:09PM (#30739061)
After reading that post, I'm pretty sure that Project Loom only fits my definition of structured concurrency if it's used solely with the try-with-resources construct.

However, if it is used that easy, then yes, absolutely, it fits my definition.

Using the Executor class as a threadset might also make it fit my definition, but I think my opinion of my definition has changed in the two years since I wrote it. I may have to revisit it because I think it may be useful to only consider concurrency that has the same block structure as structured programming does, whereas my current definition allows for passing a threadset around as a first-class value.

tl;dr: yes, it probably fits, but that might mean my definition need changing, except in the case of try-with-resources.

Re:Structured Concurrency by papercrane on Sunday March 20, 2022 @09:00AM (#30742274)
The intent for the structured concurrency part of Loom is that you'd always use it with try-with-resources. The API is still developing so this link will break eventually, but the currently the basic API is in the StructuredTaskScope class.

https://download.java.net/java/early_access/loom/docs/api/jd...

Re:Structured Concurrency by CyberDildonics on Saturday March 19, 2022 @10:40PM (#30739546)
In C++ this would just mean joining all the threads created in this block, which would be completely trivial. Is this really "structured concurrency" that warrants a Q and A?
Re:Structured Concurrency by ghoward on Saturday March 19, 2022 @11:43PM (#30739869)
The Q&A is more for people that don't know about the concept of structured concurrency. Basically, people who have questions on TFA.
Re:Structured Concurrency by hinkley on Sunday March 20, 2022 @06:30PM (#30747393)
This seems in some ways to be a special case of Communicating Sequential Processes.

In which case are we reinventing Erlang, badly (the new programmer's curse that is supplanting Lisp)?

Re:Structured Concurrency by ghoward on Sunday March 20, 2022 @10:51PM (#30749589)
From what I understand, this would go further than Erlang, in that this can be a DAG of threads, not just a tree. I could be wrong, though; I'm not terribly familiar with Erlang anymore.
Re:Structured Concurrency by hinkley on Monday March 21, 2022 @12:07PM (#30755713)
Elixir is perpetually at the top of my TODO list, but I don't make it much past the videos (I had a plan involving rasPi clones, which ended up being a bridge too far).

I take your point about a tree versus a DAG. The supervisor tree is definitely a footgun of a sort and quite a few minutes of many videos is dedicated to ways to be successful with your supervisor tree. I suspect the tree was picked and stuck around so long in large part because it's the Simplest Thing That Could Work. But the BEAM has been tackling some headier topics of late. I'd be curious to see how much of this work could be grafted onto Erlang.

DAGs are great, but they do take a bit more vigilance. In a large project there is always the risk of adding a back link somewhere and upsetting the whole thing. The product I work on has one DAG, and in fact I just fixed a nasty memory leak in the cycle detector we added a couple years ago to surface these bugs a bit more gently.

Put another way: trees are statically stable, DAGS are dynamically stable. So it's down to whether what you accomplish with it is worth all of the effort. I predict if SC gets traction, that one of the videos will be about whether you actually need a DAG or whether your problem can be better represented as a tree. (Just because the feature exists, doesn't mean you need to use it on every project)