Components and Types

Programs Consist of Components

Each component implements some services. Many also require the services of other components. The design of ML also reflects the belief that the components and connections form a dag-like hierarchy (i.e. a graph without cycles).

Manufacturing Components

The design of ML also recognizes that program components should be manufactured for re-use. In particular, when a programmer puts together a new component, the component should specify what kind of things it expects from the layer underneath, not the specific components. Dually, the component will only specify what kind of things it provides to the layer above:

The ellipses in this sketch are interfaces; the box is a component.

Functors, Signatures, and Structures

Functors and Signatures

Here is the syntax of a functor declaration:

functor F(structure s1: SIG1; ...; structure s2: SIG2) 
  :> SIG 
  = 
  struct 
    ...
  end

• the name of the functor: F;
• its imported structures as formal parameters (names): s1 ... s2;
• the signatures of the imports: SIG1 ... SIG2 (which are typically names);
• and the export signature of the functor: SIG.

signature SIG 
  = 
  sig
    ...
  end

A Simple Example

Consider the following concrete example of a signature and a functor definition:

signature VARIABLES 
  = 
  sig 
    type var
    val equal : var * var -> bool
  end

functor Variables() 
  :> VARIABLES
  = 
  struct 
    type var = string 
    fun equal(v1,v2) = (v1 = v2)
  end

signature SD 
  = 
  sig
    type term
  end 

functor StaticDistance(structure v : VARIABLES) 
  :> SD
  = 
  struct 
    ...
  end

Using Values from Structures

Inside of a functor we can refer to the pieces of an imported structure in two ways:

1. With

   s.name

   we refer to the entity called name in import s. The notation only makes sense if the signature for s specifies name.
2. If the functor's body contains the statement

   open s

   , all definitions specified in the signature of s become lexically bound. Adding this statement is dangerous if we don't know the entire signature because it may shadow some other binding. Use it with care.

Linking and Computing

After all the signatures and functors are defined, we can link the components together. We start with the bottom layer, that is, with those components that do not import other components:

(* Layer 0 *)
(* ------- *)
structure s1 = F1()
structure s2 = F2()

Now that we have the 0th or bottom layer, we can create those components that link to the bottom layer:

(* Layer 1 *)
(* ------- *)
structure s3 = F3(structure s = s1; structure t = s2)
structure s4 = F4(structure a = s3; structure t = s2)
...

Since the language of components is a functional language, we can also use nested function application to link the components together:

(* Layer 0 *)
(* ------- *)
structure s2 = F2() (* retains name because used more than once *)

(* Layer 1 *)
(* ------- *)
structure s4 = F4(structure a = F3(structure s = F1(); structure t = s2); 
                  structure t = s2)
...

[Note: The application of a functor can have a side-effect for both type checking and evaluation. It is therefore not just an option, but a necessity to consider whether F2 should be applied once or twice. The precise nature of the problem is beyond the scope of these notes.]

A Simple Example: Tables

Let us design a functor that creates environments for interpreters, i.e., tables that associate some form of variable with some form of value. An interpreter for a statically typed programming language requires at least two kinds of environments: one for mapping variables to run-time values and another one for mapping type variables to types. So being able to create environments several times, for different kinds of variables, is a natural desire.

When we design functors, we start by considering its export signature. An environment table supports two kinds of actions:

1. the extension of an existing environment with a variable and a value, and
2. the lookup of a variable in an existing environment.

This sketch suggests the following outline of a signature:

signature TABLE = 
    sig
	type table 

	val empty : table
	val extend : table * a-variable * a-value -> table
	val lookup : table * a-variable -> a-value
    end

Next we write down what kind of structures we expect as imports to the functor. As mentioned already, the table functor must import a structure that describes the domain elements. We also agreed that this structure must specify a type and an equality operation on the type:

signature DOMAIN =
    sig
	type var
	val equal : var * var -> bool
    end

Now we are ready to specify the header of the functor for environment tables:

functor Table(structure domain : DOMAIN) :> TABLE 

Coding the definitions in the functor is a straightforward exercise:

functor Table(structure d : DOMAIN) 
    :> TABLE 
    =
    struct 
	type domain = d.var
	type 'a table = domain -> 'a

	exception NotFound of domain
	val empty = 
	    (fn n => raise NotFound(n))

	fun extend(t,n,m) = 
	    (fn i => 
	     if d.equal(n,i) then m
	     else t(i))

	fun lookup(t,n) = t(n)
    end

Here are two functors for creating DOMAIN structures:

functor Var() :> DOMAIN 
    = 
    struct 
	type var = int
	val equal = (op =)
    end

functor TypeVar() :> DOMAIN
    = 
    struct 
	type var = string
	val equal = (op =)
    end

Linking functors together means to write down the intended functor applications. In this example, the Var and TypeVar functors make up layer 0:

structure var = Var()

structure type_var = TypeVar()

structure run_time = Table(structure domain = var);

structure tck_time = Table(structure domain = type_var);

After linking, we are ready to evaluate some simple examples, e.g., extending an environment with a variable and a value and looking up the same variable:

run_time1.extend(run_time1.empty,1,true) 

open run_time1;

extend(empty,1,true) 

Refining Signatures, Propagating Types

The expression

run_time1.extend(run_time1.empty,1,true) 

Based on this outline, we can refine the code for, say, lookup. When lookup encounters a leaf, it must check whether the information contains the key we are looking for. If yes, it return the information; otherwise it raises an exception:

	exception NotFound
	fun lookup(k,Leaf(x)) = 
	    if o.equal(k,i.info_key(x)) then x else raise NotFound 
	  | lookup(k,Node(l,i,r)) =
	    if o.less(k,i) then lookup(k,l) else lookup(k,r)

The key to the function definition is that what i.info_key returns is fed into o.equal, that is, the underlying type of the ordered structure and the keys in an information structure must be identical. If they aren't, we have a type conflict.

We could again use a where-clause to specify the desired constraint for the type checker:

functor Bst_F(structure i : INFO;
	      structure o : ORDERED 
	      where type o.ord = i.key)

In general, a functor might import many structures and three or more may need to agree on a type. For this quite common situation, ML provides a sharing-clause, which permits programmers to specify the constraint in a succinct fashion. For the running example, the specification is

functor Bst_F(structure i : INFO;
	      structure o : ORDERED 
	      sharing type i.key = o.ord)

ML's designer clearly showed a lot of foresight in the early 1980s with their careful design of program components and a language for linking them. Software engineers only now re-discover these ideas, typically called architectures or product lines (see Batory's talk). However, ML's module language still does not accommodate re-use as much as "product line programming" demands. There are three specific problems. First, ML makes it difficult to re-use functors with signatures that weren't designed together. Second, linking enforces a program organization that adheres to a strictly hierarchical schema; as practice has shown, systems are often cyclic graphs of components, not just dags. Finally, the language of linking is a restrictive first-order functional language. Again, practice suggests that on occasion "component programmers" want more power.

Renaming at Module Boundaries

Suppose some ML programmer has created a functor for integers:

signature INTS
    = 
    sig
	type my_int

	val zero : my_int

	val succ : my_int -> my_int
	val is_zero : my_int -> bool

	val equal : my_int * my_int -> bool
	val less : my_int * my_int -> bool 
    end

functor Ints() :> INTS 
    = 
    struct 
	datatype my_int = zero | succ of my_int 
	    
	fun is_zero(zero) = true
	  | is_zero(succ(x)) = false

	...
    end 

Warning