History of the Actor model

From Wikipedia, the free encyclopedia

 This page is a candidate to be copied to Wikibooks using the Import process.
If the page can be re-written into an encyclopedic article, please do so and remove this message.
Before you move this content to Wikibooks, verify that it conforms to Wikibooks policies of acceptable content at What is Wikibooks? Often content unacceptable to Wikipedia may not be acceptable on Wikibooks either; facilitate the copying of this article by listing it on Wikibooks:Requests for Import.

In computer science, the Actor model, first published in 1973 (Hewitt et al. 1973), is a mathematical model of concurrent computation. Many fundamental issues were discussed and debated in the early history of the Actor model. See Actor model and process calculi history and Actor model and process calculi for coevolution with process calculi.

Contents

[edit] 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, John McCarthy introduced situation variables in logic in the Situational Calculus. In McCarthy and Hays 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).

[edit] 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 physics 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.

[edit] 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 argued against including such queues as an integral part of the Actor model. One considerations 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.

[edit] Operational model

Nevertheless progress developing the model was steady. In 1975, Irene Greif published the first operational model in her dissertation.

[edit] Scheme

Gerald Sussman 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 expessions 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.

[edit] Laws for Actors

Two years after Greif published her operational model, Carl Hewitt and Henry Baker published the Laws for Actors.

[edit] 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 continuous in the sense defined by Dana Scott (see denotational semantics).

[edit] Specifications and proofs

Aki Yonezawa published his specification and verification techniques for Actors. Russ Atkinson and Carl Hewitt published a paper on specification and proof techniques for serializers providing an efficient solution to encapsulating shared resources for concurrency control.

[edit] Mathematical characterization using domain theory

Finally eight years after the first Actor publication, Will Clinger (building on the work of Irene Greif 1975, Gordon Plotkin 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.

[edit] Was the Actor model premature?

The history of the Actor model raises the question of whether it was premature.

[edit] Original definition of prematurity

As originally defined by Gunther Stent 1972 "A discovery is premature if its implications cannot be connected by a series of simple logical steps to contemporary canonical or generally accepted knowledge." Ilana Lövy 2002 glossed the phrase "series of simple logical steps" in Stent's definition as referring to the "target community's ways of asking relevant questions, of producing experimental results, and of examining new evidence." Michael Ghiselin [2002] argued that if a "minority of scientists accept a discovery, or even pay serious attention to it, then the discovery is not altogether premature in the Stentian sense." In accord with Ghiselin's argument, the Actor model was not premature. Indeed it enjoyed initial popularity and for a couple of decades underwent steady development.

However, Stent in his original article also referred to a development as premature such that when it occurred contemporaries did not seem to able to do much with or build on. This is what happened after a while with the Actor model. The reasons were twofold:

  1. For over 30 years after the first publication of the Actor model, widely deployed computer architectures developed in the direction of making a single sequential thread of execution run faster.
  2. For over 25 years after the first publication, there was no agreed standard by which software could communicate high level data structures across organizational boundaries.

[edit] Before its time?

According to Elihu M. Gerson 2002, phenomena that lead people to talk about discoveries being before their time can be analyzed as follows: "We can see the phenomenon of 'before its time' as composed of two separate steps. The first takes place when a new discovery does not get tied to the conventional knowledge of its day and remains unconnected in the literature. The second step occurs when new events lead to the 'rediscovery' of the unconnected results in a changed context that enables or even facilitates its connection to the conventional knowledge of the rediscovering context."

Now both of the above circumstances that held back the Actor model have changed with the development of (1) many-core (Platform 2015 Unveiled at IDF Spring 2005) computer architectures and (2) Web Services. By the criteria of Gerson, the Actor model might be described by some as before its time.

According to Hadasa Zuckerman and Joshua Lederberg [1986], premature discoveries are those that were made but neglected. By their criteria it remains to be seen whether or not the Actor model was premature!

Gerson 2002 argued, "But histories and sociological studies repeatedly show that we do not have a discovery until the scientific community accepts it as such and stops debating about it. Until then the proposed solution is in an intermediate state." By his argument, the Actor model is a discovery but since its practical importance is not yet accepted by the community, its practical importance is not a discovery.

[edit] See also

[edit] References

  • John McCarthy. Situations, actions and causal laws Technical Report Memo 2, Stanford University Artifcial Intelligence Laboratory. 1963.
  • John McCarhty and Patrick Hayes. Some Philosophical Problems from the Standpoint of Artificial Intelligence in Machine Intelligence 4. Edunburgh University Press. 1969.
  • Werner Heisenberg. Physics and Beyond: Encounters and Conversations translated by A. J. Pomerans (Harper & Row, New York, 1971), pp. 63 – 64.
  • Gunther Stent. Prematurity and Uniqueness in Scientific Discovery Scientific American. December, 1972.
  • -  Carl Hewitt, Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence 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..
  • Irene Greif. Semantics of Communicating Parallel Professes MIT EECS Doctoral Dissertation. August 1975.
  • 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.
  • Carl Hewitt and Henry Baker Laws for Communicating Parallel Processes IFIP-77, August 1977.
  • Aki Yonezawa Specification and Verification Techniques for Parallel Programs Based on Message Passing Semantics MIT EECS Doctoral Dissertation. December 1977.
  • Peter Bishop Very Large Address Space Modularly Extensible Computer Systems MIT EECS Doctoral Dissertation. June 1977.
  • Carl Hewitt. Viewing Control Structures as Patterns of Passing Messages Journal of Artificial Intelligence. June 1977.
  • Henry Baker. Actor Systems for Real-Time Computation MIT EECS Doctoral Dissertation. January 1978.
  • 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.
  • 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.
  • Henry Lieberman. Thinking About Lots of Things at Once without Getting Confused: Parallelism in Act 1 MIT AI memo 626. May 1981.
  • Henry Lieberman. A Preview of Act 1 MIT AI memo 625. June 1981.
  • Gerry Barber. Reasoning about Change in Knowledgeable Office Systems MIT EECS Doctoral Dissertation. August 1981.
  • Bill Kornfeld. Parallelism in Problem Solving MIT EECS Doctoral Dissertation. August 1981.
  • Will Clinger. Foundations of Actor Semantics MIT Mathematics Doctoral Dissertation. June 1981.
  • Daniel Theriault. A Primer for the Act-1 Language MIT AI memo 672. April 1982.
  • Henry Lieberman and Carl Hewitt. A real Time Garbage Collector Based on the Lifetimes of Objects CACM June 1983.
  • 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.
  • M. Jammer The EPR Problem in Its Historical Development in Symposium on the Foundations of Modern Physics: 50 years of the Einstein-Podolsky-Rosen Gedankenexperiment, edited by P. Lahti and P. Mittelstaedt (World Scientific, Singapore, 1985), pp. 129 – 149.
  • A. Fine The Shaky Game: Einstein Realism and the Quantum Theory (University of Chicago Press, Chicago, 1986)
  • Carl Hewitt and Henry Lieberman. Design Issues in Parallel Architecture for Artificial Intelligence MIT AI memo 750. Nov. 1983.
  • Hadasa Zuckerman and Joshua Lederberg. Postmature Scienfic Discovery? Nature. December, 1986.
  • Christopher Fuchs Quantum mechanics as quantum information (and only a little more) in A. Khrenikov (ed.) Quantum Theory: Reconstruction of Foundations (Växjo: Växjo University Press, 2002).
  • Elihu M. Gerson. Prematurity and Social Worlds in Prematurity in Scientific Discovery. University of California Press. 2002.
  • Carl Hewitt. What is Commitment? Physical, Organizational, and Social COIN@AAMAS. April 27, 2006.