Typechecking and Modules for Multi-Methods

Craig Chambers and Gary Leavens
Two major obstacles hindering the wider acceptance of multi-methods are concerns over the lack of encapsulation and modularity and the absence of static typechecking in existing multi-method-based languages. This paper addresses both of these problems. We present a polynomial-time static typechecking algorithm that checks the conformance, completeness, and consistency of a group of method implementations with respect to declared message signatures. This algorithm improves on previous algorithms by handling separate type and inheritance hierarchies, abstract classes, and graph-based method lookup semantics. We also present a module system that enables independently-developed code to be fully encapsulated and statically typechecked on a per-module basis. To guarantee that potential conflicts between independently-developed modules have been resolved, a simple well-formedness condition on the modules comprising a program is checked at link-time. The typechecking algorithm and module system are applicable to a range of multi-method-based languages, but the paper uses the Cecil language as a concrete example of how they can be applied.
Appeared in ACM Transactions on Programming Languages (TOPLAS), Vol. 17, No. 9, November, 1995, and as UW-CS TR 95-08-05.

An earlier version of this work appeared in the OOPSLA'94 Conference Proceedings, Portland, Oregon, October, 1994 and as UW-CS TR 94-03-01.

To get a PostScript file containing just the main body of the paper (30 pages total; what appeared in TOPLAS), click here.

To get the PostScript file for the full technical report, with proofs (68 pages total), click here.

Cecil/Vortex Project