Type Checking and Modules for Multi-Methods

Abstract

<p>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.</p>