![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to module.tex CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / sml / doc / refman|
Return to module.tex CVS log | Up to [Research Unix] / researchv10no / cmd / sml / doc / refman |
1.1 root 1: \chapter{Modules}
2: ML provides a powerful module system, which can be used to partition
3: programs along clean interfaces.
4:
5: \section{Structures}
6:
7: In its simplest form, a module is
8: (syntactically) just a collection of declarations viewed as a unit,
9: or (semantically) the environment defined by those definitions.
10: This is one form of a {\em structure--expression}:
11: \verb"struct"~dec~\verb"end". For example, the following structure--expression represents an implementation of stacks:
12: \begin{verbatim}
13: struct
14: datatype 'a stack = Empty | Push of 'a * 'a stack
15: exception Pop and Top
16: fun empty(Empty) = true | empty _ = false
17: val push = Push
18: fun pop(Push(v,s)) = s | pop(Empty) = raise Pop
19: fun top(Push(v,s)) = v | top(Empty) = raise Top
20: end
21: \end{verbatim}
22: Structure--expressions and ordinary expressions are distinct classes;
23: structure--expressions may be bound using the \verb"structure"
24: keyword to structure--names, while ordinary expressions are
25: bound using \verb"val" to value--variables.
26: The form of a \verb"structure" binding is as follows:
27: \begin{quote}
28: \verb"structure" name \verb"=" structure--expression
29: \end{quote}
30: Thus, we might make a structure Stack using the structure--expression
31: shown above:
32: \begin{verbatim}
33: structure Stack = struct
34: datatype . . .
35: exception . . .
36: . . .
37: end
38: \end{verbatim}
39:
40: The environment $E$ that binds the identifiers \verb"stack",
41: \verb"Pop", \verb"empty", etc. is now itself bound to the
42: structure--identifier \verb"Stack". To refer to names in $E$, {\em
43: qualified identifiers} must be used. A qualified identifier consists
44: of a structure--name, a dot, and the name of a structure component,
45: e.g. \verb"Stack.empty" (a value), \verb"Stack.stack" (a type),
46: \verb"Stack.Pop" (an exception), etc.
47:
48: {\bf Structure closure:} In order to isolate the interface between a
49: structure and its context, a \verb"struct" phrase is not allowed to
50: contain global references to types, values, or exceptions, except for
51: pervasive primitives of the language like \verb"int", \verb"nil",
52: etc. It can, however, contain global references to other structures,
53: signatures, and functors, including qualified names referring to
54: compenents (values, types, etc.) of other structures.
55:
56: There are three forms of structure-expression:
57: \begin{enumerate}
58: \item An environment enclosed in \verb"struct" ... \verb"end" (as
59: above),
60:
61: \item An identifer that has been previously bound in a
62: \verb"structure" declaration, and
63:
64: \item A functor application \verb"F("{\it str}\verb")", where
65: \verb"F" is the name of a functor and {\it str} is a structure
66: expression.
67: \end{enumerate}
68: Thus, the declaration \verb"structure~Pushdown~=~Stack" binds the
69: name \verb"Pushdown" to the same structure that \verb"Stack" is bound
70: to; here, \verb"Stack" is an example of the second kind of structure
71: expression.
72:
73: \subsection{Accessing structure components}
74: The bindings making up a structure define named {\em components} of
75: the structure, as in a record. To refer to such components we use
76: qualified names, which are formed by appending a period followed by a
77: component name to the name of a structure. For instance,
78: \verb"Stack.empty" refers to the function \verb"empty" defined in the
79: structure \verb"Stack". If the qualified name designates a
80: substructure of a structure, then it too has components; {\em e.g.}
81: \verb"A.B.x" denotes the component \verb"x" of the substructure
82: \verb"B" of a structure \verb"A".
83:
84: Qualifiers can be attached only to names; they do not apply to other
85: forms of structure expressions. Qualified names are treated as
86: single lexical units; the dot is not an infix operator.
87:
88: Direct access to the bindings of a structure is provided by the
89: \verb"open" declaration, which is analagous to the ``with'' clause of
90: Pascal. For example, in the scope (determined in the usual way) of
91: the declaration
92: \begin{quote}
93: \verb"open Stack"
94: \end{quote}
95: the names \verb"stack", \verb"empty", \verb"pop", etc. refer to the
96: corresponding components of the \verb"Stack" structure. It is as
97: though the body of the structure definition had been inserted in the
98: program at that point, except that the bindings are not recreated,
99: but are instead simply ``borrowed'' from the opened structure.
100: \verb"open" declarations follow the usual rules for visibility, so
101: that if \verb"A" and \verb"B" are two structures containing a binding
102: for \verb"x" (of the same flavor, of course), then after opening both
103: \verb"A" and \verb"B" with the declaration
104: \begin{quote}
105: \verb"open A" \\
106: \verb"open B"
107: \end{quote}
108: the unqualified identifier \verb"x" will be equivalent to
109: \verb"B.x". The \verb"x" component of \verb"A" can still be referred
110: to as \verb"A.x", unless \verb"B" also contains a substructure named
111: \verb"A".
112:
113: Qualified identifiers do not have infix status. If \verb"+" is
114: declared infix in a structure \verb"A", the qualified identifier
115: \verb"A.+" is not an infix identifier. However, when an identifier
116: is made visible by opening a structure, it retains its infix status,
117: if any. AMBIGUOUS.
118:
119: The declaration \verb"open A B C" is equivalent to \verb"open A; open
120: B; open C".
121:
122: \subsection{Evaluating structure expressions}
123: The evaluation of a structure expression {\em str} depends on its
124: form, and assumes a current structure environment $SE$ that binds
125: structures and functors to names. Informally, evaluation proceeds as
126: follows:
127: \begin{enumerate}
128: \item If {\em str} is an encapsulated declaration ({\it i.e.}
129: \verb"struct"...\verb"end"), then the body declarations are evaluated
130: relative to $SE$ and the {\em pervasive} value, exception, and type
131: environments of ML (that is, the environments binding the built-in
132: primitives of the language). The resulting environment is packaged
133: as a structure and returned. The evaluation of value bindings may
134: have an effect on the store (the mapping of references to contents);
135: the new store is returned as well, to be used in subsequent
136: expression evaluations.
137:
138: \item If {\em str} is a simple name, then its binding in $SE$ is
139: returned. If it is qualified name, then it is used as an access path
140: starting with $SE$ and the designated substructure is returned.
141:
142: \item If {\em str} is a functor application
143: \verb"F("~$str'$~\verb")", where the functor \verb"F" is declared
144: by \verb"functor F ( A ) = "~$body$,
145: the parameter structure $str'$ is
146: evaluated in $SE$ yielding structure $s_1$; then the ``body'' of the
147: definition of \verb"M", which is a structure expression, is evaluated
148: in $SE+\{A \mapsto s_1 \}$. In other words, functor applications are
149: evaluated in a conventional call-by-value fashion.
150: \end{enumerate}
151:
152: \subsection{Evaluating structure declarations}
153: To evaluate a simple structure declaration, one evaluates the
154: defining structure expression in the current environment $SE$ and
155: returns the binding of the name of the left hand side to the
156: resulting structure. If evaluation of a structure expression raises
157: an (untrapped) exception, then the declaration has no effect.
158:
159: \subsection{Structure equivalence}
160: For certain purposes, such as checking sharing constraints
161: (Section~\ref{sharing}) we must be able to determine whether two
162: (references to) structures are equal or ``the same.'' Here
163: structures are treated somewhat like datatypes; each evaluation of an
164: encapsulated declaration or functor application creates a distinct
165: new structure, and all references to this structure are considered
166: equal. Thus after the following declarations:
167: \begin{verbatim}
168: structure S1 = struct ... end
169: structure S2 = S1
170: structure S3 = struct val x = 4 end
171: structure S4 = struct val x = 4 end
172: \end{verbatim}
173: the names \verb"S1" and \verb"S2" refer to the same structure and are
174: ``equal,'' whereas \verb"S3" and \verb"S4" are different structures
175: and are not equal, even though the right-hand-sides are identical.
176:
177: \section{Signatures}
178: It is often useful to explicitly constrain a structure binding to
179: limit the visibility of its fields. This is done with a {\em
180: signature}, which is to a structure binding as a type constraint is to a
181: value binding. For example, we might write a signature for the
182: \verb"Stack" module as
183: \begin{verbatim}
184: sig type 'a stack
185: exception Pop and Top
186: val Empty : 'a stack
187: val push : 'a * 'a stack -> 'a stack
188: val empty : 'a stack -> bool
189: val pop : 'a stack -> 'a stack
190: val top : 'a stack -> 'a
191: end
192: \end{verbatim}
193: The signature mentions the structure components that will be visible
194: outside the structure.
195:
196: Signatures may be bound to identifiers by a signature declaration,
197: \begin{quote}
198: \verb"signature" {\it sig-Id} \verb"=" {\it sig-expr}
199: \end{quote}
200: where {\it sig-Id} is an identifier and {\it sig-expr} is a signature
201: expression---either a \verb"sig"...\verb"end" phrase or a previously
202: bound signature identifier. Thus, the signature above could be bound
203: to the identifier \verb"STACK" by the declaration
204: \begin{verbatim}
205: signature STACK =
206: sig type 'a stack
207: exception Pop and Top
208: . . .
209: end
210: \end{verbatim}
211:
212: A signature can be used to constrain a structure by including it in a
213: structure declaration:
214: \begin{quote}
215: \verb"structure" {\it str-id} \verb":" {\it sig-expr} \verb"=" {\it str}
216: \end{quote}
217: For example, we could write
218: \begin{verbatim}
219: structure Stack1 : STACK = Stack
220: \end{verbatim}
221: Now the constructor \verb"Push" is not a visible component of the
222: \verb"Stack1" structure, since it doesn't appear in the signature;
223: the qualified identifier \verb"Stack1.Push" is erroneous.
224: Furthermore, since \verb"stack" is mentioned in the signature only as
225: a \verb"type" constructor and not as a \verb"datatype" constructor,
226: the identifier \verb"Stack1.stack" is usable as a type but not a datatype.
227: Finally, since the constructor \verb"Empty" is mentioned as a
228: \verb"val" in the signature, but not as a constructor ({\it i.e.} as
229: part of a datatype specification), then \verb"Stack1.Empty" may be
230: applied as a function but not matched in a pattern.
231:
232: There are many signatures that can match the structure \verb"Stack".
233: One of the ``broadest'' is
234: \begin{verbatim}
235: structure Stack2 : sig
236: datatype 'a stack = Empty | Push of 'a * 'a stack
237: exception Pop and Top
238: val empty : 'a stack -> bool
239: val push : 'a * 'a stack -> 'a stack
240: val pop : 'a stack -> 'a stack
241: val top : 'a stack -> 'a
242: end
243: = Stack
244: \end{verbatim}
245: and the ``narrowest'' is
246: \begin{verbatim}
247: structure Stack3 : sig end = Stack
248: \end{verbatim}
249: Now, the structure \verb"Stack2" is equivalent to \verb"Stack"; it is
250: the ``same'' structure, and all the same fields are visible. The
251: structure \verb"Stack3" has no components; there are no qualified
252: identifiers beginning with \verb"Stack3." However, \verb"Stack3" is
253: the ``same'' for structure-equivalence purposes as \verb"Stack",
254: \verb"Stack1", and \verb"Stack2"; signature constraints do not change
255: the identity of a structure, just which fields are visible.
256:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.