How exactly Erlang receive expression works?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

How exactly Erlang receive expression works?

Athanasios Valsamakis
I was reading the book of Mr. Joe Armstrong "Programming Erlang 2nd ed.",
when I reached the section about selective receive. 
He explained it very clearly. So, based on his explanation I decided to
make a flowchart. I would like to share it with you. Comments are welcome.



      +-----------------+
      |  Enter receive. |               ** Timer may have already been elapsed
      |  Start timer    |                when entering this state.
      +------+----------+
             |
       +-----v------+            +--------------------------------+              +-------------------+
       | is mailbox | Yes        | suspend process until          |timer elapsed | evaluate          |
+------> empty?     +------------> a new message is put in mailbox+--------------> expressionsTimeout|
|      |            |            | or  timer has elapsed**        |              |                   |
|      +------------+            +-----+--------------------------+              +--------+----------+
|            |No                       |                                                  |
|     +------v----------------+        |new msg arrived                                   |
|     | take the head message |        |                                                  |
|     | from the mailbox      <--------+                                                  |
|     +------+----------------+                                                           |
|            |                                                                            |
|      +-----v-------------+    +---------------+    +-------------+                      |
|      | match the message +---->remove message +---->evaluate     +------------+         |
|      | against pattern1  |Yes |from mailbox   |    |expressions1 |            |         |
|      +-------------------+    +---------------+    +-------------+            |         |
|            |No                                                                |         |
|            |                                                            +-----v---------v--------------------+
|      +-----v-------------+    +---------------+    +-------------+      | if any messages have been put into |
|      | match the message +---->remove message +---->evaluate     +------> the save queue, are reentered      |
|      | against pattern2  |Yes |from mailbox   |    |expressions2 |      | into the mailbox                   |
|      +-------------------+    +---------------+    +-------------+      +-----^---------+--------------------+
|            |No                                                                |         |
|            |                                                                  |         |
|      +-----v-------------+    +---------------+    +-------------+            |         |
|      | match the message +---->remove message +---->evaluate     +------------+         |
|      | against pattern3  |Yes |from mailbox   |    |expressions3 |                      |
|      +-------------------+    +---------------+    +-------------+                      |
|            |No                                                                          |
|            |                                                                            |
|      +-----v------------------------------+                                             |
|      | message is removed from the mailbox|                                             |
+------+ and put into a "save queue"        |                                             |
       |                                    |                                             |
       +------------------------------------+                                             |
                                                                                          |
        +------------------+                                                              |
        | Exit receive.    <--------------------------------------------------------------+
        | Timer is cleared.|
        +------------------+


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: How exactly Erlang receive expression works?

Xavier Noria
I think there is a detail that does not square.

Take this example[*]:

-module(foo).
-export([start/0]).

start() ->
self() ! matched_by_b,
self() ! matched_by_a,
a(),
halt().

a() ->
receive
matched_by_a ->
io:format("matched by a/0~n"),
b()
end.

b() ->
receive
matched_by_b ->
io:format("matched by b/0~n")
end.


According to your (very nice!) diagram, this program should hang, because when b/0 is invoked, the message `matched_by_b` has already been moved into the save queue, and b/0 is called while the expression that matches `matched_by_a` is evaluated. The diagram says `matched_by_b` is not in the mailbox at that point.

But the program terminates, ergo reductio ad absurdum :).

I guess that diagram comes from the algorithm outlined on page 194 of the book. I believe you need to factor in step (5).

Xavier

[*] erlc foo.erl && erl -noshell -run foo



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: How exactly Erlang receive expression works?

Athanasios Valsamakis
Mr. Xavier, you are absolutely right!

Thank you for pointing my error.

Is the following flowchart closer to the truth?


      +-----------------+
      |  Enter receive. |               ** Timer may have already been elapsed
      |  Start timer    |                when entering this state.
      +------+----------+
             |
       +-----v------+            +--------------------------------+
       | is mailbox | Yes        | suspend process until          |timer elapsed
+------> empty?     +------------> a new message is put in mailbox+-----------------+
|      |            |            | or  timer has elapsed**        |                 |
|      +------------+            +-----+--------------------------+   +-------------v---------------------+     +-------------------+
|            |No                       |                              |if any messages have been put into |     | evaluate          |
|     +------v----------------+        |new msg arrived               |the save queue, are reentered      +-----> expressionsTimeout|
|     | take the head message |        |                              |into the mailbox                   |     |                   |
|     | from the mailbox      <--------+                              +-----------------------------------+     +--------+----------+
|     +------+----------------+                                                                                          |
|            |                                        +-----------------------------------+     +-------------+          |
|      +-----v-------------+    +---------------+     |if any messages have been put into +----->evaluate     +---------->
|      | match the message +---->remove message +----->the save queue, are reentered      |     |expressions1 |          |
|      | against pattern1  |Yes |from mailbox   |     |into the mailbox                   |     +-------------+          |
|      +-------------------+    +---------------+     +-----------------------------------+                              |
|            |No                                                                                                         |
|            |                                                                                                           |
|      +-----v-------------+    +---------------+     +-----------------------------------+     +-------------+          |
|      | match the message +---->remove message +----->if any messages have been put into +----->evaluate     +---------->
|      | against pattern2  |Yes |from mailbox   |     |the save queue, are reentered      |     |expressions2 |          |
|      +-------------------+    +---------------+     |into the mailbox                   |     +-------------+          |
|            |No                                      +-----------------------------------+                              |
|            |                                                                                                           |
|      +-----v-------------+    +---------------+     +-----------------------------------+     +-------------+          |
|      | match the message +---->remove message +----->if any messages have been put into +----->evaluate     +---------->
|      | against pattern3  |Yes |from mailbox   |     |the save queue, are reentered      |     |expressions3 |          |
|      +-------------------+    +---------------+     |into the mailbox                   |     +-------------+          |
|            |No                                      +-----------------------------------+                              |
|            |                                                                                                           |
|      +-----v------------------------------+                                                                            |
|      | message is removed from the mailbox|                                                                            |
+------+ and put into a "save queue"        |                                                                            |
       |                                    |                                                                            |
       +------------------------------------+                                                                            |
                                                                                                                         |
        +------------------+                                                                                             |
        | Exit receive.    <---------------------------------------------------------------------------------------------+
        | Timer is cleared.|
        +------------------+






On Fri, Mar 16, 2018 at 4:57 PM, Xavier Noria <[hidden email]> wrote:
I think there is a detail that does not square.

Take this example[*]:

-module(foo).
-export([start/0]).

start() ->
self() ! matched_by_b,
self() ! matched_by_a,
a(),
halt().

a() ->
receive
matched_by_a ->
io:format("matched by a/0~n"),
b()
end.

b() ->
receive
matched_by_b ->
io:format("matched by b/0~n")
end.


According to your (very nice!) diagram, this program should hang, because when b/0 is invoked, the message `matched_by_b` has already been moved into the save queue, and b/0 is called while the expression that matches `matched_by_a` is evaluated. The diagram says `matched_by_b` is not in the mailbox at that point.

But the program terminates, ergo reductio ad absurdum :).

I guess that diagram comes from the algorithm outlined on page 194 of the book. I believe you need to factor in step (5).

Xavier

[*] erlc foo.erl && erl -noshell -run foo




_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

receive_after_flowchart2.txt (6K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: How exactly Erlang receive expression works?

Mikael Pettersson-5
Drop the "save queue" stuff.  You should think of the mailbox as a
queue with a read cursor.  Whenever you enter a receive, the cursor is
reset to the start of the queue, and then you enumerate messages and
match them, non-destructively, until you either find one that matches,
or the cursor reaches the end of the queue.  In case of a match, the
message is removed from the queue.  In case of a non-match, the
process is suspended until some message is appended to the queue or
your timeout (if any) fires.  When awakened due to a new message, the
process continues to scan its mailbox from the last cursor position
(avoiding the cost of rescanning is part of the semantics, IMO).

On Fri, Mar 16, 2018 at 6:37 PM, Athanasios Valsamakis
<[hidden email]> wrote:

> Mr. Xavier, you are absolutely right!
>
> Thank you for pointing my error.
>
> Is the following flowchart closer to the truth?
>
>
>       +-----------------+
>       |  Enter receive. |               ** Timer may have already been
> elapsed
>       |  Start timer    |                when entering this state.
>       +------+----------+
>              |
>        +-----v------+            +--------------------------------+
>        | is mailbox | Yes        | suspend process until          |timer
> elapsed
> +------> empty?     +------------> a new message is put in
> mailbox+-----------------+
> |      |            |            | or  timer has elapsed**        |
> |
> |      +------------+            +-----+--------------------------+
> +-------------v---------------------+     +-------------------+
> |            |No                       |                              |if
> any messages have been put into |     | evaluate          |
> |     +------v----------------+        |new msg arrived               |the
> save queue, are reentered      +-----> expressionsTimeout|
> |     | take the head message |        |                              |into
> the mailbox                   |     |                   |
> |     | from the mailbox      <--------+
> +-----------------------------------+     +--------+----------+
> |     +------+----------------+
> |
> |            |
> +-----------------------------------+     +-------------+          |
> |      +-----v-------------+    +---------------+     |if any messages have
> been put into +----->evaluate     +---------->
> |      | match the message +---->remove message +----->the save queue, are
> reentered      |     |expressions1 |          |
> |      | against pattern1  |Yes |from mailbox   |     |into the mailbox
> |     +-------------+          |
> |      +-------------------+    +---------------+
> +-----------------------------------+                              |
> |            |No
> |
> |            |
> |
> |      +-----v-------------+    +---------------+
> +-----------------------------------+     +-------------+          |
> |      | match the message +---->remove message +----->if any messages have
> been put into +----->evaluate     +---------->
> |      | against pattern2  |Yes |from mailbox   |     |the save queue, are
> reentered      |     |expressions2 |          |
> |      +-------------------+    +---------------+     |into the mailbox
> |     +-------------+          |
> |            |No
> +-----------------------------------+                              |
> |            |
> |
> |      +-----v-------------+    +---------------+
> +-----------------------------------+     +-------------+          |
> |      | match the message +---->remove message +----->if any messages have
> been put into +----->evaluate     +---------->
> |      | against pattern3  |Yes |from mailbox   |     |the save queue, are
> reentered      |     |expressions3 |          |
> |      +-------------------+    +---------------+     |into the mailbox
> |     +-------------+          |
> |            |No
> +-----------------------------------+                              |
> |            |
> |
> |      +-----v------------------------------+
> |
> |      | message is removed from the mailbox|
> |
> +------+ and put into a "save queue"        |
> |
>        |                                    |
> |
>        +------------------------------------+
> |
>
> |
>         +------------------+
> |
>         | Exit receive.
> <---------------------------------------------------------------------------------------------+
>         | Timer is cleared.|
>         +------------------+
>
>
>
>
>
>
> On Fri, Mar 16, 2018 at 4:57 PM, Xavier Noria <[hidden email]> wrote:
>>
>> I think there is a detail that does not square.
>>
>> Take this example[*]:
>>
>> -module(foo).
>> -export([start/0]).
>>
>> start() ->
>> self() ! matched_by_b,
>> self() ! matched_by_a,
>> a(),
>> halt().
>>
>> a() ->
>> receive
>> matched_by_a ->
>> io:format("matched by a/0~n"),
>> b()
>> end.
>>
>> b() ->
>> receive
>> matched_by_b ->
>> io:format("matched by b/0~n")
>> end.
>>
>>
>> According to your (very nice!) diagram, this program should hang, because
>> when b/0 is invoked, the message `matched_by_b` has already been moved into
>> the save queue, and b/0 is called while the expression that matches
>> `matched_by_a` is evaluated. The diagram says `matched_by_b` is not in the
>> mailbox at that point.
>>
>> But the program terminates, ergo reductio ad absurdum :).
>>
>> I guess that diagram comes from the algorithm outlined on page 194 of the
>> book. I believe you need to factor in step (5).
>>
>> Xavier
>>
>> [*] erlc foo.erl && erl -noshell -run foo
>>
>>
>
>
> _______________________________________________
> erlang-questions mailing list
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions
>
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: How exactly Erlang receive expression works?

Athanasios Valsamakis
In reply to this post by Athanasios Valsamakis
I think the timer should also be cleared in an earlier step.

On Fri, Mar 16, 2018 at 7:37 PM, Athanasios Valsamakis <[hidden email]> wrote:
Mr. Xavier, you are absolutely right!

Thank you for pointing my error.

Is the following flowchart closer to the truth?


      +-----------------+
      |  Enter receive. |               ** Timer may have already been elapsed
      |  Start timer    |                when entering this state.
      +------+----------+
             |
       +-----v------+            +--------------------------------+
       | is mailbox | Yes        | suspend process until          |timer elapsed
+------> empty?     +------------> a new message is put in mailbox+-----------------+
|      |            |            | or  timer has elapsed**        |                 |
|      +------------+            +-----+--------------------------+   +-------------v---------------------+     +-------------------+
|            |No                       |                              |if any messages have been put into |     | evaluate          |
|     +------v----------------+        |new msg arrived               |the save queue, are reentered      +-----> expressionsTimeout|
|     | take the head message |        |                              |into the mailbox                   |     |                   |
|     | from the mailbox      <--------+                              +-----------------------------------+     +--------+----------+
|     +------+----------------+                                                                                          |
|            |                                        +-----------------------------------+     +-------------+          |
|      +-----v-------------+    +---------------+     |if any messages have been put into +----->evaluate     +---------->
|      | match the message +---->remove message +----->the save queue, are reentered      |     |expressions1 |          |
|      | against pattern1  |Yes |from mailbox   |     |into the mailbox                   |     +-------------+          |
|      +-------------------+    +---------------+     +-----------------------------------+                              |
|            |No                                                                                                         |
|            |                                                                                                           |
|      +-----v-------------+    +---------------+     +-----------------------------------+     +-------------+          |
|      | match the message +---->remove message +----->if any messages have been put into +----->evaluate     +---------->
|      | against pattern2  |Yes |from mailbox   |     |the save queue, are reentered      |     |expressions2 |          |
|      +-------------------+    +---------------+     |into the mailbox                   |     +-------------+          |
|            |No                                      +-----------------------------------+                              |
|            |                                                                                                           |
|      +-----v-------------+    +---------------+     +-----------------------------------+     +-------------+          |
|      | match the message +---->remove message +----->if any messages have been put into +----->evaluate     +---------->
|      | against pattern3  |Yes |from mailbox   |     |the save queue, are reentered      |     |expressions3 |          |
|      +-------------------+    +---------------+     |into the mailbox                   |     +-------------+          |
|            |No                                      +-----------------------------------+                              |
|            |                                                                                                           |
|      +-----v------------------------------+                                                                            |
|      | message is removed from the mailbox|                                                                            |
+------+ and put into a "save queue"        |                                                                            |
       |                                    |                                                                            |
       +------------------------------------+                                                                            |
                                                                                                                         |
        +------------------+                                                                                             |
        | Exit receive.    <---------------------------------------------------------------------------------------------+
        | Timer is cleared.|
        +------------------+






On Fri, Mar 16, 2018 at 4:57 PM, Xavier Noria <[hidden email]> wrote:
I think there is a detail that does not square.

Take this example[*]:

-module(foo).
-export([start/0]).

start() ->
self() ! matched_by_b,
self() ! matched_by_a,
a(),
halt().

a() ->
receive
matched_by_a ->
io:format("matched by a/0~n"),
b()
end.

b() ->
receive
matched_by_b ->
io:format("matched by b/0~n")
end.


According to your (very nice!) diagram, this program should hang, because when b/0 is invoked, the message `matched_by_b` has already been moved into the save queue, and b/0 is called while the expression that matches `matched_by_a` is evaluated. The diagram says `matched_by_b` is not in the mailbox at that point.

But the program terminates, ergo reductio ad absurdum :).

I guess that diagram comes from the algorithm outlined on page 194 of the book. I believe you need to factor in step (5).

Xavier

[*] erlc foo.erl && erl -noshell -run foo





_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

receive_after_flowchart3.txt (6K) Download Attachment