Return to module.tex CVS log

Up to [Research Unix] / researchv10no / cmd / sml / doc / refman

Annotation of researchv10no/cmd/sml/doc/refman/module.tex, revision 1.1

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.