A simple technique detects structural type clashes across compilation units with an arbitrarily high degree of confidence. The type of each external object is described in canonical form. A hash function compresses the description into a short code. If the code is embedded in a symbol-table name, then consistency can be checked by an ordinary linker. For distributed programs, runtime checking of message types can be performed with very little overhead.
|Number of pages
|IEEE Transactions on Software Engineering
|Published - Aug 1988
Bibliographical noteFunding Information:
A type-checking mechanism for separate compilation must strike a difficult balance between conservatism and convenience. On the one hand, it should prevent the use of compilation units that make incompatible assumptions about their interface. On the other hand, it should cause as few unnecessary recompilations as possible. When definitions change, an ideal mechanism would recompile all and only those pieces of a program that would otherwise malfunction. Approaching this ideal has proven surprisingly difficult, enough so that many programming systems provide no checking whatsoever. We believe that a simple and easy-to-use type-checking mechanism for separate compilation is extremely important. We are particularly interested in a mechanism that can be extended to provide checking for messages exchanged between the separately loaded modules of a distributed program. We describe a technique that achieves simplicity and efficiency at the expense of an arbitrarily small probability of failure. For the semantics of types, we adopt the rules of structural type equivalence [3, p. 921. The alternative, name equivalence, requires the compiler to maintain a global name space for types. Our interest in distributed programs makes such an approach impractical: 1) A global name space requires a substantial amount of book-keeping, even on a single machine. For a distributed language, information must be kept consistent on every node at which processes may be created. While the task is certainly not impossible, the relative scarcity of compilers that enforce name equivalence across compilation units suggests that it is not trivial either. 2) Compilers that do enforce name equivalence across compilation units usually do so by affixing time stamps tojfiles of declarations. A change or addition to one declaration in a file appears to modify the others. A global name space for distributed programs can be expected to devote a file to the interface for each distributed resource. Mechanisms can be devised to allow simple extensions to an interface, but certain enhancements will inevitably invalidate all the users of a resource. In a sequential program, enhancements to one compilation unit may force the unnecessary recompilation Manuscript received October 31. 1985: re\iwd February 28. 1986. This work was supported in part by NSF Grant MCS-8105904, by ARPA Contract N0014/82/C/2087, and by a Bell Laboratories Doctoral Scholarship. M. L. Scott is with the Department of Computer Science, University of Rochester, Rochester, NY 14627. R. A. Finkel is with the Department of Computer Sciences, University of Wisconsin, Madison. WI 53706. IEEE Log Number 8822012.
ASJC Scopus subject areas