Typechecking and Modules for Multi-Methods
				  by
		  Craig Chambers and Gary T. Leavens
				   
			       Abstract

Two major obstacles preventing the wider acceptance of multi-methods
are concerns over the lack of encapsulation and modularity and the
lack 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 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, the presence of abstract classes, and graph-based method
lookup semantics. We prove formally that our algorithm fulfills its
specification. 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.