What is a recursive module?

A hierarchical module system is an effective tool for structuring large pro grams. Strictly hierarchical module systems impose an acyclic ordering on i mport 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 t o one another, nor how one might integrate them into an expressive module s ystem 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 f or higher-order module systems. We extend this calculus with a recursive mo dule 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 con structs. This interpretation may also serve as a guide for implementation.