Computer Science Department
School of Computer Science, Carnegie Mellon University
What is a Recursive Module?
Karl Crary, Robert Harper, Sidd Puri
Keywords: Type systems, module systems, functional programming,
A hierarchical module system is an effective tool for structuring large
programs. Strictly hierarchical module systems impose an acyclic ordering
on import dependencies among program units. This can impede modular
programming by forcing mutually-dependent components to be consolidated
into a single module. Recently there have been several proposals for
module systems that admit cyclic dependencies, but it is not clear how
these proposals relate to one another, nor how one might integrate them
into an expressive module system such as that of Standard ML or O'Caml.
To address this question we provide a type-theoretic analysis of the
notion of a recursive module in the context of the "phase-distinction"
formalism for higher-order module systems. We extend this calculus
with a recursive module mechanism and a new form of signature, called a
recursively-dependent signature, to support the definition of recursive
modules. These extensions are justified by an interpretation in terms of
more primitive language constructs. This interpretation may also serve
as a for implementation.