Actor model

The Actor model, first published in 1973, is a mathematical model of concurrent computation developed by Carl Hewitt and his students and colleagues at CalTech, Kyoto University, MCC, MIT, SRI, Stanford University, University of Illinois, University of Paris 6, University of Pisa, University of Tokyo and elsewhere. The Actor work built on Lisp, Simula, capability-based systems, packet switching and Smalltalk-71.

Actors are the universal primitives of concurrent 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 keys to practical success with the Actor model are specialization for functionality and optimization for performance. Currently the most common use cases are through Web Services and programming languages (e.g. Java and C#).

The Actor model differed from previous models of computation in that the model was inspired by the laws of physics (physical laws).

The global state approach

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. Then models were developed based on computers, the so-called von Neumann machines. Computational models were developed in automata theory for finite state machines and push down stack machines including their nondeterministic versions.

Probably the first concurrent models of computation were based on shared memory symetric multiple processors. An attempt was made to model these multiprocessor machines as nondeterministic automata in which a machine was modeled using a global state which changed nondeterministically.

Unbounded nondeterminism controversy

A global state based approach was developed by Edsger Dijkstra in his weakest precondition approach. The idea was that the semantics of (parallel) programs could be characterized by how they changed the global state of the machine when they terminated. Because a program that began in a well defined initial state could terminate in several different states, Dijkstra expressed the semantics beginning with a terminal state. He characterized the semantics of a program in terms of the weakest precondition on the predecessor state that will guarantee that the program will terminate in a specified state. Dijkstra's model gave rise to a controversy concerning unbounded nondeterminism which can be explained as follows: 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.

Hewitt argued otherwise: One reason was that there is no bound that can be placed on how long it takes a computational circuit called an arbiter to settle. 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.

No global state in the Actor model

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.

Early history of the Actor model

The invention of Actors occurred in the context of a great debate about control structures that occurred in Artificial Intelligence in the early 1970s.

Procedural embedding of knowledge

Under the leadership of Marvin Minsky and Seymour Papert at the MIT Artificial Intelligence Laboratory there developed a school of thought that the way to make progress was to pursue a procedural approach. This was in contrast to the logical approach pioneered by John McCarthy who advocated expressing knowledge declaratively in mathematical logic. Bill Woods was also pursuing a procedural approach. Hewitt instantiated the MIT approach as "procedural embedding of knowledge" in the programming language Planner that featured pattern-directed invocation of high level procedural plans from goals and assertions. A subset called Micro Planner was implemented by Gerry Sussman, Eugene Charniak and Terry Winograd and was used in Winograd's natural-language understanding program SHRDLU, Gene Charniak's story understanding work, and some other projects. This generated a great deal of excitement in Artificial Intelligence.

Control structure trouble

However, computer memories were very small by current standards because they were expensive, being made of iron ferrite cores at that time. So Planner adopted the then common expedient of using backtracking control structure to economize on the use of computer memory. In this way, the computer only had to store one possibility at a time while exploring alternatives.

One of the implementation decisions in Micro Planner had unfortunate consequences. Lisp had adopted the programming pun of identifying NIL, the empty list with logical false at memory location 0 because it was quicker to test for 0 than anything else. Micro Planner extended this pun also to use NIL as a signal to begin backtracking. In Micro Planner, it was common to write programs to perform some operation on every element of a list by using a loop to process the first element of a list, take the rest of the list, and then jump back to the top of the loop to test if the list was empty. If the list tested empty, then the program would go on to do other things. Such a program never made it to the testing the empty list because when the last element was processed and the rest of the list was taken, NIL was returned as a value. The Micro Planner interpreter took this as the signal to begin backtracking and began undoing all the work of processing the elements of the list! People were dumbfounded.

In this and several other ways, backtracking proved unwieldy helping to fuel the great control structure debate. Hewitt investigated some alternatives in his thesis.

Control structure characterizations

Using program schemas, Hewitt in collaboration with Mike Paterson proved that recursion is more powerful than iteration and parallelism more powerful than recursion. (He conjectured that coroutines are more powerful than recursion but couldn't prove it then.)

Hairy control structure

Peter Landin had introduced an even more powerful control structure using his J (for Jump) operator that could perform a nonlocal goto into the middle of a procedure invocation context. In fact the J operator could jump back into the middle of a procedure invocation even after it had already returned! People were amazed. Drew McDermott and Gerry Sussman called Landin's concept "Hairy Control Structure" and used it in the Conniver programming language. Scott Fahlman used Conniver in his planning system for robot construction tasks.

Message passing

Alan Kay visited MIT and discussed some of his ideas including Smalltalk-71. Hewitt was intrigued by the possibilities but was put off by the complexity of communication in Smalltalk-71 that included invocations with many fields including global, sender, receiver, reply-style, status, reply, operator selector, etc. But see Kay's early history of Smalltalk. SIMULA 67 pioneered in using the message passing metaphor for computation motivated originally by discrete event simulation applications. However it used coroutine control structure instead of true concurrency. Subsequent versions of the Smalltalk language largely followed the path of SIMULA. The Smalltalk system went on to become an enormous success innovating in bitmap displays, personal computing, the class browser interface, and many other ways. 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.)

Inspired by the Arpanet, Hewitt proposed the development of a new model of computation in which messages would not have any required fields at all: they could be empty! Of course if access to (other) Actors that may not be already known to a recipient is desired by the sender of a message, then it would have to include in the message addresses of the additional Actors. This insight building on Lisp, Simula and capability-based systems was the genesis of the Actor model.

Control structures are patterns of passing messages

Hewitt reported: ... we have found that we can do without the paraphernalia of "hairy control structure" (such as possibility lists, non-local gotos, and assignments of values to the internal variables of other procedures in CONNIVER.)... The conventions of ordinary message-passing seem to provide a better structured, more intuitive foundation for constructing the communication systems needed for expert problem-solving modules to cooperate effectively. The Actor model provided the foundation for solving the Artificial Intelligence control structure problem. It took considerable time to develop programming methodologies for the Actor model. The implementation of the Scientific Community Metaphor requires sophisticated message passing.

Early Actor model publications

The first published paper on Actors in 1973 was somewhat obscure because the Actor concept was so revolutionary in its elimination of the global state that had been central to all previous models of computation. In fact it was 8 years after the initial paper that Will Clinger published his mathematical denotational model. However progress had been steady before then: it was only 2 years after the initial published paper that Irene Greif published her operational model. And 2 years after that Carl Hewitt and Henry Baker published the Laws for Actors which they then used to derive the continuity criterion for computable functions of Dana Scott, Aki Yonezawa published his specification and verification techniques for Actors, and Hewitt published the paper on viewing control structures as patterns of passing messages.

Relationship to mathematical logic

Robert Kowalski developed the thesis that computation could be subsumed by deduction and quoted with approval "Computation is controlled deduction." which he attributed to Pat Hayes. Contrary to Kowalski and Hayes, Hewitt's thesis was that logical deduction was incapable of carrying out concurrent computation in open systems. He argued that a mathematical model of Actors did not necessarily determine particular concurrent computations. The Actor model is exactly analogous to physics: Quantum theory does not necessarily determine particular physical processes. E.g., in the double-slit experiment, Quantum theory specifically does not determine where a particular particle strikes the screen regardless of how tightly the input of the particle is controlled. Indeed, according to the standard interpretation of Quantum theory, it is impossible to determine ahead of time where a particular particle strikes. Indeterminacy carries over into concurrent computation because of arbitration in the implementation of Actor systems. Therefore mathematical logic can not implement concurrent computation in open systems. However, Hewitt's thesis is still controversial and the subject of current research.

Note that the limitations of logic do not mean that logic is not an extremely valuable tool. Bill Kornfeld and Carl Hewitt contributed to pattern-directed invocation languages with the development of the Scientific Community Metaphor, which made strong use of logic within scientific theories.

Relationship to process calculi

A subsequent approach to modeling concurrent computation inspired by algebra was process calculi as developed in Communicating Sequential Processes (the model) by CAR Hoare and pi-calculus by Robin Milner, Joachim Parrow, and David Walker. The process calculi approach differed from Actors in two core design decisions:

1. In process calculi, computing agents (processes) have discrete points of connection and interaction called names (channels) which are somewhat analogous to the TCP connections on the Internet. In contrast, communication in the Actor Model is more analogous to sending an Internet IP packet message by which a computer can send a packet to the IP address of any (other) computer requiring no prior setup on its part.
2. Communication itself is binary, point-to-point interaction between computing agents (processes) in process calculi. Interaction happens along names (channels) by handshaking or synchronization between a sender and a receiver. In contrast, in the Actor Model, there is no handshaking required between sender and receiver(s).

In recent years Ugo Montanari and Carolyn Talcott have contributed to attempting to reconcile Actors with process calculi.

A bright future for the Actor model

On the 40th anniversary of the publication of Moore's Law, hardware development is furthering both local and nonlocal massive concurrency. Local concurrency is being enabled by new hardware for 64-bit many core microprocessors, multi-chip modules, and high performance interconnect. Nonlocal concurrency is being enabled by new hardware for wired and wireless broadband packet switched communications. Both local and nonlocal storage capacities are growing exponentially. All of the above developments favor the Actor model.

The Actor model stands to continue to foster developments in computer and communications architecture, concurrent programming languages, and Web Services. A challenge for the future is to continue the development of organizational and negotiation methods, principles, and practices for Actors.

Actor researchers

Gul Agha, Beppe Attardi, Henry Baker, Will Clinger, Irene Grief, Carl Manning, Ian Mason, Ugo Montanari, Maria Simi, Scott Smith, Carolyn Talcott, and Aki Yonezawa have made important contributions to the semantics of Actors. 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, Ken Kahn, Henry Lieberman, Carl Manning, Chuck Seitz, Richard Steiger, Dan Theriault, Mario Tokoro, and Darrell Woelk.

See Also

• Scientific Community Metaphor
• Petri nets
• Data flow
• Neural networks
• Scheme

Reference

• Peter Landin. A Generalization of Jumps and Labels Report. UNIVAC Systems Programming Research. August 1965. Reprinted in Higher Order and Symbolic Computation. 1998.
• Carl Hewitt. PLANNER: A Language for Proving Theorems in Robots IJCAI 1969
• Mike Paterson and Carl Hewitt. Comparative Schematology MIT AI Memo 201. August 1970.
• Gerry Sussman and Terry Winograd. Micro-planner Reference Manual AI Memo No, 203, MIT Project MAC, July 1970.
• 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.
• Drew McDermott and Gerry Sussman. The Conniver Reference Manual MIT AI Memo 259. May 1972.
• Birtwistle, G.M., O.-J. Dahl, B. Myhrhaug and K. Nygaard. SIMULA Begin AUERBACH Publishers Inc, 1973.
• Daniel Bobrow: A Model for Control Structures for Artificial Intelligence Programming Languages IJCAI 1973.
• Carl Hewitt, Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973.
• Scott Fahlman. A Planning System for Robot Construction Tasks MIT AI TR-283. June 1973.
• Irene Greif. Semantics of Communicating Parallel Professes MIT EECS Doctoral Dissertation. August 1975.
• Alan Kay and Adele Goldberg. Smalltalk Instruction Manual Xerox PARC Memo SSL-76-6. May 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.
• 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.
• 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.
• Henry Lieberman and Carl Hewitt. A real Time Garbage Collector Based on the Lifetimes of Objects CACM 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.
• Henry Lieberman and Carl Hewitt. Design Issues in Parallel Architectures for Artificial Intelligence IEEE CompCon Conference, March 1984
• Charles Seitz. The Cosmic Cube CACM. Jan. 1985.
• CAR Hoare. Communicating Sequential Processes Prentice Hall. 1985.
• Carl Hewitt. The Challenge of Open Systems Byte Magazine. April 1985.
• Gul Agha. Actors: A Model of Concurrent Computation in Distributed Systems Doctoral Dissertation. 1986.
• Henry Lieberman. Concurrent Object Oriented Programming in Act 1 in Object Oriented Concurrent Programming , Aki Yonezawa and Mario Tokoro, eds., MIT Press, 1987.
• Carl Manning. Traveler: the actor observatory ECOOP 1987. Also appears in Lecture Notes in Computer Science, vol. 276.
• Robert Kowalski. The Early Years of Logic Programming CACM. January 1988.
• 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, G. Agha, P. Wegner, and A. Yonezawa, Eds. ACM, N.Y., April 1989. 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 ‘89.
• W. Horwat, A. Chien, and W. Dally. Experience with CST: Programming and Implementation PLDI. 1989.
• Robin Milner, Joachim Parrow and David Walker. A calculus of mobile processes Computer Science Dept. Edinburgh. Reports ECS-LFCS-89-85 and ECS-LFCS-89-86. June 1989. Revised Sept. 1990 and Oct. 1990 respectively.
• 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.
• Carl Hewitt. Open Information Systems Semantics Journal of Artificial Intelligence. January 1991.
• Carl Hewitt and Gul Agha. Guarded Horn clause languages: are they deductive and Logical? in Artificial Intelligence at MIT, Vol. 2. MIT Press 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.
• William Dally, et al. The Message-Driven Processor: A Multicomputer Processing Node with Efficient Mechanisms IEEE Micro. April 1992.
• Gul Agha, Ian Mason, Scott Smith, and Carolyn Talcott. A Foundation for Actor Computation Journal of Functional Programming January 1993.
• 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.
• Carl E. Hewitt. From Contexts to Negotiation Forums AAAI Symposium on Formalizing Context. Nov. 10-11, 1995. Cambridge Mass.
• 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. Dec. 8-13, 1996.
• Ugo Montanari and Carolyn Talcott. Can Actors and Pi-Agents Live Together? Electronic Notes in Theoretical Computer Science. 1998.
• Jaques Ferber Multiagent Systems: An Introduction to Distributed Artificial Intelligence Addison-Wesley. 1999.
• Robin Milner. Communicating and Mobile Systems: The Pi-Calculus University of Cambridge Press. 1999.