Previous Contents Next

Modules as Compilation Units

The Objective CAML distribution includes a number of predefined modules. We saw in chapter 8 how to use these modules in a program. Here, we will show how users can define similar modules.

Interface and Implementation

The module Stack from the distribution provides the main functions on stacks, that is, queues with ``last in, first out'' discipline.

# let queue = Stack.create () ;;
val queue : '_a Stack.t = <abstr>
# Stack.push 1 queue ; Stack.push 2 queue ; Stack.push 3 queue ;;
- : unit = ()
# Stack.iter (fun n -> Printf.printf "%d " n) queue ;;
3 2 1 - : unit = ()


Since Objective CAML is distributed with full source code, we can look at the actual implementation of stacks.

ocaml-2.04/stdlib/stack.ml
type 'a t = { mutable c : 'a list }
exception Empty
let create () = { c = [] }
let clear s = s.c <- []
let push x s = s.c <- x :: s.c
let pop s = match s.c with hd::tl -> s.c <- tl; hd | [] -> raise Empty
let length s = List.length s.c
let iter f s = List.iter f s.c


We see that the type of stacks (written Stack.t outside the Stack module and just t inside) is a record with one mutable field containing a list. The list holds the contents of the stack, with the list head corresponding to the stack top. Stack operations are implemented as the basic list operations applied to the field of the record.

Armed with this insider's knowledge, we could try to access directly the list representing a stack. However, Objective CAML will not let us do this.

# let list = queue.c ;;
Characters 12-19:
Unbound label c
The compiler complains as if it did not know that Stack.t is a record type with a field c. It is actually the case, as we can see by looking at the interface of the Stack module.

ocaml-2.04/stdlib/stack.mli
(* Module [Stack]: last-in first-out stacks *)
(* This module implements stacks (LIFOs), with in-place modification. *)

type 'a t (* The type of stacks containing elements of type ['a]. *)

exception Empty (* Raised when [pop] is applied to an empty stack. *)

val create: unit -> 'a t
(* Return a new stack, initially empty. *)
val push: 'a -> 'a t -> unit
(* [push x s] adds the element [x] at the top of stack [s]. *)
val pop: 'a t -> 'a
(* [pop s] removes and returns the topmost element in stack [s],
or raises [Empty] if the stack is empty. *)
val clear : 'a t -> unit
(* Discard all elements from a stack. *)
val length: 'a t -> int
(* Return the number of elements in a stack. *)
val iter: ('a -> unit) -> 'a t -> unit
(* [iter f s] applies [f] in turn to all elements of [s],
from the element at the top of the stack to the element at the
bottom of the stack. The stack itself is unchanged. *)


In addition to comments documenting the functions of the module, this file lists explicitly the value, type and exception identifiers defined in the file stack.ml that should be visible to clients of the Stack module. More precisely, the interface declares the names and type specifications for these exported definitions. In particular, the type name t is exported, but the representation of this type (that is, as a record with one c field) is not given in this interface. Thus, clients of the Stack module do not know how the type Stack.t is represented, and cannot access directly values of this type. We say that the type Stack.t is abstract, or opaque.

The interface also declares the functions operating on stacks, giving their names and types. (The types must be provided explicitly so that the type checker can check that these functions are correctly used.) Declaration of values and functions in an interface is achieved via the following construct:

Syntax


val nom : type


Relating Interfaces and Implementations

As shown above, the Stack is composed of two parts: an implementation providing definitions, and an interface providing declarations for those definitions that are exported. All module components declared in the interface must have a matching definition in the implementation. Also, the types of values and functions as defined in the implementation must match the types declared in the interface.

The relationship between interface and implementation is not symmetrical. The implementation can contain more definitions than requested by the interface. Typically, the definition of an exported function can use auxiliary functions whose names will not appear in the interface. Such auxiliary functions cannot be called directly by a client of the module. Similarly, the interface can restrict the type of a definition. Consider a module defining the function id as the identity function (let id x = x). Its interface can declare id with the type int -> nt (instead of the more general 'a -> a). Then, clients of this module can only apply id to integers.

Since the interface of a module is clearly separated from its implementation, it becomes possible to have several implementations for the same interface, for instance to test different algorithms or data structures for the same operations. As an example, here is an alternate implementation for the Stack module, based on arrays instead of lists.


type 'a t = { mutable sp : int; mutable c : 'a array }
exception Empty
let create () = { sp=0 ; c = [||] }
let clear s = s.sp <- 0; s.c <- [||]
let size = 5
let increase s = s.c <- Array.append s.c (Array.create size s.c.(0))

let push x s =
if s.sp >= Array.length s.c then increase s ;
s.c.(s.sp) <- x ;
s.sp <- succ s.sp

let pop s =
if s.sp = 0 then raise Empty
else let x = s.c.(s.sp) in s.sp <- pred s.sp ; x

let length s = s.sp
let iter f s = for i = pred s.sp downto 0 do f s.sc.(i) done


This new implementation satisfies the requisites of the interface file stack.mli. Thus, it can be used instead of the predefined implementation of Stack in any program.

Separate Compilation

Like most modern programming languages, Objective CAML supports the decomposition of programs into multiple compilation units, separately compiled. A compilation unit is composed of two files, an implementation file (with extension .ml) and an interface file (with extension .mli). Each compilation unit is viewed as a module. Compiling the implementation file name.ml defines the module named Name1.

Values, types and exceptions defined in a module can be referenced either via the dot notation (Module.identifier), also known as qualified identifiers, or via the open construct.

      a.ml        b.ml
type t = { x:int ; y:int } ;; let val = { A.x = 1 ; A.y = 2 } ;;
let f c = c.x + c.y ;; A.f val ;;
  open A ;;
  f val ;;

An interface file (.mli file) must be compiled using the ocamlc -c command before any module that depends on this interface is compiled; this includes both clients of the module and the implementation file for this module as well.

If no interface file is provided for an implementation file, Objective CAML considers that the module exports everything; that is, all identifiers defined in the implementation file are present in the implicit interface with their most general types.

The linking phase to produce an executable file is performed as described in chapter 7: the ocamlc command (without the -c option), followed by the object files for all compilation units comprising the program. Warning: object files must be provided on the command line in dependency order. That is, if a module B references another module A, the object file a.cmo must precede b.cmo on the linker command line. Consequently, cross dependencies between two modules are forbidden.

For instance, to generate an executable file from the source files a.ml and b.ml, with matching interface files a.mli and b.mli, we issue the following commands:
> ocamlc -c a.mli
> ocamlc -c a.ml
> ocamlc -c b.mli
> ocamlc -c b.ml
> ocamlc a.cmo b.cmo
Compilation units, composed of one interface file and one implementation file, support separate compilation and information hiding. However, their abilities as a general program structuring tool are low. In particular, there is a one-to-one connection between modules and files, preventing a program to use simultaneously several implementations of a given interface, or also several interfaces for the same implementation. Nested modules and module parameterization are not supported either. To palliate those weaknesses, Objective CAML offers a module language, with special syntax and linguistic constructs, to manipulate modules inside the language itself. The remainder of this chapter introduces this module language.


Previous Contents Next