Anonymous Unspoofable Cyclic Distributed Static Linking: Part 2

Mark S. Miller
Fri, 14 Jan 2000 13:49:05 -0800

At 01:10 PM 1/14/00 , Chip Morningstar wrote:
> >...  In an object system, the way A's 
> >developer can achieve similar flexibility, but have it work, is to use 
> >normal object-oriented polymorphism.  A can interact with objects that 
> >instantiate modules written after A was created, given that they implement 
> >subtypes of types A knows how to invoke.  This flexibility, obtained through 
> >polymorphism, is in no conflict with static-only linking.
>This means we would get a sub-type hierarchy whose depth is linear in the
>number of versions the implementation has been through. This is probably a Bad

Two answers, one for latently-typed languages like Smalltalk/Lisp/E, and one 
for statically typed languages like C++/Java.

For latently typed languages, this merely means that, before feeding an 
instance of some version of B to some version of A, you should be confident 
that the behavior of this B is upwards-compatible from the behavior expected 
by this A -- i.e., that the type implicitly/effectively implemented by B is 
a subtype of the type that A implicitly/effectively requires.  Of course, 
without a static type system, the language doesn't much help you obtain this 
confidence, just as it doesn't for normal type compatibility.  The depth of 
the subtype hierarchy is linear, as you say, but this hierarchy is never 
expressed, so it isn't an issue.  For E, I'm pretty happy with this answer.

For statically typed languages, this does indeed create a linear declared 
hierarchy, which would seem to be unpleasant.  However, in a 
statically-typed system in which types can be versioned, we must have an 
account of which versions of a type are upwards-compatible from which other 
versions of a type.  Subtyping is already synonymous with 
"upwards-compatible", and static type systems are already a much richer 
theory of upwards-compatibility of interfaces than we could hope to produce 
independently by thinking about the versioning problem.

It would still be too scary to contemplate but for one thing.  A genuinely 
good paper from the Spring OS group at Sun is "Using Interface Inheritance 
to Address Problems in System Software Evolution" in which they propose 
to do exactly that in a Java-like static type system.  They propose a system 
of syntactic sugaring so that the programmer mostly just sees the 
conventional single-version view, but they still leverage the power of type 
systems to reason about upwards-compatibility among (versions of) 
interfaces.  It's cool.  Unfortunately, it's still purple.  Fortunately, as 
mentioned above, E needs none of this mechanism.  Although a separate type 
system for reasoning about E might need this mechanism.