RE: Alternative language versioning formalism

Hello Jonathan,

Firstly thank you for this... I will look it over, but it looks good at a superficial glance.

We repeatedly have problems with references to documents in the versioning collection. At some stage your reference [2], http://www.w3.org/2001/tag/doc/versioning-strategies, became http://www.w3.org/2001/tag/doc/versioning-compatibility-strategies. It possible that I have promulgated a reference to the wrong document (|work|expression|manifestion| item :-)).

Stuart
--
Hewlett-Packard Limited registered Office: Cain Road, Bracknell, Berks RG12 1HN
Registered No: 690597 England

> -----Original Message-----
> From: www-tag-request@w3.org [mailto:www-tag-request@w3.org]
> On Behalf Of Jonathan Rees
> Sent: 27 May 2008 22: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, 29 May 2008 09:49:45 UTC