TYPE MATCHING, TYPE-GRAPHS, AND THE SCHANUEL CONJECTURE

This work considers type systems that are defined by type-graphs (tgra phs), which are rooted directed graphs with order among the edges leav ing each node. Tgraphs are uniquely mapped into polynomials, which, in turn, are each evaluated at a special point to yield an irrational nu mber named the tgraph's magic number. This special point is chosen usi ng the Schanuel conjecture. It is shown that each tgraph can be unique ly represented by this magic number; namely. types are equal if and on ly if the corresponding magic numbers are equal. Since irrational numb ers require infinite precision, the algorithm for generating magic num bers is carried out using a double-precision floating-point approximat ion. This approximation is viewed as a hashing scheme, mapping the inf inite domain of the irrational numbers into finite computer words. The proposed hashing scheme was investigated experimentally, with the con clusion that it is a good and practical hashing method. In tests invol ving over a million randomly chosen tgraphs, we have not encountered a single collision. We conclude that this method for representation and management of types is practical, and offers novel possibilities for enforcing strict type matching at link time among separately compiled modules.