RE: Alternative language versioning formalism

Hi Jonathan,

I took a more detailed look a your formalism. Like we already noted
off-list, your approach has a lot in common with my Axioms of Versioning
http://www.marcdegraauw.com/files/axiomsofversioning.html (posted to the
list earlier; it has been accepted as a presentation at the upcoming
Versioning Symposium at Balisage Montreal, where I'll certainly talk about
your approach as well).

Both ground 'compatiblity' in receiver action (or behaviour in my parlance)
associated with an incoming message, and define forward compatiblity through
action or behaviour for 'unknown' messages. Needless to say, given the
similarities, I believe this is the right approach to give the notion of
'compatibility' a firmer footing (though not necessarily in the ISSUE-41
docs).

A general difference is your model does not include receiver state; that is,
given a message m, the receiver action a is determined by m and the function
R. This is a bit too coarse for real messaging systems; for instance
messaging systems typically include a unique message id, so accepting a
message m and rejecting (or ignoring) the same message m if it has been
resent later is desired behaviour.

Another difference is our approach to a new message m', undefined in v1 of
the language. In my approach the receiver transforms m' to a known message m
(possibly through ignoring unknown content) and will exhibit the behaviour
associated with m, in your approach you define an action by 'adequate
defaulting', i.e. providing a default action for any unknown message in v1.
I think your approach may be more fruitful here. I may steal this idea and
incorporate it into my own formalism to see how this works out.

Both approaches probably suffer from their dependance on behaviour/action -
in real messaging systems, a lot of message do not lead to a perceivable
action, but to a database update, possibly but not necessarily affecting
future actions. (I.e. store a new customer address, which may or may not be
used later.) This is one comment David Orchard gave me - what's the
behaviour of a name language message? I think this could be handled by
defining some receiver state as well, which influences the outcome of future
actions, but it may also be a point where abstraction from the 'real world'
is warranted.

Thanks anyway for this contribution, it is a insightful exercise to compare
the two approaches.

Regards,

Marc de Graauw

http://www.marcdegraauw.com 

| -----Original Message-----
| From: www-tag-request@w3.org [mailto:www-tag-request@w3.org] 
| On Behalf Of Jonathan Rees
| Sent: dinsdag 27 mei 2008 23:05
| To: www-tag@w3.org WG
| Subject: Alternative language versioning formalism
| 
| 
| (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 O
|    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.
| 
| ------------------------------------------------------------------
| 
| 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-strategies
| [3] http://scholar.google.com/scholar? 
| hl=en&lr=&cluster=11821292421815354248
| 
| 
|

Received on Thursday, 5 June 2008 07:47:54 UTC