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