Declarative Concurrency

A deterministic model of concurrency, compatible with DeclarativeProgramming.

From Chapter 4 of ConceptsTechniquesAndModelsOfComputerProgramming:

Concurrency can be simple

This chapter extends the declarative model of Chapter 2 with concurrency while still being declarative. That is, all the programming and reasoning techniques for declarative programming still apply. This is a remarkable property that deserves to be more widely known. We will explore it throughout this chapter. The intuition underlying it is quite simple. It is based on the fact that a DataflowVariable? can be bound to only one value. This gives the following two consequences:

What stays the same: The result of a program is the same whether or not it is concurrent. Putting any part of the program in a thread does not change the result.
What is new: The result of a program can be calculated incrementally. If the input to a concurrent program is given incrementally, then the program will calculate its output incrementally as well.

Let us give an example to fix this intuition. Consider the following sequential program that calculates a list of successive squares by generating a list of successive integers and then mapping each to its square:

  fun {Gen L H}
{Delay 100}
if L>H then nil else L|{Gen L+1 H} end
  end
  Xs={Gen 1 10}
  Ys={Map Xs fun {$ X} X*X end}
  {Browse Ys}

(The {Delay 100} call waits for 100 milliseconds before continuing.) We can make this concurrent by doing the generation and mapping in their own threads:

  thread Xs={Gen 1 10} end
  thread Ys={Map Xs fun {$ X} X*X end} end
  {Browse Ys}

This uses the thread <s> end statement, which executes <s> concurrently. What is the difference between the concurrent and the sequential versions? The result of the calculation is the same in both cases, namely [1 4 9 16 ... 81 100]. In the sequential version, Gen calculates the whole list before Map starts. The final result is displayed all at once when the calculation is complete, after one second. In the concurrent version, Gen and Map both execute simultaneously. Whenever Gen adds an element to its list, Map will immediately calculate its square. The result is displayed incrementally, as the elements are generated, one element each tenth of a second.

We will see that the deep reason why this form of concurrency is so simple is that programs have no observable nondeterminism. A program in the declarative concurrent model always has this property, if the program does not try to bind the same variable to incompatible values. This is explained in Section 4.1. Another way to say it is that there are no RaceConditions in a declarative concurrent program. A RaceCondition is just an observable nondeterministic behavior.

[...]

Declarative concurrency

Now we can define what it means for a concurrent program to be declarative. In general, a concurrent program can have many possible executions. [...] The key insight is that all these executions have to end up with the same result. But "the same" does not mean that each variable has to be bound to the same thing. It just means logical equivalence. This leads to the following definition:

A concurrent program is declarative if the following holds for all possible inputs. All executions with a given set of inputs have one of two results: (1) they all do not terminate or (2) they all eventually reach partial termination and give results that are logically equivalent. (Different executions may introduce new variables; we assume that the new variables in corresponding positions are equal.)

Another way to say this is that there is no observable nondeterminism. This definition is valid for eager as well as lazy execution. What’s more, when we introduce non-declarative models (e.g., with exceptions or explicit state), we will use this definition as a criterion: if part of a non-declarative program obeys the definition, we can consider it as declarative for the rest of the program.

Is there an example of declarative concurrency in more conventional situations? The example above isn't better at all than lazy evaluation.

Well, it is only an introductory example.

The example is actually completely different from lazy evaluation! Lazy evaluation does coroutining between producer and consumer (lock-step execution). Declarative concurrency gives slack between producer and consumer (the producer can get ahead of the consumer). -- PVR (PeterVanRoy?)

How would you transform an event loop to invoking concurrent threads as handlers, for example?

Programs with event loops usually have observable nondeterminism, and are not declarative. DeclarativeConcurrency is more suited to computational tasks like simulations, etc. It's a generalization of FunctionalProgramming.

CategoryConcurrency