Rather than providing completely separate languages for coordination and computation, several researchers have instead extended a functional language with a small, but distinct, process control language. In its simplest form, this can be simply a set of annotations that specify process creation etc. More sophisticated systems, such as Caliban [Kelly, 1989], or first-class schedules [Mirani and Hudak, 1995] support normal functional expressions as part of the process control language.
Several languages have been defined to use parallel annotations. Depending on the approach taken, these annotations may be either hints that the runtime system can ignore, or directives that it must obey. In addition to specifying the parallelism and evaluation degree of the parallel program (the what and how), as for evaluation strategies, annotation-based approaches often also permit explicit placement annotations (the where).
An early annotation approach that is similar to that used in GpH was that of Burton [Burton, 1984], who defined three annotations to control the reduction order of function arguments: strict, lazy and parallel. In his thesis [Hughes, 1983], Hughes extends this set with a second strict annotation (qes), that reverses the conventional evaluation order of function and argument, evaluating the function body before the argument. Clearly all these annotations can be expressed as straightforward evaluation strategies, or even directly in GpH.
These simple beginnings have led to the construction of quite elaborate annotation schemes. One particularly rich set of annotations was defined for the Hope+ implementation on ICL's Flagship machine [Glynn et al., 1988][Kewley and Glynn, 1989]. This covered behavioural aspects such as data and process placement, as well as simple partitioning and sequencing. As a compromise between simplicity and expressibility, however, we will describe the well-known set of annotations that have been provided for Concurrent Clean [Nöcker et al., 1991].
The basic Concurrent Clean annotation is e {P} f args, which sparks a task to evaluate f args to WHNF on some remote processor and continues execution of e locally. Before the task is exported its arguments, args, are reduced to NF. The equivalent strategy is rnf args `seq` (rwhnf (f args) `par` e).
The other Concurrent Clean annotations differ from the {P} annotation in either the degree of evaluation or the placement of the parallel task. Since GpH delegates task placement to the runtime system, there is no direct strategic equivalent to the annotations that perform explicit placement.
Other important annotations are:
As with evaluation strategies, Concurrent Clean annotations cleanly separate dynamic behaviour and algorithm. However, because there is no language for composing annotations, the more sophisticated behaviours that can be captured by composing strategies cannot be described using Concurrent Clean annotations. This is, in fact, a general problem with the annotation approach.
Caliban [Kelly, 1989] provides a separation of algorithm and parallelism that is similar to that used for evaluation strategies. The moreover construct is used to describe the parallel control component of a program, using higher-order functions to structure the process network. Unlike evaluation strategies, the moreover clause inhabits a distinct value space from the algorithm - in fact one which comprises essentially only values that can be resolved at compile-time to form a static wiring system. Caliban does not support dynamic process networks, or control strategies. A clean separation between algorithm and control is achieved by naming processes. These processes are the only values which can be manipulated by the moreover clause. This corresponds to the use of closures to capture computations in the evaluation strategy model.
For example, the following function defines a pipeline. The Box syntax is used to create an anonymous process which simply applies the function it labels to some argument. arc indicates a wiring connection between two processes. chain creates a chain of wiring connections between elements of a list. The result of the pipeline function for a concrete list of functions and some argument is thus the composition of all the functions in turn to the initial value. Moreover, each function application is created as a separate process.
pipeline fs x = result |
where result = (foldr (.) id fs) x |
moreover (chain arc (map (Box) fs)) |
/\ (arc Box(last fs) x) |
/\ (arc Box(head fs) result)
|
Para-functional programming [Hudak, 1986][Hudak, 1988][Hudak, 1991] extends functional programming with explicit parallel scheduling control clauses, which can be used to express quite sophisticated placement and evaluation schemes. These control clauses effectively form a separate language for process control. For ease of comparison with evaluation strategies, we follow Hudak's syntax for para-functional programming in Haskell [Hudak, 1991].
Hudak distinguishes two kinds of control construct: schedules are used to express sequential or parallel behaviours; while mapped expressions are used to specify process placements. These two notions are expressed by the sched and on constructs, respectively, which are attached directly to expressions.
In order to use functional expressions in schedules, Hudak introduces labelled expressions: l@e labels expression e with label l (this syntax is entirely equivalent to a let expression.
There are three primitive schedules: Dlab is the demand
for the labelled expression lab; ^lab represents the
start of evaluation for lab; and lab^ represents the
end of evaluation for lab. Whereas a value may be demanded many
times, it can only be evaluated once. Schedules can be combined using
either sequential composition (.) or parallel composition
(|). Since it is such a common case, the schedule lab can be
used as a shorthand for Dlab.lab^.
Schedules execute in parallel with the expression to which they
are attached.
So, for example,
(l@e0 m@e1 n@e2) sched l^ . (Dm|Dn)requires e0 to complete evaluation before either m or n are demanded.
Evaluating schedules in parallel is one major difference from the evaluation strategy approach, where all evaluation is done under control of the strategy. A second major difference is that schedules are not normal functional values, and hence are not under control of the type system.
The second kind of para-functional construct is used to specify static or dynamic process placement. The expression exp on pid specifies that exp is to be executed on the processor identified by an integer pid. There is a special value self, which indicates the processor id of the current processor, and libraries can be constructed to build up virtual topologies such as meshes, trees etc. For example,
sort (QT q1 q2 q3 q4) =
merge (sort q1 on (left self))
(sort q2 on (right self))
(sort q3 on (up self))
(sort q4 on (down self))
would sort each sub-quadtree on a different neighbouring processor,
and merge the results on the current processor. Because GpH
deliberately doesn't address the issue of thread placement, there is
no equivalent to mapped expressions in evaluation strategies.
First-Class schedules [Mirani and Hudak, 1995] combine para-functional programming with a monadic approach. Where para-functional schedules and mapped expressions are separate language constructs, first-class schedules are fully integrated into Haskell. This integration allows schedules to be manipulated as normal Haskell monadic values.
The primitive schedule constructs and combining forms are similar to those provided by para-functional programming. The schedule d e demands the value of expression e, returning immediately, while r e suspends the current schedule until e has been evaluated. Both these constructs have type a -> OS Sched. Similarly, both the sequential and parallel composition operations have type OS Sched -> OS Sched -> OS Sched. The monadic type OS is used to indicate that schedules may interact in a side-effecting way with the operating system. As we will see, this causes loss of referential transparency in only one respect.
Rather than using a language construct to attach schedules to expressions, Mirani and Hudak instead provide a function sched, whose type is sched :: a -> OS Sched -> a, and which is equivalent to our using function. The sched function takes an expression e and a schedule s, and executes the schedule. If the schedule terminates, then the value of e is returned, otherwise the value of the sched application is bottom. There are also constructs to deal with task placement and dynamic load information which have no equivalent strategic formulation.
In evaluation strategy terms, both the d and r schedules can be replaced by calls to rwhnf without affecting the semantics of those para-functional programs that terminate. Unlike evaluation strategies, however, with first-class schedules it is also possible to suspend on a value without ever evaluating it. Thus para-functional schedules can give rise to deadlock in situations which cannot be expressed with evaluation strategies. A trivial example might be:
f x y = (x,y) `sched` r x . d y | r y . d x
Compared with evaluation strategies, it is not possible to take as much direct advantage of the type system: all schedules have type OS Sched rather than being parameterised on the type of the value(s) they are scheduling. Clearly schedules could be used to encode strategies, thus regaining the type information.
There can also be a loss of referential transparency when using schedules, since expressions involving sched may sometimes evaluate to bottom, and other times to a non-bottom value. This can happen both through careless use of demand and wait as in the deadlock-inducing example above, and conceivably if dynamic load information is used to demand an otherwise unneeded value. If the program terminates (yields a non-bottom value), however, it will always yield the same value.