Actor model early history
Encyclopedia
In computer science
, the Actor model
, first published in 1973 , is a mathematical model of concurrent computation. This article is about the early history of the Actor model. See Actor model middle history
and Actor model later history
for subsequent developments.
In 1963 in the field of Artificial Intelligence
, John McCarthy
introduced situation variables in logic in the Situational Calculus. In McCarthy and Hayes 1969, a situation is defined as "the complete state of the universe at an instant of time." In this respect, the situations of McCarthy are not suitable for use in the Actor model since it has no global states.
From the definition of an Actor, it can be seen that numerous events take place: local decisions, creating Actors, sending messages, receiving messages, and designating how to respond to the next message received. Partial orderings on such events have been axiomatized in the Actor model and their relationship to physics explored (see Actor model theory
).
and relativistic physics
. One issue is what can be observed about Actor systems. The question does not have an obvious answer because it poses both theoretical and observational challenges similar to those that had arisen in constructing the foundations of quantum physics. In concrete terms for Actor systems, typically we cannot observe the details by which the arrival order of messages for an Actor is determined (see Indeterminacy in concurrent computation). Attempting to do so affects the results and can even push the indeterminacy elsewhere. e.g., see metastability in electronics
. Instead of observing the insides of arbitration processes of Actor computations, we await the outcomes.
For example, consider the following question: "Does each Actor have a queue in which its communications are stored until received by the Actor to be processed?" Carl Hewitt
argued against including such queues as an integral part of the Actor model. One consideration was that such queues could themselves be modeled as Actors that received messages to enqueue and dequeue the communications. Another consideration was that some Actors would not use such queues in their actual implementation. E.g., an Actor might have a network of arbiters
instead. Of course, there is a mathematical abstraction which is the sequence of communications that have been received by an Actor. But this sequence emerged only as the Actor operated. In fact the ordering of this sequence can be indeterminate (see Indeterminacy in concurrent computation).
Another example of abstracting away implementation detail was the question of interpretation
: "Should interpretation be an integral part of the Actor model?" The idea of interpretation is that an Actor would be defined by how its program script processed eval messages. (In this way Actors would be defined in a manner analogous to Lisp
which was "defined" by a meta-circular interpreter procedure named eval written in Lisp.) Hewitt argued against making interpretation integral to the Actor model. One consideration was that to process the eval messages, the program script of an Actor would itself have a program script (which in turn would have ...)! Another consideration was that some Actors would not use interpretation in their actual interpretation. E.g., an Actor might be implemented in hardware instead. Of course there is nothing wrong with interpretation per se. Also implementing interpreters using eval messages is more modular and extensible than the monolithic interpreter approach of Lisp.
model in her dissertation.
and Guy Steele
then took an interest in Actors and published a paper on their Scheme interpreter in which they (misleadingly) concluded "we discovered that the 'actors' and the lambda expressions
were identical in implementation." The actual situation is that the lambda calculus is capable of expressing some kinds of parallelism but, in general, not the concurrency expressed in the Actor model. On the other hand, the Actor model is capable of expressing all of the parallelism in the lambda calculus.
and Henry Baker
published the Laws for Actors.
in the sense defined by Dana Scott
(see denotational semantics
).
published a paper on specification and proof techniques for serializers providing an efficient solution to encapsulating shared resources for concurrency control
.
1976, Michael Smyth
1978, Henry Baker
1978, Francez, Hoare
, Lehmann, and de Roever 1979, and Milne
and Milner
1979) published the first satisfactory mathematical denotational
model incorporating unbounded nondeterminism
using domain theory
in his dissertation in 1981 (see Clinger's model). Subsequently Hewitt [2006] augmented the diagrams with arrival times to construct a technically simpler denotational model that is easier to understand. See History of denotational semantics.
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
Actor model
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...
, first published in 1973 , is a mathematical model of concurrent computation. This article is about the early history of the Actor model. See Actor model middle history
Actor model middle history
In computer science, the Actor model, first published in 1973 , is a mathematical model of concurrent computation. This article reports on the middle history of the Actor model in which major themes were initial implementations, initial applications, and development of the first proof theory and...
and Actor model later history
Actor model later history
In computer science, the Actor model, first published in 1973 , is a mathematical model of concurrent computation. This article reports on the later history of the Actor model in which major themes were investigation of the basic power of the model, study of issues of compositionality, development...
for subsequent developments.
Event orderings versus global state
A fundamental challenge in defining the Actor model is that it did not provide for global states so that a computational step could not be defined as going from one global state to the next global state as had been done in all previous models of computation.In 1963 in the field of Artificial Intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
, John McCarthy
John McCarthy (computer scientist)
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
introduced situation variables in logic in the Situational Calculus. In McCarthy and Hayes 1969, a situation is defined as "the complete state of the universe at an instant of time." In this respect, the situations of McCarthy are not suitable for use in the Actor model since it has no global states.
From the definition of an Actor, it can be seen that numerous events take place: local decisions, creating Actors, sending messages, receiving messages, and designating how to respond to the next message received. Partial orderings on such events have been axiomatized in the Actor model and their relationship to physics explored (see 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,...
).
Relationship to physics
According to Hewitt (2006), the Actor model is based on physics in contrast with other models of computation that were based on mathematical logic, set theory, algebra, etc. Physics influenced the Actor model in many ways, especially quantum physicsQuantum indeterminacy
Quantum indeterminacy is the apparent necessary incompleteness in the description of a physical system, that has become one of the characteristics of the standard description of quantum physics...
and relativistic physics
Theory of relativity
The theory of relativity, or simply relativity, encompasses two theories of Albert Einstein: special relativity and general relativity. However, the word relativity is sometimes used in reference to Galilean invariance....
. One issue is what can be observed about Actor systems. The question does not have an obvious answer because it poses both theoretical and observational challenges similar to those that had arisen in constructing the foundations of quantum physics. In concrete terms for Actor systems, typically we cannot observe the details by which the arrival order of messages for an Actor is determined (see Indeterminacy in concurrent computation). Attempting to do so affects the results and can even push the indeterminacy elsewhere. e.g., 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....
. Instead of observing the insides of arbitration processes of Actor computations, we await the outcomes.
Abstracting away implementation details
An important challenge in defining the Actor model was to abstract away implementation details.For example, consider the following question: "Does each Actor have a queue in which its communications are stored until received by the Actor to be processed?" 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....
argued against including such queues as an integral part of the Actor model. One consideration was that such queues could themselves be modeled as Actors that received messages to enqueue and dequeue the communications. Another consideration was that some Actors would not use such queues in their actual implementation. E.g., an Actor might have a network of arbiters
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...
instead. Of course, there is a mathematical abstraction which is the sequence of communications that have been received by an Actor. But this sequence emerged only as the Actor operated. In fact the ordering of this sequence can be indeterminate (see Indeterminacy in concurrent computation).
Another example of abstracting away implementation detail was the question of interpretation
Interpreter (computing)
In computer science, an interpreter normally means a computer program that executes, i.e. performs, instructions written in a programming language...
: "Should interpretation be an integral part of the Actor model?" The idea of interpretation is that an Actor would be defined by how its program script processed eval messages. (In this way Actors would be defined in a manner analogous to 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...
which was "defined" by a meta-circular interpreter procedure named eval written in Lisp.) Hewitt argued against making interpretation integral to the Actor model. One consideration was that to process the eval messages, the program script of an Actor would itself have a program script (which in turn would have ...)! Another consideration was that some Actors would not use interpretation in their actual interpretation. E.g., an Actor might be implemented in hardware instead. Of course there is nothing wrong with interpretation per se. Also implementing interpreters using eval messages is more modular and extensible than the monolithic interpreter approach of Lisp.
Operational model
Nevertheless progress developing the model was steady. In 1975, Irene Greif published the first operationalOperational 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...
model in her dissertation.
Scheme
Gerald SussmanGerald Jay Sussman
Gerald 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 Guy Steele
Guy L. Steele, Jr.
Guy Lewis Steele Jr. , also known as "The Great Quux", and GLS , is an American computer scientist who has played an important role in designing and documenting several computer programming languages.-Biography:...
then took an interest in Actors and published a paper on their Scheme interpreter in which they (misleadingly) concluded "we discovered that the 'actors' and the lambda expressions
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...
were identical in implementation." The actual situation is that the lambda calculus is capable of expressing some kinds of parallelism but, in general, not the concurrency expressed in the Actor model. On the other hand, the Actor model is capable of expressing all of the parallelism in the lambda calculus.
Laws for Actors
Two years after Greif published her operational model, Carl HewittCarl 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....
and 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...
published the Laws for Actors.
Proof of continuity of computable functions
Using the laws of the Actor model, Hewitt and Baker proved that any Actor that behaves like a function is continuousScott continuity
In mathematics, given two partially ordered sets P and Q a function f : P \rightarrow Q between them is Scott-continuous if it preserves all directed suprema, i.e...
in the sense defined by Dana Scott
Dana Scott
Dana Stewart Scott is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California...
(see denotational semantics
Denotational semantics
In 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...
).
Specifications and proofs
Aki Yonezawa published his specification and verification techniques for Actors. Russ Atkinson and Carl HewittCarl 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....
published a paper on specification and proof techniques for serializers providing an efficient solution to encapsulating shared resources for 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...
.
Mathematical characterization using domain theory
Finally eight years after the first Actor publication, Will Clinger (building on the work of Irene Greif 1975, Gordon PlotkinGordon Plotkin
Gordon D. Plotkin, FRS, FRSE is a Scottish computer scientist.Gordon Plotkin is best-known for his introduction of structural operational semantics and his work on denotational semantics. In particular, his notes on A Structural Approach to Operational Semantics of 1981 were very influential...
1976, Michael Smyth
Michael Smyth
Michael Smyth is an Australian journalist.-Career:Smyth was a newsreader and reporter with the Australian Broadcasting Corporation for almost 12 years. He read the weekend edition of ABC TV News with Neil Cross, and for many years read the weekday news. His work also featured on the weekly current...
1978, 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...
1978, Francez, Hoare
Hoare
Hoare may refer to:Individual people* C. A. R. Hoare , British computer scientist* Des Hoare , Australian cricketer* Desmond Hoare , British sailor & educator...
, Lehmann, and de Roever 1979, and Milne
Milne
Milne may refer to:People with the surname Milne*Milne Places*Milne Bay, large bay in Milne Bay Province*Milne Bay Province, Papua New Guinea*Milne Inlet, Nunavut, Canada*Milne Land, large island in eastern Greenland...
and Milner
Milner
-People:* Alfred Milner, 1st Viscount Milner , British colonial administrator* Andy Milner , English footballer* Brenda Milner , English-Canadian neuropsychologist* Eric Milner-White , English cleric...
1979) published the first satisfactory mathematical denotational
Denotational semantics
In 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...
model incorporating 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...
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...
in his dissertation in 1981 (see Clinger's model). Subsequently Hewitt [2006] augmented the diagrams with arrival times to construct a technically simpler denotational model that is easier to understand. See History of denotational semantics.
See also
- Actor model and process calculi historyActor model and process calculi historyThe Actor model and process calculi share an interesting history and co-evolution.-Early work:The Actor model, first published in 1973, is a mathematical model of concurrent computation...
- History of denotational semantics
- History of logic programming