|
Standard ML provides the means to define generic, or reusable,
components of a system through the notion of a functor, or parameterized
module.
A typical example of the use of functors is provided by the priority queue example from
the previous chapter. We wish to define a generic priority queue package that is
parameterized by the ordering on the elements. This is achieved using the following
functor declaration
functor PrioQueue (structure E : ORDERED) :>
PRIO_QUEUE where type Elt.t = E.t =
struct
structure Elt = E
type prio_queue = ...
...
end
Note well that the result signature of the PrioQueue functor is specified
using an opaque ascription. This ensures that each instance of PrioQueue
generates a unique abstract type prio_queue. This ensures that
we do not accidentally confuse operations from two different priority queues, say
attempting to use the remove operation of one priority queue to remove an element from
another. However, since the result is sealed with an abstract type, we must make
certain to propagate that the element type of the instances is in fact the element type
specified as the argument to the functor. This is specified using the "where
type" clause on the result signature.
Specific priority queues for specific element types and orderings are constructed by
instantiating this functor with different ordering modules as in the following examples:
structure IntPQ = PrioQueue (structure E = IntLt)
structure StrPQ = PrioQueue (structure E = String)
We tend not to ascribe signatures to these bindings since the functor itself seals the
result with a specific signature. Notice that IntPQ.Elt.t = IntLt.t
= int and that StrPQ.Elt.t = String.t = string.
Another use of functors is to provide the "impedance matching" required to
make views useful. The actual String structure provided by Standard ML
doesn't name its type component t, and doesn't name its comparison operations
eq and lt. Therefore it is impossible to ascribe the
signature ORDERED to the standard structure String. The
required renaming can be effected using a functor, as follows:
functor StringAsOrd (structure S : STRING):ORDERED = struct
type t = S.string
val lt = S.<
val eq = S.=
end
structure StringOrd : ORDERED =
StringAsOrd (structure S = String)
Strictly speaking we don't need a functor to effect the coercion, but it is natural to
regard the renaming as an operation that we may perform on any structure with signature STRING.
For a more substantial example of the use of functors, let us return to the compiler
example from the preceding chapter. The components of the system may be built up
using functors as follows. First, we define functors corresponding to each component
of the system.
functor Symbol () = struct
type symbol = ...
fun create s = ...
...
end
functor Lexer (structure S : Symbol) :> LEXER where type Symbol.symbol = S.symbol =
struct
structure Symbol = S
type token = ...
fun lex cs = ...
...
end
functor SymTab (structure S : SYMBOL) :> SYMTAB where type Symbol.symbol = S.symbol =
struct
structure Symbol = S
type symtab = ...
fun lookup (s, st) = ...
...
end
functor AbsSyn (structure S : SYMBOL) :> ABSSYN where Symbol.symbol = S.symbol =
struct
structure Symbol = S
datatype ast = Identifier of Symbol.symbol | ...
...
end
functor Parser
(structure Lexer : LEXER
structure SymTab : SYMTAB
structure AbsSyn : ABSSYN
sharing Lexer.Symbol = SymTab.Symbol = AbsSyn.Symbol) :> PARSER = struct
fun parse ts = ...
end
Notice that a sharing specification is required in the parameter list of
the Parser functor to ensure that the components from which the parser module
is built share a common notion of symbol.
Since we have used opaque ascription on the result signatures of the Lexer,
SymTab, and AbsSyn functors, is it necessary to explicitly
propagate type sharing information from the argument of the functor to the result of the
functor. This ensures that the type Symbol.symbol in each application
of the functor is known to be equal to the type Symbol.symbol given as
argument to the functor. An alternative is to use transparent ascription, allowing
the compiler to fill in the evident type sharing properties that we have here made
explicit. For example, we might define the Lexer functor as follows:
functor Lexer (structure S : SYMBOL) : LEXER = ...
In effect we allow the compiler to insert where type clauses for us, for
it is implied by the definition of Lexer that Symbol.symbol in
the result is equal to the type S.symbol in the argument.
To build the system we apply these functors in dependency order to build up the set of
structures given in the last chapter.
structure Symbol : SYMBOL =
Symbol ()
structure Lexer : LEXER =
Lexer (structure S = Symbol)
structure SymTab : SYMTAB =
SymTab (structure S = Symbol)
structure AbsSyn : ABSSYN =
AbsSyn (structure S = Symbol)
structure Parser : PARSER =
Parser (structure Lexer = Lexer and SymTab = SymTab and AbsSyn= AbsSyn)
It is a good exercise to convince yourself that this series of functor applications is
type correct, and yields the same set of structures as were given explicitly in the
preceding chapter.
This example of using functors to construct a system from its constituent parts is an
example of full functorization. The idea is that each component of the
system is explicitly parameterized on the components on which it depends. The
components are explicitly linked together by applying the functors in dependency order.
This leaves nothing to chance in determining which components are to be linked into
which modules: the programmer is required to specify the linkage explicitly by a series of
functor applications. While explicit linking has the advantage of perspicuity, it is
nevertheless notationally burdensome, both because of the explicit applications of the
functors and because of the need to explicitly maintain type sharing information. In
practice we usually rely on a compilation manager to link modules for us in such
a way that type correctness is preserved. However, compilation management is not
part of the Standard ML language per se, but is rather a provided by each
implementation. (See the documentation for your compiler for details of how to use
its compilation manager.)
|