Computing Types in Java Programs






This paper addresses the computation of 
types associated with Java class hierarchies. In 
object-oriented approaches, types often are assimilated to 
classes, but subtyping and specialization have different 
semantics and constraints. Our approach allows to 
make a clear distinction between these two 
concepts. A special policy of Java as 
regards inheritance is thoroughly used. Between Java 
classes, only single inheritance is allowed: some 
feature factorizations are impossible, and in cases 
where a ``good'' design suggests a multiple 
specialization, less natural solutions have to be 
found. By contrast, Java interfaces may be 
organized into multiple inheritance subtyping hierarchies, and 
a class may implement several interfaces. Furthermore, 
Java interfaces can be used to type 
expressions, allowing to write generic code. In 
this paper, we propose a method that, 
from a single inheritance class hierarchy, produces 
a multiple inheritance interface hierarchy that we 
connect by implementation links to the initial 
classes. It can be applied to compute 
all the interfaces needed by a Java 
class hierarchy. The resulting interface hierarchy could 
also be reused, giving it alternative implementations 
with other class hierarchies. We argue that 
the exhibited structure, where interfaces are highlighted 
and well organized, offers a good view 
of the class hierarchy in terms of 
types. Our method is based on the 
Galois lattice, that, as previous works have 
shown, appears as a reference structure to 
guide elaboration of hierarchies. We also propose 
a new efficient algorithm that builds a 
part of the Galois lattice called the 
Galois sub-hierarchy, from the binary relation mapping 
``objects'' (classes) to their ``features'' or ``properties'' 
(attributes or methods). This algorithm is useful 
compared to previous works where is built 
either only a part of the Galois 
sub-hierarchy, sometimes with additional classes that do 
not conform with the structure, or the 
Galois sub-hierarchy considering that input ``objects'' are 
always associated with leaves of the output 
hierarchy.