A language for programming recursive circuits

2. Language
2.5. Concurrency and synchronization
2.5. Concurrency and synchronization

Concurrency and synchronization are embodied directly into the Ko language model. Concurrency is captured by the directed acyclic graph structure of circuits. Synchronization is captured by function boundaries. This is made precise by the following execution invariants, which also guarantee the Ko programs can never deadlock:

C1. Allocation and execution of a circuit transformation (a transformation is an invocation of a function or a macro) does not begin until all arguments passed to it have arrived from upstream transformations.

So, for instance, in this example the function G will not commence execution until both x and y argument values have arrived. Similarly, Sum will not execute until left and right have arrived, and so on.

The pattern shown in the example below, based on (C1), is often handy. In this example the transformation labeled barrier will not execute until both F(x) and G(x) have been invoked and returned their results.

Example1(x) {
	barrier: (
		fx: F(x)
		gx: G(x)
	return: barrier.fx

Another useful pattern takes advantage of the fact that the Ko language allows passing “throw-away” arguments that are not expected by the invoked function. In the example below, strings.Join does not recognize an argument named unused . Regardless, the execution of strings.Join will not commence until Show(x, y) has completed. This technique allows the programmer to force a sequential execution relationship (first Show(x, y) , second strings.Join ), even if the sequenced transformations do not depend on each other from a returned-values point of view.

Example2(x, y) {
	return: strings.Join(
		unused: Show(x, y)
		string: x
		string: y

C2. Once a circuit is executing, it blocks until all of its internal transformations complete, regardless of whether they affect the circuit's return value or not.

For instance, in the following example the value returned by Show does not affect the return value of ShowAndReturn . Regardless, ShowAndReturn will not complete until Show has completed (and printed the value of x ) on the console.

ShowAndReturn(x) {
	showed: Show(x)
	return: x

C3. Transformations within a circuit always execute in an order consistent with their dependency graph.

By default, circuits are executed sequentially (with internal transformations executed in topological order with respect to the circuit graph). Invoking a given circuit with parallel execution can be arranged by using the Parallel macro .

In general, complex scaled synchronization and parallelism patterns can be safely composed using macros for control , like Spin and Wait , in combination with Range .