Actor model early history

From Wikipedia, the free encyclopedia

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 1 Event orderings versus global state 2 Relationship to physics 3 Abstracting away implementation details 4 Operational model 5 Scheme 6 Laws for Actors 7 Proof of continuity of computable functions 8 Specifications and proofs 9 Mathematical characterization using domain theory 10 Was the Actor model premature? 10.1 Original definition of prematurity 10.2 Before its time? 11 References

[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

Publications on the Actor model claimed that it was based on physics in contrast with other models of computation that were based on mathematical logic, set theory, algebra, etc. In fact physics influenced the Actor model in many ways, especially quantum physics and relativistic physics.

An early issue was to determine what could be observed about Actor systems. The question did not have an obvious answer because it posed both theoretical and observational challenges similar to those that had arisen in constructing the foundations of quantum physics. Werner Heisenberg in a quote that he attributed to Albert Einstein many years after the fact stated [Heisenberg 1971]:

It is quite wrong to try founding a theory on observable magnitudes alone. In reality the very opposite happens. It is the theory which decides what we can observe. You must appreciate that observation is a very complicated process. The phenomenon under observation produces certain events in our measuring apparatus. As a result, further processes take place in the apparatus, which eventually and by complicated paths produce sense impressions and help us to fix the effects in our consciousness. Along this whole path—from the phenomenon to its fixation in our consciousness—we must be able to tell how nature functions, must know the natural laws at least in practical terms, before we can claim to have observed anything at all. Only theory, that is, knowledge of natural laws, enables us to deduce the underlying phenomena from our sense impressions. When we claim that we can observe something new, we ought really to be saying that, although we are about to formulate new natural laws that do not agree with the old ones, we nevertheless assume that the existing laws—covering the whole path from the phenomenon to our consciousness—function in such a way that we can rely upon them and hence speak of “observation.”

Imre Lakatos and Thomas Kuhn had done extensive work on the '"theory laden" character of observation.

The kind of information about the physical world that is available to us according to Chris Fuchs [2004] is “the potential consequences of our experimental interventions into nature.” So this is where we stand with the information available about Actor systems. Characterizing Actor computations is part of Actor model theory.

The importance of all this is that according to [Fuchs 2004] quantum physics "is a theory whose terms refer predominantely to our interface with the world. ... It is a theory not about observables, not about beables, but about 'dingables.' We tap a bell with our gentle touch and listen for its beautiful ring." 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 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?" 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. Would such an Actor queue itself have a queue (which would in turn have ...)?! 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 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 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], phenomenon 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] 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.