Type inclusion tests consist in determining whether a type is a subtype of another. An efficient implementation of type inclusion
an important feature of object oriented programming languages. A well-known method to achieve these tests is to associate
to each type a subset of a set
S = {1, . . . , k} such that type inclusion coincides with subset inclusion. Such an embedding of types into 2
S (the lattice of all subsets of
S) is called a bit-vector encoding of the type hierarchy. These encodings are known for several interesting features. Bit-vector
encodings are perfectly appropriate for hierarchies with single subtyping as well as hierarchies with multiple subtyping.
Subset inclusion tests can be performed very efficiently.
Several works have studied bit-vector encodings froma theoretical point of view ([6], [7], [10], [14], [16], [18], [19]) and froma practical point of view ([3], [8], [9], [17]), in particular in order to minimize the size of the encoding, i.e. the size of S.
In this article, we present a new algorithmw hich computes bit-vector encodings for single subtyping hierarchies, also called
tree hierarchies. Our algorithm is simple, it computes the bit-vector encoding very quickly and gives good results for the
size of the encoding. In particular, we have significantly improved the best bounds known for the encoding sizes of some benchmarks
presented in [9].