Erlang-style concurrency
David B. Benson
What is meant by "Erlang-style concurrency"?
Vesa Karvonen
> The "Beginning with ML" thread is now too long to follow.
> What is meant by "Erlang-style concurrency"?
Actor style, conventional, asynchronous message passing?
Not to be take too seriously (I'm considering moving it under "toys"
rather than "tech" (for programming techniques)), but, for fun, I
wrote a mini "CerMLang" library using CML that allows one to
transliterate Erlang code to SML/CML:
http://mlton.org/cgi-bin/viewsvn.cgi/mltonlib/trunk/org/mlton/vesak/tech/cermlang/
I haven't yet written a README file (or even comments) there, but, for
the record, the goal of my exercise was to see how close one could get
to Erlang (to allow one to effectively transliterate examples). If I
was writing a serious library for "Erlang-style concurrency", I would
likely make a number of different design choices for pragmatic
reasons.
-Vesa Karvonen
David B. Benson
wrote: ...
> Actor style, conventional, asynchronous message passing?
Thank you. I haven't read enough of Joe Armstrong's book (yet)
to see this. I prefer synchronous message passing from which
asynchrous is easy to program when it is desired.
Neelakantan Krishnaswami
Vesa Karvonen <vesa.k...@cs.helsinki.fi> wrote:
> David B. Benson <dbe...@eecs.wsu.edu> wrote:
>> The "Beginning with ML" thread is now too long to follow.
>
>> What is meant by "Erlang-style concurrency"?
>
> Actor style, conventional, asynchronous message passing?
To this, I would add "...with no shared state between processes."
This liberates the implementation in important ways, like making
parallel GC easy to scale rather than extremely difficult.
> Not to be take too seriously (I'm considering moving it under "toys"
> rather than "tech" (for programming techniques)), but, for fun, I
> wrote a mini "CerMLang" library using CML that allows one to
> transliterate Erlang code to SML/CML:
>
> http://mlton.org/cgi-bin/viewsvn.cgi/mltonlib/trunk/org/mlton/vesak/tech/cermlang/
Cool! I had been thinking of doing the same thing. Now I don't
have to. :)
--
Neel R. Krishnaswami
ne...@cs.cmu.edu
David B. Benson
wrote: ...
> To this, I would add "...with no shared state between processes."
Yes, this is important (and lacking in CML).
I don't know how to do synchronous message passing without it.
Maybe the kernel has to control synchronous message passing?
Jon Harrop
> In article <<fi7fmm$qvt$1...@oravannahka.helsinki.fi>>,
> Vesa Karvonen <vesa.k...@cs.helsinki.fi> wrote:
>> David B. Benson <dbe...@eecs.wsu.edu> wrote:
>>> The "Beginning with ML" thread is now too long to follow.
>>
>>> What is meant by "Erlang-style concurrency"?
>>
>> Actor style, conventional, asynchronous message passing?
>
> To this, I would add "...with no shared state between processes."
I think some implementations that are referred to as being Erlang-style do
actually use shared state and almost all allow shared state (which is why
they don't scale as well).
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
Neelakantan Krishnaswami
<<f350b3ba-5b38-4a43...@e25g2000prg.googlegroups.com>>,
You can build synchronous message on top of asynchronous message
passing: a "synchronous message" from process A to B consists of A
sending a message to B, and then waiting for a confirmation message
from B that it arrived before continuing.
Ulf Wiger
The very early programming experiments that led up to Erlang
involved implementing a control system for an enterprise digital
phone switch (Ericsson MD 110).
One of the languages evaluated was Ada, which uses a synchronous
form of message passing called rendezvous. The experiments showed
that this was highly impractical in a distributed setting, and
led to convoluted code. This has been noted by others in the
Ada community (e.g. http://portal.acm.org/citation.cfm?id=91354.91371)
It is of course easy to implement synchronous message passing on
top of asynchronous message passing, even though it /may/ mean
sacrificing some optimization opportunities when both processes
are in a controlled environment with shared heap. In Erlang,
a synchronous dialogue is easily hidden within a function call,
making the abstraction perfectly comfortable:
synch_call(Process, Request) ->
Process ! {self(), Request},
receive
{Process, Reply} -> Reply
end.
This also illustrates an important point of erlang-style concurrency:
scoped message reception. In Erlang, this is done by pattern-matching
on the mailbox; in e.g. Haskell and F# (I think), it can be done with
channels. The crucial point is that you must be able to encapsulate
a transition state inside a function, and not have it leak out into
surrounding states. Some programs are near impossible to implement
without this.
To me, Erlang-style concurrency means:
1 lightweight actors
2 (conceptually) no shared memory between actors
3 (conceptally) copying asynchronous message passing
4 distribution transparency
5 scoped message reception (selective receive)
6 process monitoring, enabling "fail-fast" programming with
supervision structures for error recovery
7 cascading exits, e.g. through process linking
(I write "conceptually" just to emphasize that "copying" doesn't
mean that you must copy unnecessarily. Erlang doesn't always copy
data when sending it to another process).
I should perhaps also have listed the need for a timeout support.
(1) is important, since in a concurrency-oriented programming style,
you shouldn't have to be afraid of spawning a process, just like you
shouldn't have to worry too much about object instantiation in OO.
(2) is important for fault-tolerance. One process shouldn't be able to
destroy the memory of another process
(3) Asynchronous message passing is IMO a more general abstraction than
synchronous message passing, and the difference becomes important when
network delays are taken into account.
(4) Important both for robustness and scalability
(5) Absolutely crucial for multi-way complex finite state machines. For
those who don't think so, I have some nice examples. (:
(6) This is often called the "let it crash" philosophy in Erlang, but
on Tandem computers, it was called "fail fast". Don't try to handle
exceptions inside the failing process (no rule without exceptions,
though - we do this ourselves on occasion). Let the infrastructure
handle recovery.
(7) Cascading exit is an extremely useful technique, which cuts down
on the complexity of dealing with a large number of processes.
Not all of these things are fundamental abstractions, but it might be a
useful list for those who want to compare their concurrency abstractions
with those of Erlang.
There is certainly room for improvement. For example, Erlang initially
had two-way links between processes. This was found insufficient, and a
one-way monitor was introduced. Of course, the old links were kept for
BW compatibility. There may be a single abstraction that fulfills all
requirements... Anyone interested in studying the semantics and uses
of links vs monitors is most welcome to start a thread on the erlang-
questions mailing list.
BR,
Ulf W
ross...@ps.uni-sb.de
>
> 1 lightweight actors
> 2 (conceptually) no shared memory between actors
> 3 (conceptally) copying asynchronous message passing
But given (1) (or lightweight threads in general), isn't synchronous
messaging as good as asynchronous one? Plus, it seems to give you (5)
directly.
> 4 distribution transparency
> 5 scoped message reception (selective receive)
> 6 process monitoring, enabling "fail-fast" programming with
> supervision structures for error recovery
> 7 cascading exits, e.g. through process linking
- Andreas
Ulf Wiger
> On Nov 30, 9:54 am, Ulf Wiger <ulf.wi...@e-r-i-c-s-s-o-n.com> wrote:
>> 1 lightweight actors
>> 2 (conceptually) no shared memory between actors
>> 3 (conceptally) copying asynchronous message passing
>
> But given (1) (or lightweight threads in general), isn't synchronous
> messaging as good as asynchronous one? Plus, it seems to give you (5)
> directly.
... in the sense that a lightweight actor can be spawned
and used as a scoped channel, or a promise? Yes, I would
think so. The critique against synchronous communication,
esp in a distributed setting, was that if no answer is
required, it is unnecessarily expensive to send it over
a slow medium.
As an example, the Erlang VM uses an optional bulking
mechanism when sending messages between nodes. We've
found this to give significantly better throughput when
there is no need for explicit acknowledgment of each
message. This is an optimization if the assumption holds
for a large majority of messages going between the nodes.
An area where we use this is for stable state replication
of session data (e.g. phone or video calls). Failure to
replicate a session state is no reason to abort the session,
since the replica most likely won't be needed anyway. It
is also not regarded as a serious problem if a few sessions
are lost during a "failover" - it's a race condition anyway,
since there is no way we can guarantee atomicity in such
situations(*), given the number of devices that must be
configured in order to let a call go through.
(*) As in, no way to do it without forcing the caller to
wait much longer than he/she is prepared to.
In short, I think asynchronous communication is a more
suitable core abstraction for our domain (the one for
which Erlang was designed), and it's reasonable to view
it as a cornerstone of erlang-style concurrency, since
the choice has fairly significant consequences on
design decisions. That's not to say that it's /better/,
in general, than synchronous communication.
It's a bit like cooperative vs preemptive scheduling. One
may argue which one is better, but it's crucial that the
designer is aware of which one is used in the given
environment. A program assuming preemptive scheduling will
not work correctly in an environment using cooperative
scheduling.
BR,
Ulf W
Ben Franksen
>
> (5) Absolutely crucial for multi-way complex finite state machines. For
> those who don't think so, I have some nice examples. (:
Yes, I would be very much interested in examples for this. I have no
practical experience with Erlang, but I have been working with distributed
control systems for a long time. My experience is that non-blocking
callback based interfaces are almost always better than blocking ones, the
more so if the language directly supports closures. In his thesis
(http://www.cs.chalmers.se/~nordland/ohaskell/thesis.ps.gz, chapter 1.3)
Nordlander argues IMO very convincingly against selective receive, in
that "servers for complicated interaction protocols become
disproportionally easy to write using selective filtering, at the price of
making the clients extremely sensitive to temporal restrictions that may be
hard to express and virtually impossible to enforce".
Cheers
Ben
Stephen J. Bevan
> Ulf Wiger wrote:
>> (5) Absolutely crucial for multi-way complex finite state machines. For
>> those who don't think so, I have some nice examples. (:
>
> In his thesis
> (http://www.cs.chalmers.se/~nordland/ohaskell/thesis.ps.gz, chapter
> 1.3) Nordlander argues IMO very convincingly against selective
> receive, in that "servers for complicated interaction protocols
> become disproportionally easy to write using selective filtering, at
> the price of making the clients extremely sensitive to temporal
> restrictions that may be hard to express and virtually impossible to
> enforce".
I read chapter 1.3 but other than that sentence I didn't see any
larger discussion of the issue. Did I miss the convincing argument or
was that sentence alone meant to be it? I assumed not and kept going
and in Chapter 3.8 found a re-formulation of the Erlang POTS example.
From that it seems that the crux of the difference between O'Haskell
and Erlang is that :-
+ in O'Haskell one would naturally structure the problem such that for
each possible action/message you define how it should behave in all
possible states.
+ in Erlang one would naturally structure the problem such that for
each possible state (as represented by a function) one defines how
it handles each possible message.
The result should be the same assuming that all states and messages
are correctly identified.
An argument is made that the O'Haskell approach has the benefit that
it is reactive by default since the compiler can generate an
warning/error if any action does not handle a state. This is
contrasted with Erlang in which the programmer must manually ensure
that each state handles all messages (e.g. typically add a final
receive clause that ignores any other message). However, if Erlang
was statically typed and required one to declare all messages then its
compiler could also warn if any state did not handle a message. Thus
that O'Haskell advantage has more to do with static typing than than
the choice of axis around which to structure the design.
I read further but didn't find any other examples contrasting
O'Haskell and Erlang. Thus while Nordlander's statement might be
true, on the basis of the examples in the thesis I'd say it is not
proven (in the Scottish sense).
ross...@ps.uni-sb.de
> From that it seems that the crux of the difference between O'Haskell
> and Erlang is that :-
>
> + in O'Haskell one would naturally structure the problem such that for
> each possible action/message you define how it should behave in all
> possible states.
>
> + in Erlang one would naturally structure the problem such that for
> each possible state (as represented by a function) one defines how
> it handles each possible message.
In other words, O'Haskell uses functional design, while Erlang uses
object-oriented design.
- Andreas
Ben Franksen
> Ben Franksen <ben.fr...@online.de> writes:
>> Ulf Wiger wrote:
>>> (5) Absolutely crucial for multi-way complex finite state machines. For
>>> those who don't think so, I have some nice examples. (:
>>
>> Yes, I would be very much interested in examples for this. ...
>> In his thesis
>> (http://www.cs.chalmers.se/~nordland/ohaskell/thesis.ps.gz, chapter
>> 1.3) Nordlander argues IMO very convincingly against selective
>> receive, in that "servers for complicated interaction protocols
>> become disproportionally easy to write using selective filtering, at
>> the price of making the clients extremely sensitive to temporal
>> restrictions that may be hard to express and virtually impossible to
>> enforce".
>
> I read chapter 1.3 but other than that sentence I didn't see any
> larger discussion of the issue. Did I miss the convincing argument or
> was that sentence alone meant to be it?
The sentence merely expresses very clearly the central problem with
selective blocking receives, especially when this can be hidden in a
subroutine.
Nordlander's proposal is to outright forbid blocking behaviour in the
language. Any operation that waits for completion of anything (other than a
pure computation) /must/ express this in the API by taking a continuation
argument and this can /not/ be hidden from clients, period.
> An argument is made that the O'Haskell approach has the benefit that
> it is reactive by default since the compiler can generate an
> warning/error if any action does not handle a state.
It is not only reactive be default, it is necessarily reactive by design.
This is proved by induction, assuming there are no blocking primitives.
If the compiler didn't check exhaustiveness in case expressions and the
programmer forgets to include a case, the result would be a run-time
exception, /not/ a deadlock.
> This is
> contrasted with Erlang in which the programmer must manually ensure
> that each state handles all messages (e.g. typically add a final
> receive clause that ignores any other message). However, if Erlang
> was statically typed and required one to declare all messages then its
> compiler could also warn if any state did not handle a message. Thus
> that O'Haskell advantage has more to do with static typing than than
> the choice of axis around which to structure the design.
But the point is (or was) that Ulf Wiger expressly /wants/ to be able to
write selective receives, i.e. receives with non-exhaustive patterns, with
the intent that this blocks (indefinitely) as long as no matching message
arrives. He also argues that it is good that such blocking operations can
be hidden in a subroutine.
It may very well be that his examples convince me that such a feature is
needed, or at least useful. That's why I asked him to present them.
Cheers
Ben
Stephen J. Bevan
> Stephen J. Bevan wrote:
>> Ben Franksen <ben.fr...@online.de> writes:
>>> Ulf Wiger wrote:
>>>> (5) Absolutely crucial for multi-way complex finite state machines. For
>>>> those who don't think so, I have some nice examples. (:
>>>
>>> Yes, I would be very much interested in examples for this. ...
>>> In his thesis
>>> (http://www.cs.chalmers.se/~nordland/ohaskell/thesis.ps.gz, chapter
>>> 1.3) Nordlander argues IMO very convincingly against selective
>>> receive, in that "servers for complicated interaction protocols
>>> become disproportionally easy to write using selective filtering, at
>>> the price of making the clients extremely sensitive to temporal
>>> restrictions that may be hard to express and virtually impossible to
>>> enforce".
>>
>> I read chapter 1.3 but other than that sentence I didn't see any
>> larger discussion of the issue. Did I miss the convincing argument or
>> was that sentence alone meant to be it?
>
> The sentence merely expresses very clearly the central problem with
> selective blocking receives, especially when this can be hidden in a
> subroutine.
Indeed, but does "selective receive" imply blocking? I never thought
of it as implying that, primarily based on how the term is used in
"Concurrent Programming in Erlang". In section 5.2.3 a simple counter
example is given :-
start() -> spawn(counter, loop, [0]).
loop(Val) ->
receive
increment -> loop(Val+1)
end.
and it is noted that this example shows "selective message reception,
in this case the message increment". However, this example is
immediately followed by the comment that "There are, however, many
deficiencies in this example" and goes on to offer an alternative of
which the loop part is :-
loop(Val) ->
receive
increment -> loop(Val+1)
{From,value} -> From!{self(), Val}, loop(Val)
stop -> true
Other -> loop(Val)
end.
The third paragraph after the revised solution starts with :-
The counter process uses the selective receive mechanism to process
the incomming requests. It also presents a solution to the roblem
of handling unknown messages. The last clause i nthe receive has
the unbound variable Other as its message pattern; this will match
any message which is not matched by the other clauses.
Thus "selective receive" is being used to describe an example where
there clearly is no blocking. Consequently I've never interpreted
"selective receive" to imply blocking. If I've mis-interpreted what
"selective receive" means then is there some Erlang related material
that clearly defines "selective receive" to imply blocking?
Ben Franksen
> Ben Franksen <ben.fr...@online.de> writes:
>> Stephen J. Bevan wrote:
>>> Ben Franksen <ben.fr...@online.de> writes:
>>>> Ulf Wiger wrote:
>>>>> (5) Absolutely crucial for multi-way complex finite state machines.
>>>>> For those who don't think so, I have some nice examples. (:
>>>>
>>>> Yes, I would be very much interested in examples for this. ...
>>>> In his thesis
>>>> (http://www.cs.chalmers.se/~nordland/ohaskell/thesis.ps.gz, chapter
>>>> 1.3) Nordlander argues IMO very convincingly against selective
>>>> receive, in that "servers for complicated interaction protocols
>>>> become disproportionally easy to write using selective filtering, at
>>>> the price of making the clients extremely sensitive to temporal
>>>> restrictions that may be hard to express and virtually impossible to
>>>> enforce".
>>>
>>> I read chapter 1.3 but other than that sentence I didn't see any
>>> larger discussion of the issue. Did I miss the convincing argument or
>>> was that sentence alone meant to be it?
>>
>> The sentence merely expresses very clearly the central problem with
>> selective blocking receives, especially when this can be hidden in a
>> subroutine.
>
> Indeed, but does "selective receive" imply blocking?
/Any/ receive operation in Erang, selective or not, is blocking. It blocks
until a message arrives (or the timeout expires, if a timeout clause was
given). The receive is selective if and only if i.e. the clauses are not
exhaustive (which in Erlang, due to its untyped nature, can be only if
there is a catch-all clause, like in the above example).
> I never thought
> of it as implying that, primarily based on how the term is used in
> "Concurrent Programming in Erlang". In section 5.2.3 a simple counter
> example is given :-
>
> start() -> spawn(counter, loop, [0]).
>
> loop(Val) ->
> receive
> increment -> loop(Val+1)
> end.
The spawned task indeed blocks when no messages are pending. The task
calling start/0 does not, of course. The receive is /not/ selective, here,
so the task is reactive.
Maybe we use a different definition of the term 'blocking'?
In my dictionary, a task is blocked when it cannot progress without some
external event happening (such as a message from another task; or, in a
classical shared-memory setting, a semaphore is given; or an I/O operation
completes; etc..).
Cheers
Ben
Stephen J. Bevan
> Stephen J. Bevan wrote:
> /Any/ receive operation in Erang, selective or not, is blocking. It blocks
> until a message arrives (or the timeout expires,
If all activity is triggered by receipt of a message then a process
that has no messages is obviously idle. The term "blocked" does not
seem appropriate to me since the only thing "blocking" the process
from doing anything is that it hasn't been sent a message and there is
nothing "blocking" any other process from doing so. Thus while I
don't like the term "blocking" for this case I'll adopt it if it
widely accepted -- what papers define blocking like this?
> if a timeout clause was given). The receive is selective if and only
> if i.e. the clauses are not exhaustive
Your definition differs from the one in the Erlang book. What
papers/books define selective receive the way you do?
> The spawned task indeed blocks when no messages are pending. The task
> calling start/0 does not, of course. The receive is /not/ selective, here,
> so the task is reactive.
As noted above, the Erlang book says that is selective.
> Maybe we use a different definition of the term 'blocking'?
We appear to use a different definition of selective and blocking :-)
Ben Franksen
> Ben Franksen <ben.fr...@online.de> writes:
>> Stephen J. Bevan wrote:
>> /Any/ receive operation in Erang, selective or not, is blocking. It
>> blocks until a message arrives (or the timeout expires,
>
> If all activity is triggered by receipt of a message then a process
> that has no messages is obviously idle. The term "blocked" does not
> seem appropriate to me since the only thing "blocking" the process
> from doing anything is that it hasn't been sent a message and there is
> nothing "blocking" any other process from doing so. Thus while I
> don't like the term "blocking" for this case I'll adopt it if it
> widely accepted -- what papers define blocking like this?
It is how I learned it in university. I have never seen it used with a
different meaning (in the context of tasks/processes). I just looked it up
under http://en.wikipedia.org/wiki/Blocking_(scheduling) which supports my
definition (whatever weight wp might carry in a debate such as ours).
[citations reordered]
>> The spawned task indeed blocks when no messages are pending. The task
>> calling start/0 does not, of course. The receive is /not/ selective,
>> here, so the task is reactive.
>
> As noted above, the Erlang book says that is selective.
My mistake. I wrongly read 'increment' as a variable, when in fact it is a
constant (atom). So the receice /is/ selective (for my intuitive
understanding of the term 'selective', see below).
>> if a timeout clause was given). The receive is selective if and only
>> if i.e. the clauses are not exhaustive
>
> Your definition differs from the one in the Erlang book. What
> papers/books define selective receive the way you do?
None that I know of. I was using the term from my intuitive understanding of
the word 'selective' plus some applied logic. If you receive messages and
are 'selective' about it, it would mean to me that you don't accept
(handle) any old message that happens to come along but rather only certain
ones, namely those you are interested in. In Erlang you declare interest
with pattern matches and since any receive that does not contain a
catch-all pattern rejects certain messages, it is selective.
While this may formally be true, I see now that this view is a bit too
drastic, since messages in Erlang are usually meant to be (implicitly)
typed by using atoms that act as runtime type tags. However even if we
restrict the set of possible messages to the ones that match some top-level
receive statement, you can get problems if you do another (nested) receive
in response to a message, and if this receive handles only a certain
restricted subset of messages. You have then the situation that Nordlander
thinks should be avoided: the 'object' (task) is no longer reactive to
certain otherwise allowed messages, it is 'temporarily indisposed'. Thus a
client (that sends our task messages and expects responses or certain
effects to happen) has to be aware of this possibility, making it harder to
implement it correctly.
> We appear to use a different definition of selective and blocking :-)
I'd be very astonished if the definition of 'selective receive' in the
Erlang book were completely different from mine, but I stand to be
corrected. I don't have the Erlang book at hand. How is it defined there?
Cheers
Ben
Joachim Durchholz
> /Any/ receive operation in Erang, selective or not, is blocking.
As Stephen wrote, a blocking receive doesn't look like a problem.
However, I think in the context of this discussion, blocking messaging
was meant to be viewed from the sender's end, i.e. the sender is blocked
until the receive has received (and possibly processed) the message; to
the least, this fits with several mentions of synchronous messaging.
> The spawned task indeed blocks when no messages are pending. The task
> calling start/0 does not, of course. The receive is /not/ selective, here,
> so the task is reactive.
I don't think that selectivity makes much of a difference. Usually, an
Erlang task will either have a catch-all clause or never accept some
specific kind of message.
Oh, and Erlang tasks typically have a single receive statement, so any
message is either processed as soon as possible or ignored forever. So
messages cannot block each other, if that's what you mean by the
difference between "selective" and "reactive".
That's just typical Erlang usage, of course; it is possible to write an
Erlang process so that it will or will not accept a specific message
depending on its internal state. I would consider this Bad Design, but
it's possible.
Regards,
jo
Ulf Wiger
> Ulf Wiger wrote:
>>
>> To me, Erlang-style concurrency means:
>>
>> 1 lightweight actors
>> 2 (conceptually) no shared memory between actors
>> 3 (conceptally) copying asynchronous message passing
>> 4 distribution transparency
>> 5 scoped message reception (selective receive)
>> 6 process monitoring, enabling "fail-fast" programming with
>> supervision structures for error recovery
>> 7 cascading exits, e.g. through process linking
>>
>> [...]
>>
>> (5) Absolutely crucial for multi-way complex finite state machines. For
>> those who don't think so, I have some nice examples. (:
There's a powerpoint presentation:
Structured network programming (EUC '05)
http://www.erlang.se/euc/05/1500Wiger.ppt
(There is reference to a "demo". I ran a simulated phone switch,
which used to be used in the Beginner's Erlang course, for the
final programming assignment, day two. I had instrumented it so
that I could inject delays in the responses from the switch, which
made it quite easy to trigger timing bugs in the control software,
while the timing-safe code would clearly lag behind, but would
still perform all operations in the right order.)
> Yes, I would be very much interested in examples for this. I have no
> practical experience with Erlang, but I have been working with distributed
> control systems for a long time. My experience is that non-blocking
> callback based interfaces are almost always better than blocking ones, the
> more so if the language directly supports closures. In his thesis
> (http://www.cs.chalmers.se/~nordland/ohaskell/thesis.ps.gz, chapter 1.3)
> Nordlander argues IMO very convincingly against selective receive, in
> that "servers for complicated interaction protocols become
> disproportionally easy to write using selective filtering, at the price of
> making the clients extremely sensitive to temporal restrictions that may be
> hard to express and virtually impossible to enforce".
Yes, I've read his thesis (or rather, skimmed through it, paying more
attention to selected parts). His comparison to Erlang is based on a
POTS (Plain Old Telephony System) example from the original Erlang book,
but based on that example, he makes an assumption that usually doesn't
hold in more complex implementations: the teleos module, which exports
functions to manipulate the switch, are assumed to always return
immediately.
In practice, they don't, but will often result in message passing to
some other device, or to the network. This means that the caller cannot
be guaranteed that the result will return immediately. Note that with
Erlang-style selective receive, this doesn't really matter much, so
the authors of the Erlang book may perhaps be excused for not making
the point clear. (:
Specifically, in the POTS example, there are two interfaces of interest:
the Line Interface Module (LIM), and the number analysis. The old Erlang
POTS experiments were run on an MD 110, which had a message passing
interface and a message buffer of depth 1. The control system therefore
had to make sure that only one request at a time was send to the switch.
If another request came in too soon, it would simply overwrite the
previous one, which might result in lost messages.
B-number analysis in the good old days was usually a longest-prefix
match in a subscriber table, and could be implemented as a simple
function, but in the world of SIP, GSM, UMTS et al, subscriber lookup
is, more often than not, done through an RPC call to another box in
the network: a Home Subscriber Server in 3GPP IMS, using a Diameter-
based request-response dialogue; a Home Location Register in GSM
and 3G, via the Signaling No 7 Protocol; or perhaps a TelURI lookup
in DNS, which might call on several DNS servers before returning an
answer. As other autonomous systems need to be queried, there is
no guarantee that the answer will return promptly, and several
kinds of failure scenarios are likely.
The really juicy part is that if all these dialogues are handled
at the top level, as individual request and response messages,
the event-state matrix will grow geometrically. In some of the
systems we develop now, we have at least seven different
signaling interfaces for one call setup. Luckily, most are RPC-
style, and we can dispatch them as a simple function call.
I've seen several projects march unsuspectingly into this
complexity explosion, sometimes despite the fact that they have
been warned early on. "How hard can it be?" is a common question,
and the answer, "unimaginably hard", doesn't seem to sink in.
I've been through it too, and I have to admit that I completely
underestimated the difficulties the first time.
I could go on, as there are other interfaces in modern signaling
networks with similar properties, but I'm sure you get the point.
From the perspective of an individual call setup, most of these
requests can conceptually be seen as a function call, but only
if the environment allows such encapsulation.
BR,
Ulf W
Stephen J. Bevan
> Stephen J. Bevan wrote:
>> Ben Franksen <ben.fr...@online.de> writes:
>>> Stephen J. Bevan wrote:
>>> /Any/ receive operation in Erang, selective or not, is blocking. It
>>> blocks until a message arrives (or the timeout expires,
>>
>> If all activity is triggered by receipt of a message then a process
>> that has no messages is obviously idle. The term "blocked" does not
>> seem appropriate to me since the only thing "blocking" the process
>> from doing anything is that it hasn't been sent a message and there is
>> nothing "blocking" any other process from doing so. Thus while I
>> don't like the term "blocking" for this case I'll adopt it if it
>> widely accepted -- what papers define blocking like this?
>
> It is how I learned it in university. I have never seen it used with a
> different meaning (in the context of tasks/processes). I just looked it up
> under http://en.wikipedia.org/wiki/Blocking_(scheduling) which supports my
> definition (whatever weight wp might carry in a debate such as ours).
The Wikipedia definition talks about one process being blocked while a
shared resource is in use by another process. If that's what you mean
then given that passing is asynchronous in Erlang the the sender can't
block on a send so the only way to block on a receive. If the
protocol is such that you should not respond to message B until you've
received message A then there are a few of ways to implement it
depending on what should be done with a B that comes before an A and
what should be done with any other message C that may arrive while
waiting for an A or B. Nested receives are one way to handle it and
it is up to the writer of the nested receive to decide whether it
blocks only for B (possibly with a timeout) or whether it will accept
a B and some kind of cancel message, or whether it accepts a B and
most of the other messages that are allowed in the receive of A.
Consequently I'll agree that it is possible to write a receive can
block, but I don't agree that _any_ receive in Erlang is blocking, at
least not for any useful definition of "blocking".
> ... However even if we
> restrict the set of possible messages to the ones that match some top-level
> receive statement, you can get problems if you do another (nested) receive
> in response to a message, and if this receive handles only a certain
> restricted subset of messages. You have then the situation that Nordlander
> thinks should be avoided: the 'object' (task) is no longer reactive to
> certain otherwise allowed messages, it is 'temporarily indisposed'. Thus a
> client (that sends our task messages and expects responses or certain
> effects to happen) has to be aware of this possibility, making it harder to
> implement it correctly.
If one wants to avoid it, then it is rather straightforward: don't do
it. It is not like it is a subtle error like a double free in C or
unwanted object retention in any language with GC.
> I'd be very astonished if the definition of 'selective receive' in the
> Erlang book were completely different from mine, but I stand to be
> corrected. I don't have the Erlang book at hand. How is it defined there?
I don't see an explicit definition in the book, rather it is defined
by example, the ones I gave in this thread. Ulf or someone more
familar with Erlang may know of a more formal definition.
Ben Franksen
Sorry, but you can't simply redefine technical terms just because you don't
find the common definition useful. This would lead to severe communication
problems. Use a different term to describe whatever you find more useful to
talk about (and, BTW, /do/ define its meaning).
I'll continue to use the term with its usual meaning, i.e. a task is blocked
if it can't make any progress until some external event happens.
In systems with an explicit notion of 'task' (such as Erlang) it is of
course necessary and normal for a task to become blocked. What I am arguing
about is whether, in message based concurrency, it is a good idea to
(indefinitely) wait for /specific/ messages, thereby (indefinitely)
postponing reactions to other legitimate messages.
The reason why I am questioning this practice is this: I think it is not
nice to clients, which have to be aware that a task might temporarily be
unable to respond to a (otherwise legitimate) request, without being
notified about this condition in any way (except possibly by a timeout, if
the client is paranoid enough to specify one).
After reading Ulf Wiger's response, I am minded to concede that there may be
situations where this, however bad, is the lesser evil, compared to the
complications caused by an exponentially exploding number of states in the
server.
Cheers
Ben
Ben Franksen
many thanks for your detailed answer.
> There's a powerpoint presentation:
Actually, when looking at it I remembered that I'd seen it before. Maybe the
main message got lost under the heap of all the code excerpts; for someone
who does not regularly program in Erlang /and/ is not a telecom expert,
they are hard to understand w/o more detailed explanations.
> The really juicy part is that if all these dialogues are handled
> at the top level, as individual request and response messages,
> the event-state matrix will grow geometrically. In some of the
> systems we develop now, we have at least seven different
> signaling interfaces for one call setup. Luckily, most are RPC-
> style, and we can dispatch them as a simple function call.
Yes, the state exlosion is a problem. I can't claim to have a solution how
to avoid it in general. (This would make a nice research project, BTW.) As
I wrote in another message, I am ready to concede that selective receive
may sometimes be the lesser evil. I would still very carefully examine in
each case whether it really results in less complication, considering that
clients have to be aware of the temporary non-responsiveness of the server.
Cheers
Ben
Stephen J. Bevan
> I'll continue to use the term with its usual meaning, i.e. a task is blocked
> if it can't make any progress until some external event happens.
OK, let's assume that your interpretation is correct so that we can
use it to analyze :-
> In systems with an explicit notion of 'task' (such as Erlang) it is of
> course necessary and normal for a task to become blocked.
O'Haskell has templates which have asynchonous action statements.
Once you instantiate the template is it it blocked or not? If it is
then referring to Erlang as blocking is not saying anything
interesting since O'Haskell is too. If instantiated templates in
O'Haskell are not blocking then what is the essential difference
between them and Erlang proceses that means the later is not blocking
but the former is?
> What I am arguing about is whether, in message based concurrency, it
> is a good idea to indefinitely) wait for /specific/ messages,
> thereby (indefinitely) postponing reactions to other legitimate messages.
And you are welcome to argue it, but the argument would be much more
convincing with a non-trivial examples. The closest to that in
Nordlander's thesis is the POTS example but that doesn't make the
case since the Erlang solution is also reactive and the complexity of
the solutions is almost identical.
> The reason why I am questioning this practice is this: I think it is not
> nice to clients, which have to be aware that a task might temporarily be
> unable to respond to a (otherwise legitimate) request, without being
> notified about this condition in any way (except possibly by a timeout, if
> the client is paranoid enough to specify one).
Reactive is a nice ideal, but is it practical? If I have a object (be
it an instantiated template, process, ... etc.) and on receipt of a
message it starts doing a 8192-bit Diffie-Hellman calculation then
with a single locus of control you aren't going to get any response to
any other message (such as the reqeust to do another Diffie-Hellman
calculation) for a few seconds. Is this nice to a client or not? If
not, how do you make it nice and is the reactively nice solution
simpler than the non-reactive one?
Ulf Wiger
>
> After reading Ulf Wiger's response, I am minded to concede that
> there may be situations where this, however bad, is the lesser
> evil, compared to the complications caused by an exponentially
> exploding number of states in the server.
Exactly. Of course, the degree of evil will vary depending on domain.
In hard real-time systems, missing a deadline is often a fatal
error. In soft real-time, it can be ok, as long as it doesn't happen
too often. (:
BR,
Ulf W
Ulf Wiger
> Hi Ulf
>
> many thanks for your detailed answer.
>
>> There's a powerpoint presentation:
>
> Actually, when looking at it I remembered that I'd seen it
> before. Maybe the main message got lost under the heap of
> all the code excerpts; for someone who does not regularly
> program in Erlang /and/ is not a telecom expert,
> they are hard to understand w/o more detailed explanations.
Of course. In my defense, the venue was, after all, the Erlang
User Conference. (:
I did try very hard to illustrate the problem with state diagrams,
but failed to draw the more complicated ones correctly. I also
had in mind to port the examples to different programming languages,
but that proved to be too much work.
The nice thing about presenting the actual code, though, is that
it is rather easy to see that the complexity explosion cannot
be avoided, given certain design decisions.
> Yes, the state exlosion is a problem. I can't claim to have a
> solution how to avoid it in general. (This would make a nice
> research project, BTW.)
Simon Peyton-Jones observed that it really ought to boil down
to a matter of proper scoping of messages. Seen from that
perspective, Erlang simulates local scope by pattern-matching
on a shared message queue. MVars in Haskell obey the same
scoping rules as any other variable.
> I would still very carefully examine in each case whether it
> really results in less complication, considering that clients
> have to be aware of the temporary non-responsiveness of the server.
Indeed. One of the nice things in in telecoms, is that the clients
/are/ aware that there will be noticeable delay, and all protocols
are equipped with timers etc.
BR,
Ulf W