Software reuse through parametric modules

Lal George      David B. MacQueen      John H. Reppy      Jon G. Riecke
Bell Laboratories

Introduction

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.

Overview of SML Modules

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.

Example: MLRISC

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.


  
Figure 1: MLRISC Module dependencies
\begin{figure}
\begin{center}
\mbox{\epsfxsize=4in
\epsffile {pictures/eps/sharing1.eps}
}\end{center}\end{figure}

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,

MLRISC flowgraphs are specialized using the target architecture instructions and front-end-specific data-layout primitives in the form of pseudo-ops.
  
Figure 2: MLRISC Sharing constraints
\begin{figure}
\begin{center}
\mbox{\epsfysize=1.25in
\epsffile {pictures/eps/sharing2.eps}
}\end{center}\end{figure}

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.

Example: SML/NJ Library

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.

References

1
James Gosling, Bill Joy, and Guy Steele.
The Java(tm) Language Specification.
Addison Wesley, 1996.

2
Samuel P. Harbison.
Modula-3.
Prentice Hall, 1992.

3
Brian W. Kernighan and Dennis M. Ritchie.
The C Programming Language (Second Edition).
Prentice Hall, 1988.

4
Barbara H. Liskov and J. V. Guttag.
Abstraction and Specification in Program Development.
McGraw Hill/MIT Press, 1986.

5
Barbara H. Liskov and S. N. Zilles.
Programming with abstract data types.
ACM SIGPLAN Notices, 9:50-59, 1974.

6
David B. MacQueen.
Modules for Standard ML.
In Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming, pages 198-207. ACM, 1984.

7
Robin Milner, Mads Tofte, Robert Harper, and David MacQueen.
The Definition of Standard ML (Revised).
MIT Press, 1997.

8
Bjarne Stroustrup.
The C++ Programming Language (Second Edition).
Addison Wesley, 1991.



Lal George
6/29/1998