...safety

This research was partially supported by NSF grant CCR-9424123.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...(immutable

Records are immutable if the individual fields cannot be updated in place. Thus the records here are more like the record expressions in functional languages like ML. We discuss later in this section the impact of allowing updatable fields.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...field.

One might also expect record construction to be an operation on a record, but we distinguish here (as is typical in object-oriented languages) between operations that can be applied to a value of a particular type, and operations that result in a value of that type (usually called constructors).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...${\it {{\rm{\it ref}}\ T}}$.

Thus, in this paper the statement, ``${\it {x}}$ is a variable of type ${\it {T}}$,'' has the same meaning as ``${\it {x}}$ has type ${\it {{\rm{\it ref}}\ T}}$''. This is similar to the usage in ML.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...superclass.

The new C++ draft standard and some current compilers now allow return types of methods to be replaced by subtypes in subclass (derived class) definitions as long as the return type is a pointer type.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...node.

We note that all objects will be represented as references (implicit pointers). As a result, there is no problem supporting recursive types. The value ${\it {nil}}$ is used as a null reference and is considered to be an element of all object types.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...undesirable.

It is worth noting here that because it contains a binary method, ${\it {DoubleNodeType}}$ will not be a subtype of ${\it {NodeType}}$. See section 5 for a detailed discussion.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...original.

Of course it is technically possible to keep track of which methods are called by other methods and annotate each class with that information. While this would allow more freedom in making changes to some methods, this seems too painful for regular use and may require a data flow analysis of even indirect uses of an object.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...${\it {NodeType}}$

As noted in the previous section, it isn't!

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...${\it {SC}}$.

This is actually only true if the body of ${\it {m}}$ does not include any mention of ${\it {super}}$, but we can ignore that possibility here.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...MyType.

Actually it is safe to assume that ${\rm{\it MyType}}{\rm \, <\!\!\!\char93 \, }{\rm{\it {ObjectType\{m_i:T_i\}}}}_{1 \le i \le n}$when determining whether ${\it {T'_i {\rm \ <: \ }T_i}}$, but we will not bother with that subtlety here. See [Bru94,BSvG95] for details.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...free

In case of nested object types, occurrences of MyType always refer to the most closely enclosing object type definition. We treat the ObjectType constructor as implicitly binding all free occurrences of MyType that occur within its definition.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...construct.

For those familiar with existential types, we note that #T can be encoded as $\exists t {\rm \, <\!\!\!\char93 \, }T.t$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.