For our shared enterprise

When I am working on theories of conversations, what strikes me is not the fact new ideas just continue to come out (though it is true: out of me, out of my colleagues, out of many people, --- I note this is not birth without pains, all birth is with pain, here we need constancy in a series of births, that is the technology I am learning now) nor the fact that they are deeply based on theories of types for functions though with new effects and new forms (and again this is true: and I wonder if it is the case that it is only when one needs to face concurrency in earnest that types become so essential that nobody can ignore them, they become central to computing, even if its significant portion was developed by those people who love these strange animals called higher-order functions which may look somewhat Ecclesiastical to some --- but even in C we can use typed higher-order functions which is indeed very useful in practice).

What really strikes me is the fact that these ideas come out as if they are predestined --- as if these notions exist from the first, buried here and there to be discovered, and we are just doing a work of discovering. If I am permitted to "draw water into one's fields" (this is a Japanese idiom to excuse a positive remark about oneself, which is regarded in Japan a bad thing, in a way similar but subtly different way in Britain) they are born in perfection (though with some pain!), like Pallas Athena was born perfectly clad (or armoured?), they come out as if what we are doing is nothing: I am being used: this was out there from the first.

Of course this does not contradict the significance of a philosophical general grasp of what a conversation is and what it can be --- which is very human after all --- my dialogue with many academic and industry colleagues, --- for academic especially colleagues those I interacted with on session types, including Vasco, Kaku-kun, Kubo-kun, Mariangiola (my respect to her for her genuineness towards our profession and subjects, that purity in interest which can encourage people's best part), Marco, Dimitris, Ray, Andi, Nobuko, and many others, --- and industry interactions, especially earnest, concrete ways Steve and Gary work with so-called business protocols --- how enriching they are in the end! --- and prompted by visceral and yet deep grasp of distributed computation by Matthew Rawlings as well as his many examples, some strange (like the birthday present protocol and its variations) some quite business-oriented --- prompted me to think about this notion from the depth. From the real depth.

I am being driven. And this seems not solely because of the desire to communicate good findings to our colleagues --- which is by the way surely an honourable motivation and is further a socially useful one. It looks it pertains to another desire, more modest and hidden, a desire to understand this virgin territory, to explore this new terrain, --- that attracts me, since this realm, it is being born like Pallas Athena, is so rich in what it can give us, and it also seems to extend to a vast hinterland not known even vaguely now, though my modest talent prevents me from spelling full details of what may be out there.

My colleagues and I reached initial theories of session types without knowing the key philosophy --- the simplest philosophical observation --- what a session or conversation is, what it can be. But it also looks I knew about it --- since if not we could not have arrived at that shape (I know: the answer is that it is simply practicality that let me settle on there together with the depth of interactional computation distilled in the shape of name passing, that small but greatest calculus: and of course both of them --- this practicality, this name passing --- are still most mysterious). And I also know it is the recent dialogues with my colleagues which equipped me with what I believe to be key insights on session types and conversations. Without these dialogues nothing could have proceeded. Why did these dialogues come about? What made them possible? What brought Gary here, what brought Steve to CDL, what brought Matthew Rawlings to chair a crucial working group of an international standard organisation in this starting point of 21st century? Why Gregor Horpe had this inception that this is something worth calling with a good name? And why at this point at Microsoft they started this operating system project and how can they be so idealistic and moreover start to include even local branching/selection which is the core of session type discipline? And Cedric Fournet, one of the strongest process theorists, why did he get interested in session types? And what brought David Frankel, careful and knowledgeable, to think that some simple and basic change in a popular UML diagram may be possible, at least casually suggesting it?

We are here. And we are seeing something interesting ahead of us. Extremely interesting. We want to see it closely, catch it in our hands, taste it, marvel it from all different angles, come to know it deeply. We are such animals. It is in our DNA. It is worth exploring.

So let's explore. Let's join our forces for this exploration. And make computing more powerful (and yes faster, even faster for a given energy), more exquisite, more stream-lined, more clearly articulated, much much more dynamic (but controllable! if not how can we make it dynamic?), more powerfully and clearly and succinctly and as needed rigorously scribbable, freely moving from high-level sketch with a quick thick brush for hugeness of distributed systems to very fine drawings of individual parts, like drawing a large painting or creating a huge sculpture, it will be kinder to the earth, kinder to us, but can yield a great power if you master it --- "something rich and strange" --- it awaits us. The land is here. Let's work together.

kohei

A note on my old note

This is inside parentheses: I happened to find my immature old memo on a thin book on philosophy (from 2006!) in a web bookshop. It was not about my speciality and the writing was far from up to quality --- I had accidentally posted it after reading this beautiful book and asked the bookshop to withdraw it: and they said they would do so (at that time the site did not allow a poster to cancel such a post oneself).

I suspect it has been there for some time: if so I wonder why I was not aware of it. Now that I found that it has been there at least for some time I feel somewhat stupid to cancel it: after all it has already been public for a while, though I may in the end cancel it, after some time (I should say I spent only a few minutes in writing it, immediately after reading that book).

What I wrote there is not as clear as I'd like my writing to be nor will it be useful for others --- but I do not find the need to add to or retract from that old note, at least what I had written might be honest in its own way, except recording one point: the author of that book is known to be both a great scholar and a political personality; and I am learning about some basics of that social part, on which I wish to unequivocally admit that I am ignorant (that little book however does not refer to this political aspect directly). I am hoping that my learning on that topic, which is slowly proceeding, will be enriched by interactions with my new acquaintance(s) in the modelling and other worlds: since the conversations with sincere individuals whom I respect are what I value most when learning about an intricate historical topic, as well as the reading of those words left by good authors.

kohei

Von Neumann Machine: why we love it.

There are a couple of things we should not forget:

(1) Hardware is about software.

(2) The diversity of software, in size and in behaviour, is staggering: and they should coexist in the same machine.

(3) Not only coexist: they need to do so asynchronously. First they are often unrelated, which is the simplest way to be asynchronous: then they will interact, and an application may demand some service at any point during its run --- we cannot predict --- for example some part of JVM will become necessary abruptly; some part of GNU library; some part of OS functions. That's how your applications work, and that's why these services need always be prepared. They are interactional.

And this is precisely what a Von Neumann machine, combined with the good old operating system architecture, can offer us: numerous pieces of software running asynchronously which may be interacting from time to time (there are further internal interactions which are hidden: we shall come back to them in later posts). Its linear memory is ideal for putting the diversity of data structures and code laid out; combined with its engineering simplicity (and here we do not intend to give any scientific elucidation of this point but just note its beauty and effectiveness coming from its simple profile) we find what this abstract machine model offers us so convenient an ecosystem for software. While the current discussion does not intend to capture the key features of this machine model with precision (for example: what element in VNM enables this asynchrony?), we have at least obtained one way to view its value --- why it is being used and why it is so robust.

There is another thing we should not forget: this model has generality, and we can build our software infrastructure essentially on the same general abstract machine, even if different applications have different purposes, and different programmers program in so diverse ways, so this is just a corollary of Turing completeness, but we cannot avoid reality: software technologies built on a general hardware interface work --- even if it is built in a rather care-free, sloppy way.

Yes that is one of the secrets: without really really good notions of types, without really really good support of assertions, our software is working, in fact if you can program for Mac you can program for PC and you can perhaps program for a mainframe computer and you may even be able to program a Cray machine (well you should study a bit if your program is to run fast and yes this is reaching a different realm but anyway they are after all the same sort of computers!); and layers of layers of libraries, APIs, network stacks, OSes, applications --- they all simply work --- in some ways or other.

So here is the axiom:

if a system of software infrastructures is built on a general hardware architecture, even if they are built with human's fallible skills, and her/his usual sloppiness, without much support from types etc., they may still work. And perhaps it will work very well if we do build infra with good care about foundations.

As to the last part of the axiom above, my argument goes further: in the coming era of inherent concurrency we dearly need foundations if we wish to be effective. But let's not go too fast: let's stick to the problem at hand. In summary our machine model is good fot the diversity of software, in the sense that it gives us a good abstract basis for the flourishing ecology of software, and perhaps relatedly in that it is general, it works with the same general principle whatever your purposes are and whoever the manufacturer of your hardware would be.

And this machine is abstract not only as an abstraction but in its concrete origin: it was not born as an abstraction of the diversity of hardware but rather all these different kinds of hardware started from this abstract machine, first Turing then Von Neumann (in Turing machine we already find the same kind of programming as we do now for Pentium or ARM or PowerPC, an early beautiful example is by Kleene). And when the originators of RISC went back to Von Neumann its simplicity and generality are again made the best of.

So we have been using machine models which are based on an abstract machine with general principles (and therefore can be used for all different purposes) which are moreover based on asynchrony --- if I am to give a very crude summary of the pre-CMP era, this is it. And I believe these criteria are rather basic --- at least in the age computing is and software is intrinsic part of our society, part of our life --- I think these will continue to be basic principles, with some fluctuations. For example any hardware architecture (say a microprocessor with multiple cores) which does not satisfy these properties may not be a good engineering basis for future programming.

In other words: let's not compromise until we reach something everybody can agree on.

* * *

In spite of my promise in my last post I went into software. In fact I am finding I may need to dwell on it for some time, before we can discuss one of the root causes that is making our hardware model asynchronous.

kohei

Asynchrony

I humbly propose: this may be the most fundamental, or at least this may be the word which comes first if we are to choose only one, .... asynchrony, asynchrony in computation, and therefore, asynchrony in communication (two are the same thing, since computation includes communication inseparably, I hope you at least agree it is one way to see distributed computing, that's my hypothesis in these discussions, as I outlined in my previous post) (and by the way just in case you are worried: I am not forgetting about scribble, in fact we are in the middle of it).

Emphasising asynchrony does not mean for example we should assume a communication medium with unlimited bandwidth (and certainly not with zero latency!). And we wish to have different ways to analyse such a medium --- they may be modelled as "ether" separate from processes or formalised as a collection of processes. We may need a queuing model on some occasions. But these will come later and as needed: at this point we do not mind these aspects, we solely want computation to be asynchronous.

But what does it mean to be "asynchronous"? One may define the notion informally thus:

the potential for each distributed process to be able to work following its own local clock, as far as there is no need to be fed data from other programs and synchronise.

First of all, it is about the potential: and we want that potential as a key element embedded in the model. Second, "local clock" etc is not too good a metaphor: anyway it gives us some idea, that a local program can be left to compute on its own as much as possible. Third it says there is some need to exchange data and synchronise --- but not saying how. Not saying it is to compute a function. If it is computing a function --- well that is one way. But there can be other ways. And there are.

Why do we know? We have known about it from the study of process algebras which are about the universe of concurrent, communicating behaviours. And especially because of our study of the pi-calculus which miraculously captures a very rich variety of interactional behaviours, and, as interactions, a wide variety of computational behaviours, in its tiny syntax. And this wide variety --- for studying which one can use many ideas, such as separation which Palamidessi once used in her beautiful and celebrated result. So we know. There are many kinds of behaviours, all couched in a small calculus of name passing.

What is further fascinating to me ---- and this is the first thing which fascinated me in theory of computing and why I started to work on science of computing seriously --- is that this calculus has an asynchronous version, and it turns out to be a minimal meaningful kernel of this calculus.

This point was observed based on the work by Milner/Parrow/Walker in 1989, and later by Milner in 1990, and let's face it I also contributed in my small way and, as I wrote, this incidental observation fascinated me so irresistibly. Later I found Gerald Boudol discovered the same calculus concurrently (and completely independently), in the context of his Chemical Abstract Machine.

Coming back to behaviours --- so I can tell you we have a huge universe of computational behaviours, and many of these things are meaningful, certainly realisable, and they are not always computing functions.

But that is not enough. That fact I knew for long and of course had been known before me by others. What we needed to know in addition is what it means for behaviours to be functions. Then we know the ground --- by knowing the figure. Since if so we know there is more than the figure --- now the ground can be a figure in its own right.

A series of studies have clarified this, starting from an embedding of functions in processes by Milner, and I do not quote them since there are so many, but let me say studies on logic and games (as we call them in our community) play a fundamental role here. This line of studies is still a very rich field and will continue to be.

So --- to make a long story short --- there are many kinds of interactional behaviours which go beyond what compute functions. And for all of them asynchrony is a foundation, a starting point, even though they may constrain asynchrony in diverse ways. So what we see is messages going hither and thither asynchronously. It is wrong to assume order-preservation in the delivery of these messages a priori --- which does not mean we cannot have it based on some mechanism, but can you think of a Turing machine which embeds a notion of objects and classes? Or data structures? Or even procedures... That will make a bad model, a good execution model should have two properties: being simple, and being very simple. And perhaps the third: being very very simple up to the point it almost (or perhaps completely) flat. I know this does not sound anyway informative (I know that) so I promise --- if you are interested --- that we shall come back to this point later. For now it suffices to say that we start from asynchronous exchange of data which may not preserve order. And we do not go into further details here, since probably the party ain't started yet and it is too early to start eating (but is about to, I believe).

For now, we have mentioned several very basic properties. Incidentally the characteristics I observed above are close to what Matthew Rawings once told me --- or declared to me --- as what should be an abstract model for financial networks.

I am not related to money so much (which surely makes me deal with money issues critically sometimes). Neither in my life nor in my profession I feel intimate about how international financial networks carry trillions of dollars each day, that's a different world, anyway it is a huge network, billions of messages going hither and thither each day, distributed all over the world, and this cannot work synchronously, can it? It cannot be order-preserving, can it? So this is something I do not understand in terms of amount of money involved but can surely understand some basic aspects of it in terms of computation involved.

So this story is after all (partly but honestly) about scribble: "One of its primary application areas of this language is modelling of financial protocols." By the way Gary just wrote to me about identities in interactions --- which are a little different from asynchronously operating localities at the abstraction level we are exploring now, but are closely related, and are certainly one of the key subjects for scribble. That is another topic, we shall surely reach there in near future: for now, we need to think a little more about hardware, to cultivate our understanding of this "a" word further.

kohei

Into the imperative depth

Imperative, I am talking about Turing machines, I am talking about Von Neumann machine, I am talking about read and write, but I am also talking about distributed systems. That has been ignored. Models of distributed systems have been ignored: as a result things are not working. At various levels, but especially at deep architectural levels, be it the Internet or multicore computing.

What are distributed systems? Perhaps one simple axiom gives you some idea:

The only way one can know the state of a remote system is to communicate with it.

And another (related) axiom, this time about a general idea to make your program run fast:

Let your program make the most of the available network bandwidth.

In other words it is a good idea to overlap computation and communication since without communication computation cannot proceed: in fact it is best to regard communication (the process of messages being sent and passed and delivered) as part of computation. In distributed systems we can see this in Internet: and in computer architecture we can see this in Transputers.

You may realise we can shorten these two axioms into one:

Communication and Concurrency

That is we cannot have concurrency without communication (in effect). Communication comes first. This is what Robin Milner said in 1980.

Imperative computation has something weird. The most weird thing is it runs. Another weird thing is it seems to become more easily cooked when it is sequential but by itself it has a strong need for asynchrony and concurrency (on this we shall come back in a later post). In other words its usual outlook may be a bit different from what it really desires in its instinct.

There are several things which have not been working: one of these things is models of distributed systems. That is why we cannot see very clearly what is taking place in CMP, chip-level multiprocessing, that is to say things are happening asynchronously and concurrently inside a chip so we say it is multiprocessing and it is happening on a chip so we say it is a CMP. And we seem to be struggling about understanding what we are struggling about. We feel there are difficulties but we do not know what they are.

A bad thing is the same thing seems to be true with the direction of hardware... When transputers were designed there was a clear understanding of what they wanted and that was deeply achieved... The history did not go in the direction of transputers, it is true. And ironically (but in fact inevitably) the other history, which is the actual history we have experienced, again leads to this idea of concurrency and asynchrony for imperative computing. But if you do not know what you wish to do then what will you do? If only so-called marketing is in your mind you see what you believe to be real which is something immediately possible and desirable or at least looks possible and desirable which means it is an answer interesting to almost nobody when it is finally introduced to this world (that is to say we do not see the potential since marketing or at least bad marketing only sees what is visibly desired now, not what is possible, since for the latter one needs true imagination which is different from both a fancy forgetting hard reality or a conformism which again is unrelated with reality in effect). Let me add in a hurry I am not criticising ignorance of others, far from it, since I confess that I do share that ignorance with everybody, in the sense that I do personally feel a severe lack of understanding, which I hope we can make clear together or at least investigate into it.

I think we have forgotten what the Von Neumann machine is about, what struck Alan Turing on one rainy day 80 years ago which started this science, this engineering, this adventure.

(To be continued.)

kohei

How the world is born

I was in Oslo. I was in Reykjavik.

In these places I thought about how the world is born. For example the world of data. If everything is a sequence of zeros and ones then there are no data --- unless they come from data.

When you start to think there are numbers and characters and strings and instructions you start to have data and then you start to have records and tagged unions and objects and all that.

The world of interactions is born in the same way. There are always messages, asynchronously born, issued, exchanged, received, processed. This has been so for thousands of years. There are however nothing we can catch there, nothing on which we can build --- not yet. Only when you single out a streak, or a zig-zag, of messages, some collection of messages, and say "here is a conversation" and you now see not messages but a flow which makes up a conversation, that is, you only have to single out one collection of messages as a flow, as an exchange, that is when a conversation is born.

Then you have many conversations, just as you have many data.

That is how types come about. Types in their basic form are there to single out, and once you learn to single out, once you can de-lineate, put a circle on the ground and find the "figure" (hence the "ground" too) you say (and this is a violent act, in a philosophical sense) there are messages inside (so in fact this is the first time you have seen those messages) and there are messages outside of it, only at that time you start to have a type, since types are there to delineate and describe, you want to say this is a "number", this is a "function/procedure over numbers", a basic form of types is something which can never be separated from individualisation.

I know this part is subtle. I know I need concrete examples. Not today. Here I hurriedly record my further thought from Reykjabik.

Static analysis can make things right and there are many powerful methods: for that purpose we first need something to start with and that is not static analysis. Similarly assertions and logic however snappy your reasoning would be are not something you can ultimately rely on since there is nothing you can ultimately rely on --- when you think you are not relying on anything you are doing so based on some tacit understanding of a closed community (which may give you comfort but which does not give you clarity). No ultimate. So you need to rely on something which has an explicit act of starting. I do not know why this is like this but it is so.

Kripke, a great thinker, wrote about something similar --- about an act of naming. For many "names" no ritual of naming as he described may have actually taken place. What he meant is that it is an explicit act, even if an unconscious act, you communicate that decision of naming, even if one on the receiving side does not see that it is a decision. And how it was fitting for me to think about these acts in Reykjabik, in the world of volcanoes and barren lands, where we need to name, we need to delineate, since if we do not do so we do not have anything to cling to, we cannot (re-)claim a place for human.

(By the way that is why there are only few good names in science and they are what will remain. And science of computing is almost not science --- at least its subject is so new in comparison with what we know as natural sciences or even mathematical sciences. So it has very few good names --- of course we have many fashionable ones but good ones are rare).

And just as yellow is yellow and a dog is a dog we have data, and we reach delineation of the whole collection of messages --- in the past, now and in the future ---- zig-zags of interactions, flows of interactions, we say "here is a conversation taking place" and "this conversation has such and such structure" and I do not think I am proposing this as a new technology, I am describing how it has begun and how it is always beginning repeatedly, just as an act of naming is taking place every time everywhere every now-and-then, but let me tell you this at least, albeit in a low voice: I do suspect things begin like this since I have some recollection of seeing them taka place.

In fact how can you analyse if you do not have the target of analysis? How can you assert and reason if you do not have the target of assertion and reasoning? What do you reason? What do you assert? Of course you can leave things implicit ... but that may be a bad strategy, in the end. And what I am saying is something well-known in science: do not think clever ideas work, clever ideas never work, only deep understanding works. One thing we have known for a long time in science is all good ideas are accumulative and almost uninterestingly built up towards generality and uniformity.

But I am not saying we cannot have that moment of striking clarity, like when Turing wrote to his mother he had found something very different from theories by his contemporaries, that his theory runs.

And it ran, and is running. That abstract discovery (with others' subsequent contributions including and notably Von Neumann's) has led to what we know as computing. And quite a few decades after that discovery perhaps only these days we started to have theories which can describe and understand the meaning of that discovery as science. But that is another story.

I was in Oslo, I was in Reykjavik. Tonight I wrote a few lines from what I remembered there, as well as after I came back to Britain. I am a foreigner living on British soil, and perhaps a foreigner for ever wherever I live. But I invite you to this abstract topos, a forum, since neither is what I pointed out above about science telling us that we cannot enjoy a few conversations, dialogues --- this is the place friends can exchange ideas in a most abstract and most concrete way, in a way which is about something universal but which can only be done in a most personal way, as human has continued to do so since they found this way of conversing and as they will continue to do so as far as human's history lasts.

kohei

Clear, straight and masterful

I hesitate to restart this blog from such a post: and this is about a grim, grave social topic (in which I have had some interest). But perhaps all the more so, it shows the importance of good mind, of good argument, and, ultimately, of good communication (*).

http://www.washingtonpost.com/wp-dyn/content/article/2008/04/08/AR2008040802607.html

kohei

(*) And of a good "rhetorical" question...

The illness which Shakespeare dreaded

My colleagues ---

After time consuming examination of blood and height and weight and all that, it turned out that I have that dreaded disease which Shakespeare sang thus:

Thou cold sciatica, cripple our senators, that their limbs may halt as lamely as their manners

I have not recounted the story of Matthew Rawlings charing in ISO20022, in F2F in December, nor David Frankel giving ever more exacting remarks about various things (December/February), nor a recent joyful workshop, nor a planned workshop in Oslo, nor Tony Hoare's visit and what chat we have had, and of course how Scribble is going (or how Gary is proceeding with this), because of this: anyway I now know the reason.

Perhaps I will anyway write here about something harmless since I cannot think and do nothing intellectually consuming.