In computer science, the Actor model, first published in 1973 (Hewitt et al. 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.
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 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).
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.
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 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.
Nevertheless progress developing the model was steady. In 1975, Irene Greif published the first operational model in her dissertation.
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 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.
Two years after Greif published her operational model, Carl Hewitt and Henry Baker published the Laws for Actors.
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).
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.
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.