General (not specific to LV/AF) Actor Theory

[Todd_Lesher]

This is 45 minute talk about actor theory. As someone not trained in CS who has been (slowly) working on understanding AF, I found it useful to be immersed in the terminology.

http://channel9.msdn.com/Shows/Going+Deep/Hewitt-Meijer-and-Szyperski-The-Actor-Model-everything-you...

[komorbela]

Thanks for sharing! Great material.

[Daklu]

Good link.  Thanks for posting it Todd.

Their discussion of actors is very abstract.  Not only is it not specific to LV, it's independent of any implementation.  It seems to me the vision they present cannot be fully realized without changing the cpu architecture and creating a new programming language.  That's not to say I think there's no value it what they talk about--on the contrary I think it's very useful.  But I believe any actor implementation using current technology is going to have to sacrifice some of the features in exchange for making other features available.

[AristosQueue (NI)]

Daklu: The functional language folks have been saying that for *years*. It is only with the advent of multicore and the end of Moore's Law on single core that anyone is willing to face that possibility.

[Daklu]

AristosQueue wrote:

Daklu: The functional language folks have been saying that for *years*. It is only with the advent of multicore and the end of Moore's Law on single core that anyone is willing to face that possibility.

I'm confused.  Do you mean to say functional language folks have been claiming for years a new cpu architecture is needed, but due to the industry investment in x86 processors and relatively low cost to increase performance nobody was willing to listen.  And only now that processor speed has peaked and performance increases require parallelism are people willing to entertain alternatives to the x86 architecture?  (If that's the case, I'm curious what reasons the functional language folks gave for needing a new cpu architecture besides better fitting their programming paradigm.)

[drjdpowell]

Daklu wrote:

But I believe any actor implementation using current technology is going to have to sacrifice some of the features in exchange for making other features available.

Hi Daklu, 

Could you elaborate on what features are lacking in current actor-focussed languages like Erlang or Scala/Akka?

[AristosQueue (NI)]

Daklu wrote:

And only now that processor speed has peaked and performance increases require parallelism are people willing to entertain alternatives to the x86 architecture?

Yes

Daklu wrote:

(If that's the case, I'm curious what reasons the functional language folks gave for needing a new cpu architecture besides better fitting their programming paradigm.)

I am not an expert in functional language compilation/execution, but here is my understanding of the problem: Functional language execution is not based on a stack. Nor is it based on a dataspace the way LV's dataflow is. Rather it achieves highest performance through graph reductions on a heap. The cache strcutres used by modern CPUs assume you optimize for local changes to the local thread space and write back to memory as rarely as possible. The functional languages want to share computations among many threads and want multiple threads to be able to share computations. Under the current architecture, that is only possible by full write backs to memory, as opposed to saying, "these N threads are all going to use this part of the cache and it doesn't matter which one works on that cache because each of them is going to calculate the result in exactly the same way, we just don't know ahead of itme which thread will need that part of the calculation first." It's a non-trivial problem for hardware design, but supposedly is theoretically possible.

The reason they need a new CPU arch is that functional languages are better languages than procedural for expressing parallelism, for validation and verification,  for extension without contradiciton and for artificial intelligence. To put it another way:

* Just like dataflow never has to worry about a computation on one wire affecting another wire (ignoring reference types), functional languages have the same safety mechanisms. Their type systems are often able to go far beyond what LabVIEW can do (in theory, LV's type system can be strengthened to do this too, but it would be a big change, requiring lots of research).

* Because of the way the languages are structured, they are very amenable to mathematical analysis and theorem proving. This means it is possible to do things like (true strories) prove absolutely that an operating system includes zero memory leaks or buffer overruns, prove the AMD floating point CPU unit does not have any errors across all of its cores, prove a graphics library has no bit planing errors. [All of these are true strories of the language ACL2 which is, to me, the most amazing of the functionals, but the others have their impressive tricks.]

* The highly structured nature of the language makes adding new language features much simpler as research advances about what languages need to be able to express.

* Our needs in artificial intelligence and robotics keep increasing, and these languages are consistently ahead of procedural languages because the languages can reflect upon themselves, recreate themselves as they execute, and alternately compile or interpret themselves fluidly.

[Daklu]

Could you elaborate on what features are lacking in current actor-focussed languages like Erlang or Scala/Akka?

Heh... not really.  I don't know understand Erlang or Scala (or the actor model presented in the video) well enough to answer your question directly.(^1)  The best I can do is explain the thought process that led to that belief.  I don't claim my belief is correct (which is why I used "belief") or my thought process is without flaws, but it is founded on reasons that make sense to me.

The actor model is an abstract concept--it's a different approach to breaking down problems and thinking about interactions.  It offers properties (I said "features" in the original post, but I think properties is a better word) that simplify the difficulties we encounter with concurrent programming.  The actor model separates the properties from the implementation.  It assumes an implementation exists that supports the properties, but does not specify what the implementation is.  As an abstract concept none of the properties are available to us.  Making them available requires an implementation.

At one point I noted two properties in the actor model that seem to defy implementation.(^2)  The first property is the ability to send messages to another actor directly with no intermediary.  There are no queues, pointers, etc. between the actor sending the message and the actor receiving the message.  However, Hewitt also said messages are sent to a "mailbox," which has a many-to-many relationship with the actors who ultimately receive the message.  (Many mailboxes may go to the same actor and a single mailbox may go to many actors.)  This seems to be inconsistent.  Isn't the mailbox an intermediary? 

During the video Hewitt made a comment along the lines of, "queues may be used in the implementation."  That implies the "no intermediary" property is intended to be a condition on the language syntax, not on the run-time execution.  Still, it seems to me that if that language syntax enforces direct actor-to-actor communication without an intermediary (i.e. no mailbox objects are explicitly defined) then there must be a 1:1 relationship between mailboxes and actors.  Setting up a 1:n or n:1 relationship requires recognition of an intermediary object within the language.

The second property is that sending a message entails the same overhead as a calling a function.  This property puts specific performance requirements on the implementation.  Current desktop cpus and operating systems are oriented more around multi-tasking (thread swapping) rather than concurrency (simultaneous execution.)  A function call within a thread is *much* cheaper than swapping threads, and to even get them close in terms over overhead/performance will require a single core for each actor and an extensive hardware messaging system.(^3)  Such processors with associated languages and compilers may exist in a skunkworks somewhere or for high end supercomputers, but to the best of my knowledge there is nothing like that available for mainstream users. 

I don't see how it is even possible to implement the actor model in a way that satisfies either one of these properties using current technologies, to say nothing of all the other properties I don't comprehend.  The logical basis for the comment you quoted can be summed up like this:

1. Making any actor properties available for use requires an implementation.

2. Current technology cannot support an implementation which supports all properties described by the actor model.

3. Therefore, some properties must be sacrificed to make other properties available.

-Dave

-------------

(^1) I understand Erlang and Scala to be (primarily) functional languages, not "actor focused" languages.  Functional programming and actor oriented programming both simplify concurrent programming but I haven't seen anything that suggests they are the same thing.  In fact, one of the properties of actors is they may retain state information.  Isn't that generally contrary to the functional programming paradigm?

(^2) I'm pretty sure the first property was described in the video.  I may have picked up the second property from one of the articles I read afterwards.

(^3) Or you could effectively make a function call more expensive.

[drjdpowell]

I don't think using queues is inconsistent with actors.  By intermediary, I think they may mean some central broker system (like ShaunR's "Dispatcher"). 

By the overhead of "sending", I think they may mean the overhead to the sending actor of enqueuing the message, not the total overhead of send, carry, and receive.  In fact, actors are supposed to work distributed over the Internet, so it can't be that they are required to have low-overhead communication.  Basically, I suspect they're distinguishing asynchronous message passing from various synchronous methods that other programmers may have used. 

[Daklu]

drjdpowell wrote:

I don't think using queues is inconsistent with actors.  By intermediary, I think they may mean some central broker system (like ShaunR's "Dispatcher"). 

By the overhead of "sending", I think they may mean the overhead to the sending actor of enqueuing the message, not the total overhead of send, carry, and receive.  In fact, actors are supposed to work distributed over the Internet, so it can't be that they are required to have low-overhead communication.  Basically, I suspect they're distinguishing asynchronous message passing from various synchronous methods that other programmers may have used.

I watched part of the video again and made the following observations:

~2:45 - Hewitt says in the actor model everything is an actor.  If an actor has a mailbox, and the mailbox is an actor, then the mailbox has a mailbox.  This doesn't make any sense, so actors don't have mailboxes, they have addresses.  (My use of the term "mailbox" previously was incorrect.)  The address is a fundamental property of an actor.  It is an inherent part of the actor construct, not a separate entity.  Oddly, the address to actor relationship still may be 1:1, 1:n, or n:1.

~9:00 - Clemens asks if "the address of an actor is equivalent to its identity."  In other words, does comparing two addresses tell you anything about the actors that receive the message?  The answer is no.  The *only* thing an actor knows about its external world is it can send a message to an address.  It cannot make any assumptions about the specific actor receiving the message.  It will not know the state of the receiving actor, which actor instance will handle the message, or even that the actor will receive the messages in the order they were sent.

Queues, as implemented in Labview, impose restrictions with a concrete implementation that simplifies certain programming tasks but do not (as near as I can tell) function as an adequate communication mechanism for the generalized actor model.  In Labview, a queue refnum is effectively equivalent to the identity of the concurrent processes that will receive the message.  That is specifically not true in the actor model Hewitt presents.  I presume this lack of identifying information is intended to help preserve concurrency and scalability by eliminating the ability to track state across actors.

(Hmm... this does make me wonder about implementing an actor where multiple instances all use the same receive queue...)

~14:50 - Erik uses the term "channels" to identify the communication mechanism between actors.  Hewitt immediately jumps on that and says, "This is very important.  No channels.  No overhead.  Talk directly."  It sounds to me like he is referring to the send, carry, and receive, though he may simply be referring the syntax of the language in which the actors are implemented.

~15:40 - Clemens says, "the channel would be another actor," to which Hewitt agrees.

~30:50 - Hewitt says, "The actors are in fact very abstract.  Any implementation that obeys the axioms is okay.  That's the achievement of abstraction, is where you can work at a higher level and don't have to be concerned with lower level things like locks, like queues in front of your actors, all these lower level implementation things."

-----------------

That's as far as I got tonight.  It really sounds to me like he is suggesting a language written specifically for actors rather than frameworks on top of existing languages.  In any case this is definitely something I'm putting in my mental composter to ferment.