Smartest Recompilation

Abstract:

To separately compile a program module in traditional statically--typed
languages, one has to manually write down an import interface which
explicitly specifies all the external symbols referenced in the module.
Whenever the definitions of these external symbols are changed, the module
has to be recompiled. In this paper, we present an algorithm which can
automatically infer the ``minimum'' import interface for any
module in languages based on the Damas--Milner type discipline (e.g., ML).
By ``minimum'', we mean that the interface specifies a set of assumptions
(for external symbols) that are just enough to make the module type--check and
compile. By compiling each module using its ``minimum'' import interface,
we get a separate compilation method that can achieve the following
optimal property: A compilation unit never needs to be recompiled
unless its own implementation changes.

This technical report has been published as

Smartest Recompilation. Andrew W. Appel, Proc. twentieth ACM
Symp. on Principles of Programming Languages, January 1993.