Denotational semantics of the Actor model

The domain of Actor computations

Clinger [1981] explained the domain of Actor computations as follows:

The augmented Actor event diagrams [see Actor model theory] form a partially ordered set < Diagrams,  ≤ > from which to construct the power domain P[Diagrams] (see the section on Denotations below). The augmented diagrams are partial computation histories representing "snapshots" [relative to some frame of reference] of a computation on its way to being completed. For x,y∈Diagrams, x≤y means x is a stage the computation could go through on its way to y. The completed elements of Diagrams represent computations that have terminated and nonterminating computations that have become infinite. The completed elements may be characterized abstractly as the maximal elements of Diagrams [see William Wadge 1979]. Concretely, the completed elements are those having non pending events. Intuitively, Diagrams is not ω-complete because there exist increasing sequences of finite partial computations

x₀ ≤ x₁ ≤ x₂ ≤ x₃ ≤ ...

in which some pending event remains pending forever while the number of realized events grows without bound, contrary to the requirement of finite [arrival] delay. Such a sequence cannot have a limit, because any limit would represent a completed nonterminating computation in which an event is still pending.

To repeat, the actor event diagram domain Diagrams is incomplete because of the requirement of finite arrival delay, which allows any finite delay between an event and an event it activates but rules out infinite delay.

Denotations

In his doctoral dissertation, Will Clinger explained how power domains are obtained from incomplete domains as follows:

From the article on Power domains: P[D] is the collection of downward-closed subsets of domain D that are also closed under existing least upper bounds of directed sets in D. Note that while the ordering on P[D] is given by the subset relation, least upper bounds do not in general coincide with unions.

For the actor event diagram domain Diagrams, an element of P[Diagrams] represents a list of possible initial histories of a computation. Since for elements x and y of Diagrams, x≤y means that x is an initial segment of the initial history y, the requirement that elements of P[Diagrams] be downward-closed has a clear basis in intuition.

...

Usually the partial order from which the power domain is constructed is required to be ω-complete. There are two reasons for this. The first reason is that most power domains are simply generalizations of domains that have been used as semantic domains for conventional sequential programs, and such domains are all complete because of the need to compute fixed points in the sequential case. The second reason is that ω-completeness permits the solution of recursive domain equations involving the power domain such as

R ≈ S → P[S + (S $\times$ R)]

which defines a domain of resumptions [Gordon Plotkin 1976]. However, power domains can be defined for any domain whatsoever. Furthermore the power domain of a domain is essentially the power domain of its ω-completion, so recursive equations involving the power domain of an incomplete domain can still be solved, provide the domains to which the usual constructors (+, $\times$,  → , and *) are applied are ω-complete. It happens that defining Actor semantics as in Clinger [1981] does not require solving any recursive equations involving the power domain.

In short, there is no technical impediment to building power domains from incomplete domains. But why should one want to do so?

In behavioral semantics, developed by Irene Greif, the meaning of program is a specification of the computations that may be performed by the program. The computations are represented formally by Actor event diagrams. Greif specified the event diagrams by means of causal axioms governing the behaviors of individual Actors [Greif 1975].

Henry Baker has presented a nondeterministic interpreter generating instantaneous schedules which then map onto event diagrams. He suggested that a corresponding deterministic interpreter operating on sets of instantaneous schedules could be defined using power domain semantics [Baker 1978].

The semantics presented in [Clinger 1981] is a version of behavioral semantics. A program denotes a set of Actor event diagrams. The set is defined extensionally using power domain semantics rather than intensionally using causal axioms. The behaviors of individual Actors is defined functionally. It is shown, however, that the resulting set of Actor event diagrams consists of exactly those diagrams that satisfy causal axioms expressing the functional behaviors of Actors. Thus Greif's behavioral semantics is compatible with a denotational power domain semantics.

Baker's instantaneous schedules introduced the notion of pending events, which represent messages on the way to their targets. Each pending event must become an actual (realized) arrival event sooner or later, a requirement referred to as finite delay. Augmenting Actor event diagrams with sets of pending events helps to express the finite delay property, which is characteristic of true concurrency [Schwartz 1979].

Sequential computations form an ω-complete subdomain of the domain of Actor computations

In his 1981 dissertation, Clinger showed how sequential computations form a subdomain of concurrent computations:

Instead of beginning with a semantics for sequential programs and then trying to extend it for concurrency, Actor semantics views concurrency as primary and obtains the semantics of sequential programs as a special case.

...

The fact that there exist increasing sequences without least upper bounds may seem strange to those accustomed to thinking about the semantics of sequential programs. It may help to point out that the increasing sequences produced by sequential programs all have least upper bounds. Indeed, the partial computations that can be produced by sequential computation form an ω-complete subdomain of the domain of Actor computations Diagrams. An informal proof follows.

From the Actor point of view, sequential computations are a special case of concurrent computations, distinguishable by their event diagrams. The event diagram of a sequential computation has an initial event, and no event activates more than one event. In other words, the activation ordering of a sequential computation is linear; the event diagram is essentially a conventional execution sequence. This means that the finite elements of Diagrams

x₀ ≤ x₁ ≤ x₂ ≤ x₃ ≤ ...

corresponding to the finite initial segments of a sequential execution sequence all have exactly one pending event, excepting the largest, completed element if the computation terminates. One property of the augmented event diagrams domain < Diagrams,  ≤ > is that if x≤y and x≠y, then some pending event of x is realized in y. Since in this case each x_i has at most one pending event, every pending event in the sequence becomes realized. Hence the sequence

x₀ ≤ x₁ ≤ x₂ ≤ x₃ ≤ ...

has a least upper bound in Diagrams in accord with intuition.

The above proof applies to all sequential programs, even those with choice points such as guarded commands. Thus Actor semantics includes sequential programs as a special case, and agrees with conventional semantics of such programs.