Tuesday, 13 November 2007

Modelling Objects, Modelling Processes (2)

Well I am starting to write this at 2:25 so I will be brief today. The following account is based on what I learned from David's draft discussions on the metamodel for UNIFI 2.0 even though my understanding may still be shallow. Communications from Matthew (especially his Pierce interpretation of message delivery) have also given me a fertile ground to start from.

And yet another source, an experience --- today I saw a piece of software which is up and running and which I may call the first genuine conversational/session programming working in the real world (not my creation). It is not only working: it is superbly working with every bit fully working. But on that perhaps a month or so later.

* * *

We were discussing about how we position processes

As I wrote last time if we wish to have a foundational model then we start from a process and its specialisation being an object.

So a class model will be about a process (or let us call it a conversant) and if a conversant is so special as to have only call-return then it is an object.

This works of course. But if two communicate they need messages. These messages are mostly passive (this is not the pi-calculus view: but is a practically relevant view I believe).

And components of these messages may as well be described by class models.

This is one of the reasons we may start from objects and classes. Then a process which converses should be a special kind of an object. That is
some objects are also engaged in "conversation". They may be called conversational objects.
A conversation is different from method invocation since it uses a channel: moreover we assume there are another "thread" in the interacting party and they converse even though they can interact in the "co-routine" fashion.

Note the idea of conversational objects above conforms to Maxims 1--3 we discussed in the preceding post.

Now an object can be engaged in a conversation as a result of being invoked: and an object can also be invoked in a conversation when it is born --- automatically after its "initial state" (in the state diagram sense).

Suppose Alice, Bob and Carol are conversing. A message Alice sends should belong to a class which Bob understands. That is there should be a class model which encompass both Alice and Bob --- or at least we wish to have signature (structure) compatibility.

OK so we have some picture. This can be written as a diagram. I did not start from a "user" in UML (though this is natural). Here a "class" can be considered as a "participant (actor) in a role". We may as well wish to have a company like Amazon in this picture. Say this is a rectangle part of a UML use case diagram (that system with which a User interacts). Then where is a rectangle?

Well why not to have a rectangle? Put it around Alice. Note Alice is now a class: so its instance converses and perhaps we can colour Alice since it is a conversational object. In many cases (if we use conversations for programming-in-the-large) this object may as well be an object which only does a conversation and no method invocation any more (Alice has this to say: "I do more complex things now so how can we go back to that simplistic model even though I do have nostalgia"). Perhaps we can colour its border with orange to say it is a class for a conversant object.

I will upload some diagram (hand drawn so please do not expect much) which shows an instance of this. For now note that we have here
  • three rectangles (participants)
  • a specific class model for each which may be rather deep in hierarchy
  • a common "shallow" model (or models) for messages
I do not wish to say this is one class model articulated with three "local enclosures" for each participant: in general we do not need a common class model even for message components even though this may be very useful in practical concerns and if we can afford this may be good to have (if you can easily have transparency in some cases why not to have it --- especially given one of our current primary applications is a meta-standard for different protocols).

So perhaps we may as well have a common class model for message components? Another thing which can be useful is a notion of a role which one can consider is a way to relate two conversational objects by saying "these guys are the same" or "these guys are essentially the same except wearing different colours" (say). Note however we need to write down a conversation between these two conversants: they are from the same template (they are instances of the same class) but when they converse they should converse as different persons.

One possible way (I do not say the best, we need more examinations) is to have a class model and consider about "using" one class in two participants --- by sort of projecting relation. This means we can also make two roles related by a class hierarchy.

This means we can have the following different kinds of class models in our conversation diagram:
  1. Individual class models for each participant (deep)
  2. Common class model(s) for message components (shallow)
  3. Common conversational class model(s) for common or related roles (shallow)
At this point I do not know how useful 3 above can be: that point as well as all points including the basic setup, we shall examine from now on through use cases.

Today I will finish here. In the next post --- perhaps tomorrow --- we shall think about how we can adapt several standard diagrams for conversaitons, starting from tje use case diagrams.

Thursday, 8 November 2007

Modelling Objects, Modelling Processes (1)

Modelling with capital M: that is what I am thinking here.

UML centres on objects (consider the class models, which are a lynch pin of this whole modelling framework). What are differences between objects and processes?

Not processes in any difficult sense: we need to think of them since they are the entities who converse. We are trying to describe conversations, so we naturally need to have the ontology of conversants --- if ever we want our modelling framework to be wholesome. It may also be better to be clear that I am not talking about "business processes" here even though it is closely related. I am talking about processes as a central concept in modelling: that is my discussions are purely from the viewpoint of modelling concerns. We need to position it as a fundamental notion for abstraction and modelling.

As Robin Milner observed in his recent short note, modelling is about explanation. So a process explains --- some behaviour, some structure. What is a process, what does it explain, how does it differ from an object?

It's better to start from a process. A process is an entity which interacts. Here "interaction" means it exchanges messages: it sends messages and receives messages. That is what a process does. And perhaps we want it to have its own state. So here is a simple definition:
MAXIM 1: A process is an entity with interactional behaviour and its own internal state.
The use of the term "interacitonal" may not be common, we can call it "interacting", I did not use the term "interactive" since this term may sound as if it is about human interaction. No, a process will usually interact with another process.

But this looks like quite like an object: what is a difference? An object has:
  1. attributes
  2. methods
And this second item carries an object's behaviour, doesn't it? Here we come to the first key difference between processes and objects:
An object may interact by method invocation and return; processes may interact with the outside in more varied ways --- it will have a series of interactions part of which can even be done in parallel but whose interactions as a whole form a meaningful structure.
In other words processes are engaged in a conversation: and patterns of conversations include, as a very special case, a method invocation and its return (including an exception return). That is
MAXIM 2: the behaviour of objects as we know of is a special case of that of processes: that is, an object is a special case of a process.
Note here I am exclusively taking the modelling viewpoint: of course a process may be implemented using objects, but that does not concern us in the present inquiry. Here we are trying to find steps towards an abstract entity which can be a basis of modelling the kind of software which predominantly consists of mutually and concurrently interacting software --- and perhaps the development of such a kind of software may become a lynch pin of software structuring methodologies in near future.

The modelling viewpoint demands us to stipulate --- make it exist --- the minimum essential structure of an abstract entity we are now struggling to build. Incidentally Maxim 2 offers us a hint: if so we need the same thing as an object in a process. How should it be named? Can it be something readable from the outside just as an attribute of an object? Or should it be strictly local to that process? But let's be conservative, we can change it later, this is anyway an experiment, we use the same term as an object:
MAXIM 3: a process has its attributes whose content defines the current state of a process.
Now this is a decision: and a necessary decision for that matter. And we have two more things to think given Maxim 3, answering (or trying to answer, let's be honest) the following two questions:
  1. Can a process get engaged in two or more conversations at the same time?
  2. How about messages? Perhaps messages consist of objects? Then don't you need objects before processes?
I will discuss these points tomorrow: for the time being I just give yes-no answers (which are not answers we are seeking but gives us a starting point at least): for 1 the answer is yes, and of course this necessitates us to think about shared mutual data. This is the concern treated in a corner of UML (so-called "active objects": on which there are a lot to discuss) but will become a basic concern from now on. Exploring this topic may need some time. For 2, again (and perhaps surprisingly) the answer is yes: we assume the existence of objects as our prerequisite. In fact conversations need messages and messages should be defined from some components. Well we could have started this discussion from messages as our expert colleagues are doing now in UNIFI.

But that will also be a topic we shall treat later. For now we finish this initial part of an exploration.

Monday, 29 October 2007

modelling needs meta-modelling!

I finally came to know about this: and this is not a simple tautology (tautology is a proposition which is always true). This is practical.

We are talking about domain specific metamodel. And this is the key to the use of meta-modelling as I am now starting to learn from David's recent note as well as rereading of his book.

One simple way to see this is to think about naming (whose importance in modelling has been stressed since the ancient times --- it is even in Michael Jackson --- though my understanding on this matter came from Matthew Rawlings). Now naming has at least the following two purposes in modelling:
  • to make something existent which has not been existed (well to be precise reify but I think this may not be too far fetched)
  • to make this stage prepared for future usage esp integration but also for maintenance and evolution and all that
So names are important especially for integration: but how then can we make uniform naming useful for integration?

One of the well-practiced answers is a dictionary, a dictionary of terms and conceps which are used in modelling. But this means a dictionary should cross over individual model elements, that is it should be at a meta-model.

From a different viewpoint, modelling can easily be lousy. And even good models are hardly useful except when they are equipped with useful helping infrastructure, including model transformation, assertion checking, automatic template generation, etc. (consider MOF transformations David discussed in his book). Without such infrastructure we do not have a good use of models themselves except as the means of communication --- but even the latter becomes much much more efficient with the use of metamodels which govern and guide them.

And this has a direct relevance to the design of Scribble --- even though it is a general-purpose language for describing interactions (well it is domain-specific in the sense that it is about interactions, but as such it is general purpose, and from the viewpoint of MDA too general-purpose --- so we do need be ready for domain specificity --- and here am I revealing too much? As it is reflected on Scribble's design we shall report on this and other columns).

NB: I am sorry updates this blog are not done so much recently: this is because I am busy in two fronts: (1) logics for interactions (motivated by both foundations and from Matthew's ingenious *short* treatise); and (2) understanding (meta)modelling to be reflected onto the design of the language. I also confess I am writing many technical papers, since to communicate something new one needs to prepare people's minds --- on this point perhaps we can discuss later. But on scribble, our main topic now is modelling and meta-modelling, which will prepare for other associated technologies such as DBC.

Tuesday, 23 October 2007

On modelling

We shall soon publish here and in other places a compilation of examples in scribble (an updated version). But a recent news I wish to report is that I am learning aboug modelling in UML sense in practice --- from David's writings and from ongoing discussions in WG4 (I am lucky I could listen to the first-rate modelling experts and domain experts engaged in actual modelling through conversations).

As an interim report I found that the modelling is about articulation of such things as:
  • cardinality (n-m relationships)
  • part-of relationship
  • subtype relationship
.... all these kinds of relationships among entities. And by stipulating these relationships it is defining basic ontology of software to be made, or of messages to be exchanged.

So a modelling defines existence. That is why naming is so important in this endeavour.

This gives us the following observation, apart from my interest in Scribble: this level of "basic-ness" is needed if we are to introduce specification of interactional behaviour at the core of the modelling framework. I mean, at the same level as class models and associated diagrams.

This new element should be, if to be introduced, for defining the basic ontology of behaviour.

In other words and more concretely, I want the kind of technical discussions currently being carried out in WG4, or (in case you are not there) that standard modelling steps when we build entities and their relationships one by one, to be done at the level of interaction behaviours --- about the rules of exchange of messages.

Of course through the current discussions I am now concious of the challenging nature of the ontology of messages themselves, which is already new to the world of modelling --- and my (perhaps not too short) experience in the world of theory can easily let me see the value of having true experts in such technical works --- since they know the most important thing is to start from basics and to have a lucid understanding of it, gradually one by one: what a pleasure to see this unfolding in real-time!

So --- albeit, or all the more because of, my personal interest coming from scribble --- I will for the time focus on the understanding of ontology of messages by listening to these conversations. Why not, this is most exciting, I am learning a new attitude to the understanding of computation.

Tuesday, 9 October 2007

Copenhagen 2

Just in case this is of any interest to you, this is the abstract of the talk on logics I gave in Copenhagen. My thanks go to Lars Berkdale and Thomas Hildebrandt for hosting my talk.

An Observationally Complete Program Logic for Higher-Order Functions

Time and Place:
October 3rd, 11:15-12:30, ITU Copenhagen

If you have a program and run it, then it usually shows some behaviour. This may take the form of interactions with a display, a printer, or communication ports. More closely looked, its main interactions may be with an operating system, libraries and other software. Anyway it has a certain behaviour, which can be useful, can be disastrous, or can be enjoyable.

A program logic allows us to describe such software behaviour using logical assertions. It often also enables syntactic derivation of valid descriptions. Such a logic may as well have a semantic basis, in the sense that its assertions discuss all and only observable behaviour of programs. One of the well-known logics with this property is Hoare's logic for first-order imperative programs, developed on the basis of Floyd's assertion method.

This talk is about extensions of Hoare logic to higher-order functions. Extending Hoare logic to higher-order functions (which also underlie such popular languages as Java) has been known to be one of the subtle issues for decades: this work uses ideas from the pi-calculus to develop such an extension. The logic allows clean, precise description of higher-order behaviour and has several strong completenesss properties. In this talk, I will illustrate core ideas of the logic using simple examples, discuss its completeness properties and their proof methods, position them among related works and its extensions, and point out several remaining topics.



It was a great visit --- Nobuko and I went to ITU last week.

First night we were roaming around Kongens Nytorv. Then we happened to walk into a placecalled hviids vinstue --- this should be since I kept a card --- and this was a place where a lot of locals are drinking and singing, and the man who looked like an owner is playing a piano.

I may not say he is a master. But he clearly had a musical soul. It was unmistakable.

There are two ladies who were taking care of the place, aperitif is good and food is ample and simple if not exquisite. A basic danish food which is edible. Many locals, as I wrote, and even somehow two local british --- one with a strong welsh accent --- were there, one of whom has his portrait on the wall, I think he is an old customer.

We also have a black singer who roamded into the house, all sang Danish songs and this master with a music spirit, an old man who was fat and bold and not with a great voice but so deeply driven by his inner urge to sing so you cannot help joining (if you knew Danish) it was one of the most welcoming nights we could have in a foreign city.

We can discuss about another restaurant but I will leave it for another occasion.

* * *

By the way Matthew sent me a mail about Physiognomy --- what was it about? Is it a new idea about asynchrony? He did find another asynchrony in communication recently. He is a man of asynchrony. He also calls telephone "telephonum".

So another question: did Romans use telephone?

[added a couple of days later: it turned out that he wrote "teleplenum" which means a conference via telephone, so this is simply my misconception. It also turned out that "telephonum" has some useful meaning but anyway he (nor Romans perhaps) did not use this word.]

* * *

I am currently too occupied with a few absorbing (one of which not so unrelated to scribble) subjects my colleagues and I have been working on so could not proceed with scribble: but Gary is proceeding with the design of 10 subjects --- 10 google docs we share --- at this moment. I will join soon. A basic part of this language will be complete in a close future. Well almost *now*.

Friday, 21 September 2007


I have been so lazy: I cannot believe it.

What is happening?

Well many new findings: and discussions: and I think we shall have a roadmap soon.

But in this blog I will proceed one by one, illustrating each construct through examples.

Because of the difficulty and subtlety of our goal, because of the beauty and simplicity we want, because of the coverage of the descriptive tools we are making, it is best we proceed one by one.

Since interactions are everywhere and since many people seem to be approaching this idea from many angles --- from the observation that transaction is too restrictive for huge systems; from the observation that sharing and using financial protocols together is really beneficial for users; from the obvervation that we should share the infrastructure for message passing since in business we deal with messages not call-return; and from the need to describe applications and even operating systems as concurrent modules communicating with each other --- it does seem a good paradigm for describing interactions is being desired.

A paradigm --- or abstraction: we surely need a good abstraction or abstractions to articulate, model and describe, as well as building such interactional systems. And tools. And rules. And of course good implementation ideas. Everything. But we need some abstractions to start from.

A conversation is only one of possible such abstractions, a modest proposal from us and some of our friends. We recall it was once named session: it was also named contract; it was also named protocol. All these names give one side of this idea. Whatever it is there seems to be something which may be usable here: something concretely usable, at least for some purposes, for scribbling interactions nicely and clearly. Scribble is an experiment to create a new piece of a descriptive tool (or a family of tools) based on this abstraction.

It is for scribbling: so it should work with a simple setting of pencil and paper: but of course it will make the best of all software tools and artifacts and infrastructure we can avail.

And starting from a smallest conversation which is just one-time interaction done alone, and reaching a conversation which consists of 10 million messages or even more (in the large scale this is a norm in international financial protocols such as SWIFT; and in the minuscule level this is again a norm in on-chip interconnect which easily allows 1 million message passing in a second), we have many conversations and its phenomenology (or zoology if you like) never ceases to surprise this one of the humble designers of scribble. These are what we should capture and I now realise it is a fascinating journey we are now going through.

Today I finish here: I will continue with the choice example in the next blog. There are some who have new examples --- which we may be introduce when here is a chance. Let's also treat it here. Scribble is about a conversation so it is not surprising we are starting have several conversations. And conversations are never just one way: ideas are merged and interwoven and will lead to further budding ideas. This blog is just a record of such conversations surrounding scribble.

Saturday, 8 September 2007

channel or port: a problem of English

I have not posted for some time: during that time I thought a bit about difference between port and channel starting from a chat with Matthew which let me recall what Gary cautioned me initially. For a channel one can read as follows from wikipedia:
Channel in communications refers to the medium used to convey information from a sender (or transmitter) to a receiver.

Well this is what Gary and Matthew told me: a channel is a path between two endpoints rather than a place at which we send some datum. The latter is called port:
A port is an interface between the computer and other computers or devices. Physically, a port is a specialized outlet on a piece of equipment to which a plug or cable connects .... (etc.)
So a channel is a path whereas a port is an interface; and our declaration syntax:
channel chWorld @ World;
looks somewhat strange since a channel cannot be located at an endpoint World: and I can now see why Gary suggested I should use the term "to" as in:
channel chWorld to World;
but at that point I did not precisely see what he was getting at. And then Matthew said a channel is like English channel and it is not a place which you throw a message at and well it is quite right. And I realised a channel in the pi-calculus is a name for a channel and as such it is also a port since it is also an interface: it is a name. A name can be given to a path/medium (even perhaps a path which can be shared by many inputs and many outputs) or to a port and in such a basic formalism as pi all these different notions come out by different usage of names (just as objects and functions and streams and all that can be represented by specific ways of name passing in this calculus).

Perhaps more understandably, one may also say a name in the pi-calculus is a name of a channel: and if we regard that channel's input capability is fixed to some process then it becomes a port of that process.

All in all the main point is we can use "to" if what we are declarting is indeed a channel, as we did above. Alternatively if it is to be a port which we wish to declare --- as the prefix "at" suggests --- then we may as well write:
port pWorld @ World;
Then we can write:
pWorld.greetings(string) from You to World;
which may not be so bad after all.

But if we have two participants which share a port to receive how does it look like?
port pWorld @ {World1, World2};
So pWorld is a port --- an entry point --- in which a message may arrive, to be received by either World1 or World2.Well this sounds slightly magical --- how can a port be placed in two disparate locations? --- and in fact it now sounds more like a channel.....

So may we come back to channel?
channel chWorld to {World1, World2};
Well this makes a better sense: chWorld is the name of a medium, a path, through which a message will be passed to one of these participants. We did extend the idea of "one sender one receiver" idea above, but a communication medium in computing can be more versatile than geographical ones and indeed this generality is a matter-of-fact in the pi-calculus (note however a receiver is almost always unique: we consider a single receiver a default and perhaps even prohibit multiple receivers in some class of applications).

And if "from" is not specified then it means (in principle) anybody can use that channel for sending his or her message as far as a protocol as a whole is well-formed. Here "well-formed" means we do not have a message mix-up as we have seen in Example (1) Asynchrony a fortnight ago (which is here) (by the way having multiple senders may not be so bad in comparison, this time the medium is something like having multiple inlets and a single outlet: we can visualise it as a filter: and of course we can also have a multicast channel too in which a message is always copied to each outlet).

OK so perhaps a channel is still a good idea and we are going to use "to" instead of "at" or "@" when we declare the receiver(s) of a channel: that looks to me more and more natural. But if you have any observations please let us know!

Monday, 3 September 2007

Example (11): one by one

I admit what I wrote yesterday was an off-topic --- something was complete so I got slightly relieved.

Anyway we prepare for auction protocols: now an auction has a lot of constructs in it (unicasting, multicasting, loop, perhaps a global escape, choice, ...) so perhaps it's a good idea to introduce each of the basic constructs one by one. Our simplest protocol so far is one for the "hello world":
protocol GreetWorld {

  participant You, World;
  channel chWorld @ World;

  chWorld.greetings(string) from You to World;

where we declare this is the protocol, we declare its name (GreetWorld), then we declare participants we shall use as pure names so that models and programs can bind later, and we declare a channel we use.

Recall @ indicates the locatedness:
  channel chWorld @ World;
says that (1) we use the channel chWorld and that channel is located at World: World is the participant who can receive messages from this channel.

When a channel is declared, it will not be bound to anything later: a declared channel is entirely a logical entity inside a conversation (if you are familiar with the pi-calculus it corresponds to declaring a channel with "new"). This is like a method name (selector) is a pure name and is logically independent from any external entities. Or perhaps better it is like a locally declared variable which gets generated when a method is called and discarded when the method returns. So declaring a channel as above means specifying this channel is local to a conversation which will materialise this protocol.

This is subtlety of channel, how it is different from participants, and that which is important when we consider a protocol which allows the description of unbounded conversation structure.

Once we have everything declared we can have an interaction --- we formally call this interaction signature as distinct from conversation signature, but let's be simple --- which is:
  chWorld.greetings(string) from You to World;
The interaction says You (in fact somebody who is bound to You) will send a greeting to World via the channel chWorld. As we have discussed, we are assuming asynchronous messaging which will travel through some network infrastructure --- that expanse. The phrases such as from You and to World can be changed heir positions so we can say
to World from You if you like. Sometimes uniformity does pay for a quick understanding though.

To leave no stones unturned let's see what this
which is the message You will send to World. Here greetings is an operator name --- or a selector, quite like a method name --- and string is its argument type. Like method names, operator names are internal to a protocol. So a message (logically) in this interaction will/should consist of an envelope which is this operator name and its content which is a string.

But what is the use of this operator name? In OOPL we had a method dispatch table and we need to go to an appropriate code: but how does the operator name have use in interaction? Just as the mechanism of dynamics in OOPL, logically or as embodied in the design of VM (in the sense of JVM, not VM as in Xen), this operator name is closely tied to a key mechanism of conversation-based interaction which is a finite state automata which governs conversation behaviour. In brief an operator name serves as a transition label in FSA. So when a state in a FSA has several choices it is different labels which are used for this purpose. Of course logically (just like method names) it serves as a way to indicate what this message is about.

We shall come back to this point later. Here we note there is a simple way to go without an operator name and it is using a type name instead of an operator name, like (presenting the whole interaction):
  chWorld.string from You to World;
where we specify only the type, not a selector. This works well especially when you are sending a specific message type as in:
  chWorld.Greetings from You to World;
In such a case the name Greetingsserves as both the operator name and the message content.

To this topic we shall also come back later. I think this is enough as detailed examination of these basic constructs.

My original purpose was to introduce the next most basic constructs, sequencing and choice, after I briefly examined what we introduced already, but this prelude took long: I will continue with sequencing and choice in a new post, perhaps a couple of hours later.

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:
http://www.somewhewre.org/xsdrepository 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=
"http://www.somewhewre.org/xsdrepository 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:
ch1.bid(integer) from Bidder1 to Auctioneer;
ch2.bid(integer) 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.

Tuesday, 31 July 2007

Before Next Day

Some note is due on the difference between signature, class model and behavioural description , before going into the next day. These three form (roughly classified) layers of descriptions of software, sequential or interactional. We take the existing (OO) practice as an example but the idea is the same layering also applies to or needed for interactional software.

(1) Signature: this is for example
int foobar(string, int)
which does not have a variable: it only has the name of the method (operation) and the types for argument and the result. For a class it includes all of its public methods and all of its field variables as well as its superclasses: the whole pieces of the information are called class signature.

(2) Class model: here we have a class signature augmented with, for each method
int foobar(string s, int i)
we add a variable. We can also add various constraints in the relationship between classes and their fields such as aggregation, n-to-m relationships, etc. A good thing of having variables is that we can now have DBC going all right: for example we can write using an informal syntax (for a formal syntax see Chapter 4 in Frankel's book):
int foobar(string s, int i) {
assert pre: s!=nul and Even(i);
assert post: Odd(result);
where "result" is a special variable for indicating the return value. The two assertions as a whole say that:
When you call foobar, you should specify as its arguments (1) a non-null string and (2) an even integer and then foobar will return an odd integer if it ever terminates.
Note we are using argument variables (i and s) to specify the precondition: a beauty of clas models is that we only need to have the signature and these variables, combined with field variables as needed, to specify the overall behaviour of a method. They are very good legs (of course if you specify the body of the method you can further annotate the statements with assertions). So class models offer very good legs for further modelling artifacts and tools, MDA-oriented and otherwise. The importance of the relationship between (1) and (2) is that these legs --- class models --- have class signature at its core: robustness of the former comes from that of the latter and the usefulness of the latter becomes substantiated by its use in the former.

(3) Behavioural Description: On the basis of class models we reach behavioural description. Here we can use varied techniques but a most familiar one is to prescribe how your system behaves by programming language you like best. One basic point: it is impossible to synthesise (3) from (2) in general and most practical cases: if we can automatically come up with non-trivial programs from specifications then we can solve essentially any number theoretic problems. No need to despair since DBC is useful precisely because of that: this allows declarative description which is independent from how the behaviour is implemented.

* * *

For the design of scribble, it is good to know the distinction between (2) and (3): and for (2) understanding how it is induced from (1). In (2) we have no control structures, no assignment, no function calls: however it offers foundations of software upon which these elements are built one by one.

In the initial design of scribble we focus on (2) together with the basic parts of (3) which should be useful even for the concern of abstract modelling. The distinction is fundamental for both practical usage of scribble and conformance to the UML architecture: but it is also fundamental for us to be able to smoothly go between these two, just as we can go between (2) and (3) smoothly in object-oriented software development.

Monday, 30 July 2007

First Days

1 In the beginning there were interactions. Then interactions formed conversations. There were more conversations from more interactions, filling the earth. Conversations were separated from non-conversations.1.1 This was the first day, when we first had conversations.

2 A conversation needs conversants. So it was said, ‘Let there be two or more conversants in each conversation.’ 2.1 Then conversants are separated from conversations, and so are called participants. This is how participants came about. And there was evening and there was morning, the second day.

3 Interactions in a conversation need be addressed at ports, to avoid confusion, since confusion was evil.3.1 It was said, ‘Let there be one or more fresh3.2 ports for each conversation.’ Ports are separated from conversations, and so are called channels. This is how channels came about. And there was evening and there was morning, the third day.

4 It was said,
‘Let an interaction in a conversation be with an operator and values since it gives us both rigour and freedom.4.1 A decree therefore said:
An interaction consists of a channel, a participant who sends it, a participant who receives it, and an operator, and messages.
This was the fourth day: it brought a decree for an interaction.

5 And it was said, ‘Let a conversation be thoroughly distilled and the result be separated from a conversation, called the signature of a conversation, and in it include the participants it uses, the channels it uses, and the paths a conversation can take, where a path can branch or loop or escape.’ Signatures of conversations were separated from conversations, and so were called protocols.5.1 Each conversation has a protocol, and obeys a protocol. This is how protocols first came about. Two conversations which have the same protocol are similar. Two conversations whose protocols differ are not similar.5.2 This is the fifth day: we now had protocols.

Comments: We covered a lot in this first post. Two more posts are enough. "Separated" means an idea is articulated as an independent concept, like from water we find liquid and coldness etc.

1.1 Separation of a conversation as an independent structure is the starting point of this whole design endeavour. Historically this was first done (perhaps) in cryptographic protocols and later in UML sequence diagrams as well as in message sequence charts, and with more type-theoretic inclination in session types.

2.1 It is assumed that even if a participant has two threads they are not to converse: you can use sub-conversation (and sub-participants) so this does not lose generality.

3.1 If Alice sends to Bob two messages in parallel and do not wish to incur confusion then Alice can send it to two channels at Bob and Bob receive them as distinct messages. Channels can be omitted from scribbling in some cases though they are always implicit in descriptions.

3.2 Here "fresh" means (like variables declared inside a block) each channel is made fresh for each run of a conversation.

4.1 If we wish to be without an operator use a default operator "send". The use of operators is to use them as labels when we abstract a conversation as a finite state automata. So it is good to use them. Scribblers may as well start very informally however: our language formally defines how we can be informally in different ways.

5.1 A protocol is extracted from a real conversation, distilling its fundamental structure as a finite state automata. A protocol should not contain any concrete expressions nor their evaluation since if so it is not "thoroughly distilled": it should only contain static structure and should still be able to check whether a real conversation follows a protocol or not just by checking its program text (this is the MDA part of the signature). A real "class model" (which we shall call "conversation model") will include a little more than this, but it is good first we fix the notion of signature, since unlike signature in OOPLs we do not have this idea explicitly beforehand.

5.2 Thus a protocol can be used for classifying whether two programs realising conversations are similar --- in other words we can check whether a program conforms to a conversation structure given by a protocol. A protocol is a way to classify conversations, just as a class is a way to classify objects.

[to be continued to the next post, moving to internal structure of conversation]