Lal George
David B. MacQueen
John H. Reppy
Jon G. Riecke
Bell Laboratories
Good programming languages provide ways of organizing code, mainly as a way to support the evolution of a program. For example, some class-based languages like Java [1] include interfaces that specify the types of methods and fields. If the implementation, but not the interface, of a class changes (e.g., due to bug fixes or performance tuning), then other parts of a program need not be modified. Inheritance in Java and C++ [8], and templates in C++, are other code organization mechanisms. Inheritance allows a programmer to enhance an existing class with more methods or change existing methods; templates allow a programmer to parameterize classes.
Class-based languages are not the only languages with mechanisms for organizing code. Module-based languages like CLU [4], Ada, Modula-3 [2], and Standard ML (SML) [7] also provide notions of such mechanisms. This paper briefly describes the SML module system, gives some anecdotal but extensive evidence of its usefulness, and compares it with class-based mechanisms. Our experience with the SML module system shows that one can easily modify and reuse other parts of the system in in programs with more than 100,000 lines of code.
SML is a module-based, rather than class-based, language (no ``objects'' are generated from modules). It contains ways of defining interfaces, implementations, parameterized modules, abstract data types, as well as mechanisms for name-space management and hiding of implementation details.
In SML, interfaces--called signatures--can be written separately from implementations--called structures, and both signatures and structures can be named. Signatures can contain type declarations, definitions of the types of functions and values (like prototypes in ANSI C [3]), and signatures representing substructures. Structures, on the other hand, can contain type definitions, implementations of functions and values, and substructures.
For example, suppose we wish to describe ordered types. The signature in SML would read
signature ORD =
sig
type ordered
val stringToOrd : string -> ordered
val compare : ordered * ordered -> bool
end
The signature ORD has a type ordered and a function
compare which, given two values of type ordered (the
* represents the type of pairs), returns a boolean result.
A structure corresponding to the signature is
structure Ord =
struct
type ordered = string
fun stringToOrd x = x
fun compare (x:string,y:string) = (x < y)
end
The structure gives the implementation of the type (a
concrete representation), and an implementation of the
compare function. Outside the structure, we can refer to the
compare function using the qualified name
Ord.compare.
Much of the novelty of the SML module system comes from a many-to-many relationship between structures and signatures. Structures can be matched against multiple signatures, yielding structures that share implementation details but have different interfaces. Correspondingly, a structure has a default signature, but it can be matched against signatures to yield structures with more restrictive views. For instance, we can match the structure Ord with the signature ORD and get a new structure Ord1 as follows:
structure Ord1 : ORD = Ord
Of course, Ord1 and Ord have exactly the same
signature. If Ord included a declaration for a function
equal, then equal would not be a part of
Ord1--the function would be ``thinned'' from the structure.
SML also includes parameterized modules, called functors, that accept structures as arguments and return structures as results. For instance, suppose
signature ORDSET =
sig
structure Key : ORD
type item = Key.ordered
type set
val empty : set
val insert : item * set -> set
end
represents sets of elements whose underlying type has an order
relation. A functor can be written that accepts a structure with
signature Ord and produces a structure with signature
ORDSET:
functor OrdSet (structure K : ORD) : ORDSET =
struct
structure Key = K
type item = Key.ordered
type set = item list
val empty = [] (* the empty list *)
fun insert (x,s) = x :: s (* consing to the head of the list *)
end
Functors thus provide a way to control linking.
All of the above examples use ``transparent'' types--that is, the types in structures are not abstract. For example, in Ord, the type ordered is known to be string outside the structure, so that
Ord.compare ("hello","world")
is type correct. One can also match a signature ``opaquely.'' If
we write
structure OrderedKey :> ORDSET = OrdSet (structure K = Ord)
then the type Ord2.ordered is not known to be int
outside the structure, making Ord2 into an abstract data
type [5]. This prevents accidental equivalences of
types, and forces the programmer to respect the data abstraction.
The New Jersey implementation of SML (developed at Bell Labs and Princeton) enhances the SML module system with higher-order functors (functors that can accept other functors as arguments, or return functors as results), and a compilation manager that statically determines dependencies between source files, and recompiles only those files that need to be recompiled when a program changes. We give a more detailed account of these features in the final version.
The module system has proven to be very useful in writing
large programs (over 100,000 lines), including the SML of New Jersey compiler
and other SML compilers (MLKit, TIL), HOL90 and other theorem provers,
database query languages (Kleisli/CPL), and operating systems (Express).
A list of large applications may be found at
SPMamphttp://www.cs.princeton.edu/ appel/smlnj/projects.html&.
One example that exploits the flexibility of the module system is a framework, called MLRISC, in the SML of NJ compiler for building reusable code generators. Native code generators for modern processors take much time to debug and write, and it is often difficult to reuse the code for other architectures or other source languages. The MLRISC framework has been successfully used for multiple architectures (Intel x86, DEC Alpha, HP PA, and PowerPC) and deals elegantly with the special requirements imposed by the execution model of different high-level source languages. Nearly all aspects of back-end code generation and advanced optimizations such as global-register allocation, profile-driven superblock and percolation-style scheduling can be reused in all of the code generators.
In a heavily parameterized system like MLRISC, there are a large number of modules and dependencies. For example, Figure 1 shows the module dependencies of various functors that make up part of the system. Each of the functor inputs represents client- or front-end-specific information that is fed into the system. For example,
In integrating a system that involves modules created by these functors, it must be the case that they were created with the same base modules. For example, we want the pseudo-ops in flowgraphs to be the same abstraction that was used to define the MLRISC intermediate representation (see Figure 2). Sharing constraints in SML modules provide exactly this mechanism, and are used here to assert that identity of modules used to specialize other modules. Even though the INSTRUCTIONS interface is abstract and general, all optimizations in MLRISC are done directly on a flowgraph of target machine instructions. The final paper will describe in more detail how this is done, and how the use of higher-order functors can be used to simplify the interface presented to the user.
Many examples of code reuse via modules can be found in the SML/NJ Library, which is part of the SML/NJ distribution. Finite maps and sets with ordered keys are implemented as functors parameterized over the key type (the library provides three different implementations). For example,
structure IntSet = BinarySetFn (struct
type ord_key = int
val compare = Int.compare
end)
creates an implementation of sets of integers using balanced
binary trees as the representation.
Other examples include hash tables, a pretty-printing engine that
is parameterized over its output device, sorting routines, and
dynamically-sized arrays.
The style of reuse exhibited by libraries like this is similar to
that found in the C++ Standard Template Library.