Thedenotational semantics of theActor model is the subject of denotationaldomain theory forActors. The historical development of this subject is recounted in [Hewitt 2008b].

The denotational theory of computational system semantics is concerned with finding mathematical objects that represent what systems do. Collections of such objects are calleddomains. TheActor uses the domain of event diagram scenarios. It is usual to assume some properties of the domain, such as the existence of limits of chains (seecpo) and a bottom element. Various additional properties are often reasonable and helpful: the article ondomain theory has more details.

A domain is typically apartial order, which can be understood as an order of definedness. For instance, given event diagram scenariosx andy, one might let "x≤y" mean that "y extends the computationsx".

The mathematical denotation denoted by a systemS is found by constructing increasingly better approximations from an initial empty denotation called⊥_S using some denotation approximating functionprogression_S to construct a denotation (meaning ) forS as follows:

${\displaystyle {\mathbf{D}\mathbf{e}\mathbf{n}\mathbf{o}\mathbf{t}\mathbf{e}}_{\mathtt{S}}\equiv \underset{i\to \mathrm{\infty }}{lim}{\mathbf{p}\mathbf{r}\mathbf{o}\mathbf{g}\mathbf{r}\mathbf{e}\mathbf{s}\mathbf{s}\mathbf{i}\mathbf{o}\mathbf{n}}_{{\mathtt{S}}^i}({\mathrm{\perp }}_{\mathtt{S}})}$

It would be expected thatprogression_S would bemonotone,i.e., ifx≤y thenprogression_S(x)≤progression_S(y). More generally, we would expect that

If ∀i∈ωx_i ≤x_i+1, then${\displaystyle {\mathbf{p}\mathbf{r}\mathbf{o}\mathbf{g}\mathbf{r}\mathbf{e}\mathbf{s}\mathbf{s}\mathbf{i}\mathbf{o}\mathbf{n}}_{\mathtt{S}}(\underset{i\to \mathrm{\infty }}{lim}{\mathtt{x}}_i)=\underset{i\to \mathrm{\infty }}{lim}{\mathbf{p}\mathbf{r}\mathbf{o}\mathbf{g}\mathbf{r}\mathbf{e}\mathbf{s}\mathbf{s}\mathbf{i}\mathbf{o}\mathbf{n}}_{\mathtt{S}}({\mathtt{x}}_i)}$

This last stated property ofprogression_S is called ω-continuity.

A central question of denotational semantics is to characterize when it is possible to create denotations (meanings) according to the equation forDenote_S. A fundamental theorem of computational domain theory is that ifprogression_S is ω-continuous thenDenote_S will exist.

It follows from the ω-continuity ofprogression_S that

progression_S(Denote_S) =Denote_S

The above equation motivates the terminology thatDenote_S is afixed point ofprogression_S.

Furthermore this fixed point is least among all fixed points ofprogression_S.

An important aspect ofdenotational semantics of programming languages is compositionality, by which the denotation of a program is constructed from denotations of its parts. For example consider the expression "<expression₁> + <expression₂>". Compositionality in this case is to provide a meaning for "<expression₁> + <expression₂>" in terms of the meanings of<expression₁> and<expression₂>.

TheActor model provides a modern and very general way the compositionality of programs can be analyzed. Scott and Strachey [1971] proposed that the semantics of programming languages be reduced to the semantics of thelambda calculus and thus inherit thedenotational semantics of the lambda calculus. However, it turned out that concurrent computation could not be implemented in the lambda calculus (seeIndeterminacy in concurrent computation). Thus there arose the problem of how to provide modular denotational semantics for concurrent programming languages. One solution to this problem is to use the Actor model of computation. In Actor model, programs are Actors that are sentEval messages with the address of an environment (explained below) so that programs inherit their denotational semantics from the denotational semantics of the Actor model (an idea published in Hewitt [2006]).

Environments hold the bindings of identifiers. When an environment is sent aLookup message with the address of an identifierx, it returns the latest (lexical) binding ofx.

As an example of how this works consider the lambda expression<L> below which implements a tree data structure when supplied with parameters for aleftSubTree andrightSubTree. When such a tree is given a parameter message"getLeft", it returnleftSubTree and likewise when given the message"getRight" it returnsrightSubTree.

 λ(leftSubTree, rightSubTree)   λ(message)if (message == "getLeft")then leftSubTreeelse if (message == "getRight")then rightSubTree

Consider what happens when an expression of the form"(<L> 1 2)" is sent anEval message with environmentE. One semantics for application expressions such as this one is the following:<L>, 1 and2 are each sentEval messages with environmentE. The integers1 and2 immediately reply to theEval message with themselves.

However,<L> responds to theEval message by creating aclosure Actor (process)C that has an address (calledbody) for<L> and an address (calledenvironment) forE. The Actor"(<L> 1 2)" then sendsC the message[1 2].

WhenC receives the message[1 2], it creates a new environment ActorF which behaves as follows:

1. When it receives aLookup message for the identifierleftSubTree, it responds with1
2. When it receives aLookup message for the identifierrightSubTree, it responds with2
3. When it receives aLookup message for any other identifier, it forwards theLookup message toE

The Actor (process)C then sends anEval message with environmentF to the following actor (process):

   λ(message)if (message == "getLeft")then leftSubTreeelse if (message == "getRight")then rightSubTree

For another example consider the Actor for the expression "<expression₁> + <expression₂>" which has addresses for two other actors (processes)<expression₁> and<expression₂>. When the composite expression Actor (process) receives anEval message with addresses for an environment ActorE and a customerC, it sendsEval messages to<expression₁> and<expression₂> with environmentE and sendsC a new Actor (process)C₀. WhenC₀ has received back two valuesN₁ andN₂, it sendsC the valueN₁+N₂. In this way, the denotational semantics forprocess calculi and theActor model provide a denotational semantics for "<expression₁> + <expression₂>" in terms of the semantics for<expression₁> and<expression₂>.

The denotational compositional semantics presented above is very general and can be used forfunctional,imperative,concurrent,logic,etc. programs (see [Hewitt 2008a]). For example it easily provides denotation semantics for constructs that are difficult to formalize using other approaches such asdelays andfutures.

In his doctoral dissertation,Will Clinger developed the first denotation semantics for the Actor model.

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

The augmented Actor event diagrams [seeActor model theory] form a partially ordered set <Diagrams,  ≤ > from which to construct the power domainP[Diagrams] (see the section onDenotations 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. Forx,y∈Diagrams,x≤y meansx is a stage the computation could go through on its way toy. The completed elements ofDiagrams represent computations that have terminated and nonterminating computations that have become infinite. The completed elements may be characterized abstractly as the maximal elements ofDiagrams [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

${\displaystyle x_0\le x_1\le x_2\le x_3\le ...}$

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 domainDiagrams 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.

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

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

For the actor event diagram domainDiagrams, an element ofP[Diagrams] represents a list of possible initial histories of a computation. Since for elementsx andy ofDiagrams,x≤y means thatx is an initial segment of the initial historyy, the requirement that elements ofP[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

${\displaystyle R\approx S\to 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 (+, ×, →, 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?

Inbehavioral semantics, developed byIrene 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 ofpending 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 asfinite 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].

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 computationsDiagrams. 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 ofDiagrams

${\displaystyle x_0\le x_1\le x_2\le x_3\le ...}$

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 ifx≤y andx≠y, then some pending event ofx is realized iny. Since in this case eachx_i has at most one pending event, every pending event in the sequence becomes realized. Hence the sequence

${\displaystyle x_0\le x_1\le x_2\le x_3\le ...}$

has a least upper bound inDiagrams in accord with intuition.

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

Hewitt [2006b] published a new denotational semantics for Actors based on Timed Diagrams. The Timed Diagrams model stands in contrast to Clinger[1981] which constructed an ω-complete power domain from an underlying incompletediagrammatic domain, which did not include time. The advantage of the domainTimed Diagrams model is that it is physically motivated and the resultingcomputations have the desired property of ω-completeness (therefore unboundednondeterminism) which provides guarantee of service.

Timed Diagrams denotational semantics constructs an ω-complete computationaldomain for Actor computations. In the domain, for each eventin an Actor computation, there is a delivery time which represents the time at whichthe message is delivered such that each delivery time satisfies the following conditions:

1. The delivery time is a positive rational number that is not the same as the delivery time of any other message.
2. The delivery time is more than a fixed δ greater than the time of its activating event. It will later turn out that the value of δ doesn't matter. In fact the value of δ can even be allowed to decrease linearly with time to accommodate Moore's Law.

The Actor event timed diagrams form a partially ordered set <TimedDiagrams, ≤>. The diagrams are partial computation histories representing "snapshots" (relativeto some frame of reference) of a computation on its way to being completed. Ford1,d2εTimedDiagrams, d1≤d2 means d1 is a stage the computation could gothrough on its way to d2The completed elements ofTimedDiagrams represent computations that haveterminated and nonterminating computations that have become infinite. The completedelements may be characterized abstractly as the maximal elements ofTimedDiagrams. Concretely, the completed elements are those having no pending events.

Theorem:TimedDiagrams is an ω-complete domain of Actor computations i.e.,

1. If D⊆TimedDiagrams is directed, the least upper bound ⊔D exists; furthermore ⊔D obeys all the laws ofActor model theory.
2. The finite elements ofTimedDiagrams are countable where an element xεTimedDiagrams is finite (isolated) if and only if D⊆TimedDiagrams is directed and x≤VD, there exists dεD with x≤d. In other words, x is finite if one must go through x in order to get up to or above x via the limit process.
3. Every element ofTimedDiagrams is the least upper bound of a countable increasing sequence of finite elements.

• Definition: The domain <Power[TimedDiagrams], ⊆> is the set of possible initial histories M of a computation such that
  1. M is downward-closed,i.e., if dεM, then ∀d’εTimedDiagrams d’≤d ⇒ d’εM
  2. M is closed under least upper bounds of directed sets, i.e. if D⊆M is directed, then VDεM
• Note: Although Power[TimedDiagrams] is ordered by ⊆, limits are not given byU. I.e.,

  (∀i∈ω M_i≤M_i+1) ⇒U_i∈ω M_i ⊆ ⊔_i∈ω M_i

  E.g., If ∀i d_iεTimedDiagrams and d_i≤d_i+1 and M_i= {d_k | k ≤i} then

  ⊔_i∈ω M_i =U_i∈ωM_iU{ ⊔_i∈ω d_i }

• Theorem: Power [TimedDiagrams] is an ω-complete domain.

An Actor computation can progress in many ways.Let d be a diagram with next scheduled event e andX ≡ {e’ | e ─≈→_1-message e’} (seeActor model theory),Flow(d) is defined to be the set of all timed diagrams with d and extensions of d by Xsuch that

1. the arrival all of the events of X has been scheduled where
2. the events of X are scheduled in all possible orderings among the scheduled future events of d
3. subject to the constraint that each event in X is scheduled at least δ after e and every event in X is scheduled at least once in every δ interval after that.

(Recall that δ is the minimum amount of time to deliver a message.)

Flow(d) ≡ {d} if d is complete.

Let S be an Actor system, Progression_S is a mapping

Power[TimedDiagrams]→Power[TimedDiagrams]

Progression_S(M) ≡ U_dεM Flow(d)

Theorem: Progression_S is ω-continuous.

I.e., if ∀i M_i⊆M_i+1 then Progression_S(⊔_iεω M_i) = ⊔_iεω Progression_S(M_i)

Furthermore the least fixed point of Progression_S is given by the Concurrency Representation Theorem as follows:

⊔_iεω Progression_Sⁱ(⊥_S)

where ⊥_S is the initial configuration of S.

The denotation Denote_S of an Actor system S is the set of all computations of S.

Define thetime abstraction of a timed diagram to be the diagram with the time annotationsremoved.

Representation Theorem: The denotation Denote_{S of an Actor system S is thetime abstraction of}

⊔_iεω Progression_Sⁱ (⊥_S)

Using the domainTimedDiagrams, which is ω-complete, is important because itprovides for the direct expression of the above representation theorem for the denotationsof Actor systems by directly constructing a minimal fixed point.

The criterion of continuity for the graphs of functions that Scott used to initially develop the denotational semantics of functions can be derived as a consequence of the Actor laws for computation as shown in the next section.

• Dana Scott and Christopher Strachey. Toward a mathematical semantics for computer languages Oxford Programming Research Group Technical Monograph. PRG-6. 1971.
• Irene Greif.Semantics of Communicating Parallel Professes MIT EECS Doctoral Dissertation. August 1975.
• Joseph E. Stoy,Denotational Semantics: The Scott-Strachey Approach to Programming Language Semantics.MIT Press, Cambridge, Massachusetts, 1977. (A classic if dated textbook.)
• Gordon Plotkin.A powerdomain construction SIAM Journal of Computing September 1976.
• Edsger Dijkstra.A Discipline of ProgrammingPrentice Hall. 1976.
• Krzysztof R. Apt, J. W. de Bakker.Exercises in Denotational Semantics MFCS 1976: 1-11
• J. W. de Bakker.Least Fixed Points Revisited Theor. Comput. Sci. 2(2): 155-181 (1976)
• Carl Hewitt andHenry BakerActors and Continuous Functionals Proceeding of IFIP Working Conference on Formal Description of Programming Concepts. August 1–5, 1977.
• Henry Baker.Actor Systems for Real-Time Computation MIT EECS Doctoral Dissertation. January 1978.
• Michael Smyth.Power domainsJournal of Computer and System Sciences. 1978.
• C.A.R. Hoare.Communicating Sequential ProcessesCACM. August, 1978.
• George Milne andRobin Milner.Concurrent processes and their syntaxJACM. April, 1979.
• Nissim Francez,C.A.R. Hoare, Daniel Lehmann, and Willem-Paul de Roever.Semantics of nondeterminism, concurrency, and communication Journal of Computer and System Sciences. December 1979.
• Nancy Lynch andMichael J. Fischer.On describing the behavior of distributed systems in Semantics of Concurrent Computation.Springer-Verlag. 1979.
• Jerald SchwartzDenotational semantics of parallelism in Semantics of Concurrent Computation. Springer-Verlag. 1979.
• William Wadge.An extensional treatment of dataflow deadlock Semantics of Concurrent Computation. Springer-Verlag. 1979.
• Ralph-Johan Back.Semantics of Unbounded NondeterminismICALP 1980.
• David Park.On the semantics of fair parallelism Proceedings of the Winter School on Formal Software Specification. Springer-Verlag. 1980.
• Will Clinger,Foundations of Actor Semantics. MIT Mathematics Doctoral Dissertation, June 1981. (Quoted by permission of author.)
• Carl HewittWhat is Commitment? Physical, Organizational, and Social Pablo Noriegaet al. editors. LNAI 4386. Springer-Verlag. 2007.

• Subject:Computer science