Inheritance Hierarchies

[Reference Manual]
[ALE Code--Inheritance and Unification]
ALE is a language with strong typing. What this means is that every structure it uses comes with a type. These types are arranged in an inheritance hierarchy, whereby type constraints on more general types are inherited by their more specific subtypes, leading to what is known as inheritance-based polymorphism. Inheritance-based polymorphism is a cornerstone of object-oriented programming. In this section, we discuss the organization of types into an inheritance hierarchy. Thus many types will have subtypes, which are more specific instances of the type. For instance, person might have subtypes male and female.

ALE does much of its processing of types at compile time, as it is reading and processing the grammar file. Thus the user is required to declare all of the types that will be used along with the subtyping relationship between them. An example of a simple ALE type declaration is as follows:

  bot sub [b,c].          % two basic types -- b and c
    b sub [d,e].
      d sub [g,h].        
      e sub [].
    c sub [d,f].          % b and c unify to d
      f sub [].

There are quite a few things to note about this declaration. The types declared here are bot, b, c, d, e, f and g. Note that each type that is mentioned gets its own specification. Of course, the whitespace is not important, but it is convenient to have each type start its own line. A simple type specification consists of the name of the type, followed by the keyword sub, followed by a list of its subtypes (separated by whitespace). In this case, bot has two subtypes, b and c, while f, d and e have no subtypes. The subtypes are specified by a Prolog list. In this case, a Prolog list consists of a sequence of elements separated by commas and enclosed in square brackets. Note that no whitespace is needed between the list brackets and types, between the types and commas, or between the final bracket and the period. Whitespace is only needed between constants. The extra whitespace on successive lines is conventional, indicating the level in the ordering for the user, but is ignored by the program. Also notice that there are comments on two of the lines; recall that comments begin with a % sign and continue the length of the line. Every type (except a_/1 atoms, discussed below) must have at most one sub declaration, i.e., all of the immediate subtypes must be declared in one declaration.

The subtyping relation is only specified by immediate subtyping declarations; but subtyping itself is transitive. Thus, in the example, d is a subtype of c, and c is a subtype of bot, so d is also a subtype of bot. The user only needs to specify the direct subtyping relationship. The transitive closure of this relation is computed by the compiler. While redundant specifications, such as putting d directly on the subtype list of bot, will not alter the behavior of the compiler, they are confusing to the reader of the program and should be avoided. In addition, the derived transitive subtyping relationship must be anti-symmetric. In particular, this means that there should not be two distinct types each of which is a subtype of the other.

There are two additional restrictions on the inheritance hierarchy beyond the requirement that it form a partial order. First, there is a special type bot, which must be declared as the unique most general type. In other words, every type must be a subtype of bot. If a type is used on the left-hand side of a sub declaration, but never declared as a sub-type of anything else, it is assumed that this type is an immediate subtype of bot. Similarly, ALE assumes that all types for which no subtypes are declared are maximal, i.e., have no subtypes.

The second and more subtle restriction on type hierarchies is that they be bounded complete. Since type declarations must be finite, this amounts to the restriction that every pair of types which have a common subtype have a unique most general common subtype. In the case at hand, b and c have three common subtypes, d, g, and h. But these subtypes of b and c are ordered in such a way that d is the most general type in the set, as both g and h are subtypes of d. An example of a type declaration violating this condition is:

  bot sub [a,b].
    a sub [c,d].
      c sub [].
      d sub [].
    b sub [c,d].

The problem here is that while a and b have two common subtypes, namely c and d, they do not have a most general common subtype, since c is not a subtype of d, and d is not a subtype of c. In general, a violation of the bounded completeness condition such as is found in this example can be patched without destroying the ordering by simply adding additional types. In this case, the following type hierarchy preserves all of the subtyping relations of the one above, but satisfies bounded completeness:

  bot sub [a,b].
    a sub [e].
      e sub [c,d].
        c sub [].
        d sub [].
    b sub [e].

In this case, the new type e is the most general subtype of a and b.

This last example brings up another point about inheritance hierarchies. When a type only has one subtype, the system provides a warning message (as opposed to an error message). This condition will not cause any compile-time or run-time errors, and is perfectly compatible with the logic of the system. It is simply not a very good idea from either a conceptual or implementational point of view. For more on this topic, see Carpenter (1992:Chapter 9).