Lambda the Ultimate

if .. is optimized to a jump or call that doesn't check the mailbox then if the first go gets there before the stop then the stop will never be processed

Of course, an implementation must adhere to the semantics of a programming language ;-)

It's the "hole" that causes some amount of fairness so the external messages can run.

Without the hole it would be allowed to ignore them forever.

Also since go messages run forever until there's a stop, and go's also check the hole for external messages, doesn't that imply that every external go could cause another go to wait forever on a go..

Unlimited external go calls are a memory leak.

hole that runs a message that loops forever is a memory leak!

There is no memory leak in SimpleCounter implementation.

Also, there is at most one go[] message in transit at a time.

to process a message that might never end. :/

Just pointing that out.

It doesn't look like a SERIOUS memory leak.

if you had something like

a_message = pop_hole
if a_message==nil then a_message='go

.. a_message

An implementation of the go[ ] message doesn't have to grow the stack.

to explain how that works.

I assume it works like JavsScript, so sending 'go' just queues the message. The same actor can only process one message at a time, so it cannot receive the 'go' until the current thread leaves the actor.

What does seem a bug however, is that if the actor receives a second 'go' from an external source, you would have two or more interleaved cycles, both incrementing the same counter.

There is oat most one go[ ] message at a time.

A counter does not receive any other go[ ] messages from outside because the counter is created using CreateUnbounded.[ ].

I would rather the behaviour was specified by the actor, rather than how it is constructed. What happens if you create without using CreateUnbounded.[]? How do you communicate to the developer they should use CreateUnbounded? If its in the documentation for the counter, it would be much better specified in the counter itself so you cannot create it the wrong way, or like in my C++ code it is clear a 'go' whilst it is already going is ignored from the implementation.

What happens if you create without using CreateUnbounded.[]? How do you communicate to the developer they should use CreateUnbounded? If its in the documentation for the counter, it would be much better specified in the counter itself so you cannot create it the wrong way, or like in my C++ code it is clear a 'go' whilst it is already going is ignored from the implementation.

I think you misunderstood. CreateUnbounded.[] is an (procedure) actor definition that is part of a demo program. There is no "external modifier" here.

The actor bound to "aCounter" is observably not shared by any other actors. One new counter is created for every call to CreatedUnbounded. The counter gets only (two) messages from CreateUnbounded, a "go" and a "stop". The order in which those messages arrive is unspecified.

The counter (may) also get "go" messages sent by itself, to itself. Such messages are sent only in the continuation of an earlier "go" message. Thus, it follows that there is always at most one "go" message and at most one "stop" message "in flight" to the counter actor.

Elsewhere you worried what would happen if there were two "go" messages in flight. Then, barring communication failures, until the receipt of a "stop", there will always be either 1 or 2 "go messages" in flight.

If you think that is a bug for your needs, you could write a slightly different version of Counter that would avoid that bug. Hint: if a counter is already "going", it could ignore incoming "go" messages.

It's bad practice to assume the counter will never be instantiated from anywhere else, and to not document the pre-conditions. And its bad language design to not have the pre-conditions specified programmatically in the interface of actors.

It's bad practice to assume the counter will never be instantiated from anywhere else, and to not document the pre-conditions. And its bad language design to not have the pre-conditions specified programmatically in the interface of actors.

OK, but your assertions have more to do with misunderstanding the example than anything else.

So are you claiming I cannot write a different function from CreateUnbound that uses aCounter incorrectly? I don't see the definition of aCounter is private in any way?

So are you claiming I cannot write a different function from CreateUnbound that uses aCounter incorrectly?

No, I'm saying you are ignoring the features the example is meant to illustrate while being argumentative about topics unrelated to the example or the post.

So you agree the timer is unsafe, and can go wrong if I call 'go' more than once. It's not a good example to show people as it handles the issues of asynchronous and parallel environments incorrectly.

Surely the better response is to fix the implementation?

It's not a good example to show people

I do not agree. It illustrates the concepts it was intended to illustrate without superfluous noise. That makes it a good example.

So you agree the timer is unsafe

No, I agree it does not do what you imagine a Counter actor should do in some other situation you are imagining in your head. I agree that you (personally) could probably jot down at least an approximate definition for an actor that does what you have in mind. I agree that you are picking strange arguments rather than just satisfying yourself by writing down that alternative definition.

Surely the better response is to fix the implementation?

I look forward to seeing your work.

What is with the defensive responses? Actors are supposed to make parallel programming safer and more accessible, yet posting examples with synchronisation problems seems counter productive. I think it makes people believe they are not actually very good at describing parallel algorithms.

Because you are being rude.

Sorry, I was not intending to be rude, and I am puzzled as to what I am saying that is being perceived as rude? All I can see is you not liking the direction the conversation is going, and trying to shut it down, as if any attempt to criticise the example is somehow being taken as a personal criticism.

Let's review the thread of Josh and Keean. I will give an overview.

 

+ It started with me asking a clarifying question of Hewitt.

++ Josh wants to know if compiling the code incorrectly 
   would cause it to malfunction.

+++ Hewitt cracks that implementations should be correct.

++++ Josh offers a confused, hence hard to follow "proof" 
     that SimpleCounter leaks memory.

+++++ Hewitt guesses Josh is worried about unbounded
      numbers of "go" messages in flight at one time
      and points out that isn't the case here.

+++++ Josh mistakenly argues (in the subject line) "..Go.[]"
      consumes memory

++++++ Josh self-replies with some confusion

++++++ Hewitt points out "..Go.[]" does not have to 
       consume memory

+++++++ Josh expresses a need for pseudocode

++++++++ Keean speculates wildly and wonders about "external
         messages"

+++++++++ Hewitt points out that scoping precludes "external 
          messages" here

++++++++++ Keean poses strange questions about using Counter in 
           unrelated programs.

+++++++++++ I mistakenly assume Keean has a minor, easily cleared 
            up confusion about scoping.

++++++++++++ Keean changes the topic to his vague assertions 
             about software engineering.

+++++++++++++ I point out these assertions mainly express 
              confusion as to what the topic is.

++++++++++++++ Keean puts words in my mouth ("So are you claiming 
               I cannot write a different function...incorrectly ...?")

+++++++++++++++ I point out I'm saying he is off topic and argumentive.

++++++++++++++++ Keean puts words in my mouth ("So you agree the timer
                 is unsafe...")

+++++++++++++++++ I more firmly point out Keean is being off-topic and 
                  argumentative.  I suggest how he can display good
                  will and get back on topic.

++++++++++++++++++ Keean asks the ultimate troll's question:
                   "why so defensive"?   He then goes on to insult Hewitt's
                   work without any indication he has made any effort
                   to understand any of it.

++++++++++++++++++++ I point out that Keean is rude.

The assuming-good-faith interpretation I could have given Josh and Keean is that they are concerned about the possibility of having an unbounded number of messages in flight -- but neither is able to express that concern in a clear and direct way.

Later, though, Keean made a reply to Hewitt that indicated he
can express that concern in a clear and direct way and does understand scope.

So, hmm.

So perhaps it was your assumption that I did not understand the scope and didn't have a useful point that started the journey to the dark side. You are then dismissive of my concerns, but when the exact problem is pointed out, try and deflect by claiming I am off-topic without saying that you disagree, or providing any evidence that I am actually wrong. When I call you out on this, you get defensive and claim it doesn't matter if the implementation has problems, its not the point of the example (when the point of the example is not exactly clear in the original post), and end up with some kind of snide remark about seeing my work. If anything you are being rude at that point, where I am at worst being a bit off topic.

Where you have claimed I am putting words in your mouth, I am simply trying to point out you managed to reply without addressing the question, by being dismissive, or having a meta argument about being off-topic, rather than addressing the actual technical issue.

Hewitt challenged the technical points in a completely reasonable way, and that branch of the conversation took a completely different route.

So perhaps it was your assumption that I did not understand the scope

I made no such assumption. I made that conclusion from what you addressed to Hewitt in this thread.

I realized I had been misled when I saw a later comment you made to Hewitt elsewhere.

I believe the term the kids use is that you are a "skilled ruseman" or something like that. Would you like some "Reddit gold"?

I am certainly not trying to mislead anyone, and I don't understand how you came to that conclusion.

I have described the problem as best I can, and have stuck to the same problem, trying to communicate what it is throughout. If you now understand from the conversation with Hewitt what I was getting at, I am sure if you re-read my posts you will see my position has been honest and consistent, with no attempt to mislead or otherwise do anything other than discuss a specific technical point that I think is relevant to the example given.

(Apologies to Keean for discussing mental state in the third person, as if you weren't right here.)

I believe the term the kids use is that you are a "skilled ruseman" or something like that.

I don't think he does it on purpose. My theory is his version of high IQ inserts subtle positioning effects without any conscious effort, as a background savant process. At first I was bothered a lot by the nuance of spin in discussions a while back, but Keean says enough interesting things to put up with it, in my book. I haven't noticed anything mean-spirited about the implied positioning.

(This paragraph is about one factor some folks experience as rudeness, myself included. Attribution of intent based on guessing, intuition, of inference is sometimes considered rude unless put as a politely phrased inquiry. To be told "your position is this" without that already having been said explicitly feels like being handled like baggage, and rubs a lot of people the wrong way. [Edit: I meant any time Keean infers a thing someone didn't say, and puts them on a position, the effect can feel rude as being handled.])

I haven't noticed anything mean-spirited about the implied positioning.

I have.

Attribution of intent based on guessing

Not based on guessing. Based on indifference to feedback about how he is being perceived. Actually, "indifference" is generous -- hence my perception of mean-spiritedness.

Finally, the patterns of communication Keean is using are very much those of the people who (by self-admission) troll comment-sections-of-good-will on purpose. I'm not kidding with the "ruseman" comparison.

What he is doing... the constant "move the goal-posts", the never getting a point, the self-contradictory "misunderstandings", the escalating rudeness and "Who me?" indifference to having given offence...

This is reddit-style chan4-style stuff.

If, as you say, it is an innocent mistake, then the remedy is for him, her or they to back off and figure out why it comes across that way.

That is your opinion, which you are obviously entitled to. I have been acting entirely in good faith, and any misunderstandings have been genuine, and i have not moved the goalposts once. My original point was about multiple messages to 'go' from elsewhere in the same program, and that is still my point.

On reflection it was probably a mistake to call you out on being defensive, after I found your post titled "No Keean, I do not agree" to be overly aggressive. Further my initial post about multiple messages to 'go' should probably have been a new top level message, as it did not follow from Josh's point, which I was helping explain to him.

If I make a point, and the response completely ignores that point and discusses something different, then is it not reasonable to assume the person agrees with the point, otherwise they would have noted their disagreement? The person has been given fair opportunity to respond.

This idea is so alien to me, I could not have imagined you held this view:

then is it not reasonable to assume the person agrees with the point, otherwise they would have noted their disagreement?

Oh no, because that obligates someone else to do work in proportion to the amount of effort you put into speaking. That alone puts it completely out of bounds, because you cannot proactively obligate someone without their explicit consent. (Their behavior obligates them, not yours, though sometimes because of things they initiate themselves.) When someone starts to talk to you, this is not assent to correct, ratify, deny, or adjust everything you say until consensus is reached. Minimally it obligates them to be civil and avoid insulting you.

In fact, the obligation not to insult you will guarantee some disagreements will not be voiced, because stated baldly, some opinions may be somewhat to very offensive. For example, I often find things people say are unclear, boring, banal, verbose, off-topic, drivel, meandering, simple-minded, confused, mistaken, misguided, irrelevant, deranged, manipulative, lies, smokescreens, attacks, backhand-insults, as well as several other things that most people don't want to hear said about their remarks. I skip things where my reaction is insulting, unless I find a constructive way to go about it, doing no harm. There's no way assuming silence means agreement will work.

In college, a journalism major asked me to read her paper and provide feedback. It was complete gibberish. At a glance I could see she would never work as a writer. But that's not a very constructive thing to say. I asked what she had intended to write about (because I couldn't tell at all), and asked questions, aiming to get her to itemize points she wished had ended up in the paper somehow. Most folks are nowhere near this unclear in writing, and yet everything has faults. For example, if I write something boring, I assume my words read as blah, blah, blah, going in one ear and out the other. So I assume folks skip paragraphs, not that they agree with me. Isn't that reasonable?

Indeed, so when I respond "so, are you saying ..." That should not be offensive. It is so inoffensive that it is a phrase used in education to help children understand how to ask for clarification. I don't think substituting claiming for saying makes it more offensive, its still a direct request for clarification
When the other party responds with "No, ...", do you think I am being unreasonable to conclude that they disagree with what I thought they were saying, and they actually think the opposite. When I attempt further clarification with "so, you agree", I get an overly aggressive response. Where has anything I have said been unreasonable or overly aggressive?

I generally find your writing intelligent, useful, and unoffensive. But sometimes your volleys get a lot of spin on them, what USofA players of pool and ping pong call "english" for reasons I never looked up. If you did it on purpose (which I don't think you do), it would feel like being baited by a lawyer who can't quell the urge to lace traps into conversation.

Since intent is hard to get across in writing, I expect a bit of rage now and then from folks who don't get your style. If you mute tone of pressing insistence a bit, and connect fewer things as riders (ideas depending on one another as inseparable propositions), fewer people would feel like you're pushing them off the high dive instead of letting them jump.

I only say this because it seems like you don't get why some folks get mad. Partly it's because you seem really competent, which makes nettles sting more, and because higher standards are unfairly imposed on folks who show skill. (E.g., the better one's accent, the more perfect one's speech is expected to be.) I don't want you to go away, or tell you what to do, but when someone seems upset you might want to press less and ask what went wrong. I hope my saying this helps make up for my interference above.

(Edit: see also Why is putting some spin on a ball described in some circles as giving it some “English”?. Sorry if my advice stinks, this is the best I could do. In summary, don't offer folks pre-written positions for them to sign and initial here, here and here; also don't imply they have already done so.)

I think you are giving misleading advice.

It's clear that Rys should stop defending you.

I am not sure what you are implying here? How is Rys being misleading.

How is Rys being misleading.

It's not who says it. It's what is said.

So two comments is excessive? Then I get an aggressive response, and the whole exchange is derailed, preventing any possibility of concluding the conversation.

When re-reading the conversation, I think Thomas gets aggressive, trying to put me off posting, rather than addressing my point, or simply saying its off-topic and I should start a new thread. If this was the aim, it was obviously counter-productive, as it has now generated a sub-thread unrelated to actors, and seemingly intent on analysing my conversation style in an unfair one sided way. It takes two to cause a disagreement, and I have posted where I think I may have been able to improve my communication already.

Being charitable, and with the benefit of hindsight, Thomas might have been trying to limit the side discussions to keep the thread readable, but if that's what he was trying to do, all he needed to do was say so.

In college, a journalism major asked me to read her paper and provide feedback. It was complete gibberish. At a glance I could see she would never work as a writer.

(emph added.)

Every good writer started like your college friend, writing complete gibberish. A hard part of how writers develop is when they start to get read enough to realize that. Good ones then figure out what to do about it.

bad signal.

bad connectivity on a train.

double post.

Would you mind changing those asterisks to something else, please? I'll find it inconvenient to read new posts in this thread if I get 19 false positives when I search for a space followed by three asterisks.

.

Thanks very much. :)

Since on some other topics you seemed out of practice:

Josh wants to know if compiling the code incorrectly would cause it to malfunction.

Not at all.

There is an issue here about whether it would be possible to make an efficient system that was "Actors all the way down".

I someone here once quoted Alan Kay saying that he originally considered making Smalltalk more Actor based than Object based but for some reason didn't do it. In one way an Actor based model would make a simpler system as every change to an Actor would be atomic and there's be no reason to worry about synchronization.

Well lets imagine such a system on current hardware.

The first issue is that communication between multiple processors required synchronization instructions to flush caches and/or prevent reading ahead speculatively and getting stale values. But those instruction are not only slow, but they occasionally cause contention that slows the other processors down.

Since the actor model, as I understand, doesn't guarantee that messages from multiple source arrive in any particular order relative to each other, there's a lot opportunity for optimization based on sacrificing some fairness, but a question arises whether it's ok to sacrifice ALL fairness.

Lets say that the system is a common SMP processor system. While I'm interested in what, say stream processors can do, I don't know enough about them to talk about them - though they are common too.

So say that you have 2 to 8 symmetric processors on a chip. In a system like that it would make sense to marry each actor to a processor at least temporarily. Then messages within a single processor ecosystem could be as fast as jumps or indirect jumps.

But what about checking the messages from other processors? To get there we need a memory model. I'd mention three:
1) the real hardware model of common intel processors
2) the real hardware model of common Arm processors.
3) the C++ memory model

#3 isn't that great because if you use it in a way that's close to optimal for #1 then you're far from optimal for #2 and vise versa, so even if you program to this abstract model you end having versions of it optimized for the underlying hardware.

Say we have three processor A, B and C and we specify writes by those processors A1 is the first write by processor A, A2 the second and so on. On intel machines all processors automatically see A1, A2, A3 in order even without any synchronization - but without synchronization there is not necessarily an agreement on the order between A1 and CN etc.

On Arm, processors B and C don't necessarily see writes A1, A2 in order, in fact they don't necessarily see the writes at all without synchronization instructions. On Arm both sides have to synchronize - flushing a cache isn't enough, the other side also has to disable read-ahead.

So while it would be safe and fast on intel for processor A to have a queues of messages to processor B and add messages with no sync instruction, on Arm you might want to batch messages - aggregate them, THEN make the aggregated batch of messages visible with a single synchronized write.

Also, under intel, it would be safe (if you don't mind missing messages for a while) to check for them with no synchroniztion, with Arm you might want to wait - process local messages for a while first, then synchronize to prevent reading stale values and check for a new batch.

But even under intel, it might, under high contention, be faster to aggregate reads a bit - reading from memory that's dirty in another processor's cache stops the bus and makes every processor wait while memory gets shipped around. Also local sends are just faster.

So the question of turning local message sends into mere jumps and of reading queues late isn't pointless, it's posing the question "how do we optimize actor systems" and "how far can we go?"

Also it didn't occur to me until later that "go" will be sent only once. But if it's sent only once, maybe it shouldn't be a message, maybe it should be in a constructor.

There is an issue here about whether it would be possible to make an efficient system that was "Actors all the way down".

No, that is some off topic bs you brought up AND, more to the point, it has no relation to your original troll in which you literally asked if a mis-compiled actor would function incorrectly.

while you go aggressive on people as soon as they show some interest in implementing actors.

If this really was like other spots on the internet, I'd go personal now. I'm on topic and you're acting like a hurt child.

of implemention.

Obviously that person won't be Lord Lord.

Obviously that person won't be Lord Lord.

I rest my case.

go do something you actually like.

I brought up actual issues.

Mockery is pretty uncool, and working someone's name into a taunt seems formal insult. You wouldn't really do that in person, would you? Even more important, you don't want to sound the age of kids who mock each other's names. Beware of saying things that make folks avoid you in work situations, because they fear when you would stoop to childish tactics.

Fight intelligently if you must, since it's okay if folks don't always get along. But I find emotion always burns afterward, and it's never worth it, no matter how much fun it was to say at the moment. If you lose five minutes sleep reliving it later, you lose, even if you don't worry about folks avoiding you.

I like Thomas Lord's writing a lot, so I wish you wouldn't piss him off enough to stop posting. At least be as polite as you would to someone seated near you.

Is it ok to ignore one message forever, as long as there are other messages to the same actor?

If that's a bad idea, how about aggregating from specific sources, say messages from a specific source may wait for a significant number of message cycles before attention turns to them out of fairness.

A response must be received for a request message or the infrastructure will throw an exception.

It is private by definition, I think, with actors.

The spec/declaration of an actor gives a constructor function. That's the only way to make that type of actor. Once you get that actor, everything inside is encapsulated like an object. Like a "good" object, it can only be frobbed via messages. Like a "synchronized" object, only one message can be run at a time, and is run-to-completion. IIUC.

So you can't get at the counter.

You can call go from multiple places and make it go wrong.

In its implementation, each CreateUnbounded.[ ] creates its own counter to which no one else can send a message.

However I can replace CreateUnbounded with a different actor. Say I want to use the counter for something else. I don't want to rewrite the counter from scratch, so O find the existing definition and then implement my own Actor creating a SimpleCounter and sending the 'go' message to the counter interface several times.

You cannot "replace" CreateUnbounded with a different Actor; nor can you "replace" CreateUnbounded.[ ] with a different Actor.

I am not talking about replacing the actor at runtime, I mean changing the source code of the program. Programs rarely get written and remain unchanged. People modify them over time, and re-use components. For example, I want to use SimpleCounter somewhere else in the same program:

CreateUnbounded2.[ ]:Integer ≡
  Let aCounter ←  SimpleCounter.[ ]｡    // let aCounter be a new Counter
    Prep □aCounter.go[ ]｡  // send aCounter a go message and concurrently
    Prep □aCounter.go[ ]｡
      □aCounter.stop[ ]▮ // return the result of sending aCounter a stop message

It would be better to implement SimpleCounter so the second 'go' gets ignored, rather than triggering a pathological behaviour. If not, there should be some way of indicating in the type of the go message in the interface that it can only be triggered once, so that the compiler could flag the double send as an error statically.

You may not be able change the source code of another party even if you know what the code used to be.

However, you can always write you own code ;-)

Where I work, code is very rarely written by a single person. Projects get worked on by teams, sharing their code in version control repositories, and we try and maximise code reuse.

It is clearly better to express the preconditions for messages in the target not the source? Do you have a reason to not do that?

How can the implementation of CreateUnbounded.[ ] be improved?

I am not sure how to fix simple counter. Can you have a privileged message that only can only be sent to from certain actors (say itself)?

You need the ability to separate the 'go' message, from a separate 'inc' message that increments the counter. The 'inc' message needs to be 'private' so it can only be sent from SimpleCounter itself. Is this possible?

If the type Counter is not provided to others; they cannot create counters, nor can they send them messages.

I think a potential solution is to have an inner counter that provides 'go', and 'stop' in the same way as SimpleCounter, and then another actor that only forwards the 'go' message to SimpleCounter if the counter is not running, by keeping the state in a Boolean flag. I might have a go at writing it later. You then need some way of hiding the inner counter definition, so that the only thing that can ever forward messages to it is the outer counter.

It doesn't matter to CreateUnbounded.[ ] if others create counters.

Duplicate.

There is no bug in the implementation of CreateUnbounded.[ ]

True, there is no bug in CreateUnbounded.[], there is however an unsafe assumption in the implementation of aCounter.

There is no unsafe assumption in the implementation of CreateUnbounded.[ ]

In the cheese, a message can be sent to self only in the continuation. However, it is important to watch out for deadlock (which will result in the infrastructure throwing an exception).

Also, message passing in Actors does not involve "phases".

I would say that the handling of a message is divided into "phases", by definition, if parts of the message handling obvservably, causally precede other parts.

If "<<" indicates observable causal ordering, isn't it the case that:

prep << hole << afterward?

"Phases" may not be the best terminology for causality.

As you have indicated, there are causal orderings among activities in the implementation of SimpleCounter that are governed by the Actor Model.

Understandability is key to programming languages. Also, a programming language has to play well with IDEs.

Suggestions for improvement of ActorScript are greatly appreciated.

An Actor implementation can use whatever hardware is available.

The implementation at the beginning of this post is not an inherently inefficient implementation of the interface Counter.

The interface is fine, and I have tried to copy the semantics in the C++ code. I assume go spawning another message loop is a bug, so I ignore go if its already going, and ignore stop if its already stopped. It's basically like a classic stop-watch behaviour, just needs a reset.

Why does the Counter interface need to add a reset[ ] message?

Currently the Counter interface is as follows:

Interface Counter with
     stop[ ] ↦ Integer,
     go[] ↦ Void▮

It's better to reuse an actor, possibly from a pool of pre-constructed actors, than create and destroy them. Further it models a physical stop-watch. You could say sending stop when already stopped resets it, but I think a separate reset is clearer.

It's better to reuse an actor, possibly from a pool of pre-constructed actors, than create and destroy them.

That is isomorphic to "The Myth of the Expensive Procedure Call" that made the Rabbit thesis famous.

Object creation cost us real, and has caused performance problems in real world applications. If you don't pay attention to these things, the cumulative cost soon adds up, especially on an FPGA implementation where instantiation may require re-layout of the whole program, or communication issues on extremely parallel machines (where allocation thrashing may result in overly long routes between nodes).

Object creation cost

Did you post this in the wrong topic?

I don't know how you plan on implementing an actor with internal state that has identity, but such a thing is like an object with added thread control. The actor has to have a heap allocated data store, because its life is not stack controlled. The new actor when instantiated has to have the data store initialised. Finally it must be able to receive messages, and these messages interpreted according to the instance (IE there is no guarantee that all counter objects implement the interface in the same way). This is equivalent to a C++ object with virtual methods and an abstract base class. Finally mutex locks are needed to prevent more than one message being in the actor at any one time. The C++ code I posted is pretty much the implementation of this actor, except it uses function call semantics for calling the methods rather than message passing, but thats an optimisation when running on a shared memory computer. You only need to send real messages on a shared disk or shared nothing computer.

How to compile actors is a big and interesting question. I suspect that a reasonable set of transportations would compile CreateUnbounded to a loop like this pseudo-assembly code.
Note that this is a loop that could run entirely in registers.

CreateUnbounded:

  count ← 0
  jump_random Go, Stop

Go: 

  count ← 1 + count
  jump_random Go, Stop


Stop:

  return count

I don't know how you plan on implementing an actor with internal state that has identity, but such a thing is like an object with added thread control. The actor has to have a heap allocated data store, because its life is not stack controlled. The new actor when instantiated has to have the data store initialised. Finally it must be able to receive messages, and these messages interpreted according to the instance (IE there is no guarantee that all timer objects implement the interface in the same way). This is equivalent to a C++ object with virtual methods and an abstract base class. Finally mutex locks are needed to prevent more than one message being in the actor at any one time. The C++ code I posted is pretty much the implementation of this actor, except it uses function call semantics for calling the methods rather than message passing, but thats an optimisation when running on a shared memory computer. You only need to send real messages on a shared disk or shared nothing computer.

Thats not really low level enough to see how a compiler would have to implement it. It looks like you are implementing in a language that has closures and garbage collection. You don't really want to implement on top of that. I think you should be looking at something like 'C--' or LLVM as a target.

Thats not really low level enough to see how a compiler would have to implement it. It looks like you are implementing in a language that has closures and garbage collection.

Where do you see closures or garbage collection there?

I misunderstood, and I don't think there are closures and GC, but you don't provide a way for other messages to be processed (due to the hole). I had assumed this was a closure and a co-routine, so that it has the same semantics as the original actors.

Edit: the semantics don't seem very clear so I made some assumptions that you say are wrong. On re-reading I can see an interpretation of the semantics where closures and GC are unnecessary, sort-of, but its not clear what return is doing there if go and stop are not alternative function entry points.

I misunderstood,

I'm not playin'.

It is not clear where count would be stored. It looks to me as there are no function call semantics that it cannot be register or stack allocated (as other parts of the program may call go and stop). Also mutexes to prevent multiple threads entering go and stop at the same time are missing. Count is private, and you want to read the tick counter to save power by not keeping the CPU busy all the time, you would seem to end up with something like the C++ implementation I posted.

That does not appear to be a faithful implementation of the CreateUnbounded actor according to many previous claims of the Actor semantics. Not every trace of that program will terminate unless there is some hidden fairness constraint on jump_random.

Personally I would like to see an implementation of any actor event loop that includes the guaranteed processing of message eventually. Of course I would like to see it written in anything other than actors in order to demonstrate that the semantic guarante can be bootstrapped from a constructable / executable code.

I would like to see an implementation of any actor event loop that includes the guaranteed processing of message eventually.

Personally I would like to see an implementation of any actor event loop that includes the guaranteed processing of message eventually. Of course I would like to see it written in anything other than actors in order to demonstrate that the semantic guarante can be bootstrapped from a constructable / executable code.

It seems a fairly straightforward consequence of the finiteness (in physical space) of any such system that there is no such implementation. It's just a convenient fiction. To "implement" an actor system, you'd need to interpret eventual delivery as delivery with probability one.

Edit: Well, "finiteness" is a bad explanation. Suppose there is a physical machine that produces integers. Call a machine state "open" if set of integers producable from that state is still unbounded. The claim is that if the machine starts in an open state, then there is path for the machine that stays in the open state forever. Trying to enforce a machine to stay in the open state for arbitrary but only finite time would require something global and non-physical. ... Maybe still not the best explanation, but at least that's kind of my intuition.

Some fictions would be tolerable as they only slow down the speed of the execution. For example: a TM implemented on a finite length tape, when it seeks past the edge a new larger machine is built and the state is copied into a prefix of the larger tape. Execution then continues.
In a similar vein: a RAM machine with 2^n n-bit cells. When full, copy the state to a 2^(n+1) (n+1)-bit cells using zero-extension on each word.

In either case we know that the execution speed would decrease and eventually some physical resource limit would be reached. But in principle the finiteness of the implementation is not an issue. Hewitt has made comments along these line before that seem reasonable. But even allowing such "reasonable" fictions it is not clear how to implement guaranteed eventual delivery. I would like to see the claim that such a thing is possible to be backed by some form of evidence.

Sorry, the quality of my previous post was low. Let me try again.

But even allowing such "reasonable" fictions it is not clear how to implement guaranteed eventual delivery.

I was arguing that it is impossible to implement guaranteed eventual delivery in a strict sense. Basically, non-deterministic Turing machines offer a pretty good model of what we can physically implement (this is unprovable like the Church thesis, so you'll have to convince yourself). And, as Hewitt likes to point out, if a non-deterministic Turing machine can produce an arbitrarily large integer, then it can also diverge. The problem is that non-deterministic Turing machines can only branch finitely. If there is a non-deterministic path through those finite branches of arbitrary depth, then in the limit it becomes a non-deterministic path of infinite depth. Q.E.D.

So in a strict sense, I believe that a machine that eventually delivers an unbounded natural number cannot be constructed. But what we can do is build a machine that delivers an unbounded natural with probability one (subject to the same qualifiers about resource exhaustion that you explained). What we can then do is interpret any statement Hewitt makes about the existence of an eventual natural number machine as actually meaning "implemented as a Turing machine that terminates with probability one".

The reason this can be a useful fiction is that at this level of abstraction, there are only three interesting probability classes: zero, one, and other. Reasoning directly about probabilities is a pain. And in practice, there is no distinction between a machine that terminates with probability one and one that eventually terminates. If I gave you both as block boxes, how would you tell them apart? You'd first have to wait forever.

And in practice, there is no distinction between a machine that terminates with probability one and one that eventually terminates. If I gave you both as block boxes, how would you tell them apart? You'd first have to wait forever.

Would eventual termination with probability one be good enough for a proof-checking algorithm? I don't see a reason people wouldn't be investigating the potential of a "yes" answer already, but I wonder what research is out there.

If the answer is in doubt, or if the answer is "no," then it's necessary for proof-checking to stick to computations that eventually terminate, not just computations that terminate with probability one.

Congratulations. You're one step off of defining the notions of weak and strong fairness.

Hewitt leaves these notion underspecified; it doesn't make much sense discussing them.

Every message sent eventually receives a reply or an exception.

An exception may leave the sender in the dark as to whether or not the send failed, and in the dark as to whether or not a proper reply was ever sent.

The semantics sound exotic when abstracted to a bare essence, but they are completely familiar from messy, real-world communications.

Or, the Actor dies before either happens.

the spanish inquisition

Or, the Actor dies before either happens.

Which would reliably produce exceptions with actors that correspond with the dead parrot (other than in plague situations).

Not every trace of that program will terminate unless there is some hidden fairness constraint on jump_random.

Yes, I expected readers to assume that jump_random will eventually take both branches if the instruction is repeatedly executed.

The probability distribution of values returned by CreateUnbounded is not determined by the source code. It is an emergent effect of the "communication medium". If "jump_random" happens to be a fair coin flip, the probability of returning N will be 1/(2^(N+1)).

Personally I would like to see an implementation of any actor event loop that includes the guaranteed processing of message eventually.

Your web browser has one that satisfies the semantic requirements: message sends (requests sent by the browser) time out if a reply is not received quickly enough. In ActorScript, that timeout would appear as an exception.

Of course, if all of your actors are running on one machine and you aren't faced with the possibility of message or reply drops, ordinary schedulers will do the trick.

Of course I would like to see it written in anything other than actors in order to demonstrate that the semantic guarante can be bootstrapped from a constructable / executable code.

I'd like to see that, too, although I have no problem if the low levels are written in "trivial actors" -- a restricted dialect of ActorScript that trivially compiles to some very low level target language.

Or possibly an old topic - there is no way to be sure given the options for navigation in the previous actor topics. Why would this be difficult to implement?

In particular, if I squint a little at the SimpleCounter then I see a FSM with access to an RNG, a timer, and a message queue. There is constantly the claim that the actor semantics for message handling is different / more than that (i.e. from memory I think that Hewitt has explicitly stated there is no queue many times).

If I wanted to examine the semantics of the message passing and execution flow within an actor - that is erase all value computations and look only at an abstract model of concurrency and communication - then I would sketch out the following as a starting point:

Each actor is a set of message handlers and a set of incoming messages.
To send a message is an asynchronous operation - add the message to the target set.
To start a computation is a synchronous operation - fire the asynchronous message and start a timer.
The execution is as follows:

• Either:
  • Observe that a timer has expired and propagate a failure.

  • Pick a random message from the set and process it.
    • If the message handler returns a value then fire it back as an asynchronous message.

From this starting point I would then ask:

• Is this an accurate description - are these true statements about how the system behaves, and where they are not how does the system differ in behaviour?

• Is this a complete description - where are the holes in this description that allow a diverge from the behaviour of actors?

If this is an interesting line of discussion then I am quite happy to copy this into a top-level post in order to continue as it is wandering quite far from the topic of prep.

Andrew,

Please start a new topic.

Unfortunately, your description has a few bugs :-(

Thanks!
Carl

The topic of the topic would be to (hopefully without trolling and flamewars) settle questions about actor semantics.

Detailed information about how to efficiently implement Actor Systems can be found at the following links:

Actor Model of Computation

ActorScript

I quickly read through those papers and I couldn't really see much that would help actually implementing actors. There was no pseudo-code or 'C' code showing the implementation of construction, message-passing or destruction.

Admittedly the articles are written for experts.

However, there are probably some corner cases that are left open.

It would useful to find some ;-)

I don't quite know what to make of that response. Are you implying because I don't see how the articles describe the implementation, that I am somehow not an expert? I am sure that can't be what you are saying because that seems somewhat presumptuous.

We can reasonably abstract register allocation from compiling to machine code, buy targeting 'C'. Taking the counter actor as an example, what transformations are required to convert this into 'C' code. This is what you need to define in order to have a detailed explanation of implementation.

For example for functional languages the basic operation necessary to compile them is closure conversion.

The C++ code I gave for the counter is what I think it could compile into. If I am wrong and there is a better implementation, could you post the 'C' code that you would expect a compiler to produce from the counter example.

C code is not very suitable for implementing Actors.

The X86 or ARM from ART would be fairly verbose :-(

How else are you going to implement actors on existing computers? I really would not want to start generating platform specific assembler, targeting 'C' is a much more portable way to build a language.

C is effectively portable assembler in any case, so saying 'C' is not suitable is like saying a modern computer is not very suitable for implementing actors.

C need not be part of the tool chain for implementing Actors.

For example, C is not part of the ART tool chain.

I would suggest that if you cannot write an efficient 'C' target for actors, then they are not going to be efficient on a modern CPU, as CPUs are pretty much designed to run 'C' code as fast as possible.

Besides, even if you don't intend 'C' to be part of the toolchain it is a widely understood language that is effectively portable assembly language, and compiling to 'C' as a target should be a lot easier than generating x86 machine code.

ART can generate X86 and ARM code requiring any need for C.

Isn't that generating a lot of unnecessary work? Is the ART register allocator as good as LLVM? Is the optimiser as good as LLVM? It's also a lot of ongoing work too keep up with the improvements being made an GCC and LLVM. Further its a huge amount of work to support all the architectures that they support, and to continue to update instruction schedulers for new versions of x86 and ARM that require different optimisations. Outputting to LLVM intermediate code, or even just 'C' code seems a much better idea.

What assembly opcodes do you use that you think cannot be efficiently implemented in 'C'?

Where can in download ART or get the documentation etc?

Both have low level memory models for multiprocessing and threads and mutexes etc.

So they're now complete enough to use as a low level target for concurrent systems.

C++ could be a higher level target, depending on how much pain you can stand and how much time you can devote to it.

I first assumed prep meant construction in object lingo: an init step to establish starting invariants. But so far I don't get the whole subtext about phases in actor messages.

I liked that Hewitt tried to do something different, but it would be better with more establishing context, perhaps via a small story setting up why a question makes sense with respect to motivation offered. (You don't need to make the story goofy like I would, about a developer named Dex and the three angry bears, for example.)

The sub-thread about synchronization would be better if the basic actor model involved was explained. I generally assume actors use a monitor model, implying mutex while an actor is running messages it sends itself in response to other messages. There isn't any good way to talk about concurrency without a model of when context switch can occur.

ActorScript does not use monitors.

To see the difference, see the Wikipedia example here.

In particular, ActorScript does not use condition variables (which can be inefficient).

What does the actor script implementation use to synchronise multiple threads to prevent more than one message at a time? Even if the language does not have these concepts, there are limited ways to implement this on a modern multi-core super-scalar out-of-order processor.

"..MSG.[ARGS]" is the Actor version of a self-tail-call.

When a message is a received, an Actor gets a continuation. Calling that continuation sends a reply.

Instead of calling that continuation directly, an actor *may* pass the continuation in a "tail-message" (analogous to a tail-call).

The Counter busy-loop "Go" is tail-forwarding a continuation of return type Void.

Semantically (though compilers can be clever here), "invoking the continuation" (or forwarding the continuation in some other tail-sent message) sends an asynchronous, one-way message.

Therefore, (semantically), an actor's message handler can "keep running" even after supposedly sending the reply. "Afterward" sections let the actor further update its internal state before it gets another message, but after sending a reply.

There's a trick there, though:

Actor semantics do not seem to make it observable whether or not the afterward section is *literally* executed before or after asynchronously transmitting the reply (or forwarding the reply continuation).

In that sense, prep, hole, and afterward appear to be higher-level syntactic sugar, pretty easily eliminated by a compiler.

"Afterward" assignments affect the next message received.

Isn't that what I said? :-)

No, you're not the only one. I almost posted the same "what is prep?" question myself. But then I realized that I wasn't even sure exactly what the point of the original post was. On the one hand, "prep" seems to have an obvious interpretation in terms of the "phases" Tom mentioned (in which case I'm not sure what there is to discuss). On the other hand, the ActorScript paper has very little to say about "prep". It doesn't (or at least didn't the last time I looked) appear to show up as a syntactic keyword. There's a vague mention of "preparation" maybe halfway through the paper, and some other possibly prep-related stuff in the metacircular definition. But that's about all I could find. Which left me thinking that it was a fairly obscure part of the Actor model, and unclear about the motivation for this post.

"Prep" is a new construct that seems generally useful in programming languages because preparation is a common idiom.

Perhaps it would help if you explained what "prep" is supposed to mean. It's unclear to me from the ActorScript paper, and the inference from the example you posted is that it represents part of a "phase-like" scheme of the sort that Tom described. Which makes it seem like simply a coarse-grained definition of sequential execution (prep actions, followed by hole actions, followed by afterwards actions). Is there more to it than that?

"Prep" (like "Let") is very simple.

The semantics is do the preparation and return something.

But there are some subtleties in that preparation is potentially allowed to overlap execution of returning.

Let me try it this way: in what way is the execution (either observable behavior, or internal implementation steps) different for your example unbounded integer with and without "prep"? Would the program work without "prep"? Would it work differently? I note that the equivalent example in the ActorScript paper doesn't use "prep", and instead increments count "afterward". Would that be observably different? Or simply different in implementation?

Let's say for a moment that "prep" is just syntax sugar ..but sugar for *what*?

One possible way to "intuit" an actor is

An actor is a kind of closure. It is closed over the state variables of the actor. It's a closure with (possibly) multiple entry points. It's not a simple "lambda". Each kind of message an actor can receive is some entry point to this closure.

The continuations passed to this closure are a generalization of the continuations in a language like Scheme. In particular, passing an argument to an Actor continuation transmits a reply, an asychronous act.

Conversely, the multiple entry points to an actor are a generalization of function calls in a language like Scheme. In particular the receipt of a message invokes an entry point in an Actor.

The body of an entry point updates bindings in the actor, and either (a) passes arguments to the continuation, or (b) tail-sends the continuation to some actor, counting on the actor that gets that message to later transmit a reply. Option (b) is a generalization of tail calls.

The body of an actor performs only message sends, reply-or-exception receipts, assignments, conditional branches, random branches, and finally either a tail-send or a direct reply. Notice: no loops in that body unless in the form of a tail-send to self ("..MSG.[ARGS]").

An isolated actor is not turing complete, except for in its ability to create additional actors and communicate with them. In fact, an isolated actor (that does not create and communicate with additonal actors) is a regular automaton and nothing more.

In any event, strange-unicode-character sequencing operators, "prep" and "afterwards" are all just syntax for describing what Hewitt believes (rightly I think) are "popular" patterns for how the body of an actor method is usefully structured.

"Prep" lays out initial side effects and computes either an argument to pass to the continuation, or an actor to whom to forward the continuation. "Afterwards" lays out additional modifications to bindings and additional message sends that should also happen before the next message is processed by *this* actor.

Thanks Tom.

I'm trying to reconcile this with the assertion that "prep" is "generally useful in programming languages", when it sounds like (a) something that is applicable only to Actors and the way they execute, and (b) essentially just coarse-grained enforcement of a sequence of execution steps within an execution model that is otherwise concurrent (not unlike creating a SEQ of PAR blocks in occam, or using a monad to sequence actions and side effects in Haskell). Is it something more than that? If so, can you elaborate on what that is?

Also, why restrict yourself to just "prep" and "afterwards", instead of allowing a more general sequence of actions?

Edit: Which perhaps gets us back to the point of this post. Is "prep" a neglected topic in programming languages simply because it doesn't matter for most of them?

"generally useful in programming languages",

The concept is applicable to any language with something akin to a "basic block". The proposition is that this notation can help clarity by letting us specify what-continuation-to-invoke from the *middle* of a sequence of updates all of which are performed by the block. (A special case. In some C code I wind up declaring a variable named "answer". Setting the variable in the middle of the function. Then doing other side effects. Then returning "answer". This is such a common pattern. Maybe it deserves a concept memorialized in syntax.)

There's probably some analogous prior art in some niche part of lisp-machine dialect lisp macros.

Does the Prep'd statement happen before the hole, after the hole, or before the tail call? What would be wrong with:

hole
count = count + 1
..go[]

Other languages use yield instead of hole to indicate other messages be given a chance to be processed.

(A special case. In some C code I wind up declaring a variable named "answer". Setting the variable in the middle of the function. Then doing other side effects. Then returning "answer". This is such a common pattern. Maybe it deserves a concept memorialized in syntax.)

There's probably some analogous prior art in some niche part of lisp-machine dialect lisp macros.

I know that pattern from Arc as do1. The Common Lisp standard calls it prog1. R6RS Scheme calls it begin0. I can't say I know the history.

My second book on lisp was a famous one (I forget what it's called) that in that edition was on interlisp or was it MacLisp not Common Lisp like the later editions.

Well, I guess I can see some minor value in syntactically marking something that should happen "before" everything else (something like a "finally" block, but at the other end of the execution), although I have to admit that I'm not sure what it really buys you.

And yet looking at the examples in the ActorScript paper (including the metacircular definition of "hole"), "prep" seems to be used primarily to enforce sequential execution of statements that would otherwise be concurrent (in other words, something applicable to Actors, but not to languages that already have a notion of sequential execution). Indeed, the only real discussion of "prep" in the paper says

Concurrency can be controlled using preparation that is expressed in a continuation using preparatory expressions, “⚫” and an expression that proceeds only after the preparations have been completed.

which sure makes it sound like a mechanism for creating a sequential execution (the metacircular definition doesn't seem to include a definition for “⚫” except in the context of "Enqueue", so it's hard to know exactly what it means). Of course, the paper doesn't include the "prep" keyword. Then again, it does include several examples (including the definitions of "after" and "afterwards") in which there is a sequence of statements each separated by “⚫”. In those examples it seems less like "prep" would aid clarity, and more like the "prep" keyword would just be undesirable syntactic noise to what would otherwise just be a sequence of statements.

Aside: While I appreciate your attempts to enlighten me here, it seems unfortunate that none of what you're explaining was mentioned in the original post. As a result, everyone was left guessing about what "prep" meant, and what Hewitt's intention in posting about it was. To be honest, I'm still kind of in the dark about the latter.

Hewitt seems to be trying to get us to read the fine manual, and mostly failing.

I keep saying that I'll read it eventually.

Sure. As I said (back there):

The proposition is that this notation can help clarity by letting us specify what-continuation-to-invoke from the *middle* of a sequence of updates all of which are performed by the block.

(emphasis added).

The comparison to prog1, especially in a pattern like

  (prog prep (prog1 hole afterward))

seems pretty apt except that (as you observe) the actor version is a generalization since the hole can describe a tail-send while the lisp version of prog1 is strict in the value to be computed by the hole.

(h/t Ross Angle for the prog1 observation.)

One thing I'd like to see explored more is the way Actors are a kind of "tinker-toy" (or other construction set) approach to building complex transactions out of simpler transactions by composition.

I'm not sure really where to go with that, but there it is. :-)

Prep does not necessarily involve Actor construction.

For example, neither of the uses of Prep in the program in the posting that begins this topic involves Actor construction.

Yeah I got it wrong, it constructs the counter, but that's not what it returns.

It's a function with odd syntax.

But I would guess that the integer is "the actor being created" which is why waiting on that message is in "Prep" so that the integer actor won't be considered ready, or return its address to what created it till it gets the value back from the counter.

□ (a box?)
｡ (a circle)
▮ (a tall black box?)
are symbols I don't know

There is an explanation of the Unicode symbols here.

running Chrome.

All of the characters work for me on a PC using Firefox.