1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="generator" content="hevea 2.32">
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1">
<link rel="stylesheet" type="text/css" href="manual.css">
<title>8.2 Recursive modules</title>
</head>
<body>
<a href="letrecvalues.html"><img src="previous_motif.svg" alt="Previous"></a>
<a href="extn.html"><img src="contents_motif.svg" alt="Up"></a>
<a href="privatetypes.html"><img src="next_motif.svg" alt="Next"></a>
<hr>
<h2 class="section" id="s:recursive-modules"><a class="section-anchor" href="#s:recursive-modules" aria-hidden="true"></a>8.2 Recursive modules</h2>
<p>
<a id="hevea_manual.kwd206"></a>
<a id="hevea_manual.kwd207"></a></p><p>(Introduced in Objective Caml 3.07)</p><div class="syntax"><table class="display dcenter"><tr class="c019"><td class="dcell"><table class="c001 cellpading0"><tr><td class="c018">
<a class="syntax" href="modules.html#definition"><span class="c010">definition</span></a></td><td class="c015">::=</td><td class="c017">
...
</td></tr>
<tr><td class="c018"> </td><td class="c015">∣</td><td class="c017"> <span class="c004">module</span> <span class="c004">rec</span> <a class="syntax" href="names.html#module-name"><span class="c010">module-name</span></a> <span class="c004">:</span> <a class="syntax" href="modtypes.html#module-type"><span class="c010">module-type</span></a> <span class="c004">=</span> <a class="syntax" href="modules.html#module-expr"><span class="c010">module-expr</span></a>
{ <span class="c004">and</span> <a class="syntax" href="names.html#module-name"><span class="c010">module-name</span></a> <span class="c004">:</span> <a class="syntax" href="modtypes.html#module-type"><span class="c010">module-type</span></a> <span class="c004">=</span> <a class="syntax" href="modules.html#module-expr"><span class="c010">module-expr</span></a> }
</td></tr>
<tr><td class="c018"> </td></tr>
<tr><td class="c018">
<a class="syntax" href="modtypes.html#specification"><span class="c010">specification</span></a></td><td class="c015">::=</td><td class="c017">
...
</td></tr>
<tr><td class="c018"> </td><td class="c015">∣</td><td class="c017"> <span class="c004">module</span> <span class="c004">rec</span> <a class="syntax" href="names.html#module-name"><span class="c010">module-name</span></a> <span class="c004">:</span> <a class="syntax" href="modtypes.html#module-type"><span class="c010">module-type</span></a>
{ <span class="c004">and</span> <a class="syntax" href="names.html#module-name"><span class="c010">module-name</span></a><span class="c004">:</span> <a class="syntax" href="modtypes.html#module-type"><span class="c010">module-type</span></a> }
</td></tr>
</table></td></tr>
</table></div><p>Recursive module definitions, introduced by the <span class="c004">module rec</span> …<span class="c004">and</span> … construction, generalize regular module definitions
<span class="c004">module</span> <a class="syntax" href="names.html#module-name"><span class="c010">module-name</span></a> <span class="c004">=</span> <a class="syntax" href="modules.html#module-expr"><span class="c010">module-expr</span></a> and module specifications
<span class="c004">module</span> <a class="syntax" href="names.html#module-name"><span class="c010">module-name</span></a> <span class="c004">:</span> <a class="syntax" href="modtypes.html#module-type"><span class="c010">module-type</span></a> by allowing the defining
<a class="syntax" href="modules.html#module-expr"><span class="c010">module-expr</span></a> and the <a class="syntax" href="modtypes.html#module-type"><span class="c010">module-type</span></a> to refer recursively to the module
identifiers being defined. A typical example of a recursive module
definition is:
</p><div class="caml-example verbatim">
<div class="ocaml">
<div class="pre caml-input"> <span class="ocamlkeyword">module</span> <span class="ocamlkeyword">rec</span> A : <span class="ocamlkeyword">sig</span>
<span class="ocamlkeyword">type</span> t = Leaf <span class="ocamlkeyword">of</span> string | Node <span class="ocamlkeyword">of</span> ASet.t
<span class="ocamlkeyword">val</span> compare: t -> t -> int
<span class="ocamlkeyword">end</span> = <span class="ocamlkeyword">struct</span>
<span class="ocamlkeyword">type</span> t = Leaf <span class="ocamlkeyword">of</span> string | Node <span class="ocamlkeyword">of</span> ASet.t
<span class="ocamlkeyword">let</span> compare t1 t2 =
<span class="ocamlkeyword">match</span> (t1, t2) <span class="ocamlkeyword">with</span>
| (Leaf s1, Leaf s2) -> Stdlib.compare s1 s2
| (Leaf _, Node _) -> 1
| (Node _, Leaf _) -> -1
| (Node n1, Node n2) -> ASet.compare n1 n2
<span class="ocamlkeyword">end</span>
<span class="ocamlkeyword">and</span> ASet
: Set.S <span class="ocamlkeyword">with</span> <span class="ocamlkeyword">type</span> elt = A.t
= Set.Make(A)</div></div>
</div><p>
It can be given the following specification:
</p><div class="caml-example signature">
<div class="ocaml">
<div class="pre caml-input"> <span class="ocamlkeyword">module</span> <span class="ocamlkeyword">rec</span> A : <span class="ocamlkeyword">sig</span>
<span class="ocamlkeyword">type</span> t = Leaf <span class="ocamlkeyword">of</span> string | Node <span class="ocamlkeyword">of</span> ASet.t
<span class="ocamlkeyword">val</span> compare: t -> t -> int
<span class="ocamlkeyword">end</span>
<span class="ocamlkeyword">and</span> ASet : Set.S <span class="ocamlkeyword">with</span> <span class="ocamlkeyword">type</span> elt = A.t</div></div>
</div><p>This is an experimental extension of OCaml: the class of
recursive definitions accepted, as well as its dynamic semantics are
not final and subject to change in future releases.</p><p>Currently, the compiler requires that all dependency cycles between
the recursively-defined module identifiers go through at least one
“safe” module. A module is “safe” if all value definitions that
it contains have function types <a class="syntax" href="types.html#typexpr"><span class="c010">typexpr</span></a><sub>1</sub> <span class="c004">-></span> <a class="syntax" href="types.html#typexpr"><span class="c010">typexpr</span></a><sub>2</sub>. Evaluation of a
recursive module definition proceeds by building initial values for
the safe modules involved, binding all (functional) values to
<span class="c002"><span class="c003">fun</span> <span class="c003">_</span> <span class="c003">-></span> <span class="c003">raise</span></span> <span class="c003">Undefined_recursive_module</span>. The defining
module expressions are then evaluated, and the initial values
for the safe modules are replaced by the values thus computed. If a
function component of a safe module is applied during this computation
(which corresponds to an ill-founded recursive definition), the
<span class="c003">Undefined_recursive_module</span> exception is raised at runtime:</p><div class="caml-example verbatim">
<div class="ocaml">
<div class="pre caml-input"> <span class="ocamlkeyword">module</span> <span class="ocamlkeyword">rec</span> M: <span class="ocamlkeyword">sig</span> <span class="ocamlkeyword">val</span> f: unit -> int <span class="ocamlkeyword">end</span> = <span class="ocamlkeyword">struct</span> <span class="ocamlkeyword">let</span> f () = N.x <span class="ocamlkeyword">end</span>
<span class="ocamlkeyword">and</span> N:<span class="ocamlkeyword">sig</span> <span class="ocamlkeyword">val</span> x: int <span class="ocamlkeyword">end</span> = <span class="ocamlkeyword">struct</span> <span class="ocamlkeyword">let</span> x = M.f () <span class="ocamlkeyword">end</span></div>
<div class="pre caml-output ok">Exception: Undefined_recursive_module (<span class="ocamlstring">"exten.etex"</span>, 1, 43).</div></div>
</div><p>If there are no safe modules along a dependency cycle, an error is raised</p><div class="caml-example verbatim">
<div class="ocaml">
<div class="pre caml-input"> <span class="ocamlkeyword">module</span> <span class="ocamlkeyword">rec</span> M: <span class="ocamlkeyword">sig</span> <span class="ocamlhighlight">val x: int</span> <span class="ocamlkeyword">end</span> = <span class="ocamlhighlight">struct let x = N.y end</span>
<span class="ocamlkeyword">and</span> N:<span class="ocamlkeyword">sig</span> <span class="ocamlhighlight">val x: int</span> <span class="ocamlkeyword">val</span> y:int <span class="ocamlkeyword">end</span> = <span class="ocamlkeyword">struct</span> <span class="ocamlkeyword">let</span> x = M.x <span class="ocamlkeyword">let</span> y = 0 <span class="ocamlkeyword">end</span></div>
<div class="pre caml-output error"><span class="ocamlerror">Error</span>: Cannot safely evaluate the definition of the following cycle
of recursively-defined modules: M -> N -> M.
There are no safe modules in this cycle (see manual section 8.2).
Module M defines an unsafe value, x .
Module N defines an unsafe value, x .</div></div>
</div><p>Note that, in the <a class="syntax" href="modtypes.html#specification"><span class="c010">specification</span></a> case, the <a class="syntax" href="modtypes.html#module-type"><span class="c010">module-type</span></a>s must be
parenthesized if they use the <span class="c004">with</span> <a class="syntax" href="modtypes.html#mod-constraint"><span class="c010">mod-constraint</span></a> construct.</p>
<hr>
<a href="letrecvalues.html"><img src="previous_motif.svg" alt="Previous"></a>
<a href="extn.html"><img src="contents_motif.svg" alt="Up"></a>
<a href="privatetypes.html"><img src="next_motif.svg" alt="Next"></a>
</body>
</html>
|
