Wednesday, 29 August 2007

Example (10): Import again

How can we parametrise our protocol descriptions with respect to document types? In other words how can we import opaque document type so that we can instantiate it later?

("opaque" may not be a good word, what I mean is its content is not visible now.)

This is the problem of late binding. Consider the following protocol:
import Invoice, Order;

protocol BuyerSeller {
    participant Buyer, Seller;
    channel chSeller @ Seller, chBuyer @ Buyer;

    chSeller.order(Order) from Buyer to Seller;
    choice @ Seller {
        chBuyer.invoice(Invoice) from Seller to Buyer;
    } or {
        chBuyer.outOfStock(void) from Seller to Buyer;
In the first line we are importing two document types: one may as well consider them coming from a default name space (say from the current directory): this means that by varying the content of a file named "Order" the definition of a protocol varies --- this protocol is parametric over the content of two files in the current directory.

Alternatively we can be slightly more sophisticated: we can set the default name space by an enclosing environment (say a model description which uses this protocol): then one can bind Invoice and Order into arbitrary XML namespace-based names (which includes the use of URL). Here again we are using late binding but through the explicit use of an enclosing context.

This is more organised and general, and in fact subsumes the first approach. But what is an approriate precedence in the way we bind these names? For example:
  • if we have a binding from the enclosing context then it should precede:
  • if not then we shall try to look at the default name space;
  • if there is no default name space or if that name is anyway not bound then it will go to the current directory (well that is the default then) and we try to find file of the same name (perhaps with some suffix --- there are too many suffices these days so I am wary of introducing but for example sdd --- for scribble data definition --- seems not used yet).
We also want the import clause to be able to describe direct bindings to all basic data types such as arrays and vectors and all that; and wish to be able to import Java classes, UML class models, XML schemas. We wish to have packages and we wish to have hierarchical directories (folders) and we wish to refer to somewhere on the web via URL as a location of the schema file (such as xsd files). Once imported, we wish to be able to call it not only by canonical (qualified) names but also by their local names or even aliases.

We may call the name used in Import clause designated name.

One thing I should remember: since document types are also used as (part of) selectors and becaue selectors are a key component of finite state automata (as transition labels) hence are essential for ensuring "non-mix-up" in the face of asynchrony and parallel and all that, we need to have a good way to:

  1. At editing/validating/compile time: check if seemingly different two document types (given by local names or aliases) are really distinct or not: so if there is a binding in the above sense we need to go back to the original.
  2. At compile time: give distinct identifiers to distinct document types (this is possible largely because selectors are meaningful only within a conversation at least in principle).

The identifiers in 2 are used for execution. And as Greg Morrisett said, it is often a very good idea to carry types at runtime even if you have "compiled them away" so we shall carry canonical/qualified names at runtime as much as possible.

As to 1 when there is no binding present of course we treat two (Invoice and Order) to be distinct types: so one safe way is to impose this distinction whenever we have a binding --- if two distinct opaque names are bound then the targets should also be distinct documents.

Alternatively we can treat a canonical name with an opaque name as one when we think about signature. One thing which looks a bit of an issue in this approach is that it does not allow textual replacement of an opaque name with the target of its binding.

On the other hand it has a merit of allowing the following procedure:

(1) We check consistency of a protocol --- even that of model/program descriptions conforming to it --- statically and compile it.

(2) We add bindings by enclosing environments (programs etc.) perhaps at the time of module composition (lazy binding).

(3) At runtime we want (because of (1)!) everything works all right.

Now suppose at (2) somebody insists that he wishes to use the same document format for Invoice and Order (well unlikely but anyway we can assume such a situation): then the validation in (1) becomes meaningless.

If we take the "two-in-one" approach, this issue is gone away.

Or perhaps we should take the "two-in-two" approach: that is we take the designated name for the signature used in selectors; and for data formats, use the real format. we distinguish these two.

So there are quite a few things around here, and that's quite interesting. Gary and I are at least understanding the whole domain, so I am sure we find at least one good design soon.

Tuesday, 28 August 2007


Rapid progress...shared deepening of understanding...

And inevitably a philosophical point arises:

--- conversation channels are internal ("pure names").
--- participants are external (bound to some real things).

This is rephrased into more concrete:

--- conversation channels are managed inside a conversation at runtime.
--- participants are not: they need be bound to external addresses.

Or into more technical:

--- conversation channels in a protocol are bound once they are declared.
--- declaration of participants does not induce binding.

(see for example this wikipedia article for binding and bound variables)

A conversation as an interface --- simultaneously insulating and connecting the implementation-free abstraction of interactional behaviour from/with the outside, the world, that expanse, implementation design, efficiency.

For example suppose zero or more participants can dynamically join a conversation one by one, to interact there. Then the most abstract layer of conversation descriptions, its signature (protocol), does not have to say how this join is done --- since it is about the outside. But how they may interact once they have joined, that should be described in a protocol description. And this subtle event where an outside and an inside meet, namely how joining is done, we can naturally describe by going up one level, when we treat a model. In a model, we treat externals. Since we can. Since we want. Since we already have a core called signature...

Sunday, 26 August 2007

Example (9): importing document types

Before treating the Christie's auction protocol I discuss a series of examples --- since perhaps I have to treat basic features first. This also gives me time to explore the world of diverse auction protocols which Andrew kindly introduced me to. So when we come back we shall have a compilation of real-world electronic auction protocols in scribble.

The following protocol for hello-world was already treated:
protocol GreetWorld {

  participant You, World;
  channel chWorld @ World;

  chWorld.greetings(string) from You to World;

Now suppose we have a very nice XML schema for greetings and you wish to use it as a message format. What do you do? Here is how it goes:
import greetings.xsd;

protocol GreetWorld {

  participant You, World;
  channel chWorld @ World;

  chWorld.greetings.xsd from You to World;

This protocol definition starts from an "import" clause which imports document/data types as well as other definitions (for example protocol itself) from outside. Above we assume a package hierarchy (which can use among others a standard directory/folder hierarchy) and that, in the same directory as this protocol definition is stored, there is an XML schema called greetings.xsd. We are not specifying a target name space here but we do not demand prefixing the schema with "noNameSpaceSchemeLocation" but if you like we can use the familiar XSI notation:
import xsi:noNameSpaceSchemeLocation="greetings.xsd";
(Above division into multiple sentences has no effect, as usual.) Note the import clause is still prefixed with "import": this makes clear (in our curly-brace syntax) that this is about importing a document type.

Similarly we have two ways to import an XML schema (or other data/document formats) using URL (not specifying a target namespace for simplicity). The first one is a simpler one:
import greetings.xsd;
which defines the xsd file we need. Once imported, you can use the format as greetings.xsd (or even just greetings if there is no confusion). Or if you wish to use a long format you may write:
import xsi:schemeLocation=
" greetings.xsd";
which has exactly the same effect.

Various data formats (including UML class models) can be imported in the same way. Incorporation of these data types of course means that, when we specify behaviours, we need to find a good way to fill and extract datum from such a data format: this is the concern when we move to conversation models and behavioural specifications and not needed for protocols (i.e. type structure).

The notations for importing various document and data formats are important for practical usage of scribble in the area of (among others) financial protocols: the above is a tentative idea and we ask for your ideas and observations to make this part very good, for now and for future.

Friday, 24 August 2007

Example (8): Auction (preparation)

Gary gave me a real auction example (the original one he did not put it in the auction setting: it is I who did so. Then (after Andrew's discussions: and he has an example of many staged interaction with a Greek chorus and which is about Destiny of Human: and then he also knows somebody from Chrstie so I think he likes antique; some people do like it; then Gary gave us a better way to describe auction interaction which partly uses Andrew's idea; which I wish to take up now).

However due to lack of time I only give its informal description:

(1) Auction announces the good (an old Georgian chair with signature of Shakespeare)

(2) Everybody got angry

No that is not that suppose everybody anyway decided to do a bidding

(2) Each bidder will go into a loop of sending his or her bids; may repeat zero time or once or many times. Of course each time Auctioneer should say something and say "that number of 10 pounds" etc I think (that bit unclear to me)

(3) When some fixed time has passed the auction is done and Auctioneer will announce the winnder (do we say winner)

So what we take up in the next post is to describe this example in our conversation type (signature), as a protocol. Then we may also be able to discuss a bit about how we can elaborate it as a model --- which can have more information but still declaratively.

Thursday, 23 August 2007

On signature and model

A note may be useful about distinction between signature and model. In essence a signature (say a class signature) is the core of the core of a class model and its program, something nobody dispute they are basic, programmers or modellers.

But how come? Why nobody has a dispute? Well signature in OOPLs or functions is a minimum structure by checking which it is guaranteed that your program can run without type error (assuming the lack of hardware/OS/null-pointer.. errors which we cannot completely take off). So if your program invokes methods following their signatures and in turn these methods do the same (this is a recursive definition) then all should end well --- as far as type error goes.

A model (in the sense of UML class model) is different. For example consider a natural constraint that a class only has a single instance: this is easy to specify and we do often specify in class models: but Java does not have it as part of its type structure, indeed its realisation as a code is that you restrain the behaviour of its constructor: it is declarative at the model level but it is operational in its realisation.

This is the same as how the collection of instances of two classes relate in numbers and many other such specifications: but these specifications are useful in models if their realisation as a code is messy.

And this is a good thing: all such constraints and specifications at the model level are usually easy to impose as far as we consider disciplined programming (or we can indeed do MDA); further, at the level of models, we may wish to describe many features which are not too detailed operationally --- in fact even those features whose realisation may not be uniquely determined behaviourally such as:
"This program will return an even number regardless of its input"
"In this conversation Alice may speak to one of her boy friends"
that is a model can be non-deterministic even though our target behaviour is deterministic. Also the distance between models and programs allows extensions at the level of models more easily than without. And when a model is sufficiently constrained or restricts its concern to structural properties then semantic gap can usually be filled using APIs and other semantic layers.

* * *

For some time we have been and we shall be focusing on signatures, not models, in this blog, though we may discuss (as a preparation) models and behavioural specifications in some cases (behavioural specification corresponds to say UML action semantics). So while I am sure some may find what is being presented a bit too simple and too terse please wait.

However signature is already quite rich in its power of description: it has repetition (loop), choices (and you have some choices as to choices), parallel, inner conversations, recursive conversations, sequencing, even merging. The signature offers building blocks for the whole description languages including DbC in the present context: so we shall have a plenty to see for some time.

And then we shall move to what corresponds to class models (called conversation models): and then we shall move to behavioural description. And all this is as dictated on the Sixth Day (which is recorded here).

Example (7): Signature for Hello World

Well it just occurred to me: how about this one line protocol? Everybody has written one or more "hello world" programs in your pet languages and here I give the signature for a hello world in scribble:
protocol GreetWorld {

  participant You, World;
  channel chWorld @ World;

  chWorld.greetings(string) from You to World;

Note this is a signature, so it does not specify what you would say: there are no values mentioned. So it is called GreetWorld rather than HelloWorld. It says that you will send a greeting with a string --- perhaps "hello" ---- to the world through channel chWorld.

As we have seen we can have a simpler version which does not use the operator "greetings":
protocol GreetWorld {

  participant You, World;
  channel chWorld @ World;

  chWorld.string from You to World;

or perhaps you wish to use the formatted string as in C in which case we can write:
import formattedString;
protocol GreetWorld {

  participant You, World;
  channel chWorld @ World;

  chWorld.formattedString from You to World;

Well we have not introduced "import" yet: this is the keyword to import data types and protocols from outside, usually from files deposited in the same directory as this protocol is defined. So it declares that we use a non-primitive data type called "formattedString" in this protocol. We shall later illustrate how we can use diverse data formats in our scribbling, both in signature/models and in behavioural description.

So in this way we can send a formatted string such as "hello world/n" from you to the world --- for example consider channel "chWorld" is bound to a port of a printer then your message will be printed there, after travelling through that vast expanse. This is the hello world in the era of communication-centred programming (more variations on the same theme later).

Example (6): Concurrency

First in case my yesterday's post is misleading, a note: I have a high respect to those engineers who have devised or are devising ingenious algorithms to simulate many significant trends in stock markets: I just pointed out a wrong way to use such algorithms as a way to point out what I believe to be a good engineering and scientific discipline: but I have no doubt that engineers who are at the cutting rdge of developing such algorithms are the very people who are aware of paradoxical nature of human behaviour.

Some report: Gary and I are proceeding, and perhaps some progress about notations for dynamic structures: I hope to report them soon. Anyway today I shall continue with examples, and along the way illustrate the constructs we have introduced for scribble.

Now a little bit about language constructs: the constructs for OOPLs can represent a vast array of OOP patterns, those which have been known and those which have not been known: so defining the basic constructs may be a bit bold (even crazy?) thing to do. In case you do not get a good idea: think about deciding that "while" is a good construct: why? It is less free than goto: why not goto? Yes may be it is more structured: but is this the only reason? There is something very basic on this decision, something so simple and therefore basic, which makes this construct used again and again, in C programs and Java programs surviving changes of hundreds of ISAs and hardware architectures.

So it is somewhat more scary thing to decide on "while" than deciding on ISAs (my apologies if you are a proud hardware designer: well well well each has its own view and a way of saying we should admit).

For us, without the pi-calculus and accumulated process theories we can do nothing of this sort. We have been hacking with this for a long time. But then we shall come back to that point later. Here we go into concrete examples.

* * *

Well where was I? Yes a concurrency example and we wished to introduce channels:
Bidder1 -> Auctioneer: integer;
Bidder2 -> Auctioneer: integer;
We wish to say these arrive at distinct channels since there can be a confusion: since Bidder1 and Bidder2 are asynchronous; since asynchrony is one of the basic laws of (an important class of) computation.

And then Gary said:
Channel aside, this "->" is no good, it looks like field selections, all in all no designer, no programmers would like
so we introduce a new notation: he is a designer, he is a programmer, so who else knows better? So we arrive at: from Bidder1 to Auctioneer; from Bidder2 to Auctioneer;
which reads:
  • Bidder1 will send a message of type "bid(integer)" to channel "ch1" and Auctioneer will receive the message via ch1.
  • Bidder2 will send a message of type "bid(integer)" to channel "ch2" and Auctioneer will receive that message via ch2.
Above "bid" is an operator name: just like a method name encloses arguments in method invocation, we in general enclose messages using an operator name. But it can in fact be omitted if you like. In that case this becomes:
ch1.integer from Bidder1 to Auctioneer;
ch2.integer from Bidder2 to Auctioneer;
whose meaning should be clear.

A channel is a logical entity which gives a sender and a receiver the rule of engagement:, a very simple one but an essential one:
If a participant send a message to some channel, then it will arrive at that channel.
If you know about distributed systems, you will say: well why do you know? Maybe a message can be lost! Well that is quite true and we can in fact even consider Byzantine failure (such as message corruption or a participant getting crazy). But it is the same thing as sequential programs: when you write x=1;y=x+x; there is in fact always the possibility that, for example, instead of 1 we have 2 assigned to x (this goes back to Wittgenstein-Kripke's private language argument).

Anyway it is quite true that in distributed systems such a possibility is much bigger than sequential systems. Moreover such failure can happen here and there without failing the whole site. So we should have some assumption here and it is practically as follows:
We assume a messaging service such as AMQP which gives us a reliable messaging with high assurance and with a small amount of out-of-order messages.
I do not go into details of what we mean by AMQP-like messaging service: it suffices to say that we can safely assume that applications we are considering here --- financial protocols --- are most likely running using such a transport. And in Internet, we can of course use that beauty called TCP.

Now logically put, we are generally assuming the following conditions (though this is not the sole conditions we can assume: this is just a default assumption which is useful for us to stipulate for most of the times, and the notation and its theory scales to other situations):
  • Messages are delivered safely.
  • Messages from one address (endpoint) to another address (endpoint) arrive in the order they are sent except for very few occasions.
Well this is just the repetition of what I wrote: the small rate of OoO messages allows us to recover order-preservation in the presence of conversation structures we are stipulating: so just consider there are no OoO messages. We call these conditions, the (underlying) transport conditions. Assuming the transport conditions, we stipulate the following for our channels (the first one below is a repetition but just for clarity):
  • If a participant say Alice sends to a channel say Ch then a receiving participant say Bob can receive that message from channel Ch.
  • If a participant say Alice sends to a channel say Ch two messages say M1 and M2 in this order, then M1 and M2 will arrive at Ch in that order: that is, Bob can receive these messages via Ch in this order.
Well that's it. This assumption of course gives us, in the presence of a conversation structure, the following nice property:
If Bob knows a conversation structure then Bob knows M1 and M2 will come in this order hence even if they are of different types Bob can expect how to interpret them: there is no room for type misinterpretation. Safe and fast.
Isn't this nice? So you in particular does not have to have many channels for each different type: no need for that. Usually you only have one channel for one participant and only when you need to get messages in parallel (suppose a movie distributer sending an encrypted DVD file and its preview and perhaps also an invoice in parallel to you and perhaps you wish to have some negotiation in that "invoice" conversation?). Of course physically you may as well be just multiplexing messages so that all are coming in one pipe: but it is also possible two banks are using their respective many workstations to process messages to different channels concurrently: you can also do that.

That is, channels are logical entities: they are not tied to any such notions as:
TCP connections, IP addresses, public URLs (though you can use long URLs to implement channels), etc. etc.
they can be implemented in a way you like, in fact in each instance of a conversation you can use a different implementation, as your need and whim dictates. But as we just wrote, it is precisely because it is abstract that this entity gives us good hooks for implementation, it gives implementers flexibility. And thanks to the signature for conversation we know any of these implementations work well, as far as the above two conditions on channels are met.

So channels are important: so before using them we need to declare them. This is done in the following way. Recall our interaction specifications:
ch1.integer from Bidder1 to Auctioneer;
ch2.integer from Bidder2 to Auctioneer;
Before scribbling down all this we first need to declare participants:
participant Bidder1, Bidder2, Auctioneer;
You may imagine this is the same thing as:
participant Bidder;
participant Bidder2;
participant Auctioneer;
and you are very right. Now after this you declare channels:
channel ch1@Auctioneer, ch2@Auctioneer;
Here the "@" notation indicates locatedness: so the above one line is saying both ch1 and ch2 are residing at Auctioneer, or more precisely Auctioneer is a person who will receive from the channels ch1 and ch2 (we can again write the above one line in two lines which we omit).

So as a whole our somewhat incomplete protocol can be written as follows:
protocol aLittleBitOfBidding {

  participant Bidder1, Bidder2, Auctioneer;
  channel ch1@Auctioneer, ch2@Auctioneer;

  ch1.integer from Bidder1 to Auctioneer;
  ch2.integer from Bidder2 to Auctioneer;

We can read this protocl from the top to the bottom just as easily as we can read a very short verse in Mother Goose (in particular Mother Goose itself) if not as much a fun. There are still a few things to discuss about such declarations, and we should also discuss about data/document types to be used in a protocol. Well we can leave those things to later posts: all in all this is how we can write the signature of a conversation.

(Acute readers may be realising that some of the scribbles above can be omitted: well we were already told there are "Full Scribbling" and "Fast Scribbling" and this is the full one: we later discuss about "fast" one but it is always a good idea to learn the basic then learn how to skip several things and still get the same effect, so please be patient.)

* * *

It got long today: let's finish here. In the next post we shall touch one subtle aspect of channels as we use in the present conversation models (which you can safely forget immediately after you learn them but is something better to know once anyway): then we shall either move to a ramification of the auction protocol (following a recent exchange between Gary and Andrew) or perhaps discuss how we can do Christie and its variations in the present protocol language.

Tuesday, 21 August 2007

Things to come

I do not have much time today so I instead list below examples which will be treated in this blow from tomorrow.
  • Gary's two liner revisited and ramified
  • A trader's protocol aka "Persistent Seller" protocol (it continues to send you new quote until you say yes), and its ramification
  • "am I first?" "am I first?" and "whichever!" protocol, which is part of FpML and which Steve seems to like
  • Andrew Parry's Honey Convention protocol ("hi, have you been to...")
  • Oriental Bazaar protocol
  • Matchmaker protocol
  • Going round and round (but not a round robin) and getting bigger protocol (from FpML again)
and many more, well some examples may be too complex so we may treat them independently.

We shall enjoy through all the examples: strolling is the best way to reach our goals for sure in such endeavour. And we shall treat such topics as significant of interoperability in data format, how meta-data can be used for this and other purposes, perhaps asking a help from a real expert.

So see you soon, and let's ramble on...

Monday, 20 August 2007

Example (5): Concurrency

This post is to say there is always some means if we know clearly what a trouble is.

Let's reproduce Gary's example:
Bidder1 -> Auctioneer: integer;
Bidder2 -> Auctioneer: integer;
By our Rule of Thumb (see Example (2)) we can read the above signature thus:
Bidder1 and Bidder2 will send their prices asynchronously, while Auctioner expects the price from Bidder1 first and the price from Bidder2 next.
But we ask: can this be possible? For example suppose Bidder1 sends £1,000 and Bidder2 sends £2,000: it is important that Auctioneer knows which is which. But since messages are asynchronous, they should travel over the vast expanse of networks, those bids may not arrive in the order Auctioneer want.

So some means is needed: well in fact there are several means.
  • Use the "reordering scheme" and distinguish two messages by their content, say some field: for example we may include "sender" field.
  • Ditto but this time distinguish mesages using different signatures --- that is eitherdifferent message types and/or different operator names.
  • Do not use "reordering scheme" but use distinct channels: Auctioneer now owns two distinct channels, one for Bidder1 and another for Bidder2 and each of them send to distinct channels.
The first option may seem to work but in fact it is a reasonably bad idea: for example even the same sender may send two messages from its two distinct threads. Moreover the runtime at a client-side should go deep into a message content to check whether it is a correct message or not. And further suppose you wish to encrypt your message via an end-to-end means.

The second one is a feasible idea: while it is not as robust as the third one (channels) it can surely be usable in some situations and perhaps we do not wish to prohibit it. So for example we can write:
Bidder1 -> Auctioneer: BiddingMessage1;
Bidder2 -> Auctioneer: BiddingMessage2;
Or alternatively we can use:
Bidder1 -> Auctioneer: bidding1(integer);
Bidder2 -> Auctioneer: Bidding2(integer);
where we assume "bidding1" part is an operator, like a method in objects: the idea of signature allows us to go between message types and operators seamlessly.

However this approach, while not too bad, can have a problem for example in the following situation:
parallel {
   Alice -> Bob: hello();
   Bob -> Alice: hereiscake(Cake);
   Alice -> Bob: thankyou();
} and {
   choice {
      Alce -> Bob: hello();
      Bob -> Alice: hello();
   } or {
      Alice -> Bob: goodbye()
      Bob -> Alice: goodbye();
This is a complex situation: in one conversation Alice and Bob exchange greetings and Bob offer a piece of cake to Alice: on the other Alice and Bob can be engaged in a slightly more sublte dialogue. Since we may wish to edit each conversation separately (and we may add other parallel conversations as we like) it may be a good idea to make these distinct conversations to be targetted to distinct channels.

A simple exchange such as:
Alice -> Bob: hello(Letter);
Bob -> Alice: hello(Letter);
can be considered as using default channels at each participants. It is very natural to consider Alice has one or more channels at which she is waiting to receive messages --- but belonging to that conversation. For simpler conversations you use only one channel, but if you have many conversations going on in parallel, its' good to distinguish these threads using separate channels.

From a theoretical viewpoint we are saying channels are used as units to maintain causality chains --- subconversations on distinct channels can be considered, in principle, as causally unrelated: so sequencing across channels does not matter, conversations can be monitored independently across channels, and you have reliable and highly effective basis to do various optimisations. We shall be touching each of these points in our subsequent posts.

When we use channels, there is a natural notation for interaction. We shall introduce them as well as further motivating the introduction of channels through examples.

Thursday, 16 August 2007

Example (4): Concurrency

Well too many examples on one day may not be good so I just list the two-liner contributed by Gary.
Bidder1 -> Auctioner: integer;
Bidder2 -> Auctioneer: integer;
Here there are two Bidders and one Auctioneer: the Bidders send their respective bidding prices to Auctioner.

By our Rule of Thumb (see Example (2)) we can read the above signature thus:
Bidder1 and Bidder2 will send their prices asynchronously, while Auctioneer expects the price from Bidder1 first and the price from Bidder2 next.
Let's discuss in our post tomorrow what richness the simple signature above hides behgind it, as our previous two-liners did.

Example (3): Asynchrony

We take the last example we looked at:
Alice -> Bob: integer;
Alice -> Bob: string;
and examine it again from a different angle.

Suppose Alice and Bob are using some messaging service which usually delivers messages to the same target in the order they are sent but sometimes, if rarely, fail to deliver them in the sending order, even though it does guarantee (at some level of assurance) the delivery of a message.

So one day what happened is the following message delivery
  1. Alice's string, sent later, arrives at Bob first
  2. Then Alice's integer, sent first, arrives at Bob next
Well this does not look like a big deal. But if we consider the following scenario the situation looks somewhat grave:

Buyer -> Seller: PurchaseOrder;
choice {
   Buyer -> Seller: ConfirmPurchaseOrder;
} or {
   Buyer -> Seller: CancelPurchaseOrder;

We are assuming the following business scenario:
  1. Buyer sends to Seller his purchase order (of type PurchaseOrder: consider this as an XML schema or a UML class model)
  2. Buyer then will either:
  • confirm the purchase order by sending a document of type ConfirmPurchaseOrder or
  • cancel the purchase order by sending a document of type CancelPurchaseOrder
(So "choice" allows us to write a scenario where there are two or more possible ways a conversation branches into: we shall illustrate it more fully in our later discussions.)

Now suppose a preposterous delivery of messages occur between the initial "purchase order" and, taking the second choice, its cancellation: on that day, by some hiccup of a router or something, before a purchase order message arrives at Seller, its cancellation message has arrived. Then what Seller sees is:
  1. Seller obtains a cancellation of some purchase order
  2. Seller then obtains that purchase order
which is problematic as to what Seller should do at Line 1: should it ask Buyer (for example) about what this nonsense message means? Or should it just discard this cancellation?

The answer is simple: because Seller is aware of the conversation scenario ("signature of a conversation") she is now in, she has safe knowledge that this first message is in fact a second-message-to-be which has arrived too early: so she saves this preposterous message and serenely waits for another message to arrive: and, when it does arrive, she can reorder them and start from processing the purchase order. In practice, such a reordering can of course be done by a runtime which manages conversations and associated message passing, insulating applications from troubles: or in some cases such a service can even be offered as part of a messaging service (does AMQP do this, now or in future, or should it be better left to runtime? John? Alexis?).

Above we are assuming the messaging service guarantees message delivery (up to some assurance), even though we can easily combine timer with it: in that case when Seller cannot wait any longer then she can simply time-out. We can think of other ways to treat different unexpected situations.

But in what way does this story of mix-up and re-ordering of messages have to do with signature of conversation? Well what we have been talking about is the use of the signature in the world of interaction: it allows you to expect what to come, and so it allows you to act on non-default situations in a methodological way. (Well by allowing you to expect, it of course also allows you to get disappointed, but you can at least be sure whether you should be pleased or disappointed, and if so you may also be prepared to deal with the latter case better than otherwise).

Such a use of signature is in fact close to how the signature for methods/functions is being used. Our simpler predecessor does not entail something as exquisite as reordering of messages, but it does allow you to interpret a datum you get, or check whether the datum you get is of the expected type or not. It allows you to expect, to make clear what is expected and what is not expected, and thus allows you to treat both cases in a principled way: you have no doubt (or you know how and when to have doubts and what kinds, which is the same thing).

This principle is also closely related with monitoring, as we shall discuss later.

So we have seen how a simple two-line scribbling can contain richness we may not have imagined. With his we end Matthew's examples on asynchrony. In the next post we move to another two-liner, contributed by Gary.

Example (2): Asynchrony

In the previous example:
Alice -> Bob: integer;
Alice -> Carol: integer;
We have seen that there can be a sequencing at the source (sender) without having the corresponding sequencing in the targets (receivers). A simple variant of this is:
Alice -> Bob: integer;
Dave -> Carol: integer;
In this case even though it is written in a sequential order the sending itself cannot be done in this order: it is done by different senders so that it is most natural to consider this is just a way to write: the same thing can be written as:
Dave -> Carol: integer;
Alice -> Bob: integer;
This seems to invalidate the idea of "sequencing": anyway we often wish to write down interactions as they come into our mind, so let's not worry. Our "not worrying" in fact means something like the following: if we scribble
Alice -> Bob: integer;
Dave -> Carol: integer;
Bob -> Alice: string;
and this is the whole conversation then we as a reader consider it as meaning the conversation
Alice -> Bob: integer;
Bob -> Alice: string;
and the conversation:
Dave -> Carol: integer;
done in parallel. This "in parallel" can be written as

parallel {
  Alice -> Bob: integer;
  Bob -> Alice: string;
} and {
  Dave -> Carol: integer;

which means there are two conversations in parallel: one may consider this is a "normal form" of the original three lines. In the new, and more verbose, presentation, the conversation as a whole is given as the parallel composition of smaller conversations each of which is now sequenced. For example

Alice -> Bob: integer;
Bob -> Alice: string;

is sequenced depicting the situation Alice first sends Bob an integer and then Bob sends Alice a string.

Looks ad-hoc? Well there is a simple rule underlying all this. That rule says: if

(1) Alice (say) appears in one line and
(2) Alice appears in a later line (combined by the sequencing semicolon ";")

then Alice's respective actions are in fact sequenced.

So in particular if we write
Alice -> Bob: integer;
Alice -> Bob: string;
then we assume Alice sends to Bob one integer then she sends to him a string: there is indeed a sequencing.

In the next post we consider further (and somewhat subtle) examples of asynchrony.

Wednesday, 15 August 2007

back finally

Well I have had an untimely flu: only today I am fully back. During my rest in bed I have been having a thought (and dream) about the use of conversation structure and its potential: I will continue with examples but I'd like to also post some of these ideas when there are slots.

I will be back soon, after replying all mails which I could not reply while I was sick in bed.

Thursday, 9 August 2007

a report

(1) I have a flu
(2) inspite of (1) rapid exchange about design with Gary ---32 long mails per day
(3) new development in UNIFI giving a basis

I will continue with examples when I will recover. Digests of (2) will also be posted here (it is not apt to list them as is since many of them are *very* long).

Wednesday, 8 August 2007

hot and cold

(Because of the weather the next post will be done in 12 hours later.)

Tuesday, 7 August 2007

Example (1): Asynchrony

The following is Matthew's example (well he had a few and this is the simplest one). To write it down we do not yet use our scribble notation: we borrow the standard notation people use for cryptographic protocols. We write down a signature using it.

participant Alice, Bob, Carol;

Alice -> Bob: integer;
Alice -> Carol: integer;

The first statement is declaration of three participants. Then it says Alice sends Bob an integer. Then it says Alice sends Carol an integer.

And that's it. What's a big deal about this description?

(By the way you may say we have not followed Decrees from those Initial Days: don't we also need to specify channels and operators in an interaction? We shall come back to this, but let me just note it is not that we are unfaithful: let's just say for now we are starting simple and concise.)

The question Matthew asked is this:
OK, I can see Alice does these two sendings in sequence: that makes sense. But how about the ordering of arrival events?
We are assuming here, as we should inevitably do so in most real-world settings, an asynchronous message transport such as TCP (and as in TCP we may also assume the preservation of order of messages when they are from a common source to a common target: but this point deserves a lot of discussions, and fortunately or unfortunately interesting discussions, so let's do not consider about it here, anyway this assumption is not needed).

So we assume asynchronous communication: but then since Bob and Carol are different participants, hence may as well be located in different sites, there is no guarantee that messages arrive at Bob's and Carol's in this order.

So we realise that these two simple lines are not as simple as it may look. Each interaction takes place in that vast expanse: a message should travel through it, which takes time and efforts if the latter usually hidden from users' eyes, in that expanse which to us looks as if it had been existing for eternity. So we may interpret the two lines above as follows:
Once upon a time, there were participants Alice, Bob and Carol. Alice sent two integers consecutively to Bob and Carol in this order: and Bob and Carol would receive these messages targeted for them, though we do not know the order of receptions, they would go over this expanse. And that is the end of this scenario, which happened a long time ago.
Since this is a scenario there is indeed no tense: it can be about something that has happened, it can be something which is happening (and there can be many instances of it) and it can be about what may take place in future. Anyway the scenario --- or signature --- says that there are two consecutive sendings and there are two unordered receptions of them.

So this is the story of the two line descriptions above --- indeed we have more discussions about these two lines, many more. But they can be left for later: this is enough for today. In this first example we have seen that we cannot ignore the existence of that expanse through which interactions travel through, though our expression of this understanding is done abstractly since we are interested in modelling.

Friday, 3 August 2007

Why it has been so hard

UML does not have something like class models for symmetric interactions ("symmetric" in Frankel's sense), for communicating processes.

Java does not have a typed high-level abstraction for communication, each of its API is tied to low-level transport.

Why it has been so hard?

Because communication looks bottomless. Well it is bottomless. When it comes to sequential computation you have a bottom --- the machine code. So you feel safe. That is a hardcore of computing to which you can always return to. Somewhat paradoxically this gives a good basis when we try to have high-level abstractions for programming: they have a basis to build on, a home to come back to, a hard kernel against which you can bang your abstraction, and so you are sure that what you are doing with your abstraction is not imagination.

But where is communication? Where can we find it? Is it in routers? Is it in the (hard-wired) algorithm of Ethernet, listening, talking and waiting? Is it in algorithms for switch? Is it in the protocol stacks in each endpoint? Where is its rockbottom? Where can we start from and go back to and test your abstraction? It looks too complex. It looks that what makes up communication is completely ad hoc and a hodgepodge of heterogeneous machineries involving so much interplay among many kinds of software and many kinds of hardware. There can be no general theory here and there can be no general abstraction here not to speak of such basic things as, for example, "signature".

So is it too bold (or even ridiculous) to consider a general modelling/programming language for communication? Not quite: since after all we are not going to be bold at all. We wish to make something useful. And it looks we do need something --- something flexible and (at least modestly) comprehensive and comprehensible: something in fact simple and which serves our purpose. We take this stance, a utilitarian, practical stance. Foundationally we have the pi-calculus. But let's take that story as the undercurrent for some time, and continue our practical thread of thought.

As such the next post will treat examples (and inter alia illustrate the events on the sixth day). à bientôt!

Thursday, 2 August 2007

The Sixth Day

6 It was said, "Let there be languages for scribbling conversations: since it is good to write down and share. Let there be three languages, one for outlining, one for foundations, and one for enriched details." And it was so. And according to the kinds of conversations there were made many outlines and foundations, called patterns of conversations. Then it was said, "Let patterns include other patterns, details include other details, so that they be fruitful and increase in number without too much scribbling. But you can even scribble fully a pattern inside another pattern, a detail inside another detail, so that they can multiply anywhere you like. Indeed let the languages be enriched with Rule of Scoping (that is Brown's decree). And let foundations rule over details, while details enrich and give feedbacks to foundations. Let this be Fundamental Rule of Conversation." So conversations can now include conversations either by name or by texts and they are built on foundations.

And it was said, "We will give all three languages a good Way of Descriptions, common to all: start from declarations of participants and channels, then move to interactions which use them: this is the Rule of Description: declaration first then description." And it was also said, "We will also give all three languages, Rules for Fast Scribbling. They will be yours for scribbling as fast as you like without ruining rigour. But you can also respect Rules for Full Scribbling if you like. It is good to be explicit (this is Matthew's decree). So be fruitful and increase in number."

And it was said, "Modellers, do not hate Programmers; Programmers, do not hate Modellers; I give each People, a whole language, and these languages will have many fruits each with enlightened seeds in it, so that you can write what you like in the style you like and get what you like. They will be yours for your hearty scribbling, do it to your heart's content. And to all modellers and programmers of the earth and all the designers and analysts—everything that has the breath of digital architecting life in it—we give these languages. And so these languages, one for foundation and one for enriched details, and many others which will elaborate these two, will work together very well, so you can work together very well."

It was said a language of assertions helps design, so it now elaborated both foundations and details. So patterns relate with each other by assertions, specifying reciprocal responsibility (this is Frankel's decree of Design by Contract).

And it was said, "Let the languages for scribbling interactions take different forms so that scribbling can be done by two- and three- dimensional drawing, for many who like drawing. And let there be good tools for scribbling, including Projection and Runtime (which are Marco's and Ray's)." And it was also said, "Let all these languages for interaction work well with other useful tools and languages which are on the earth for good reasons."

And we saw all that had been made, and it was very good. And there was evening, and there was morning—the sixth day.

Thus the languages for interactions on the earth were completed in all their vast array.

By the seventh day we had finished the work we had been doing; so on the seventh day we took rest from our work (obviously we were very tired). And we were happy (that is I hope we shall be happy) because it is always good to have tea or lunch or Vodka after all the work of creating that had to be done has been more or less superbly accomplished.

(An acute reader may guess there is a further tale which details events that took place in a garden in the east: the garden of architects, where we shall find Humanity in Digits: but that demands a different time and occasion: as is often said, there is a time for everything.)

NB: Comments on the events on the Sixth Day will be presented as independent posts, one or more for each topic: since each topic, such as DBC, will demand not a short footnote but a wholesome technical discussion.