(Tracker, this is ACTION-158)

I was a bit befuddled by the versioning terminology draft [1], so I
made an attempt at my own formalism of language compatibility.  Others
at last week's TAG meeting expressed interest in this, so I am posting
it here.  This message does not constitute a request to update any of
the ISSUE-41 documents [1] [2].

Apologies for any errors.  I've spent too much time on this and need
to send it off...

Most of the complexity here is to try to show that all aspects of the
model are forced by particular extensibility requirements.  If I could
just tell you the punchline it would be easier, but I feel I have to
persuade myself of the necessity of all the preconditions - that they
are as weak as they can be.

At the risk of being overly pedantic, I'll start with a framework
inspired by a paper by Peter L. Hurd (J. Theor. Biol. 174:217-222 1995
[3]).  If you don't like this introductory discussion please skip down
to "A language L is ...".

Two agents, a sender and a receiver, are playing a game that goes as
follows:
  1. An objective (target action) o is chosen somehow from A = a space
     of possible action
  2. Given o, the sender's choice of message is via a function S: A->M
     where M = a space of possible messages (texts, strings)
  3. Given m, the receiver's choice of action is a function R: M->A
     where A = a space of possible actions (meanings, interpretations)
  4. Given o and a, success is judged according to a success criterion
     Z(o,a).
     I.e. if Z(R(S(o)),o) then communication has been successful.

The simplest situation would be where the objective is simply to
perform the desired action:
  Z(a,o)  iff  a = o.

Note: M = message space includes *all* possible messages, including
those that are not used for communication.

Note: A = action space includes all possible actions, not just those
that might be achieved through communication.  Examples: displaying
some text with certain visual or behavioral effects, or the results
(output, effects) that one might want to expect from a program.

The functions S and R are not determined by A, so the sender and
receiver will need to agree on a correspondence.  I'll define a
"language" to be a contract that might be entered into between a
sender and a receiver, presumably for the purpose of maximizing
communication success.

The simplest kind of language would be to agree on the function R that
is to be implemented by the receiver.  Then given an objective o the
sender can choose any message for which Z(R(S(o)),o).

However, we are interested in language extensibility.  A language
defined to merely specify the behavior of R cannot be extended because
the receiver cannot change the interpretation of any message for fear
that a sender unaware of the change might send it, in which case 
there would be no way to
guarantee that R's action would meet the objective.  Therefore we
consider languages in which some messages are reserved for future
expansion (i.e. sent messages are limited):

A language L is a pair (F,I) where
  F (the "final" messages) is a subset of M
  I (the interpretation function) is a function from M to A

The unused messages are those that are in M but not in F.  Note that I
defines actions for unused messages.  This will come in handy later.

Def: A sender speaks L if the image of S is a subset of F.

Def: A receiver understands L if R(m) = I(m) for all m in F.

(The sender will generally choose to further constrain S in order to
maximize success.)

Now consider a language change - a language L changing to become a
language L'.

Def. L' is backward compatible with L iff any receiver that
understands L' understands L in the same way on F.

Put more simply (trivial theorem): L' is backward compatible with L
iff I'(m) = I(m) for m in F.

We would like to also have some notion of forward compatibility: Any
sender that speaks L' also speaks L.  Since a receiver that
understands L cannot know how in advance what new messages (in F') are
supposed to mean, we have a problem: what should R(m) be when m is new?

To answer this, we introduce the notion of adequate defaulting.  The
idea is that there might be communication success if we substitute some
action a^ for the unknown future desired action a.  In this situation
we write a^ ~> a.  To simplify the formalism we also allow a ~> a for
all a in A.

Def: A receiver respects L iff R(m) ~> I(m) for all m in M.

We can define forward compatible as follows: L' is forward compatible
with L iff any receiver that respects L also respects L', i.e. R(m) ~>
I(m) implies R(m) ~> I'(m) for all m in M.  Trivial theorem: Forwards
compatibility holds iff I(m) ~> I'(m) for m in M.

Def: L weakly extends to L iff L' is backward and forward compatible
with L, i.e.
   F' superset of F
   I(m) = I'(m)  for all m in F
   I(m) ~> I'(m) for all m in {F' - F}

In order for forward compatibility to be transitive, we also need to
make sure nothing happens with non-final messages to break future
extensibility:

Def. L extends to L' iff it weakly extends to L' and preserves or
improves defaults defined by L:
   F' superset of F
   I(m) = I'(m)  for all m in F
   I(m) ~> I'(m) for all m

Def. L is extensible if there is an L' that extends it.

Note. If ~> is transitive (is a partial order), then extends and the
other relations are all transitive.  [requires proof?]

------------------------------------------------------------------

Example:
  A = {stop, go, caution, reverse, unassigned}
  M = {red, yellow, green}
  unassigned ~> o  for all o in A
  L = (F,I), L'=(F',I')
  I = {green:go, stop:red, yellow:unassigned}
  F = {red, green}
  I' = {green:go, stop:red, yellow:caution}
  F' = {red, green, yellow}

------------------------------------------------------------------

We want to be able to "kill off" a message - to decide in a future
extension that it shouldn't have any meaning and shouldn't be sent.
We can specify I(m) = k with Z(k,o) always false, and then the sender
won't send it.  This only works if either
  (1) k is not on any "upgrade path" to an action that succeeds
      (i.e. not k ~> a), or
  (2) k is not upgradable (k is in F).
(2) puts fewer constraints on A - it requires only one
special undefined action, e.g. u as in the example, instead of two
that behave differently in the partial order.  However, (1) is better
formally as one simply specifies a ~> k for any a, and then one may
upgrade any message's action from a to k.  (2) would require a change
in some of our definitions to allow the meaning of a message to pass
from a default action a to k, which is not related to it by ~>.  (Maybe
we could introduce a set K of killed messages as a component
of a language.)

------------------------------------------------------------------

If an action can only be done using a defaulted message, why would a
sender not "cheat" by sending a message outside F in order to achieve
that objective?  We can remove the temptation by making sure that a
defaulted objective is always achievable by a non-defaulted message:
For all m, if Z(I(m),o), then there is some m' in F such that
Z(I(m'),o).

------------------------------------------------------------------

Correspondence with [1]:
  sender = producer
  receiver = consumer
  message = text
  final = in defined set OR undefined by virtue of having been "killed"
  message's action succeeds for some objective = in accept set

------------------------------------------------------------------

Enrichments:

We could extend the framework to nondeterministic sender and receiver
behavior, to quantitative payoffs, and/or to differential
sender/receiver payoffs.  Evolutionary biologists do these things in
order to explain the presence and absence of cheating in natural
communication systems.  There is probably no need to do this in a
protocols and formal languages engineering setting, except by way of
explaining why a sender would choose a richer action when a default
would suffice.

We should be able to model distributed extensibility in this setting:
how precoordination can enable the existence of upper bounds among the
compatibility relations.

------------------------------------------------------------------

This work was done in ignorance of Marc de Graauw's [4].

Thanks to Alan Bawden for checking my math.  Any remaining errors are
mine.

- Jonathan

[1] http://www.w3.org/2001/tag/doc/versioning
[2] http://www.w3.org/2001/tag/doc/versioning-compatibility-strategies
[3] http://scholar.google.com/scholar?hl=en&lr=&cluster=11821292421815354248
[4] http://www.marcdegraauw.com/files/axiomsofversioning.html