Home | DMP | Project | Journal | Contact
Relevant Java Classes | Delete Call Site | Template Call Graph | Research | Final Report
Previous (Type Handling)
Next (Polymorphism)

CONCRETE TYPES VS. ABSTRACT TYPES

CONCRETE TYPES

Concrete types describe object implementations, including memory layout and the code executed upon method invocation. A concrete type is the exact class of which an object is an instance - not the more general set of the class and its subclasses. But beware of falling into the trap of thinking that all concrete types are single classes! For a variable or expression that can hold or evaluate to an instance of more than one class, the concrete type is a set of classes. For example, a variable x that holds instances of either SetModel or VirtualModel (see class hierarchy below) has the concrete type {SetModel, VirtualModel}. Although Model is the parent class of SetModel and VirtualModel, x's concrete type cannot be {Model}; in that case, x could hold only instances of Model - not of its subclasses.

Class hierarchy diagram taken from Summary of Recent Discussions About an Application Programming Interface for RDF, by Peter Hannappel. Used without express permission.

Concrete Type = Set of Exact Classes


ABSTRACT TYPES

Abstract types, on the other hand, describe properties of objects. They do not distinguish between different implementations of the same behavior. Java provides abstract types in the form of interfaces, which list the fields and operations that implementations must support. Interfaces specify the type signatures of methods without specifying how the methods are evaluated. The details are left to the (possibly many) implementing classes.


CLASS TYPES

Class types fall near the center of the concrete/abstract typing spectrum and include a specified class and all of its subclasses. In the words of Agesen, a class type expresses the property of "being an instance of the given class or one of its subclasses". The class hierarchy diagram above yields several useful examples:

  • class type(Resource) = {Resource, Model, Statement, SetModel, VirtualModel}
  • class type(Literal) = {Literal}

    (We assume that the leaf nodes of the diagram have no subclasses.)

    Class types are neither fully abstract nor fully concrete. Unlike abstract types, they reveal some implementation details. In Java, for instance, if Model has a field material, one can assert that its subclasses - SetModel and VirtualModel - also have this field. In fact, any object with class type Model would include the material field. And, in contrast to the more complete information provided by concrete types, knowing an object's class type simply reveals that the specified class is a superclass of the actual class of the object. The object may have additional instance variables and operations beyond those implied by the class type.

    A similar situation is encountered in the FLEX compiler, with the GenType class. GenTypes can represent both monomorphic and polymorphic types, with polymorphic types corresponding to a set of HClasses - a type cone rooted in a specific HClass and including all subclasses of the root class. This root class parallels the concept of class type.


    RELEVANCE

    The goal of type inference in the context of template call graph construction is to infer the most concrete types possible. With concrete types, there are fewer templates to construct, and the sets of added and deleted reaching types upon the removal of a call site are more manageable. Precision increases, and analysis time may possibly decrease. The FLEX compiler includes many built-in features and classes to support such an approach to typing and analysis:


    GENERAL TYPES VS. SPECIFIC TYPES

    Types describe the ways in which code may be used and reused. A single piece of code can often be used with several types of objects. The identity function, for example, applies to many different classes:

    identity(x) {
    return x;
}

    Assume that identity is a static method in Java:

    public static Object identity(Object x) {
    return x;
}

    The most general type of the function is Object->Object (since Object is the ultimate superclass of every class in Java - the root of the class hierarchy). This general type specifies the legal use of the identity function. Regardless of the exact class of the argument x, identity succeeds, returning an object of the same class.

    In the context of a specific program that invokes identity only on objects of class A, the method could be represented by the type A->A. This type is the most specific type possible with respect to the target program, describing the actual use of identity. If another program calls identity on both int and float objects, its most specific type is {int->int, float->float}. Note that most specific types are relative to a particular program - in our case, the program being analyzed for call graph construction and modification.


    RELEVANCE

    As with concrete and abstract types, general and specific types serve different purposes. General types are helpful in determining how a piece of code may be used, while most specific types are essential in determining how the code is used in a certain program. To build a call graph with the smallest possible number of unrealizable call chains, we want the less conservative, more exact type information provided by most specific types in the context of the source program. In fact, the ideal for the template call graph construction and modification upon the deletion of a call site is a combination of the most specific and most concrete types possible. The call graph would thus be smaller and more manageable, and fewer edges would have to be deleted and added during the propagation of changes. But in practice, type inferencers often must settle for slightly more general types due to the demands of practicality. The Cartesian Product Algorithm (and its concomitant typing system) devised by Ole Agesen and used by Professor Souter in her work on incremental call graph updates was designed to infer more specific types than many other type inference schemes.



    Home | DMP | Project | Journal | Contact
    Relevant Java Classes | Delete Call Site | Template Call Graph | Research | Final Report
    Previous (Type Handling)
    Next (Polymorphism)

    ©2002, Katie Heise

    		•