ParaSail has had “structured concurrency” since its inception in 2009. A very recent article published in the new journal, describing ParaSail may be found here: http://programming-journal.org/2019/3/7/
The main ParaSail web page is at: http://parasail-lang.org where a link to a blog on the design of ParaSail may be found (parasail-programming-language on blogspot).
ParaSail supports automatic thread cancellation by returning or exiting from a concurrent loop or other concurrent control structure. This is discussed in the paper mentioned above, and is illustrated in examples that come with the ParaSail release (available at the parasail-lang web page), such as the breadth-first search operation in the Directed-Graph module (dgraph.psl), shown below. Note the “return” statement which cancels other threads participating in the parallel search, once a desired node is found:
func BFS(DGraph; Start : Node_Set;
Is_Target : func (DGraph; Node_Id) -> Boolean)
-> optional Node_Id is
// Do a breadth-first search on graph for node that satisfies Is_Target.
// Start is set of nodes to start from.
// Return Node_Id for first node that satisfies Is_Target.
// Return null if no such node.
var Seen : Array<Atomic<Boolean>, Indexed_By => Node_Id> :=
Create(1..Length(DGraph.G), Initial_Value => Create(#false));
// NOTE: This is only an approximate breadth-first search.
// It is possible for some parts of the search to get "ahead"
// of other parts in terms of depth. A barrier would need
// to be created if it was important that the result returned
// represented the shallowest node that satisfied Is_Target.
*Outer*
for Next_Set => Start loop // Start with the initial set of roots
for N in Next_Set concurrent loop // Look at each node in set
if not Value(Seen[N]) then
// Not yet seen; mark it to prevent re-checking this node.
// NOTE: Race condition here, but we want to avoid overhead
// of comp-and-swap, and race condition is "benign"
Set_Value(Seen[N], #true);
if Is_Target(DGraph, N) then
// Found a node that satisfies Is_Target
// This "return" will cancel other concurrent threads
return N;
end if;
// Continue with successors of this node
continue loop Outer with Next_Set => DGraph.G[N].Succs;
end if;
end loop;
end loop Outer;
// No node found
return null;
end func BFS;
Huh, that’s really interesting. Thanks for sharing!
From your example and a quick glance at the links, it sounds like ParaSail mostly expresses parallelism “implicitly”, via other language constructs like loops or n-ary function arguments that are resolved in parallel. So I’m curious how it handles “explicit” and dynamic concurrency. For example, what does a server accept loop look like in ParaSail?
ParaSail supports the notion of “concurrent” objects which can be used for synchronizing between multiple clients and multiple servers, using implicit locks and optionally implicit queuing. This is described in the article mentioned above in the journal, V3.3.
So I read the article, and it was really interesting. (I especially like the regions and return value optimizations, that’s pretty slick.) But I’m still not sure what an explicitly concurrent ParaSail program looks like. The emphasis in the examples all seems to be on how you can write sequential-ish code and then ParaSail’s semantics allow it to extract a parallel speedup. Which is really cool, but I still don’t know how to write an accept loop :-).
I’m also curious to hear more about how you handle cancellation. Is there any way to control where cancellation can happen? How do you prevent a task from being cancelled in the middle of a critical section? How fine-grained in the cancellation? For example, can you write an accept loop that lets some external code cancel accepting new connections, while waiting for the old connections to finish?
Below is an example of a breadth-first search (BFS) that is explicitly parallel, and includes a “return” statement that cancels all “sibling” concurrent threads once a node is found that satisfies the Is_Target predicate. Cancellation is deferred when inside a “locked” operation on a “concurrent” object. In this case, the only “locked” operations are “Value” and “Set_Value,” which are in fact operations on Atomic that can be implemented as uninterruptible lock-free operations on most hardware.
The general idea of having a return or exit from a concurrent loop automatically cancel all sibling threads works quite well, but as you imply, it is important that locking operations not be interrupted. There is also a rule that a concurrent loop with the possibility of a disruptive early exit (as in this example) must not update non-concurrent objects declared outside the loop. This is a compile-time check. So in this example, the update to Seen[N] is permitted, because Seen[N] is of an Atomic<…> type, which is a concurrent type with locking operations. This is discussed more in the ParaSail reference manual.
In any case, here is the breadth-first search. Note that this is part of a directed graph module (dgraph.psl), which is among the examples included in the downloadable (source + binary) release 8.0 of ParaSail:
func BFS(DGraph; Start : Node_Set;
Is_Target : func (DGraph; Node_Id) -> Boolean)
-> optional Node_Id is
// Do a breadth-first search on graph for node that satisfies Is_Target.
// Start is set of nodes to start from.
// Return Node_Id for first node that satisfies Is_Target.
// Return null if no such node.
var Seen : Array<Atomic<Boolean>, Indexed_By => Node_Id> :=
Create(1..Length(DGraph.G), Initial_Value => Create(#false));
// NOTE: This is only an approximate breadth-first search.
// It is possible for some parts of the search to get "ahead"
// of other parts in terms of depth. A barrier would need
// to be created if it was important that the result returned
// represented the shallowest node that satisfied Is_Target.
*Outer*
for Next_Set => Start loop // Start with the initial set of roots
for N in Next_Set concurrent loop // Look at each node in set
if not Value(Seen[N]) then
// Not yet seen; mark it to prevent re-checking this node.
// NOTE: Race condition here, but we want to avoid overhead
// of comp-and-swap, and race condition is "benign"
Set_Value(Seen[N], #true);
if Is_Target(DGraph, N) then
// Found a node that satisfies Is_Target
// This "return" will cancel other concurrent threads
return N;
end if;
// Continue with successors of this node
continue loop Outer with Next_Set => DGraph.G[N].Succs;
end if;
end loop;
end loop Outer;
// No node found
return null;
end func BFS;