Restriction Semantics, Substitutability, and Subtyping: a Perspective

Author: Phil Pfeiffer (ETSU/ORNL)

Date: May 2003

Introduction

The SciDAC Scalable Systems Initiative (SSI) is a DOE-funded research
project that's concerned with the development of applications for
managing clustered computers. One of the SSI's key concerns has been the
formulation of a strategy for developing components that allows a
designer to

-   implement a superset of the functionality of a component's base API,
    in a way that

-   ensures the system's robustness: i.e., that guarantees that a
    component that does more than an API requests doesn't somehow
    accidentally crash the entire system by overimplementing that API.

This work is being done in the context of XML, the SciDAC's language of
choice for supporting inter-component communication.

At a presentation at Argonne in February 2003, Rusty Lusk outlined a
strategy for interpreting XML messages that appears to achieve the sort
of component extensibility described in the previous paragraph. In XML,
the "unexpected functionality" problem corresponds to messages that
contain unexpected tags; unexpected combinations of attributes; and
unexpected attribute values. Lusk's strategy for supporting
overimplementation, as I understood it, uses two guidelines for
interpreting unexpected combinations of XML attributes:

-   *Ignore superfluous attributes.* A code that receives an XML message
    M with an unknown attribute A should

```{=html}
<!-- -->
```
-   ignore attribute A when processing message M, but

-   forward A intact when forwarding the updated M to any downstream
    nodes.

```{=html}
<!-- -->
```
-   *Drop fields characterized by missing attributes.* Let M be a type
    of message that

```{=html}
<!-- -->
```
-   selects a set of n-tuples {(A~1~, A~2~, A~3~, .., A~n~), (B~1~,
    B~2~, B~3~,.., B~n~), ... } from a dataset, and that

-   "ordinarily" uses an attribute A to constrain the content of k of
    these n-fields---e.g., 2, 3, and 4.

> A code that receives a version of message M that lacks attribute A
> should return a "restricted" n-tuple that omits those fields indicated
> by A: here, a set of (n-3)-tuples of the form {(A~1~, A~5~, A~6~,..,
> A~n~), (B~1~, B~5~, A~6~,.., B~n~), ... }.

Lusk referred to this strategy as a *restriction semantics* for XML. A
short series of examples may help to clarify the use of these rules in
XML message processing:

-   A code C that expects to process messages of the form \<stopjobs
    runtime-exceeds="..."/\> would process

    -   \<stopjobs runtime-exceeds="v1" priority="low"/\>, where
        priority is an attribute unknown to code C, as

    -   \<stopjobs runtime-exceeds="v1"/\>.

-   A code C that expects to process messages of the form \<stopjobs
    runtime-exceeds=".."/\>, and then to forward updated messages of the
    form \<stopprocesses runtime-exceeds=".."/\> to a downstream code,
    would process

    -   \<stopjobs runtime-exceeds="v1" priority ="low"/\>, where
        priority is an attribute unknown to code C, as

    -   \<stopjobs runtime-exceeds="v1"/\>.

> then

-   forward \<stopprocesses runtime-exceeds="vnew" /\>

-   as \<stopprocesses runtime-exceeds="vnew" priority="low"/\>

```{=html}
<!-- -->
```
-   A tuple-retrieving code C that

    -   expects to process messages of the form \<getjobIDs
        runtime-exceeds=".." priority="low"/\>, and

    -   return tuples of the form \<jobIDs jobid="v1" runtime= "v2"
        priority= "v3" /\>

> would process select messages of the form \<getjobIDs
> runtime-exceeds=".." /\> by

-   returning tuples of the form \<jobIDs jobid="v1" runtime= "v2" /\>

> This behavior contrasts with C's expected behavior when

-   processing messages of the form \<getjobIDs runtime-exceeds=".."
    priority="\*" /\>---an action that should

-   return tuples of the form \<jobIDs jobid="v1" runtime= "v2"
    priority="v3" /\>, where values associated with priority are
    unconstrained.

Substitutability

This problem of interchangeable components is reminiscent of a problem
that was studied during the 1980's in the context of OO type
systems---*substitutability:*

When is it safe to allow one object---

say, a code that processes XML messages---

to take the place of a second object---

say, a second code for processing XML messages---

in the context of an arbitrary application?

To make the connection between the two problems more tangible, consider
a scenario involving a daemon that implements a jobs API that defines
exactly two sets of XML queries:

-   one set of queries of the form

> \<getRunningJobList host="..."/\>
>
> that each elicit a list of IDs for running jobs on the specified host,
> as a response of the form
>
> \<runningJobList host="..." list= "ID**~1~** ID**~2~** ...
> ID**~N~**"/\>

-   one set of queries of the form

> \<getRunningJobStatistics jobID="..." /\>
>
> that each elicit a start time and a CPU time for the specified job, as
> a response of the form
>
> \<runningJobStatistics jobID="..." startTime="..." CPUtime="..."/\>

Assume, for the sake of this example, that a second group has designed
and implemented an improved version of this daemon: i.e., one that
recognizes additional attributes like "user", and additional queries
like "getPendingJobList". Assume, further, that users would prefer to
use this second daemon---*if* that daemon's implementation is truly
consistent with the original. How can a system architect determine
whether the second is an acceptable extension of the first?

The programming languages community commonly frames the substitutability
problem in terms of type-subtype relationships. The community frames an
assertion like

# Code B can be substituted for code A without breaking the application that houses A

as an assertion like

# Code B is a subtype of code A

relative to a "suitable" definition of subtyping: one that, for
starters,

-   treated a XML-processing code as an implementation of a class C,
    where

    -   C's signature is the XML-processing code's API, and

    -   C's visible attributes are a set of codes---one for each of the
        message (tag) types that the API defines.

-   and the assertion that

> "daemon 2 can be safely substituted for daemon 1"
>
> as equivalent to the assertion that
>
> "the class of daemon 2 is a subtype of the class of daemon 1".

My rationale for comparing restriction semantics to
programming-languages-based work on subtyping is that the PL community
has given extensive thought to the subtyping, and discovered subtleties
that, to me, help to illuminate comparable subtleties related to the use
of Lusk's restriction semantics. Because the notion of subtyping is
somewhat subtle, I will develop the comparison in stages, and refer to
the XML message-passing example throughout the discussion.

The standard starting point for a substitutability-preserving subtype
relationship constrains the attributes that a derived type must support,
relative to the initial type:

Definition #1: Let A and B be classes. Then class B is a subtype of
class A iff,

-   *for every visible attribute A**.** a in A,*

-   *there exists a visible attribute B**.**a in B whose definition is
    "compatible" with that of A**.**a (for a suitable notion of
    "compatible")*

Rephrasing this definition in terms of the design of XML---a world where
a code's only visible attributes are that code's (implicit) methods for
processing tags---yields the following, XML-code-specific constraint on
message processing:

Definition #1 (XML-specific): Let A and B be codes whose sole purpose it
is to process XML messages. Then class B is a subtype of class A iff,

-   *for every set of tagged messages \<some-tag ... \> processed by
    A**, ***

-   *B processes the set \<some-tag ... \> in a way that's compatible
    with A's processing of this set (for a suitable notion of
    "compatible".)*

The rationale for imposing this constraint is that not preserving the
supertype's attributes risks failure: if *B* lacks an attribute *a*,
then substituting *B* for *A* risks a situation where

-   a client code that formerly used *A**.** a.* attempts to access
    *B**.** a*

-   *B,* lacking understanding of *a,* crashes the application.

Here, we will treat the "missing attributes are always bad news"
strategy for preserving substitutability as a given, even though there
are at least two workable alternatives for ensuring substitutability in
the presence of missing attributes:

-   demonstrate that the missing attribute was superfluous: i.e., that
    the client code will never invoke *B**.** a*

-   develop an "artificially intelligent" substitution: i.e., design a
    *B* that, when queried about *a*, can make up a suitable behavior on
    the fly---even though *B* has no intrinsic knowledge of *A* per se.

The first strategy---the "drop unnecessary attributes strategy"---is one
that is studied repeatedly in the literature on program optimization and
partial evaluation. This strategy is relatively difficult to implement
without special tools for code analysis; somewhat difficult to implement
correctly, even with those tools; and only works when a missing
attribute is truly not in use. The second strategy is one that I've seen
discussed in the context of extensible UI design, where researchers have
attempted to make inferences about user actions that aren't designed
into the original interface. Based on the little that I've seen of this
strategy, it also appears difficult to implement---at least, in the
absence of a reasonably complete catalogue of application attributes,
and reasonably comprehensive conventions regarding attribute naming.

Returning to the jobs daemon example described at the start of this
section, in order for the second jobs daemon to be substitutable for the
first, that second jobs daemon must, *at a minimum*, process

-   every \<getRunningJobList host="..."/\> message accepted by the
    first daemon, and

-   every \<getRunningJobStatistics jobID="..." startTime="..."
    CPUtime="..."/\>

in a way that is *compatible* with how the first daemon processes these
messages. The second jobs daemon may also support handlers for other
messages, as well as handlers for tags with additional attributes; but
the second daemon must, at a minimum, support compatible handlers for
\<getRunningJobList /\> and \<getRunningJobStatistics /\>.

What it means for a pair of definitions to be *compatible* in the sense
of substitutability is something of a subtle problem. I find it helpful
to start with a pair of definitions that focus on a method's inputs and
outputs, respectively:

Definition #2 (covariance): Let A and B be classes that each have a
method m. Then class B**.**m's inputs are compatible with class
A**.**m's inputs iff,

-   *for every tuple of parameters (p**~1~**, p**~2~**, p**~3~**, ...
    p**~n~**) accepted by A**.** m*

-   *B**.**m also accepts (p**~1~**, p**~2~**, p**~3~**, ... p**~n~**)*

Or, in terms of the XML examples,

Definition #2 (XML-specific): Let A and B be codes whose sole purpose it
is to process XML messages. Then class B is a subtype of class A iff,

-   *for every tagged message \<some-tag attr**~1~**="v**~1~**"
    attr**~2~**="v**~2~**" ... attr**~n~**="v**~n~**"/ \> accepted by
    A**, ***

-   *B also accepts \<some-tag attr**~1~**=" v**~1~**" attr**~2~**="
    v**~2~**" ... attr**~n~**=" v**~n~**" /\>.*

The notion of *accepts* is a term whose meaning varies by context.

-   The simplest definition for "accepts" is "A doesn't fail  B doesn't
    fail". This definition, which can be less than satisfactory, may
    nevertheless be the strongest guarantee that one can make in the
    name of substitutability. For example, two daemons that use polling
    to monitor a job's resource consumption can, if they poll at
    different rates, obtain different characterizations of peak
    usage---with no one rate guaranteeing a more accurate
    characterization than any other.

-   A second definition for "accepts" is "A produces result R  B
    produces R". Whether this definition is satisfactory also depends on
    what behavior one expects from B, relative to A.

```{=html}
<!-- -->
```
-   A third, and tighter, definition of "accepts" is "A produces result
    R  B produces a better version of R". This notion of better is
    obtained by imposing an ordering on the values yielded by a
    particular query: e.g.,

    -   *Specificity*: A, which divides the day into quarter-hour
        intervals, reports that job 10 finished between 10:00 am and
        10:15 am; B, which divides the day into minute-long intervals,
        reports that the same job finished sometime between 10:04 am and
        10:05 am.

    -   *Completeness*: A, which was configured with a list of hosts
        that's six months old, reports that user U is running jobs 10,
        11, and 12 on site machines; B, which has an up-to-date list of
        hosts, reports that U is running jobs 10, 11, 12, 33, and 47.

I am not advocating one definition over any other; rather, I am simply
pointing out a need to define what one means carefully by the notion of
comparable responses, relative to a particular attribute.

One of the ***key*** ideas in the classic PL literature on
substitutability is that "B responds with more information than A" is
***not***, in general, a viable strategy for guaranteeing
substitutability:

Definition #3 (contravariance): Let A and B be classes that each have a
method m. Then class B**.**m's outputs are compatible with class
A**.**m's outpus iff,

-   *for every output O that B**.**m* [might]{.underline} *generate in
    response to parameters (p**~1~**, p**~2~**, p**~3~**, ... p**~n~**),
    it is the case that*

-   *A**.**m* [might]{.underline} *also generate O in response to
    (p**~1~**, p**~2~**, p**~3~**, ... p**~n~**)*

The concern here is that surprising the client with an unexpected return
value might cause that client to break. Suppose, for example, A reports
the amount of time that a job ran to the nearest minute. Substituting a
B that reported the amount of time taken to the nearest minute *and
second* may cause A's client codes, which are expecting data in a
different format, to fail. In the worst case, any attempt to replace A
with a subtype B that

-   expands or modifies a range of values used by A to report a result;

-   modifies the result's format; or, ultimately,

-   returns any value that the client does not expect

risks breaking a client code---e.g., a client code that is suspicious of
anything it sees but does not expect---and is therefore forbidden.

Substitutability, from a Restriction Semantics Perspective

The principle of contravariant outputs enunciated in Definition
#3---allow B to generate output O ***[only]{.underline} if*** A might
also generate output O---is as strict as it is, in part, because the
definition fails to differentiate between

-   the components of a response returned by B alone;

-   the components of a response returned by A alone; and

-   the components of a response returned by A and B

The ability to differentiate between a response's component values,
however, is built into XML---if one takes the time to define responses
that consist of multiple, tagged values.

A second reason for Definition #3's strictness is that "never surprise
the client" is a simple and conservative way of maintaining
substitutability. The constraint imposes ***no*** requirements on a
client code, beyond those that were originally built into the client.
The principle, therefore, should always preserve substitutability,
regardless of the client in use.

The restriction semantics approach to ensuring substitutability is more
like the Eiffel approach to managing component interactions. The
restriction semantics approach to managing messages shifts some of the
burden for preserving substitutability from the responder to the
requestor, by requiring that a client ignore any unknown attributes it
receives as a part of a response. What is gained from this "contract" is
the ability to create XML message processing codes that provide more
information than a client requested---as explained below.

I will assume, for the sake of this discussion, that Lusk's notion of a
restriction semantics preserves the principles of covariant inputs and
contravariant outputs, as these apply to ***individual*** attributes in
the "baseline" version of an XML API. Preserving covariance and
contravariance in the context of individual attributes guarantees that

-   a B will not be surprised by any of the attributes that a client
    minimally expects to pass to A, and that

-   a client will not be surprised by the value of any of the attributes
    that it minimally expects to get from A---and gets from B, instead:

Definition #4 (XML-specific): Let A and B be codes whose sole purpose it
is to process XML messages. B is substitutable for A only if, for every
input-output message pair

\<some-input-tag in-attr**~1~**="vin**~1~**" in-attr**~2~**="vin**~2~**"
... in-attr**~n~**="vin**~n~**" /\> 

> \<some-output-tag out-attr**~1~**="A-vout**~1~**" ...
> out-attr**~j~**="A-vout**~j~**" /\>

accepted and returned by A, B accepts and returns an input-output
message pair of the form

\<some-input-tag in-attr**~1~**="vin**~1~**" in-attr**~2~**="vin**~2~**"
... in-attr**~n~**="vin**~n~**" /\> 

> \<some-output-tag out-attr**~1~**="B-vout**~1~**" ...
> out-attr**~j~**="B-vout**~j~**" ...-attr**~k~**="B-vout**~k~**" /\>

where B-vout**~1~,** B-vout**~2~, ...** B-vout**~j~,** are in the range
of possible values for A-vout**~1~,** A-vout**~2~, ...** A-vout**~j~,**
respectively**.**

Definition #4, however, leaves us free to write responders (servers, B
processes) that return "new" attributes as part of existing
messages---attributes in a response from B that are not present in a
response from A. Recall that the programming languages principle of
substitutability protects the client against crashes by guaranteeing
that such information won't be introduced into a response, period.
Again, in Lusk's restriction semantics, this unconditional guarantee is
traded for a "contract" between the responder and the client, in which
the client promises to simply ignore these superfluous attributes---in
effect, to refrain from crashing. What this "contract" buys is the
ability to make substitutability work with client codes as well as
server codes: i.e., to substitute more sophisticated clients that accept
a superset of the original client's responses.

A Few Loose Ends

The semantics of wildcard operators described in the paper's opening
section---and mentioned specifically by Lusk during his
presentation---follows from these definitions as a special case of
covariance. If a superclass A accepts a particular wildcard in a query,
then a subclass B should also accept that wildcard---but B's ability to
process a wildcard should impose no obligations on A.

The contravariance requirement formulated in Definition #4 could be
relaxed, for a specific output attribute
*out-attr**~j~***="*vout**~j~***", with the aid of a predetermined
"splitter function" that

-   split an arbitrary *vout**~j~*** into two components:

    -   a first component that represented the contribution that the
        client would ordinarly expect to see from A

    -   a second component that represented the "value added" component
        from B

> and

-   returned only the first component to a "simpler" client that
    expected to communicate with A

Under these circumstances, however, it would seem to be cleaner for B to
simply return two attributes to begin with, and avoid bundling the
"value added" component of the response into *out-attr**~j~***.

Preserving substitutability in situations that involve alternative
responses to client requests is a little trickier to handle, but common
cases should be manageable. In particular, the most common case of
alternative message transmission probably involves the use of two
responses to a client:

-   a "message successful" response, with characteristic information

-   a "message failed" response, with failure information

Semantic treatments of programming language semantics commonly treat
success as a more highly defined condition than failure, and rank the
two kinds of responses accordingly, for the purpose of ensuring object
substitutability. Rules like the following can be used to ensure that a
substitutability relationship holds between an XML-processing code A and
a second, substitutable code B:

-   Server A sends a success response R to a message M  Server B sends
    a success response R' to message M, and the relationship R'
    described in Definition #4 holds between R and R'.

-   Server A sends a failure response R to a message M  either

    -   B sends a success response---precisely, *any* success response
        consistent with the format of A's success responses\--or

    -   B sends a failure response R' to message M, and the message
        compatibility relationship described in Definition #4 holds
        between R and R'.

This interpretation of success and failure imposes one additional
requirement on the client, and a second on B. To maintain
substitutability, a client C must *not* invert the sense of success and
failure: i.e., must not handle a response to a particular message by

-   propagating a success response to a fourth code D upon receiving a
    failure response, and

-   propagating a failure response to a fourth code D upon receiving a
    success response.

Failing to preserve failure can violate preservation of substitutability
by creating a situation where replacing a server A that fails with a
server B that succeeds causes a successful application to fail.

Similarly, B should *never* fail where A would have succeeded.

Finally, substitutability with respect to messages with unexpected
initial tags can be obtained in a way that's directly analogous to the
handling of messages with unexpected attributes. Unknown requests and
responses should be ignored. And extended responses should only be
generated as a supplement to the required responses prescribed by the
API.

Concluding Unscientific Disclaimer

This "white paper" on restriction semantics represents something of a
leap of faith for its author: I am not a practicing type theorist, and I
have serious reservations about whether I should be undertaking this
sort of formulation. However, Lusk's request for help with elucidating
an idea that proved to be more subtle than it first appeared was too
interesting of a challenge to resist. Moreover, even if restriction
semantics proves to be a rediscovery of an older idea---and that would
be my guess, given the immense amount of thought devoted to typing---the
idea is still worthy enough to merit enough of an explication to make
others aware of its implications.