8 ms·

Actor Model of Computation (2010) [pdf]

117 points by ninjakeyboard 8y ago

evrydayhustling 8y ago
Awesome overview! I've built actor -oriented implementations in a variety of domains, from finance to education to messaging, and find it a very useful way to think about the world. It can focus your thinking around which state (and actions) should be colocated, and orient you towards event based interfaces that focus around that data rather than specific client needs. People coming from modern programming paradigms will find many useful analogies -- e.g. to SOA/microservice decomposition, to components in a redux event loop. Some cautions: as with any factorization scheme, granularity is important. The actor model makes it easy to think within actors, and hard to reason about interactions. Don't overfactor! Also, orienting around event streams means forgoing synchronous requests. This can lead to insane complexity where each actor awaits specific replies to act on remote state. When adopting a framework, never ignore the useful tools it leaves behind (like the way synchronous request interfaces imply a round trip handshake being handled by another layer).
Zalastax 8y ago
I find this resource confusing and annoying to read. When performing my thesis research I wasted a bunch of time trying to make sense of Hewitt's writing. I think a big problem is that the term "actor model" is so overloaded that it almost becomes meaningless. The actors that Hewitt is talking about is not at all the same as Erlang or Akka. As an example I consider this quote from the text nonsensical "Actor systems can perform computations that are impossible by Turing Machines" or of very little relevance to the actor models we use for programming. This has been discussed at [0]. For an overview of different actor models I prefer, see "43 years of actors: a taxonomy of actor models and their key properties" [1]. Agha's book [2] is also very good and I'd also like to recommend "Mixing Metaphors: Actors as Channels and Channels as Actors" [3]. [0]: http://lambda-the-ultimate.org/node/5208 http://lambda-the-ultimate.org/node/5208 [1]: http://soft.vub.ac.be/Publications/2016/vub-soft-tr-16-11.pdf http://soft.vub.ac.be/Publications/2016/vub-soft-tr-16-11.pd... [2]: https://dspace.mit.edu/handle/1721.1/6952 https://dspace.mit.edu/handle/1721.1/6952 [3]: https://arxiv.org/abs/1611.06276 https://arxiv.org/abs/1611.06276
- PhilWright 8y ago
  > "Actor systems can perform computations that are impossible by Turing Machines" As a turing machine can compute anything that is computable it is therefore impossible for an Actor to do any computation that is not possible by a turing machine. This is computer science 101 and makes me wonder about the value of anything else said in the paper.
  - westoncb 8y ago
    Well the interesting thing would be if that old lesson were violated. Of course it's sealed forever for a specific definition of 'compute,' but I'm still open to the idea that we find something which resembles computation enough that we call it the same thing, yet its precise definition is different enough from the one used in connection with contemporary theory of computation that old proofs of universality won't necessarily apply to it. That said... it seems unlikely to me that the Actor model does something non-trivially beyond what Turing machines are capable of, since it would likely be better known, and we would see Chomsky's hierarchy expanded to hold another class, etc. (Unless it goes beyond Turing Machines by being non-linguistic in some way, which could certainly be interesting. Maybe dealing with non-sequential symbols or something?)
    - carlehewitt 8y ago
      Message passing was omitted from the Turing Model. (Two Turing Machines cannot send messages to each other.) Message passing is fundamental for IoT, etc.
  - mindslight 8y ago
    > it is therefore impossible for an Actor to do any computation that is not possible by a turing machine It is impossible for Actors implemented on a Turing machine to do anything that a Turing machine cannot. But the Actor model itself is larger than a Turing machine - eg nondeterminism. Turing completeness is a lower bound on computation, not a maximum. For instance, a CPU with a hardware random number generator is a Turing machine, but a (basic/strict/pure) Turing machine cannot emulate a CPU with a hardware random number generator!
curuinor 8y ago
Hewitt is now kind of a crank. When Hofstadter came over for the Symsys thing in Stanford a few years back, Hewitt handed Hofstadter a little sheet of paper saying that mere contradiction allowed axiomatic systems to transcend Godel incompleteness theorems. Hofstadter: "Thanks, Carl." and then he threw it away when Hewitt wasn't looking. I think there's a thread in Lambda the Ultimate.
- jchassoul 8y ago
  and yet it moves
- arglebarnacle 8y ago
  You can see a flash of that in this article with "Actor systems can perform computations that are impossible by Turing Machines"
  - jchassoul 8y ago
    The statement is true, Actor systems can handle uncertainty in ways that Turing Machines can not.
    - imode 8y ago
      Actor systems are no more able to handle uncertainty than Turing Machines are, either via nondeterministic TMs or by deterministic TMs. This is basic computability theory.
      - jchassoul 8y ago
        That is wrong, Actor systems have a property called "Unbounded nondeterminism" nondeterministic TM have only bounded nondeterminism. https://en.wikipedia.org/wiki/Unbounded_nondeterminism https://en.wikipedia.org/wiki/Unbounded_nondeterminism
        carlehewitt 8y ago
jchassoul 8y ago
Hewitt work so relevant today, I found interesting that the Lisp Scheme was a failed attempt to implement this model of computation, ORGs, the scientific community metaphor, Planner, Inconsistency robustness, he even have a paper with David Marr from the same year of Actors "Video Ergo Scio" related today with the idea of inverse 3D graphics of capsules.
cokernel 8y ago
According to the abstract at https://arxiv.org/abs/1008.1459 https://arxiv.org/abs/1008.1459 , this document has been revised many times (the current version, from 2015, is v38). Is there a particular reason that v8 was the version selected for submission?
modells 8y ago
I prefer the rapper actor model astronaut form of compuation, but hey, CSP and STM are cool too. Sorry, couldn’t help it. And RDMA is, and always will be, pure evil.
threatofrain 8y ago
Carl Hewitt, Erik Meijer, Clemens Szyperski, talking about the actor model in 2012. https://www.youtube.com/watch?v=1zVdhDx7Tbs https://www.youtube.com/watch?v=1zVdhDx7Tbs
carlehewitt 8y ago
For a more recent description of the Actor Model and associated work, see the following: https://www.amazon.com/Inconsistency-Robustness-Studies-Logic-Hewitt/dp/1848901593 https://www.amazon.com/Inconsistency-Robustness-Studies-Logi... Also, those who will be in London on November 9 can come to my Code Mesh Keynote. See https://plus.google.com/+CarlHewitt-StandardIoT/posts/BXSZ7Y25b4p https://plus.google.com/+CarlHewitt-StandardIoT/posts/BXSZ7Y... It is fair to say that the implementation of Actors is still in its infancy. There is a startup in Silicon Valley that is attempting to remedy this situation. They are looking for expert programming language and run-time implementers ;-) Older publications are obsolete and unfortunately many of them have errors (including my own!). I wrote the Wikipedia article on the Actor Model but am no longer allowed to update it :-( Actors are very well defined up to a unique isomorphism by axioms. The reason that Actors can perform computations that Turing Machines cannot is that the Turing Machine model left out message passing.
- krmboya 8y ago
  > "Older publications are obsolete and unfortunately many of them have errors (including my own!). I wrote the Wikipedia article on the Actor Model but am no longer allowed to update it :-(" As someone who's been interested in the Actor Model recently, thanks for this statement, and the link to the book you've provided. This would help avoid going down the wrong path.
  - carlehewitt 8y ago
    Thanks! Additional information that you might find helpful is here: https://plus.google.com/+CarlHewitt-StandardIoT https://plus.google.com/+CarlHewitt-StandardIoT
devxpy 8y ago
I created a library for multiprocessing, which is loosely based on actor model. The interesting bit is that you'll never have to do the wiring yourself, zproc does it all in the background. https://github.com/pycampers/zproc https://github.com/pycampers/zproc

117 points by ninjakeyboard 8y ago

Awesome overview! I've built actor -oriented implementations in a variety of domains, from finance to education to messaging, and find it a very useful way to think about the world. It can focus your thinking around which state (and actions) should be colocated, and orient you towards event based interfaces that focus around that data rather than specific client needs. People coming from modern programming paradigms will find many useful analogies -- e.g. to SOA/microservice decomposition, to components in a redux event loop. Some cautions: as with any factorization scheme, granularity is important. The actor model makes it easy to think within actors, and hard to reason about interactions. Don't overfactor! Also, orienting around event streams means forgoing synchronous requests. This can lead to insane complexity where each actor awaits specific replies to act on remote state. When adopting a framework, never ignore the useful tools it leaves behind (like the way synchronous request interfaces imply a round trip handshake being handled by another layer).

Zalastax 8y ago

I find this resource confusing and annoying to read. When performing my thesis research I wasted a bunch of time trying to make sense of Hewitt's writing. I think a big problem is that the term "actor model" is so overloaded that it almost becomes meaningless. The actors that Hewitt is talking about is not at all the same as Erlang or Akka. As an example I consider this quote from the text nonsensical "Actor systems can perform computations that are impossible by Turing Machines" or of very little relevance to the actor models we use for programming. This has been discussed at [0]. For an overview of different actor models I prefer, see "43 years of actors: a taxonomy of actor models and their key properties" [1]. Agha's book [2] is also very good and I'd also like to recommend "Mixing Metaphors: Actors as Channels and Channels as Actors" [3]. [0]: http://lambda-the-ultimate.org/node/5208 http://lambda-the-ultimate.org/node/5208 [1]: http://soft.vub.ac.be/Publications/2016/vub-soft-tr-16-11.pdf http://soft.vub.ac.be/Publications/2016/vub-soft-tr-16-11.pd... [2]: https://dspace.mit.edu/handle/1721.1/6952 https://dspace.mit.edu/handle/1721.1/6952 [3]: https://arxiv.org/abs/1611.06276 https://arxiv.org/abs/1611.06276

PhilWright 8y ago
> "Actor systems can perform computations that are impossible by Turing Machines" As a turing machine can compute anything that is computable it is therefore impossible for an Actor to do any computation that is not possible by a turing machine. This is computer science 101 and makes me wonder about the value of anything else said in the paper.
- westoncb 8y ago
  Well the interesting thing would be if that old lesson were violated. Of course it's sealed forever for a specific definition of 'compute,' but I'm still open to the idea that we find something which resembles computation enough that we call it the same thing, yet its precise definition is different enough from the one used in connection with contemporary theory of computation that old proofs of universality won't necessarily apply to it. That said... it seems unlikely to me that the Actor model does something non-trivially beyond what Turing machines are capable of, since it would likely be better known, and we would see Chomsky's hierarchy expanded to hold another class, etc. (Unless it goes beyond Turing Machines by being non-linguistic in some way, which could certainly be interesting. Maybe dealing with non-sequential symbols or something?)
  - carlehewitt 8y ago
    Message passing was omitted from the Turing Model. (Two Turing Machines cannot send messages to each other.) Message passing is fundamental for IoT, etc.
- mindslight 8y ago
  > it is therefore impossible for an Actor to do any computation that is not possible by a turing machine It is impossible for Actors implemented on a Turing machine to do anything that a Turing machine cannot. But the Actor model itself is larger than a Turing machine - eg nondeterminism. Turing completeness is a lower bound on computation, not a maximum. For instance, a CPU with a hardware random number generator is a Turing machine, but a (basic/strict/pure) Turing machine cannot emulate a CPU with a hardware random number generator!

curuinor 8y ago

Hewitt is now kind of a crank. When Hofstadter came over for the Symsys thing in Stanford a few years back, Hewitt handed Hofstadter a little sheet of paper saying that mere contradiction allowed axiomatic systems to transcend Godel incompleteness theorems. Hofstadter: "Thanks, Carl." and then he threw it away when Hewitt wasn't looking. I think there's a thread in Lambda the Ultimate.

jchassoul 8y ago
and yet it moves
arglebarnacle 8y ago
You can see a flash of that in this article with "Actor systems can perform computations that are impossible by Turing Machines"
- jchassoul 8y ago
  The statement is true, Actor systems can handle uncertainty in ways that Turing Machines can not.
  - imode 8y ago
    Actor systems are no more able to handle uncertainty than Turing Machines are, either via nondeterministic TMs or by deterministic TMs. This is basic computability theory.
    - jchassoul 8y ago
      That is wrong, Actor systems have a property called "Unbounded nondeterminism" nondeterministic TM have only bounded nondeterminism. https://en.wikipedia.org/wiki/Unbounded_nondeterminism https://en.wikipedia.org/wiki/Unbounded_nondeterminism
      - carlehewitt 8y ago

jchassoul 8y ago

Hewitt work so relevant today, I found interesting that the Lisp Scheme was a failed attempt to implement this model of computation, ORGs, the scientific community metaphor, Planner, Inconsistency robustness, he even have a paper with David Marr from the same year of Actors "Video Ergo Scio" related today with the idea of inverse 3D graphics of capsules.

cokernel 8y ago

According to the abstract at https://arxiv.org/abs/1008.1459 https://arxiv.org/abs/1008.1459 , this document has been revised many times (the current version, from 2015, is v38). Is there a particular reason that v8 was the version selected for submission?

modells 8y ago

I prefer the rapper actor model astronaut form of compuation, but hey, CSP and STM are cool too. Sorry, couldn’t help it. And RDMA is, and always will be, pure evil.

threatofrain 8y ago

Carl Hewitt, Erik Meijer, Clemens Szyperski, talking about the actor model in 2012. https://www.youtube.com/watch?v=1zVdhDx7Tbs https://www.youtube.com/watch?v=1zVdhDx7Tbs

carlehewitt 8y ago

For a more recent description of the Actor Model and associated work, see the following: https://www.amazon.com/Inconsistency-Robustness-Studies-Logic-Hewitt/dp/1848901593 https://www.amazon.com/Inconsistency-Robustness-Studies-Logi... Also, those who will be in London on November 9 can come to my Code Mesh Keynote. See https://plus.google.com/+CarlHewitt-StandardIoT/posts/BXSZ7Y25b4p https://plus.google.com/+CarlHewitt-StandardIoT/posts/BXSZ7Y... It is fair to say that the implementation of Actors is still in its infancy. There is a startup in Silicon Valley that is attempting to remedy this situation. They are looking for expert programming language and run-time implementers ;-) Older publications are obsolete and unfortunately many of them have errors (including my own!). I wrote the Wikipedia article on the Actor Model but am no longer allowed to update it :-( Actors are very well defined up to a unique isomorphism by axioms. The reason that Actors can perform computations that Turing Machines cannot is that the Turing Machine model left out message passing.

krmboya 8y ago
> "Older publications are obsolete and unfortunately many of them have errors (including my own!). I wrote the Wikipedia article on the Actor Model but am no longer allowed to update it :-(" As someone who's been interested in the Actor Model recently, thanks for this statement, and the link to the book you've provided. This would help avoid going down the wrong path.
- carlehewitt 8y ago
  Thanks! Additional information that you might find helpful is here: https://plus.google.com/+CarlHewitt-StandardIoT https://plus.google.com/+CarlHewitt-StandardIoT

devxpy 8y ago

I created a library for multiprocessing, which is loosely based on actor model. The interesting bit is that you'll never have to do the wiring yourself, zproc does it all in the background. https://github.com/pycampers/zproc https://github.com/pycampers/zproc