We now describe three example applications that will allow us to get a feel of the programming style required by our model and each of its implementations. They will also serve to collect some performance data on the various implementations.
We consider a problem treated by Dijkstra, and solve it by a Kahn process network, as described in [11]. One is requested to generate the first n elements of the sequence of integers of the form 2a3b5c (a,b,c≥0) in increasing order, without omission or repetition. The idea of the solution is to think of that sequence as a single object and to notice that if we multiply it by 2, 3 or 5, we obtain subsequences. The solution sequence is the least sequence containing 1 and satisfying that property and can be computed as illustrated on Figure 1. The thread merge assumes two increasing sequences of integers as input and merges them, eliminating duplications on the fly. The thread times multiplies all elements of its input Fifo by the scalar a. Finally the thread x prints the flow of numbers and put them in the three Fifos.2
All threads communicate and synchronize through MVars, except that the x thread itself writes its data in three Fifos for the times threads to take it. The computation is initiated by putting the value 1 in the m235 MVar so that x starts running. Such a computation can be expressed as a list comprehension in some languages, such as Haskell3 [21].
Our second example is Eratosthene sieve. The sieve as a set of concurrent threads is described in [11] (where it is said to appear the very first time in [19]). A variant can also be found in [10]. The program is structured as a chain of threads exchanging messages.
Thus the sieve builds as a chain of filter threads with a generator (integers) on the left and an expander (sift) preceding the consumer (output) on the right. Threads communicate through MVars. Figure 2 shows the threads at startup and after the first and second prime numbers have been found.
The code, shown in Appendix A.2 in both direct and indirect style (we’ll explain the distinction when presenting the implementations), is particularly simple.
Our third example is a concurrent sort described in [10]. As pointed out by the authors, both bubble sort and insertion sort are sequentialized versions of this concurrent algorithm.
This sorting algorithm is made of a network of simple comparator threads, each of which is used to sort a pair of values from two input MVars to two output MVars. Such a comparator with inputs x and y and outputs hi and lo is shown on Figure 3(a). Figure 3(b) shows a network for sorting a group of 4 values.
MVars will be used to store the initial and final values, as well as for the communication between the comparators. They are not shown on the figure. We don’t show the source code of the concurrent sort to save space.
