Actor model
Encyclopedia
In computer science
, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and determine how to respond to the next message received. The Actor model originated in 1973. It has been used both as a framework for a theoretical understanding
of computation
, and as the theoretical basis for several practical implementations
of concurrent systems. The relationship of the model to other work is discussed in Indeterminacy in concurrent computation and Actor model and process calculi
.
, Simula
and early versions of Smalltalk
, as well as capability-based systems and packet switching
. Its development was "motivated by the prospect of highly parallel computing machines consisting of dozens, hundreds or even thousands of independent microprocessors, each with its own local memory and communications processor, communicating via a high-performance communications network." Since that time, the advent of massive concurrency through multi-core
computer architectures has rekindled interest in the Actor model.
Following Hewitt, Bishop, and Steiger's 1973 publication, Irene Greif developed an operational semantics
for the Actors model as part of her doctoral research. Two years later, Henry Baker
and Hewitt published a set of axiomatic laws for Actor systems. Other major milestones include William Clinger's
dissertation, in 1981, introducing a denotational semantics
based on power domains, and Gul Agha
's 1985 dissertation which further developed a transition-based semantic model complementary to Clinger's. This resulted in the full development of actor model theory
.
Major software implementation work was done by Russ Atkinson, Beppe Attardi, Henry Baker, Gerry Barber, Peter Bishop, Peter de Jong, Ken Kahn, Henry Lieberman, Carl Manning, Tom Reinhardt, Richard Steiger, and Dan Theriault, in the Message Passing Semantics Group at Massachusetts Institute of Technology
(MIT). Research groups led by Chuck Seitz at California Institute of Technology
(Caltech) and Bill Dally at MIT constructed computer architectures that further developed the message passing in the model. See Actor model implementation
.
Research on the Actor model has been carried out at Caltech Computer Science, Kyoto University
Tokoro Laboratory, MCC
, MIT Artificial Intelligence Laboratory, SRI
, Stanford University
, University of Illinois at Urbana-Champaign
Open Systems Laboratory, Pierre and Marie Curie University
(University of Paris 6), University of Pisa
, University of Tokyo
Yonezawa Laboratory and elsewhere.
, but differs in that object-oriented software is typically executed sequentially, while the Actor model is inherently concurrent.
An actor is a computational entity that, in response to a message it receives, can concurrently:
There is no assumed sequence to the above actions and they could be carried out in parallel.
Decoupling the sender from communications sent was a fundamental advance of the Actor model enabling asynchronous communication
and control structures as patterns of passing messages
.
Recipients of messages are identified by address, sometimes called "mailing address". Thus an actor can only communicate with actors whose addresses it has. It can obtain those from a message it receives, or if the address is for an actor it has itself created.
The Actor model is characterized by inherent concurrency of computation within and among actors, dynamic creation of actors, inclusion of actor addresses in messages, and interaction only through direct asynchronous message passing
with no restriction on message arrival order.
There are also formalisms that are not fully faithful to the Actor model in that they do not formalize the guaranteed delivery of messages including the following (See Attempts to relate Actor semantics to algebra and linear logic):
of Alonzo Church
can be viewed as the earliest message passing
programming language
(see Hewitt, Bishop, and Steiger 1973; Abelson and Sussman 1985
). For example, the lambda expression below implements a tree data structure when supplied with parameters for a leftSubTree and rightSubTree. When such a tree is given a parameter message "getLeft", it returns leftSubTree and likewise when given the message "getRight" it returns rightSubTree.
λ(leftSubTree,rightSubTree)
λ(message)
if (message "getLeft") then leftSubTree
"getRight") then rightSubTree
However, the semantics of the lambda calculus were expressed using variable substitution
in which the values of parameters were substituted into the body of an invoked lambda expression. The substitution model is unsuitable for concurrency because it does not allow the capability of sharing
of changing resources. Inspired by the lambda calculus, the interpreter
for the programming language Lisp
made use of a data structure called an environment so that the values of parameters did not have to be substituted into the body of an invoked lambda expression. This allowed for sharing of the effects of updating shared data structures but did not provide for concurrency.
pioneered using message passing for computation, motivated by discrete event simulation applications. These applications had become large and unmodular in previous simulation languages. At each time step, a large central program would have to go through and update the state of each simulation object that changed depending on the state of whichever simulation objects that it interacted with on that step. Kristen Nygaard
and Ole-Johan Dahl
developed the idea (first described in an IFIP workshop in 1967) of having methods
on each object
that would update its own local state based on messages from other objects. In addition they introduced a class structure
for objects with inheritance
. Their innovations considerably improved the modularity of programs.
However, Simula used coroutine
control structure instead of true concurrency.
Alan Kay
was influenced by message passing in the pattern-directed invocation of Planner
in developing Smalltalk
-71. Hewitt was intrigued by Smalltalk-71 but was put off by the complexity of communication that included invocations with many fields including global, sender, receiver, reply-style, status, reply, operator selector, etc.
In 1972 Kay visited MIT and discussed some of his ideas for Smalltalk-72 building on the Logo work of Seymour Papert
and the "little person" model of computation used for teaching children to program. However, the message passing of Smalltalk-72 was quite complex. Code in the language was viewed by the interpreter as simply a stream of tokens. As Dan Ingalls later described it:
Thus the message-passing model in Smalltalk-72 was closely tied to a particular machine model and programming-language syntax that did not lend itself to concurrency. Also, although the system was bootstrapped on itself, the language constructs were not formally defined as objects that respond to Eval messages (see discussion below). This led some to believe that a new mathematical model of concurrent computation based on message passing should be simpler than Smalltalk-72.
Subsequent versions of the Smalltalk language largely followed the path of using the virtual methods
of Simula in the message-passing structure of programs. However Smalltalk-72 made primitives such as integers, floating point numbers, etc. into objects
. The authors of Simula had considered making such primitives into objects but refrained largely for efficiency reasons. Java
at first used the expedient of having both primitive and object versions of integers, floating point numbers, etc. The C# programming language (and later versions of Java, starting with Java 1.5) adopted the less elegant solution of using boxing and unboxing, a variant of which had been used earlier in some Lisp
implementations.
The Smalltalk system went on to become very influential, innovating in bitmap displays, personal computing, the class browser interface, and many other ways. For details see Kay's The Early History of Smalltalk. Meanwhile the Actor efforts at MIT remained focused on developing the science and engineering of higher level concurrency. (See the paper by Jean-Pierre Briot for ideas that were developed later on how to incorporate some kinds of Actor concurrency into later versions of Smalltalk.)
s were widely used to model nondeterministic computation. However, they were widely acknowledged to have an important limitation: they modeled control flow but not data flow. Consequently they were not readily composable, thereby limiting their modularity. Hewitt pointed out another difficulty with Petri nets: simultaneous action. I.e., the atomic step of computation in Petri nets is a transition in which tokens simultaneously disappear from the input places of a transition and appear in the output places. The physical basis of using a primitive with this kind of simultaneity seemed questionable to him. Despite these apparent difficulties, Petri nets continue to be a popular approach to modelling concurrency, and are still the subject of active research.
, locks
and buffers
(channels
). It certainly is the case that implementations of the Actor model typically make use of these hardware capabilities. However, there is no reason that the model could not be implemented directly in hardware without exposing any hardware threads and locks. Also, there is no necessary relationship between the number of Actors, threads, and locks that might be involved in a computation. Implementations of the Actor model are free to make use of threads and locks in any way that is compatible with the laws for Actors.
s. During the course of its normal operation, a computer needed to be able to receive information from outside (characters from a keyboard, packets from a network, etc.). So when the information arrived, execution of the computer was "interrupted" and special code called an interrupt handler was called to put the information in a buffer
where it could be subsequently retrieved.
In the early 1960s, interrupts began to be used to simulate the concurrent execution of several programs on a single processor. Having concurrency with shared memory
gave rise to the problem of concurrency control
. Originally, this problem was conceived as being one of mutual exclusion
on a single computer. Edsger Dijkstra
developed semaphores
and later, between 1971 and 1973, Tony Hoare and Per Brinch Hansen
developed monitors
to solve the mutual exclusion problem. However, neither of these solutions provided a programming-language construct that encapsulated access to shared resources. This encapsulation was later accomplished by the serializer construct ([Hewitt and Atkinson 1977, 1979] and [Atkinson 1980]).
The first models of computation (e.g. Turing machines, Post productions, the lambda calculus
, etc.) were based on mathematics and made use of a global state to represent a computational step (later generalized in [McCarthy and Hayes 1969] and [Dijkstra 1976] see Event orderings versus global state). Each computational step was from one global state of the computation to the next global state. The global state approach was continued in automata theory
for finite state
machines and push down stack
machines, including their nondeterministic versions. Such nondeterministic automata have the property of bounded nondeterminism
; that is, if a machine always halts when started in its initial state, then there is a bound on the number of states in which it halts.
Edsger Dijkstra
further developed the nondeterministic global state approach. Dijkstra's model gave rise to a controversy concerning unbounded nondeterminism. Unbounded nondeterminism
(also called unbounded indeterminacy), is a property of concurrency
by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while still guaranteeing that the request will eventually be serviced. Hewitt argued that the Actor model should provide the guarantee of service. In Dijkstra's model, although there could be an unbounded amount of time between the execution of sequential instructions on a computer, a (parallel) program that started out in a well defined state could terminate in only a bounded number of states [Dijkstra 1976]. Consequently, his model could not provide the guarantee of service. Dijkstra argued that it was impossible to implement unbounded nondeterminism.
Hewitt argued otherwise: there is no bound that can be placed on how long it takes a computational circuit called an arbiter
to settle (see metastability in electronics
). Arbiters are used in computers to deal with the circumstance that computer clocks operate asynchronously with input from outside, e.g. keyboard input, disk access, network input, etc. So it could take an unbounded time for a message sent to a computer to be received and in the meantime the computer could traverse an unbounded number of states.
The Actor Model features unbounded nondeterminism which was captured in a mathematical model by Will Clinger using domain theory
. There is no global state in the Actor model.
); there is no requirement for a synchronous handshake with the recipient.
[1961 and 1964], Hewitt proposed the development of a new model of concurrent computation in which communications would not have any required fields at all: they could be empty. Of course, if the sender of a communication desired a recipient to have access to addresses which the recipient did not already have, the address would have to be sent in the communication.
A computation might need to send a message to a recipient from which it would later receive a response. The way to do this is to send a communication which has the message along with the address of another actor called the resumption (sometimes also called continuation
or stack frame) along with the message. The recipient could then cause a response message to be sent to the resumption.
Actor creation plus the inclusion of the addresses of actors in messages means that Actors have a potentially variable topology in their relationship to one another much as the objects in Simula also had a variable topology in their relationship to one another.
.
order. So if an Actor X sent a message M1 to an Actor Y, and later X sent another message M2 to Y, there is no requirement that M1 arrives at Y before M2.
In this respect the Actor model mirrors packet switching
systems which do not guarantee that packets must be received in the order sent. Not providing the order of delivery guarantee allows packet switching to buffer packets, use multiple paths to send packets, resend damaged packets, and to provide other optimizations.
For example, Actors are allowed to pipeline the processing of messages. What this means is that in the course of processing a message M1, an Actor can designate the behavior to be used to process the next message, and then in fact begin processing another message M2 before it has finished processing M1. Just because an Actor is allowed to pipeline the processing of messages does not mean that it must pipeline the processing. Whether a message is pipelined is an engineering tradeoff. How would an external observer know whether the processing of a message by an Actor has been pipelined? There is no ambiguity in the definition of an Actor created by the possibility of pipelining. Of course, it is possible to perform the pipeline optimization incorrectly in some implementations, in which case unexpected behavior may occur.
Locality means that in processing a message an Actor can send messages only to addresses that it receives in the message, addresses that it already had before it received the message and addresses for Actors that it creates while processing the message. (But see Synthesizing Addresses of Actors.)
Also locality means that there is no simultaneous change in multiple locations. In this way it differs from some other models of concurrency, e.g., the Petri net
model in which tokens are simultaneously removed from multiple locations and placed in other locations.
that was developed in Gul Agha's doctoral dissertation, developed later by Gul Agha, Ian Mason, Scott Smith, and Carolyn Talcott.
Behaviors also freed the Actor model from implementation details, e.g., the Smalltalk-72 token stream interpreter. However, it is critical to understand that the efficient implementation of systems described by the Actor model require extensive optimization. See Actor model implementation
for details.
In this way, S can be mathematically characterized in terms of all its possible behaviors (including those involving unbounded nondeterminism). Although DenoteS is not an implementation of S, it can be used to prove a generalization of the Church-Turing-Rosser-Kleene thesis [Kleene 1943]:
A consequence of the above theorem is that a finite Actor can nondeterministically respond with an uncountable number of different outputs.
. Once the Actor model was initially defined, an important challenge was to understand the power of the model relative to Robert Kowalski
's thesis that "computation can be subsumed by deduction". Kowalski's thesis turned out to be false for the concurrent computation in the Actor model (see Indeterminacy in concurrent computation). This result is still somewhat controversial and it reversed previous expectations because Kowalski's thesis is true for sequential computation and even some kinds of parallel computation, e.g. the lambda calculus.
Nevertheless attempts were made to extend logic programming
to concurrent computation. However, Hewitt and Agha [1991] claimed that the resulting systems were not deductive in the following sense: computational steps of the concurrent logic programming systems do not follow deductively from previous steps (see Indeterminacy in concurrent computation).
uses a URL
for the address of an endpoint where an Actor can be reached. Since a URL
is a character string, it can clearly be synthesized although encryption can make it virtually impossible to guess.
Synthesizing the addresses of Actors is usually modeled using mapping. The idea is to use an Actor system to perform the mapping to the actual Actor addresses. For example, on a computer the memory structure of the computer can be modeled as an Actor system that does the mapping. In the case of SOAP
addresses, it's modeling the DNS
and rest of the URL
mapping.
's initial published work on concurrency was also notable in that it was not based on composing sequential processes. His work differed from the Actor model because it was based on a fixed number of processes of fixed topology communicating numbers and strings using synchronous communication. The original Communicating Sequential Processes
model published by Tony Hoare differed from the Actor model because it was based on the parallel composition of a fixed number of sequential processes connected in a fixed topology, and communicating using synchronous message-passing based on process names (see Actor model and process calculi history). Later versions of CSP abandoned communication based on process names in favor of anonymous communication via channels, an approach also used in Milner's work on the Calculus of Communicating Systems
and the π-calculus
.
These early models by Milner and Hoare both had the property of bounded nondeterminism. Modern, theoretical CSP
([Hoare 1985] and [Roscoe 2005]) explicitly provides unbounded nondeterminism.
and subsequent Process calculi. In his Turing lecture, Robin Milner wrote:
, hardware development is furthering local and nonlocal massive concurrency. Local concurrency is enabled by new hardware for 64-bit
multi-core
(Platform 2015 Unveiled at IDF Spring 2005) microprocessors, multi-chip modules, and high performance interconnect
. Nonlocal concurrency is being enabled by new hardware for wired and wireless
broadband
packet switched communications (see Wi-Fi
and Ultra wideband). Both local and nonlocal storage capacities are growing exponentially.
According to Hewitt [2006], the Actor model faces issues in computer and communications architecture, concurrent programming languages, and Web Services including the following:
Many of the ideas introduced in the Actor model are now also finding application in multi-agent systems for these same reasons [Hewitt 2006b 2007b]. The key difference is that agent systems (in most definitions) impose extra constraints upon the Actors, typically requiring that they make use of commitments and goals.
The Actor model is also being applied to client cloud computing
.
, Beppe Attardi, Henry Baker
, Will Clinger, Irene Greif, Carl Hewitt
, Carl Manning, Ian Mason, Ugo Montanari, Maria Simi, Scott Smith, Carolyn Talcott, Prasanna Thati, and Aki Yonezawa.
Important contributions to the implementation of Actors have been made by: Bill Athas, Russ Atkinson, Beppe Attardi, Henry Baker, Gerry Barber, Peter Bishop, Nanette Boden, Jean-Pierre Briot, Bill Dally, Peter de Jong, Jessie Dedecker, Travis Desell, Ken Kahn, Carl Hewitt, Henry Lieberman, Carl Manning, Tom Reinhardt, Chuck Seitz, Richard Steiger, Dan Theriault, Mario Tokoro, Carlos Varela, Darrell Woelk.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and determine how to respond to the next message received. The Actor model originated in 1973. It has been used both as a framework for a theoretical understanding
Actor model theory
In theoretical computer science, Actor model theory concerns theoretical issues for the Actor model.Actors are the primitives that form the basis of the Actor model of concurrent digital computation. In response to a message that it receives, an Actor can make local decisions, create more Actors,...
of computation
Concurrency (computer science)
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
, and as the theoretical basis for several practical implementations
Actor model implementation
In computer science, Actor model implementation concerns implementation issues for the Actor model.-Cosmic Cube:The Cosmic Cube was developed by Chuck Seitz et al. at Caltech providing architectural support for Actor systems...
of concurrent systems. The relationship of the model to other work is discussed in Indeterminacy in concurrent computation and Actor model and process calculi
Actor model and process calculi
In computer science, the Actor model and process calculi are two closely related approaches to the modelling of concurrent digital computation...
.
History
Unlike previous models of computation, the Actor model was inspired by physics including general relativity and quantum mechanics. It was also influenced by the programming languages LispLisp programming language
Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older...
, Simula
Simula
Simula is a name for two programming languages, Simula I and Simula 67, developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl and Kristen Nygaard...
and early versions of Smalltalk
Smalltalk
Smalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
, as well as capability-based systems and packet switching
Packet switching
Packet switching is a digital networking communications method that groups all transmitted data – regardless of content, type, or structure – into suitably sized blocks, called packets. Packet switching features delivery of variable-bit-rate data streams over a shared network...
. Its development was "motivated by the prospect of highly parallel computing machines consisting of dozens, hundreds or even thousands of independent microprocessors, each with its own local memory and communications processor, communicating via a high-performance communications network." Since that time, the advent of massive concurrency through multi-core
Multi-core (computing)
A multi-core processor is a single computing component with two or more independent actual processors , which are the units that read and execute program instructions...
computer architectures has rekindled interest in the Actor model.
Following Hewitt, Bishop, and Steiger's 1973 publication, Irene Greif developed an operational semantics
Operational semantics
In computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way. Operational semantics are classified into two categories: structural operational semantics formally describe how the individual steps of a computation take place in a...
for the Actors model as part of her doctoral research. Two years later, Henry Baker
Henry Baker (computer scientist)
Henry Givens Baker Jr. is a computer scientist who has made contributions in garbage collection, functional programming languages, and linear logic. He was also one of the founders of Symbolics...
and Hewitt published a set of axiomatic laws for Actor systems. Other major milestones include William Clinger's
William Clinger (computer scientist)
William D. Clinger is an Associate Professor in the College of Computer and Information Science at Northeastern University. Clinger is known for his work on higher-order and functional programming languages, and in particular for his contributions to the standardization of the Scheme programming...
dissertation, in 1981, introducing a denotational semantics
Denotational semantics of the Actor model
The denotational semantics of the Actor model is the subject of denotational domain theory for Actors. The historical development of this subject is recounted in [Hewitt 2008b].-Actor fixed point semantics:...
based on power domains, and Gul Agha
Gul Agha (computer scientist)
Gul Agha is a Professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign, and Director of the Open Systems Laboratory. He is known for his work on the Actor model of concurrent computation, and was also Editor-in-Chief of ACM Computing Surveys from 1999 to...
's 1985 dissertation which further developed a transition-based semantic model complementary to Clinger's. This resulted in the full development of actor model theory
Actor model theory
In theoretical computer science, Actor model theory concerns theoretical issues for the Actor model.Actors are the primitives that form the basis of the Actor model of concurrent digital computation. In response to a message that it receives, an Actor can make local decisions, create more Actors,...
.
Major software implementation work was done by Russ Atkinson, Beppe Attardi, Henry Baker, Gerry Barber, Peter Bishop, Peter de Jong, Ken Kahn, Henry Lieberman, Carl Manning, Tom Reinhardt, Richard Steiger, and Dan Theriault, in the Message Passing Semantics Group at Massachusetts Institute of Technology
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
(MIT). Research groups led by Chuck Seitz at California Institute of Technology
California Institute of Technology
The California Institute of Technology is a private research university located in Pasadena, California, United States. Caltech has six academic divisions with strong emphases on science and engineering...
(Caltech) and Bill Dally at MIT constructed computer architectures that further developed the message passing in the model. See Actor model implementation
Actor model implementation
In computer science, Actor model implementation concerns implementation issues for the Actor model.-Cosmic Cube:The Cosmic Cube was developed by Chuck Seitz et al. at Caltech providing architectural support for Actor systems...
.
Research on the Actor model has been carried out at Caltech Computer Science, Kyoto University
Kyoto University
, or is a national university located in Kyoto, Japan. It is the second oldest Japanese university, and formerly one of Japan's Imperial Universities.- History :...
Tokoro Laboratory, MCC
Microelectronics and Computer Technology Corporation
Microelectronics and Computer Technology Corporation was the first, and - at one time - one of the largest, computer industry research and development consortia in the United States....
, MIT Artificial Intelligence Laboratory, SRI
SRI International
SRI International , founded as Stanford Research Institute, is one of the world's largest contract research institutes. Based in Menlo Park, California, the trustees of Stanford University established it in 1946 as a center of innovation to support economic development in the region. It was later...
, Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
, University of Illinois at Urbana-Champaign
University of Illinois at Urbana-Champaign
The University of Illinois at Urbana–Champaign is a large public research-intensive university in the state of Illinois, United States. It is the flagship campus of the University of Illinois system...
Open Systems Laboratory, Pierre and Marie Curie University
Pierre and Marie Curie University
The Paris VI University , or the Pierre and Marie Curie University , is a university located on the Jussieu Campus in the Latin Quarter of the 5th arrondissement of Paris, France....
(University of Paris 6), University of Pisa
University of Pisa
The University of Pisa , located in Pisa, Tuscany, is one of the oldest universities in Italy. It was formally founded on September 3, 1343 by an edict of Pope Clement VI, although there had been lectures on law in Pisa since the 11th century...
, University of Tokyo
University of Tokyo
, abbreviated as , is a major research university located in Tokyo, Japan. The University has 10 faculties with a total of around 30,000 students, 2,100 of whom are foreign. Its five campuses are in Hongō, Komaba, Kashiwa, Shirokane and Nakano. It is considered to be the most prestigious university...
Yonezawa Laboratory and elsewhere.
Fundamental concepts
The Actor model adopts the philosophy that everything is an actor. This is similar to the everything is an object philosophy used by some object-oriented programming languagesObject-oriented programming
Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...
, but differs in that object-oriented software is typically executed sequentially, while the Actor model is inherently concurrent.
An actor is a computational entity that, in response to a message it receives, can concurrently:
- send a finite number of messages to other actors;
- create a finite number of new actors;
- designate the behavior to be used for the next message it receives.
There is no assumed sequence to the above actions and they could be carried out in parallel.
Decoupling the sender from communications sent was a fundamental advance of the Actor model enabling asynchronous communication
Asynchronous communication
In telecommunications, asynchronous communication is transmission of data without the use of an external clock signal, where data can be transmitted intermittently rather than in a steady stream. Any timing required to recover data from the communication symbols is encoded within the symbols...
and control structures as patterns of passing messages
Message passing
Message passing in computer science is a form of communication used in parallel computing, object-oriented programming, and interprocess communication. In this model, processes or objects can send and receive messages to other processes...
.
Recipients of messages are identified by address, sometimes called "mailing address". Thus an actor can only communicate with actors whose addresses it has. It can obtain those from a message it receives, or if the address is for an actor it has itself created.
The Actor model is characterized by inherent concurrency of computation within and among actors, dynamic creation of actors, inclusion of actor addresses in messages, and interaction only through direct asynchronous message passing
Message passing
Message passing in computer science is a form of communication used in parallel computing, object-oriented programming, and interprocess communication. In this model, processes or objects can send and receive messages to other processes...
with no restriction on message arrival order.
Formal systems
Over the years, several different formal systems have been developed which permit reasoning about systems in the Actor model. These include:- Operational semanticsOperational semanticsIn computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way. Operational semantics are classified into two categories: structural operational semantics formally describe how the individual steps of a computation take place in a...
- Laws for Actor systems
- Denotational semanticsDenotational semanticsIn computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...
- Transition semantics
There are also formalisms that are not fully faithful to the Actor model in that they do not formalize the guaranteed delivery of messages including the following (See Attempts to relate Actor semantics to algebra and linear logic):
- Several different Actor algebras
- Linear logic
Applications
The Actors model can be used as a framework for modelling, understanding, and reasoning about, a wide range of concurrent systems. For example:- Electronic mail (e-mail) can be modeled as an Actor system. Accounts are modeled as Actors and email addressesE-mail addressAn email address identifies an email box to which email messages are delivered. An example format of an email address is lewis@example.net which is read as lewis at example dot net...
as Actor addresses. - Web Services can be modeled with SOAPSOAPSOAP, originally defined as Simple Object Access Protocol, is a protocol specification for exchanging structured information in the implementation of Web Services in computer networks...
endpoints modeled as Actor addresses. - Objects with lockLock (computer science)In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
s (e.g. as in JavaJava (programming language)Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
and C#) can be modeled as a Serializer, provided that their implementations are such that messages can continually arrive (perhaps by being stored in an internal queue). A serializer is an important kind of Actor defined by the property that it is continually available to the arrival of new messages; every message sent to a serializer is guaranteed to arrive. - Testing and Test Control Notation (TTCNTTCNTTCN is a programming language used for testing of communication protocols and web services. A TTCN test suite consists of many test cases written in the TTCN programming language....
), both TTCN-2 and TTCN-3TTCN-3TTCN-3 is a strongly typed test scripting language used in conformance testing of communicating systems and a specification of test infrastructure interfaces that glue abstract test scripts with concrete communication environments. TTCN-3 has been developed by ETSI and its predecessor is TTCN-2...
, follows Actor model rather closely. In TTCN, Actor is a test component: either parallel test component (PTC) or main test component (MTC). Test components can send and receive messages to and from remote partners (peer test components or test system interface), the latter being identified by its address. Each test component has a behaviour tree bound to it; test components run in parallel and can be dynamically created by parent test components. Built-in language constructs allow the definition of actions to be taken when an expected message is received from the internal message queue, like sending a message to another peer entity or creating new test components.
Lambda calculus
The lambda calculusLambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
of Alonzo Church
Alonzo Church
Alonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, Frege–Church ontology, and the Church–Rosser theorem.-Life:Alonzo Church...
can be viewed as the earliest message passing
Message passing
Message passing in computer science is a form of communication used in parallel computing, object-oriented programming, and interprocess communication. In this model, processes or objects can send and receive messages to other processes...
programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
(see Hewitt, Bishop, and Steiger 1973; Abelson and Sussman 1985
Structure and Interpretation of Computer Programs
Structure and Interpretation of Computer Programs is a textbook published in 1984 about general computer programming concepts from MIT Press written by Massachusetts Institute of Technology professors Harold Abelson and Gerald Jay Sussman, with Julie Sussman...
). For example, the lambda expression below implements a tree data structure when supplied with parameters for a leftSubTree and rightSubTree. When such a tree is given a parameter message "getLeft", it returns leftSubTree and likewise when given the message "getRight" it returns rightSubTree.
λ(leftSubTree,rightSubTree)
λ(message)
if (message
"getLeft") then leftSubTree
else if (message
"getRight") then rightSubTreeHowever, the semantics of the lambda calculus were expressed using variable substitution
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
in which the values of parameters were substituted into the body of an invoked lambda expression. The substitution model is unsuitable for concurrency because it does not allow the capability of sharing
Sharing
Sharing the joint use of a resource or space. In its narrow sense, it refers to joint or alternating use of an inherently finite good, such as a common pasture or a shared residence. It is also the process of dividing and distributing. Apart from obvious instances, which we can observe in human...
of changing resources. Inspired by the lambda calculus, the interpreter
Interpreter (computing)
In computer science, an interpreter normally means a computer program that executes, i.e. performs, instructions written in a programming language...
for the programming language Lisp
Lisp programming language
Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older...
made use of a data structure called an environment so that the values of parameters did not have to be substituted into the body of an invoked lambda expression. This allowed for sharing of the effects of updating shared data structures but did not provide for concurrency.
Simula
Simula 67Simula
Simula is a name for two programming languages, Simula I and Simula 67, developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl and Kristen Nygaard...
pioneered using message passing for computation, motivated by discrete event simulation applications. These applications had become large and unmodular in previous simulation languages. At each time step, a large central program would have to go through and update the state of each simulation object that changed depending on the state of whichever simulation objects that it interacted with on that step. Kristen Nygaard
Kristen Nygaard
Kristen Nygaard was a Norwegian computer scientist, programming language pioneer and politician. He was born in Oslo and died of a heart attack in 2002.-Object-oriented programming:...
and Ole-Johan Dahl
Ole-Johan Dahl
Ole-Johan Dahl was a Norwegian computer scientist and is considered to be one of the fathers of Simula and object-oriented programming along with Kristen Nygaard.- Career :...
developed the idea (first described in an IFIP workshop in 1967) of having methods
Method (computer science)
In object-oriented programming, a method is a subroutine associated with a class. Methods define the behavior to be exhibited by instances of the associated class at program run time...
on each object
Object (computer science)
In computer science, an object is any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure...
that would update its own local state based on messages from other objects. In addition they introduced a class structure
Class (computer science)
In object-oriented programming, a class is a construct that is used as a blueprint to create instances of itself – referred to as class instances, class objects, instance objects or simply objects. A class defines constituent members which enable these class instances to have state and behavior...
for objects with inheritance
Inheritance (object-oriented programming)
In object-oriented programming , inheritance is a way to reuse code of existing objects, establish a subtype from an existing object, or both, depending upon programming language support...
. Their innovations considerably improved the modularity of programs.
However, Simula used coroutine
Coroutine
Coroutines are computer program components that generalize subroutines to allow multiple entry points for suspending and resuming execution at certain locations...
control structure instead of true concurrency.
Smalltalk
Alan Kay
Alan Kay
Alan Curtis Kay is an American computer scientist, known for his early pioneering work on object-oriented programming and windowing graphical user interface design, and for coining the phrase, "The best way to predict the future is to invent it."He is the president of the Viewpoints Research...
was influenced by message passing in the pattern-directed invocation of Planner
Planner programming language
Planner is a programming language designed by Carl Hewitt at MIT, and first published in 1969. First, subsets such as Micro-Planner and Pico-Planner were implemented, and then essentially the whole language was implemented in Popler...
in developing Smalltalk
Smalltalk
Smalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
-71. Hewitt was intrigued by Smalltalk-71 but was put off by the complexity of communication that included invocations with many fields including global, sender, receiver, reply-style, status, reply, operator selector, etc.
In 1972 Kay visited MIT and discussed some of his ideas for Smalltalk-72 building on the Logo work of Seymour Papert
Seymour Papert
Seymour Papert is an MIT mathematician, computer scientist, and educator. He is one of the pioneers of artificial intelligence, as well as an inventor of the Logo programming language....
and the "little person" model of computation used for teaching children to program. However, the message passing of Smalltalk-72 was quite complex. Code in the language was viewed by the interpreter as simply a stream of tokens. As Dan Ingalls later described it:
- The first (token) encountered (in a program) was looked up in the dynamic context, to determine the receiver of the subsequent message. The name lookup began with the class dictionary of the current activation. Failing there, it moved to the sender of that activation and so on up the sender chain. When a binding was finally found for the token, its value became the receiver of a new message, and the interpreter activated the code for that object's class.
Thus the message-passing model in Smalltalk-72 was closely tied to a particular machine model and programming-language syntax that did not lend itself to concurrency. Also, although the system was bootstrapped on itself, the language constructs were not formally defined as objects that respond to Eval messages (see discussion below). This led some to believe that a new mathematical model of concurrent computation based on message passing should be simpler than Smalltalk-72.
Subsequent versions of the Smalltalk language largely followed the path of using the virtual methods
Method (computer science)
In object-oriented programming, a method is a subroutine associated with a class. Methods define the behavior to be exhibited by instances of the associated class at program run time...
of Simula in the message-passing structure of programs. However Smalltalk-72 made primitives such as integers, floating point numbers, etc. into objects
Object (computer science)
In computer science, an object is any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure...
. The authors of Simula had considered making such primitives into objects but refrained largely for efficiency reasons. Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
at first used the expedient of having both primitive and object versions of integers, floating point numbers, etc. The C# programming language (and later versions of Java, starting with Java 1.5) adopted the less elegant solution of using boxing and unboxing, a variant of which had been used earlier in some Lisp
Lisp programming language
Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older...
implementations.
The Smalltalk system went on to become very influential, innovating in bitmap displays, personal computing, the class browser interface, and many other ways. For details see Kay's The Early History of Smalltalk. Meanwhile the Actor efforts at MIT remained focused on developing the science and engineering of higher level concurrency. (See the paper by Jean-Pierre Briot for ideas that were developed later on how to incorporate some kinds of Actor concurrency into later versions of Smalltalk.)
Petri nets
Prior to the development of the Actor model, Petri netPetri net
A Petri net is one of several mathematical modeling languages for the description of distributed systems. A Petri net is a directed bipartite graph, in which the nodes represent transitions and places...
s were widely used to model nondeterministic computation. However, they were widely acknowledged to have an important limitation: they modeled control flow but not data flow. Consequently they were not readily composable, thereby limiting their modularity. Hewitt pointed out another difficulty with Petri nets: simultaneous action. I.e., the atomic step of computation in Petri nets is a transition in which tokens simultaneously disappear from the input places of a transition and appear in the output places. The physical basis of using a primitive with this kind of simultaneity seemed questionable to him. Despite these apparent difficulties, Petri nets continue to be a popular approach to modelling concurrency, and are still the subject of active research.
Threads, locks, and buffers (channels)
Prior to the Actor model, concurrency was defined in low-level machine terms of threadsThread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
, locks
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
and buffers
Buffer (computer science)
In computer science, a buffer is a region of a physical memory storage used to temporarily hold data while it is being moved from one place to another. Typically, the data is stored in a buffer as it is retrieved from an input device or just before it is sent to an output device...
(channels
Channel (programming)
A Channel is a construct used in interprocess communication to represent some binding between concurrent processes. An object may be sent over a channel, and a process is able to receive any objects sent over a channel it has a reference to...
). It certainly is the case that implementations of the Actor model typically make use of these hardware capabilities. However, there is no reason that the model could not be implemented directly in hardware without exposing any hardware threads and locks. Also, there is no necessary relationship between the number of Actors, threads, and locks that might be involved in a computation. Implementations of the Actor model are free to make use of threads and locks in any way that is compatible with the laws for Actors.
Unbounded nondeterminism controversy
Arguably, the first concurrent programs were interrupt handlerInterrupt handler
An interrupt handler, also known as an interrupt service routine , is a callback subroutine in microcontroller firmware, operating system or device driver whose execution is triggered by the reception of an interrupt...
s. During the course of its normal operation, a computer needed to be able to receive information from outside (characters from a keyboard, packets from a network, etc.). So when the information arrived, execution of the computer was "interrupted" and special code called an interrupt handler was called to put the information in a buffer
Buffer (computer science)
In computer science, a buffer is a region of a physical memory storage used to temporarily hold data while it is being moved from one place to another. Typically, the data is stored in a buffer as it is retrieved from an input device or just before it is sent to an output device...
where it could be subsequently retrieved.
In the early 1960s, interrupts began to be used to simulate the concurrent execution of several programs on a single processor. Having concurrency with shared memory
Shared memory
In computing, shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Depending on context, programs may run on a single processor or on multiple separate processors...
gave rise to the problem of concurrency control
Concurrency control
In information technology and computer science, especially in the fields of computer programming , operating systems , multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible.Computer...
. Originally, this problem was conceived as being one of mutual exclusion
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
on a single computer. Edsger Dijkstra
Edsger Dijkstra
Edsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...
developed semaphores
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
and later, between 1971 and 1973, Tony Hoare and Per Brinch Hansen
Per Brinch Hansen
Per Brinch Hansen was a Danish-American computer scientist known for concurrent programming theory.-Biography:He was born in Frederiksberg, in Copenhagen, Denmark....
developed monitors
Monitor (synchronization)
In concurrent programming, a monitor is an object or module intended to be used safely by more than one thread. The defining characteristic of a monitor is that its methods are executed with mutual exclusion. That is, at each point in time, at most one thread may be executing any of its methods...
to solve the mutual exclusion problem. However, neither of these solutions provided a programming-language construct that encapsulated access to shared resources. This encapsulation was later accomplished by the serializer construct ([Hewitt and Atkinson 1977, 1979] and [Atkinson 1980]).
The first models of computation (e.g. Turing machines, Post productions, the lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
, etc.) were based on mathematics and made use of a global state to represent a computational step (later generalized in [McCarthy and Hayes 1969] and [Dijkstra 1976] see Event orderings versus global state). Each computational step was from one global state of the computation to the next global state. The global state approach was continued in automata theory
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
for finite state
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
machines and push down stack
Stack machine
A stack machine may be* A real or emulated computer that evaluates each sub-expression of a program statement via a pushdown data stack and uses a reverse Polish notation instruction set....
machines, including their nondeterministic versions. Such nondeterministic automata have the property of bounded nondeterminism
Unbounded nondeterminism
In computer science, unbounded nondeterminism or unbounded indeterminacy is a property of concurrency by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while still guaranteeing that the request will eventually be...
; that is, if a machine always halts when started in its initial state, then there is a bound on the number of states in which it halts.
Edsger Dijkstra
Edsger Dijkstra
Edsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...
further developed the nondeterministic global state approach. Dijkstra's model gave rise to a controversy concerning unbounded nondeterminism. Unbounded nondeterminism
Unbounded nondeterminism
In computer science, unbounded nondeterminism or unbounded indeterminacy is a property of concurrency by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while still guaranteeing that the request will eventually be...
(also called unbounded indeterminacy), is a property of concurrency
Concurrency (computer science)
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while still guaranteeing that the request will eventually be serviced. Hewitt argued that the Actor model should provide the guarantee of service. In Dijkstra's model, although there could be an unbounded amount of time between the execution of sequential instructions on a computer, a (parallel) program that started out in a well defined state could terminate in only a bounded number of states [Dijkstra 1976]. Consequently, his model could not provide the guarantee of service. Dijkstra argued that it was impossible to implement unbounded nondeterminism.
Hewitt argued otherwise: there is no bound that can be placed on how long it takes a computational circuit called an arbiter
Arbiter (electronics)
-Asynchronous arbiters:An important form of arbiter is used in asynchronous circuits, to select the order of access to a shared resource among asynchronous requests. Its function is to prevent two operations from occurring at once when they should not...
to settle (see metastability in electronics
Metastability in electronics
Metastability in electronics is the ability of a digital electronic system to persist for an unbounded time in an unstable equilibrium or metastable state....
). Arbiters are used in computers to deal with the circumstance that computer clocks operate asynchronously with input from outside, e.g. keyboard input, disk access, network input, etc. So it could take an unbounded time for a message sent to a computer to be received and in the meantime the computer could traverse an unbounded number of states.
The Actor Model features unbounded nondeterminism which was captured in a mathematical model by Will Clinger using domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...
. There is no global state in the Actor model.
Direct communication and asynchrony
Messages in the Actor model are not necessarily buffered. This was a sharp break with previous approaches to models of concurrent computation. The lack of buffering caused a great deal of misunderstanding at the time of the development of the Actor model and is still a controversial issue. Some researchers argued that the messages are buffered in the "ether" or the "environment". Also, messages in the Actor model are simply sent (like packets in IPInternet Protocol
The Internet Protocol is the principal communications protocol used for relaying datagrams across an internetwork using the Internet Protocol Suite...
); there is no requirement for a synchronous handshake with the recipient.
Actor creation plus addresses in messages means variable topology
A natural development of the Actor model was to allow addresses in messages. Influenced by packet switched networksPacket switching
Packet switching is a digital networking communications method that groups all transmitted data – regardless of content, type, or structure – into suitably sized blocks, called packets. Packet switching features delivery of variable-bit-rate data streams over a shared network...
[1961 and 1964], Hewitt proposed the development of a new model of concurrent computation in which communications would not have any required fields at all: they could be empty. Of course, if the sender of a communication desired a recipient to have access to addresses which the recipient did not already have, the address would have to be sent in the communication.
A computation might need to send a message to a recipient from which it would later receive a response. The way to do this is to send a communication which has the message along with the address of another actor called the resumption (sometimes also called continuation
Continuation
In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e...
or stack frame) along with the message. The recipient could then cause a response message to be sent to the resumption.
Actor creation plus the inclusion of the addresses of actors in messages means that Actors have a potentially variable topology in their relationship to one another much as the objects in Simula also had a variable topology in their relationship to one another.
Inherently concurrent
As opposed to the previous approach based on composing sequential processes, the Actor model was developed as an inherently concurrent model. In the Actor model sequentiality was a special case that derived from concurrent computation as explained in Actor model theoryActor model theory
In theoretical computer science, Actor model theory concerns theoretical issues for the Actor model.Actors are the primitives that form the basis of the Actor model of concurrent digital computation. In response to a message that it receives, an Actor can make local decisions, create more Actors,...
.
No requirement on order of message arrival
Hewitt argued against adding the requirement that messages must arrive in the order in which they are sent to the Actor. If output message ordering is desired, then it can be modeled by a queue Actor that provides this functionality. Such a queue Actor would queue the messages that arrived so that they could be retrieved in FIFOFIFO
FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
order. So if an Actor X sent a message M1 to an Actor Y, and later X sent another message M2 to Y, there is no requirement that M1 arrives at Y before M2.
In this respect the Actor model mirrors packet switching
Packet switching
Packet switching is a digital networking communications method that groups all transmitted data – regardless of content, type, or structure – into suitably sized blocks, called packets. Packet switching features delivery of variable-bit-rate data streams over a shared network...
systems which do not guarantee that packets must be received in the order sent. Not providing the order of delivery guarantee allows packet switching to buffer packets, use multiple paths to send packets, resend damaged packets, and to provide other optimizations.
For example, Actors are allowed to pipeline the processing of messages. What this means is that in the course of processing a message M1, an Actor can designate the behavior to be used to process the next message, and then in fact begin processing another message M2 before it has finished processing M1. Just because an Actor is allowed to pipeline the processing of messages does not mean that it must pipeline the processing. Whether a message is pipelined is an engineering tradeoff. How would an external observer know whether the processing of a message by an Actor has been pipelined? There is no ambiguity in the definition of an Actor created by the possibility of pipelining. Of course, it is possible to perform the pipeline optimization incorrectly in some implementations, in which case unexpected behavior may occur.
Locality
Another important characteristic of the Actor model is locality.Locality means that in processing a message an Actor can send messages only to addresses that it receives in the message, addresses that it already had before it received the message and addresses for Actors that it creates while processing the message. (But see Synthesizing Addresses of Actors.)
Also locality means that there is no simultaneous change in multiple locations. In this way it differs from some other models of concurrency, e.g., the Petri net
Petri net
A Petri net is one of several mathematical modeling languages for the description of distributed systems. A Petri net is a directed bipartite graph, in which the nodes represent transitions and places...
model in which tokens are simultaneously removed from multiple locations and placed in other locations.
Composing Actor Systems
The idea of composing Actor systems into larger ones is an important aspect of modularityModularity (programming)
Modular programming is a software design technique that increases the extent to which software is composed of separate, interchangeable components called modules by breaking down program functions into modules, each of which accomplishes one function and contains everything necessary to accomplish...
that was developed in Gul Agha's doctoral dissertation, developed later by Gul Agha, Ian Mason, Scott Smith, and Carolyn Talcott.
Behaviors
A key innovation was the introduction of behavior specified as a mathematical function to express what an Actor does when it processes a message including specifying a new behavior to process the next message that arrives. Behaviors provided a mechanism to mathematically model the sharing in concurrency.Behaviors also freed the Actor model from implementation details, e.g., the Smalltalk-72 token stream interpreter. However, it is critical to understand that the efficient implementation of systems described by the Actor model require extensive optimization. See Actor model implementation
Actor model implementation
In computer science, Actor model implementation concerns implementation issues for the Actor model.-Cosmic Cube:The Cosmic Cube was developed by Chuck Seitz et al. at Caltech providing architectural support for Actor systems...
for details.
Modeling other concurrency systems
Other concurrency systems (e.g. process calculi) can be modeled in the Actor model using a two-phase commit protocol.Computational Representation Theorem
There is a Computational Representation Theorem in the Actor model for systems which are closed in the sense that they do not receive communications from outside. The mathematical denotation denoted by a closed system S is constructed from an initial behavior ⊥S and a behavior-approximating function progressionS. These obtain increasingly better approximations and construct a denotation (meaning) for S as follows [Hewitt 2008; Clinger 1981]:-
- DenoteS ≡ ⊔i∈ω progressionSi(⊥S)
In this way, S can be mathematically characterized in terms of all its possible behaviors (including those involving unbounded nondeterminism). Although DenoteS is not an implementation of S, it can be used to prove a generalization of the Church-Turing-Rosser-Kleene thesis [Kleene 1943]:
A consequence of the above theorem is that a finite Actor can nondeterministically respond with an uncountable number of different outputs.
Relationship to mathematical logic
The development of the Actor model has an interesting relationship to mathematical logic. One of the key motivations for its development was to understand and deal with the control structure issues that arose in development of the Planner programming languagePlanner programming language
Planner is a programming language designed by Carl Hewitt at MIT, and first published in 1969. First, subsets such as Micro-Planner and Pico-Planner were implemented, and then essentially the whole language was implemented in Popler...
. Once the Actor model was initially defined, an important challenge was to understand the power of the model relative to Robert Kowalski
Robert Kowalski
Robert "Bob" Anthony Kowalski is a British logician and computer scientist, who has spent most of his career in the United Kingdom....
's thesis that "computation can be subsumed by deduction". Kowalski's thesis turned out to be false for the concurrent computation in the Actor model (see Indeterminacy in concurrent computation). This result is still somewhat controversial and it reversed previous expectations because Kowalski's thesis is true for sequential computation and even some kinds of parallel computation, e.g. the lambda calculus.
Nevertheless attempts were made to extend logic programming
Logic programming
Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
to concurrent computation. However, Hewitt and Agha [1991] claimed that the resulting systems were not deductive in the following sense: computational steps of the concurrent logic programming systems do not follow deductively from previous steps (see Indeterminacy in concurrent computation).
Migration
Migration in the Actor model is the ability of Actors to change locations. E.g., in his dissertation, Aki Yonezawa modeled a post office that customer Actors could enter, change locations within while operating, and exit. An Actor that can migrate can be modeled by having a location Actor that changes when the Actor migrates. However the faithfulness of this modeling is controversial and the subject of research.Security
The security of Actors can be protected in the following ways:- hardwiring in which Actors are physically connected
- hardwareHardwareHardware is a general term for equipment such as keys, locks, hinges, latches, handles, wire, chains, plumbing supplies, tools, utensils, cutlery and machine parts. Household hardware is typically sold in hardware stores....
as in Burroughs B5000, Lisp machineLisp machineLisp machines were general-purpose computers designed to efficiently run Lisp as their main software language. In a sense, they were the first commercial single-user workstations...
, etc. - virtual machines as in Java virtual machineJava Virtual MachineA Java virtual machine is a virtual machine capable of executing Java bytecode. It is the code execution component of the Java software platform. Sun Microsystems stated that there are over 4.5 billion JVM-enabled devices.-Overview:...
, Common Language RuntimeCommon Language RuntimeThe Common Language Runtime is the virtual machine component of Microsoft's .NET framework and is responsible for managing the execution of .NET programs. In a process known as just-in-time compilation, the CLR compiles the intermediate language code known as CIL into the machine instructions...
, etc. - operating systems as in capability-based systems
- signingDigital signatureA digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...
and/or encryptionEncryptionIn cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
of Actors and their addresses
Synthesizing addresses of actors
A delicate point in the Actor model is the ability to synthesize the address of an Actor. In some cases security can be used to prevent the synthesis of addresses (see Security). However, if an Actor address is simply a bit string then clearly it can be synthesized although it may be difficult or even infeasible to guess the address of an Actor if the bit strings are long enough. SOAPSOAP
SOAP, originally defined as Simple Object Access Protocol, is a protocol specification for exchanging structured information in the implementation of Web Services in computer networks...
uses a URL
Uniform Resource Locator
In computing, a uniform resource locator or universal resource locator is a specific character string that constitutes a reference to an Internet resource....
for the address of an endpoint where an Actor can be reached. Since a URL
Uniform Resource Locator
In computing, a uniform resource locator or universal resource locator is a specific character string that constitutes a reference to an Internet resource....
is a character string, it can clearly be synthesized although encryption can make it virtually impossible to guess.
Synthesizing the addresses of Actors is usually modeled using mapping. The idea is to use an Actor system to perform the mapping to the actual Actor addresses. For example, on a computer the memory structure of the computer can be modeled as an Actor system that does the mapping. In the case of SOAP
SOAP
SOAP, originally defined as Simple Object Access Protocol, is a protocol specification for exchanging structured information in the implementation of Web Services in computer networks...
addresses, it's modeling the DNS
Domain name system
The Domain Name System is a hierarchical distributed naming system for computers, services, or any resource connected to the Internet or a private network. It associates various information with domain names assigned to each of the participating entities...
and rest of the URL
Uniform Resource Locator
In computing, a uniform resource locator or universal resource locator is a specific character string that constitutes a reference to an Internet resource....
mapping.
Contrast with other models of message-passing concurrency
Robin MilnerRobin Milner
Arthur John Robin Gorell Milner FRS FRSE was a prominent British computer scientist.-Life, education and career:...
's initial published work on concurrency was also notable in that it was not based on composing sequential processes. His work differed from the Actor model because it was based on a fixed number of processes of fixed topology communicating numbers and strings using synchronous communication. The original Communicating Sequential Processes
Communicating sequential processes
In computer science, Communicating Sequential Processes is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi...
model published by Tony Hoare differed from the Actor model because it was based on the parallel composition of a fixed number of sequential processes connected in a fixed topology, and communicating using synchronous message-passing based on process names (see Actor model and process calculi history). Later versions of CSP abandoned communication based on process names in favor of anonymous communication via channels, an approach also used in Milner's work on the Calculus of Communicating Systems
Calculus of Communicating Systems
The Calculus of Communicating Systems is a process calculus introduced by Robin Milner around 1980 and the title of a book describing the calculus. Its actions model indivisible communications between exactly two participants. The formal language includes primitives for describing parallel...
and the π-calculus
Pi-calculus
In theoretical computer science, the π-calculus is a process calculus originally developed by Robin Milner, and David Walker as a continuation of work on the process calculus CCS...
.
These early models by Milner and Hoare both had the property of bounded nondeterminism. Modern, theoretical CSP
Communicating sequential processes
In computer science, Communicating Sequential Processes is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi...
([Hoare 1985] and [Roscoe 2005]) explicitly provides unbounded nondeterminism.
Influence
The Actor Model has been influential on both theory development and practical software development.Theory
The Actor Model has influenced the development of the Pi-calculusPi-calculus
In theoretical computer science, the π-calculus is a process calculus originally developed by Robin Milner, and David Walker as a continuation of work on the process calculus CCS...
and subsequent Process calculi. In his Turing lecture, Robin Milner wrote:
- Now, the pure lambda-calculus is built with just two kinds of thing: terms and variables. Can we achieve the same economy for a process calculus? Carl Hewitt, with his Actors model, responded to this challenge long ago; he declared that a value, an operator on values, and a process should all be the same kind of thing: an Actor.
- This goal impressed me, because it implies the homogeneity and completeness of expression ... But it was long before I could see how to attain the goal in terms of an algebraic calculus...
- So, in the spirit of Hewitt, our first step is to demand that all things denoted by terms or accessed by names--values, registers, operators, processes, objects--are all of the same kind of thing; they should all be processes.
Practice
The Actor Model has had extensive influence on commercial practice. For example Twitter has used actors for scalability. Also, Microsoft has used the Actor Model in the development of its Asynchronous Agents Library. There are numerous other Actor libraries listed in the Actor Libraries and Frameworks section below.Current importance
Forty years after the publication of Moore's LawMoore's Law
Moore's law describes a long-term trend in the history of computing hardware: the number of transistors that can be placed inexpensively on an integrated circuit doubles approximately every two years....
, hardware development is furthering local and nonlocal massive concurrency. Local concurrency is enabled by new hardware for 64-bit
64-bit
64-bit is a word size that defines certain classes of computer architecture, buses, memory and CPUs, and by extension the software that runs on them. 64-bit CPUs have existed in supercomputers since the 1970s and in RISC-based workstations and servers since the early 1990s...
multi-core
Multicore
Multicore may refer to:* Multi-core processor ** Multicore Association, founded in 2005, a non-profit, industry consortium focused on multicore technology* multicore cable, a generic term for an electrical cable that has multiple cores...
(Platform 2015 Unveiled at IDF Spring 2005) microprocessors, multi-chip modules, and high performance interconnect
Electrical connection
An electrical connection between discrete points allows the flow of electrons . A pair of connections is needed for a circuit.Between points with a low voltage difference, direct current can be controlled by a switch...
. Nonlocal concurrency is being enabled by new hardware for wired and wireless
Wireless
Wireless telecommunications is the transfer of information between two or more points that are not physically connected. Distances can be short, such as a few meters for television remote control, or as far as thousands or even millions of kilometers for deep-space radio communications...
broadband
Broadband
The term broadband refers to a telecommunications signal or device of greater bandwidth, in some sense, than another standard or usual signal or device . Different criteria for "broad" have been applied in different contexts and at different times...
packet switched communications (see Wi-Fi
Wi-Fi
Wi-Fi or Wifi, is a mechanism for wirelessly connecting electronic devices. A device enabled with Wi-Fi, such as a personal computer, video game console, smartphone, or digital audio player, can connect to the Internet via a wireless network access point. An access point has a range of about 20...
and Ultra wideband). Both local and nonlocal storage capacities are growing exponentially.
According to Hewitt [2006], the Actor model faces issues in computer and communications architecture, concurrent programming languages, and Web Services including the following:
- scalabilityScalabilityIn electronics scalability is the ability of a system, network, or process, to handle growing amount of work in a graceful manner or its ability to be enlarged to accommodate that growth...
: the challenge of scaling up concurrency both locally and nonlocally. - transparencyTransparency (computing)Any change in a computing system, such as new feature or new component, is transparent if the system after change adheres to previous external interface as much as possible while changing its internal behaviour. The purpose is to shield from change all systems on the other end of the interface...
: bridging the chasm between local and nonlocal concurrency. Transparency is currently a controversial issue. Some researchers have advocated a strict separation between local concurrency using concurrent programming languages (e.g. JavaJava (programming language)Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
and C#) from nonlocal concurrency using SOAPSOAPSOAP, originally defined as Simple Object Access Protocol, is a protocol specification for exchanging structured information in the implementation of Web Services in computer networks...
for Web services. Strict separation produces a lack of transparency that causes problems when it is desirable/necessary to change between local and nonlocal access to Web Services (see distributed computingDistributed computingDistributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
). - inconsistency: Inconsistency is the norm because all very large knowledge systems about human information system interactions are inconsistent. This inconsistency extends to the documentation and specifications of very large systems (e.g. Microsoft Windows software, etc.), which are internally inconsistent.
Many of the ideas introduced in the Actor model are now also finding application in multi-agent systems for these same reasons [Hewitt 2006b 2007b]. The key difference is that agent systems (in most definitions) impose extra constraints upon the Actors, typically requiring that they make use of commitments and goals.
The Actor model is also being applied to client cloud computing
Cloud computing
Cloud computing is the delivery of computing as a service rather than a product, whereby shared resources, software, and information are provided to computers and other devices as a utility over a network ....
.
Actor researchers
Important contributions to the semantics of Actors have been made by: Gul AghaGul Agha (computer scientist)
Gul Agha is a Professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign, and Director of the Open Systems Laboratory. He is known for his work on the Actor model of concurrent computation, and was also Editor-in-Chief of ACM Computing Surveys from 1999 to...
, Beppe Attardi, Henry Baker
Henry Baker (computer scientist)
Henry Givens Baker Jr. is a computer scientist who has made contributions in garbage collection, functional programming languages, and linear logic. He was also one of the founders of Symbolics...
, Will Clinger, Irene Greif, Carl Hewitt
Carl Hewitt
Carl Hewitt is Board Chair of the International Society for Inconsistency Robustness. He has been a Visiting Professor at Stanford University and the University of Keio. In 2000, he became emeritus in the EECS department at MIT....
, Carl Manning, Ian Mason, Ugo Montanari, Maria Simi, Scott Smith, Carolyn Talcott, Prasanna Thati, and Aki Yonezawa.
Important contributions to the implementation of Actors have been made by: Bill Athas, Russ Atkinson, Beppe Attardi, Henry Baker, Gerry Barber, Peter Bishop, Nanette Boden, Jean-Pierre Briot, Bill Dally, Peter de Jong, Jessie Dedecker, Travis Desell, Ken Kahn, Carl Hewitt, Henry Lieberman, Carl Manning, Tom Reinhardt, Chuck Seitz, Richard Steiger, Dan Theriault, Mario Tokoro, Carlos Varela, Darrell Woelk.
Programming with Actors
A number of different programming languages employ the Actor model or some variation of it. These languages include:Later Actor programming languages
- ABCLActor-Based Concurrent LanguageActor-Based Concurrent Language is a family of programming languages, developed in Japan in the 1980s and 1990s.-ABCL/1:ABCL/1 is a prototype-based concurrent programming language for the ABCL MIMD system, created in 1986 by Akinori Yonezawa, of the Department of Information Science at the...
- AmbientTalkAmbientTalkAmbientTalk is an experimental object-oriented distributed programming language developed at the Programming Technology Laboratory at the Vrije Universiteit Brussel, Belgium...
- AxumAxum (programming language)Axum is a domain specific concurrent programming language, based on the Actor model, being developed by Microsoft...
- EE (programming language)E is an object-oriented programming language for secure distributed computing, created by Mark S. Miller, Dan Bornstein, and others at Electric Communities in 1997. E is mainly descended from the concurrent language Joule and from Original-E, a set of extensions to Java for secure distributed...
- Erlang
- Fantom
- Humus
- IoIo (programming language)Io is a pure object-oriented programming language inspired by Smalltalk, Self, Lua, Lisp, Act1, and NewtonScript. Io has a prototype-based object model similar to the ones in Self and NewtonScript, eliminating the distinction between instance and class. Like Smalltalk, everything is an object and...
- Ptolemy Project
- Rebeca Modeling LanguageRebeca Modeling LanguageRebeca is an actor-based modeling language with a formal foundation, designed in an effort to bridge the gap between formal verification approaches and real applications. It can be considered as a reference model for concurrent computation, based on an operational interpretation of the actor model...
- ReiaReia (programming language)Reia is a general-purpose concurrent object-oriented programming language for the Erlang virtual machine.Reia supports multiple programming paradigms including imperative, functional, declarative, object oriented, and concurrent. It uses the actor model for concurrency in a manner that works...
- SALSASALSA programming languageThe SALSA programming language is an actor-oriented programming language that uses concurrency primitives beyond asynchronous message passing, including token-passing, join, and first-class continuations...
- Scala
- Scratch
Actor libraries and frameworks
Actor libraries or frameworks have also been implemented to permit actor-style programming in languages that don't have actors built-in. Among these frameworks are:- Akka - A Java and Scala framework with Actors, STMSoftware transactional memoryIn computer science, software transactional memory is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. It is an alternative to lock-based synchronization. A transaction in this context is a piece of code that...
& Transactors - Ateji PX - Ateji PX provides an Actor Model for Java
- F# MailboxProcessor - an Actor Model in the F# core library
- Korus - A Java parallel and distributed programming framework based on Actor Model
- Kilim - a message-passing framework for Java
- ActorFoundryActorFoundryActorFoundry is a Java-based library for Actor programming. It enables writing actor programs in the usual Java syntax. It support safe as well as efficient messaging, actor mobility, and message ordering using local synchronization constraints...
- a Java library for Actor programming - Retlang for .NET
- Jetlang for Java
- Haskell-Actor for Haskell
- GPars - the concurrency and actor library for Groovy (was GParallelizer)
- PARLEY - The Python Actor Runtime Library
- Pykka - actor library for Python
- Termite Scheme - provides Erlang-like concurency for the Gambit implementation of Scheme
- Theron - provides an Actor Model for C++.
- Libactor - provides an Actor Library for C
- S4 , a distributed, scalable platform featuring many aspects of the Actors Model.
See also
- Data flow
- Special relativitySpecial relativitySpecial relativity is the physical theory of measurement in an inertial frame of reference proposed in 1905 by Albert Einstein in the paper "On the Electrodynamics of Moving Bodies".It generalizes Galileo's...
(specifically, Relativity of simultaneityRelativity of simultaneityIn physics, the relativity of simultaneity is the concept that simultaneity–whether two events occur at the same time–is not absolute, but depends on the observer's reference frame. According to the special theory of relativity, it is impossible to say in an absolute sense whether two events occur...
) and Quantum physics, for some physical motivation for the Actor model theoryActor model theoryIn theoretical computer science, Actor model theory concerns theoretical issues for the Actor model.Actors are the primitives that form the basis of the Actor model of concurrent digital computation. In response to a message that it receives, an Actor can make local decisions, create more Actors,... - Multi-agent systemMulti-agent systemA multi-agent system is a system composed of multiple interacting intelligent agents. Multi-agent systems can be used to solve problems that are difficult or impossible for an individual agent or a monolithic system to solve...
- Neural networksNeural NetworksNeural Networks is the official journal of the three oldest societies dedicated to research in neural networks: International Neural Network Society, European Neural Network Society and Japanese Neural Network Society, published by Elsevier...
- Gordon PaskGordon PaskAndrew Gordon Speedie Pask was an English cybernetician and psychologist who made significant contributions to cybernetics, instructional psychology, experimental epistemology and educational technology....
- Scientific Community MetaphorScientific community metaphorIn computer science, the Scientific Community Metaphor is a metaphor used to aid understanding scientific communities. The first publications on the Scientific Community Metaphor in 1981 and 1982 involved the development of a programming language named Ether that invoked procedural plans to...
- Communicating sequential processesCommunicating sequential processesIn computer science, Communicating Sequential Processes is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi...
Further reading
- Stephen Kleene Recursive Predicates and Quantifiers American Mathematical Society Transactions. 1943.
- Paul Baran. On Distributed Communications Networks IEEE Transactions on Communications Systems. March 1964.
- Peter Landin. A Generalization of Jumps and Labels Report. UNIVAC Systems Programming Research. August 1965. Reprinted in Higher Order and Symbolic Computation. 1998.
- Edsger DijkstraEdsger DijkstraEdsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...
Solution of a Problem in Concurrent Programming Control CACMCommunications of the ACMCommunications of the ACM is the flagship monthly journal of the Association for Computing Machinery . First published in 1957, CACM is sent to all ACM members, currently numbering about 80,000. The articles are intended for readers with backgrounds in all areas of computer science and information...
. 1965. - Jack DennisJack DennisJack Dennis is a computer scientist and retired MIT professor.Dennis entered the Massachusetts Institute of Technology in 1949 as an electrical engineering major; he received his MS degree in 1954, and continued doctoral research and received his ScD in 1958...
and Earl Van Horn. Programming Semantics for Multiprogrammed Computations CACM. March 1966. - Ole-Johan DahlOle-Johan DahlOle-Johan Dahl was a Norwegian computer scientist and is considered to be one of the fathers of Simula and object-oriented programming along with Kristen Nygaard.- Career :...
and Kristen NygaardKristen NygaardKristen Nygaard was a Norwegian computer scientist, programming language pioneer and politician. He was born in Oslo and died of a heart attack in 2002.-Object-oriented programming:...
. Class and subclass declarations IFIP TC2 Conference on Simulation Programming Languages. May 1967. - Carl HewittCarl HewittCarl Hewitt is Board Chair of the International Society for Inconsistency Robustness. He has been a Visiting Professor at Stanford University and the University of Keio. In 2000, he became emeritus in the EECS department at MIT....
. PLANNER: A Language for Proving Theorems in Robots IJCAI 1969 - William A. Woods. Transition network grammars for natural language analysis CACM. 1970.
- Terry Winograd. Procedures as a Representation for Data in a Computer Program for Understanding Natural Language MIT AI TR-235. January 1971.
- Carl Hewitt. Procedural Embedding of Knowledge In Planner IJCAI 1971.
- G.M. Birtwistle, Ole-Johan Dahl, B. Myhrhaug and Kristen Nygaard. SIMULA Begin Auerbach Publishers Inc, 1973.
- Daniel Bobrow: A Model for Control Structures for Artificial Intelligence Programming Languages IJCAI 1973.
- Carl Hewitt, et al. Actor Induction and Meta-evaluation Conference Record of ACM Symposium on Principles of Programming Languages, January 1974.
- Carl Hewitt, et al. Behavioral Semantics of Nonrecursive Control Structure Proceedings of Colloque sur la Programmation, April 1974.
- Irene Greif and Carl Hewitt. Actor Semantics of PLANNER-73 Conference Record of ACM Symposium on Principles of Programming Languages. January 1975.
- Carl Hewitt. How to Use What You Know IJCAI. September, 1975.
- Alan Kay and Adele Goldberg. Smalltalk-72 Instruction Manual Xerox PARC Memo SSL-76-6. May 1976.
- Edsger DijkstraEdsger DijkstraEdsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...
. A discipline of programming Prentice Hall. 1976. - Carl Hewitt and Henry Baker Actors and Continuous Functionals Proceeding of IFIP Working Conference on Formal Description of Programming Concepts. August 1–5, 1977.
- Henry Baker and Carl Hewitt The Incremental Garbage Collection of Processes Proceeding of the Symposium on Artificial Intelligence Programming Languages. SIGPLAN Notices 12, August 1977.
- Gilles Kahn and David MacQueen. Coroutines and networks of parallel processes IFIP. 1977
- Aki Yonezawa Specification and Verification Techniques for Parallel Programs Based on Message Passing Semantics MIT EECS Doctoral Dissertation. December 1977.
- Henry Baker. Actor Systems for Real-Time Computation MIT EECS Doctoral Dissertation. January 1978.
- Carl Hewitt and Russ Atkinson. Synchronization in Actor Systems Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. 1977
- Carl Hewitt and Russ Atkinson. Specification and Proof Techniques for Serializers IEEE Journal on Software Engineering. January 1979.
- Ken Kahn. A Computational Theory of Animation MIT EECS Doctoral Dissertation. August 1979.
- Carl Hewitt, Beppe Attardi, and Henry Lieberman. Delegation in Message Passing Proceedings of First International Conference on Distributed Systems Huntsville, AL. October 1979.
- Nissim Francez, C.A.R. Hoare, Daniel Lehmann, and Willem-Paul de Roever. Semantics of nondetermiism, concurrency, and communication Journal of Computer and System Sciences. December 1979.
- George Milne and Robin MilnerRobin MilnerArthur John Robin Gorell Milner FRS FRSE was a prominent British computer scientist.-Life, education and career:...
. Concurrent processes and their syntax JACM. April 1979. - Russ Atkinson. Automatic Verification of Serializers MIT Doctoral Dissertation. June, 1980.
- Bill Kornfeld and Carl Hewitt. The Scientific Community Metaphor IEEE Transactions on Systems, Man, and Cybernetics. January 1981.
- Bill Kornfeld. Parallelism in Problem Solving MIT EECS Doctoral Dissertation. August 1981.
- Daniel Theriault. A Primer for the Act-1 Language MIT AI memo 672. April 1982.
- Daniel Theriault. Issues in the Design and Implementation of Act 2 MIT AI technical report 728. June 1983.
- Henry Lieberman. An Object-Oriented Simulator for the Apiary Conference of the American Association for Artificial Intelligence, Washington, D. C., August 1983
- Carl Hewitt and Peter de Jong. Analyzing the Roles of Descriptions and Actions in Open Systems Proceedings of the National Conference on Artificial Intelligence. August 1983.
- Carl Hewitt and Henry Lieberman. Design Issues in Parallel Architecture for Artificial Intelligence MIT AI memo 750. Nov. 1983.
- Daniel Ingalls. The Evolution of the Smalltalk Virtual Machine in Smalltalk-80: Bits of History, Words of Advice. Addison Wesley. 1983.
- Hal AbelsonHal AbelsonHarold Abelson is a Professor of Electrical Engineering and Computer Science at MIT, a fellow of the IEEE, and is a founding director of both Creative Commons and the Free Software Foundation....
, Gerald Jay SussmanGerald Jay SussmanGerald Jay Sussman is the Panasonic Professor of Electrical Engineering at the Massachusetts Institute of Technology . He received his S.B. and Ph.D. degrees in mathematics from MIT in 1968 and 1973 respectively. He has been involved in artificial intelligence research at MIT since 1964...
and Julie Sussman, Structure and Interpretation of Computer Programs MIT Press and McGraw-Hill, 1985. - C.A.R. Hoare. Communicating Sequential Processes Prentice Hall. 1985.
- Carl Hewitt. The Challenge of Open Systems Byte Magazine. April 1985. Reprinted in The foundation of artificial intelligence---a sourcebook Cambridge University Press. 1990.
- Carl Manning. Traveler: the actor observatory ECOOP 1987. Also appears in Lecture Notes in Computer ScienceLecture Notes in Computer ScienceLecture Notes in Computer Science is a series of computer science books that has been published by Springer Science+Business Media since 1973....
, vol. 276. - William Athas and Charles Seitz Multicomputers: message-passing concurrent computers IEEE Computer August 1988.
- William Athas and Nanette Boden Cantor: An Actor Programming System for Scientific Computing in Proceedings of the NSF Workshop on Object-Based Concurrent Programming. 1988. Special Issue of SIGPLAN Notices.
- Jean-Pierre Briot. From objects to actors: Study of a limited symbiosis in Smalltalk-80 Rapport de Recherche 88-58, RXF-LITP, Paris, France, September 1988
- William Dally and Wills, D. Universal mechanisms for concurrency PARLE 1989.
- W. Horwat, A. Chien, and W. Dally. Experience with CST: Programming and Implementation PLDI. 1989.
- Carl Hewitt. Towards Open Information Systems Semantics Proceedings of 10th International Workshop on Distributed Artificial Intelligence. October 23–27, 1990. Bandera, Texas.
- Akinori Yonezawa, Ed. ABCL: An Object-Oriented Concurrent System MIT Press. 1990.
- K. Kahn and Vijay A. Saraswat, "Actors as a special case of concurrent constraint (logic) programming", in SIGPLAN Notices, October 1990. Describes Janus.
- Carl Hewitt. Open Information Systems Semantics Journal of Artificial Intelligence. January 1991.
- Carl Hewitt and Jeff Inman. DAI Betwixt and Between: From "Intelligent Agents" to Open Systems Science IEEE Transactions on Systems, Man, and Cybernetics. Nov./Dec. 1991.
- Carl Hewitt and Gul Agha. Guarded Horn clause languages: are they deductive and Logical? International Conference on Fifth Generation Computer Systems, Ohmsha 1988. Tokyo. Also in Artificial Intelligence at MIT, Vol. 2. MIT Press 1991.
- William Dally, et al. The Message-Driven Processor: A Multicomputer Processing Node with Efficient Mechanisms IEEE MicroIEEE MicroIEEE Micro is a broad-based practitioner-oriented magazine of the IEEE Computer Society targeting small system and semiconductor chip professionals, including electronic engineers, designers, architects, developers, process improvement experts, testers, quality engineers, and project managers...
. April 1992. - S. Miriyala, G. Agha, and Y.Sami. Visulatizing actor programs using predicate transition nets Journal of Visual Programming. 1992.
- Alan Kay. The Early History of Smalltalk The second ACM conference on history of programming languages. 1993.
- Carl Hewitt and Carl Manning. Negotiation Architecture for Large-Scale Crisis Management AAAI-94 Workshop on Models of Conflict Management in Cooperative Problem Solving. Seattle, WA. Aug. 4, 1994.
- Darrell Woelk. Developing InfoSleuth Agents Using Rosette: An Actor Based Language Proceedings of the CIKM '95 Workshop on Intelligent Information Agents. 1995.
- Carl Hewitt and Carl Manning. Synthetic Infrastructures for Multi-Agency Systems Proceedings of ICMAS '96. Kyoto, Japan. December 8–13, 1996.
- S. Frolund. Coordinating Distributed Objects: An Actor-Based Approach for Synchronization MIT Press. November 1996.
- W. Kim. ThAL: An Actor System for Efficient and Scalable Concurrent Computing PhD thesis. University of Illinois at Urbana Champaign. 1997.
- Jean-Pierre Briot. Acttalk: A framework for object-oriented concurrent programming-design and experience 2nd France-Japan workshop. 1999.
- N. Jamali, P. Thati, and G. Agha. An actor based architecture for customizing and controlling agent ensembles IEEE Intelligent Systems. 14(2). 1999.
- Don Box, David Ehnebuske, Gopal Kakivaya, Andrew Layman, Noah Mendelsohn, Henrik Nielsen, Satish Thatte, Dave Winer. Simple Object Access Protocol (SOAP) 1.1 W3C Note. May 2000.
- M. Astley, D. Sturman, and G. Agha. Customizable middleware for modular distributed software CACM. 44(5) 2001.
- Carlos Varela. Worldwide Computing with Universal Actors: Linguistic Abstractions for Naming, Migration, and Coordination PhD thesis. U. of Illinois at Urbana-Champaign. 2001.
- N. Venkatasubramanian, C. Talcott, and G. Agha. A formal model for reasoning about adaptive QoS-enabled middleware Formal Methods Europe (FME). 2001.
- Edward Lee, S. Neuendorffer, and M. Wirthlin. Actor-oriented design of embedded hardware and software systems Journal of circuits, systems, and computers. 2002.
- P. Thati, R. Ziaei, and G. Agha. A Theory of May Testing for Actors Formal Methods for Open Object-based Distributed Systems. March 2002.
- P. Thati, R. Ziaei, and G. Agha. A theory of may testing for asynchronous calculi with locality and no name matching Algebraic Methodology and Software Technology. Springer Verlag. September 2002. LNCS 2422.
- Gul Agha and Carlos Varela. Worldwide Computing Middleware Practical Handbook on Internet Computing. CRC Press, 2004.
- Stephen Neuendorffer. Actor-Oriented Metaprogramming PhD Thesis. University of California, Berkeley. December, 2004
- Carl Hewitt (2006a) The repeated demise of logic programming and why it will be reincarnated What Went Wrong and Why: Lessons from AI Research and Applications. Technical Report SS-06-08. AAAI Press. March 2006.
- Carl Hewitt (2006b) What is Commitment? Physical, Organizational, and Social COIN@AAMAS. April 27, 2006b.
- Carl Hewitt (2007a) What is Commitment? Physical, Organizational, and Social (Revised) Pablo Noriega .et al. editors. LNAI 4386. Springer-Verlag. 2007.
- Carl Hewitt (2007b) Large-scale Organizational Computing requires Unstratified Paraconsistency and Reflection COIN@AAMAS'07.
External links
- Actors on the JVM Dr. Dobb's, April 2011
- A now dated set of speculations by Paul Mackay can be found at Why has the actor model not succeeded?
- JavAct - a Java library for programming concurrent, distributed, and mobile applications using the actor model (and open implementation principles).
- Functional Java - a Java library of that includes an implementation of concurrent actors with code examples in standard Java and Java 7 BGGA style.
- ActorFoundry - a Java-based library for Actor programming. The familiar Java syntax, an ant build file and a bunch of example make the entry barrier very low.
- ActiveJava - a prototype Java language extension for Actor programming.