Equivalence: Different languages use different rules here. Structural equivalence treats two objects as the same type if after replacing each type with its definition, the same structure is obtained. Roughly, this means that the types are considered "records", and are equivalent if the fields of these records are recursively equivalent types. Name equivalence requires instead that types be equivalent only if they are declared with the same type name, such as "integer". Type constructors such as "array" introduce internal names for each use of the constructor. In some languages the combination, e.g. "int array" is given the same name in each declaration in which it occurs. In other languages, each declaration introduces a new internal name. In still others, each variable declared in a declaration using a type constructor is declared in effect with a different type. Discuss.

Compatibility: When different types are introduced, some mechanism must be provided for defining operations on objects of the new type. The simplest solution would be to require that every operation of the new type be defined explicitly for that type. Most languages find ways of re-using operator definitions, to simplify programming. Inheritance is a common scheme in OO languages. This rule applies when a new type is defined as a subtype of an existing one. The new type inherits all operations defined on its parent. In some languages, certain built-in operations are regarded as applicable to many different types. For instance, assignment of a expression of type T to a variable of type T is often allowed, even if T is programmer-defined. The question then arises: In an assignment, which LHS, RHS type combinations are legal? Discuss. Equality testing also applies across types, but here the question is more complex, for in a structure constructed using pointers (or references to objects), equality could mean: (a) Exact -- objects equal only if they occupy the same memory location; (b) Surface -- objects equal if their components are surface equal; (c) Deep -- objects equal only if they print the same way. In fact, assignment and equality are similar in this respect -- Should assignment make a copy? Create a new pointer to the same memory area? If a copy, should the copy be "surface" (new copy of the record, making copies of the pointers it holds), "surface structure" (new copy of the high-level list structure), "deep" (new copies of each record pointed to, so no memory sharing between the original and the copy)?

Subranges: In PASCAL, a subrange of an existing type can be treated as a separate type:

type natural = 0..MAX;

PASCAL automatically extends the arithmetic operators to the new type. Also, the new type is type-equivalent to the type being extended, so

type feet = 0..MAX; and type meters = 0.. MAX

allow feet and meters to be treated as equivalent. Some distinct mechanism for these cases is needed. The concept of a derived type allows old operators to be re-used, while treating types derived separately from the same base type as inequivalent.

One can allow extensions to existing types. For instance, the type range = 0..3 could be extended to include "4". Enumeration types can be extended, by introducing new constants. These concepts seem similar to that of sub-types in OO languages.

Dimensions: The notion of associating a physical property with a variable which measures the magnitude of that property has value in engineering and physics. This type-like attribute could allow one to declare a variable as measuring "meters", while another measures "time". Their ratio would measure "velocity", (distance per unit time), and addition of variables with different "dimension signatures" could be prohibited. Automatic conversion between measurement units could also be provided.

Abstract Data Types: An ADT is a set of values, and a set of procedures that manipulate those values. The intent is to isolate the manipulation of the internal representation of the values from the user of the ADT. The user is restricted from modifying internal representations except through the procedures provided with that ADT. Programming theory suggests that structuring a complex program by defining such data types, and requiring the compiler to enforce the "no external manipulation of internal representations" rule tends to protect programmers from errors, and also provides a way of gradually "extending" the bare computer to a powerful machine, with operations that are "problem-oriented", rather than machine oriented. OO classes seem to me a useful generalization of ADTs. The original ADT concept required every operation on a new ADT to be defined explicitly. For the user, a typical ADT provided "axioms" describing in abstract mathematical terms how the ADT operations functioned. The classic ADT example is the definition of a Stack given in text (pp 74-5). In papers describing the value of the ADT notion, people give axioms like "Pop(Push(a, S ))=a", to define how a stack operates in general. The user is supposed to use these axioms alone in deciding whether her/his program is correct. The axiomatic approach was popular when the idea that formal mathematical reasoning should be used to "prove" program correctness. ADTs allow the ADT designer to safely define "invariants" which the ADT procedures can always assume about objects of the ADT. This allows an abstract proof that the ADT is correct, no matter what program uses it. Such a proof would not be possible, if the compiler allowed a program to modify internal representations.

Object Oriented Languages: Refined the ADT notion into that of a class, allowing inheritance rules to help in defining new classes. The notion of axioms defining the interface to classes seems to have been lost. Instead, a whole programming philosophy based on treating data objects as primary, and procedural details as secondary, has been developed. OO has its origins in "discrete event simulation" programs and languages. These languages (Simula, Simscript) are used to simulate objects moving around in the real world, say. In general, the objects they manipulate are classifiable into ditinct collections, each with its own real-world behaviors. To the extent that a computer program attempts to "simulate" the behavior of real-world objects, the OO paradigm provides an extremely useful scheme for writing programs for such simulation. The rules for type equivalence, subtyping, and modularization limit program manipulations to those that "make sense" in the real world, whether "make sense" means forbidding addition of "meters" and "seconds" (even though internally both are represented as integers), or allowing "display()" to operate on all objects. Discuss.