Paper announcement: What is a Recursive Module?

We would like to announce the availability of the following paper at URL
http://www.cs.cmu.edu/~crary/papers/index.html or
http://www.cs.cmu.edu/~rwh/papers.  This is a substantially revised version
of the paper we announced on this list last October.

Karl Crary
Robert Harper


What is a Recursive Module?

Karl Crary   Robert Harper   Sidd Puri

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 ML.

To address this question we provide a type-theoretic analysis of the
notion of a recursive module in the context of a "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 guide for implementation.