please improve API doc for send/receiveChan (capacity? order?)

[jwaldmann]

A "channel" can be one of many things, and the API docs don't say what's happening:

• does it have a capacity? (can it store messages?)
• if yes, what guarantees are there for message ordering? (is it FIFO in some concurrent sense, that is FIFO between a fixed pair of sender and receiver process?)

and the same for send/expect - with the extra difficulty that the underlying channel is untyped? What does this imply for message ordering (e.g., FIFO-by-type)?

You have some "INTERNAL NOTES" in C.D.Process - please make them visible in the Haddocks.

[hyperthunk]

A "channel" can be one of many things, and the API docs don't say what's happening:

You're right, and we are going to improve the documentation for all of CH. A channel is backed by a module implementing a subset of Control.Concurrent.STM.TQueue features.

does it have a capacity? (can it store messages?)

Yes, see above.

if yes, what guarantees are there for message ordering? (is it FIFO in some concurrent sense, that is FIFO between > a fixed pair of sender and receiver process?)

That's a bit tougher to answer. My understanding is that this is a FIFO queue but there are no ordering guarantees between sender and receiver that I can see, because incoming requests to the node controller to enqueue messages in the channel will race.

and the same for send/expect

This is a bit easier. Messages between two processes should arrive in FIFO order, if at all. Beyond that there are no guarantees about ordering (where other processes are sending messages as well).

with the extra difficulty that the underlying channel is untyped

That doesn't really make any difference AFAIK.

What does this imply for message ordering (e.g., FIFO-by-type)?

The thing to bare in mind, with the guarantees given thus far, is that the receive can choose to receive some messages before others, filtering them by type or by some arbitrary predicate using matchIf. One can also filter to receive messages from either the primary mailbox (i.e., the untyped channel) or one or more typed channels.

I will look at improving the documentation in this area and others as we work on getting CH production ready!

[jwaldmann]

FIFO between a fixed pair of sender and receiver

I meant the following: for one channel: if P1 .. Pm are writers, and Q1 .. Qn are readers, and if Pi sends A and then B, and Qj reads both A and B, then it will read them in that order.

untyped .. no difference

well - say A :: T and B :: S, but the receiver expects type S, then expexts type T. Then it could read B before A? Or does this just deadlock? (I don't think so, and a simple experiment seems to confirm.)

can we say in summary: the messages are held in a queue, and any receive/expect removes the first message that fulfils the criterion? (the API docs often say: read "any" message. But it is really "first" here?)

[hyperthunk]

well - say A :: T and B :: S, but the receiver expects type S, then expexts type T. Then it could read B before A? Or > does this just deadlock? (I don't think so, and a simple experiment seems to confirm.)

Yes, the selective receive construct will remove B before A. The other message (A) will remain in the mailbox and the ordering should be preserved.

the API docs often say: read "any" message. But it is really "first" here?

If your mailbox is Cons a (Cons b (Cons c Nil)) and you do a selective receive that matches on either b or c then you will get b as the result - the first match - then a second receive will return c. The remaining mailbox will contain a as you would expect. Does that make sense? How might the wording of the API docs better describe that? And @edsko - can you confirm I'm telling the truth here!? :)

Cheers

[hyperthunk]

Actually I should correct myself on something here. In a sender receiver pair there is a FIFO ordering guarantee. But between more than two processes there aren't any such guarantees.

[edsko]

This is documented in great detail in the semantics. The basic rule is:

Messages from Proc to Id are delivered in order (with Proc a process and Id either process, a channel (sendport), or a node). No ordering guarantees exist for messages sent by dfiferent senders or sent to different receivers.

The fact that you can extract messages in different order from how they are delivered to the mailbox or the channel is orthogonal to that definition.

Note that we will probably want to strengthen this rule so that

All messages from process P to process Q are ordered (whether they are sent directly to Qs mailbox or to one of Qs channel)

Without this guarantee it becomes very difficult to write robust algorithms (for instance, a monitor message might "overtake" a message sent on a channel). This is still under debate. However, if you are using the TCP transport (which, currently, is everybody) then we do have the stronger guarantee.

By the way, although @hyperthunk is right that a channel is currently backed by STM, I don't think that this is part of its API per say (in other words, I'm not sure whether this is just an implementation detail or whether we want to make this part of the spec).

[hyperthunk]

By the way, although @hyperthunk is right that a channel is currently backed by STM, I don't think that this is part of its API per say (in other words, I'm not sure whether this is just an implementation detail or whether we want to make this part of the spec).

Good point. It's almost certainly an implementation detail I guess - I should've probably stuck to describing the semantics but explain how it was implemented was easy (i.e., lazy). I'll try not to do that in future! :)

[hyperthunk]

All messages from process P to process Q are ordered (whether they are sent directly to Qs mailbox or to one of Qs channel)

Without this guarantee it becomes very difficult to write robust algorithms (for instance, a monitor message might "overtake" a message sent on a channel). This is still under debate. However, if you are using the TCP transport (which, currently, is everybody) then we do have the stronger guarantee.

I'm not entirely convinced this is worth worrying about unless you're using @simonmar's new matchChan primitive. How else would you receive channel messages in conjunction with regular messages, given that channel messages are handed to their ReceivePort completely independently of the regular (untyped) mailbox? Of course your point about TCP preserving the ordering is correct, but that is almost irrelevant when talking about ordering over channels and mailbox entries: the order in which you receive will be determined by the order in which the match h, matchChan h2 list of rules is provided will it not? And if you do not grab messages using receive [ match a, matchChan b, match c ] then there is no correlation between the process mailbox and channels whatsoever.

Unless we were to handle incoming channel messages differently it would be difficult to make this property hold. I can see the argument for wanting to have channel messages ordered along with regular messages, but it's going to make the mailbox implementation even more complicated and hamper things like issue #105 and more importantly #43 . And will we preserve ordering over multiple channels without using mergePorts et al in that case, given that we're trying to preserve total ordering over multiple input streams?

I think the simple solution here is to recognise that ordering is preserved for the process mailbox and ordering on channels is preserved per channel but that's it. If you are using channels for input data and using monitors, then you've got to manage the potential races yourself. Better to keep processes which use monitors focussed on the mailbox and use typed channels where you have a specific fixed domain of inputs across one or more channels and manage these yourself. Of course I'm willing to be persuaded otherwise, but currently I suspect the costs outweigh the benefit.

[edsko]

No, I disagree. Ordering is very important. For instance, I might want to wait for a reply value from a server on some typed channel, but at the same monitor that server so that I don't wait indefinitely when the server dies or I lose my connection to the server. This requires matchChan, granted, but that's precisely what it's for. But now ordering becomes very important: if the server terminates after replying to me, then I want to be sure that the monitor notification that the server is now dead does not overtake its reply to me.

[hyperthunk]

@edsko - you make a compelling argument for ordering there. I'd be inclined to use a middleman for the monitoring and make the reply channel typed as data Reply = ActualReply T | NoReply DiedReason or some such. Whilst this introduces some non-determinism, it simplifies the caller somewhat and is no less dependent on the NT layer's guarantees than what we have using receiveWait [ match m, matchChan c ] afaics.

I want to be sure that the monitor notification that the server is now dead does not overtake its reply to me.

My reading of CQueue right now is that the order in which the matches are given has priority if there is data already in the mailbox. Once we go into blocking mode waiting for the incoming channel we still fold over the matches once we've received something. The use of STM means that each match that fails causes a retry of the remaining/next matcher until we've actually received and handled something.

Using the current implementation, I don't see how we could hold the guarantee for channels too without reliable ordering in the delivery mechanism. Right now we're completely relying on the system queue receiving messages in the expected order. If the system queue delivered the monitor signal first then the code in waitIncoming would pick that up and hand it over as the result of dequeue. There's nothing in CQueue that attempts to preserve ordering over typed channels and the process mailbox and you'd need to merge all the typed channels input streams into the incoming stream in order to have that afaict. Even then the network layer could break things if it was unreliable. That doesn't sound like a fun task, though I suppose it's plausible.

I guess this is the reason for your comment:

However, if you are using the TCP transport (which, currently, is everybody) then we do have the stronger guarantee.

[edsko]

Yes, the network.transport layer guarantees ordering per lightweight channel. At the moment CH uses a lightweight channel for the main mailbox, and then other lightweight channels for each typed channel that is created. The TCP transport multiplexes all these lightweight channels to the same TCP connection, which is why we have stronger ordering guarantees. Other transports (such as a UDP transport) may do this differently.

What needs to happen (once it is agreed that these ordering guarantees are important) is that CH uses a single NT lightweight channel for each destination endpoint. This doesn't change the NT layer at all, just how it's used at the CH layer.

[hyperthunk]

Ah ok I see. I hadn't picked up on that aspect of the wiring between the two, but now you mention it I can see that from the node controller code. This should not then, affect the CQueue implementation at all, as it'll be dealt with at the node controller by switching to a single lightweight channel for all comms! Nice.