18538
|
1 |
(* $Id$ *)
|
|
2 |
|
|
3 |
theory "ML" imports base begin
|
|
4 |
|
|
5 |
chapter {* Aesthetics of ML programming *}
|
|
6 |
|
21502
|
7 |
text FIXME
|
|
8 |
|
21148
|
9 |
text {* This style guide is loosely based on
|
|
10 |
\url{http://caml.inria.fr/resources/doc/guides/guidelines.en.html}.
|
|
11 |
% FIMXE \url{http://www.cs.cornell.edu/Courses/cs312/2003sp/handouts/style.htm}
|
|
12 |
|
|
13 |
Like any style guide, it should not be interpreted dogmatically.
|
|
14 |
Instead, it forms a collection of recommendations which,
|
|
15 |
if obeyed, result in code that is not considered to be
|
|
16 |
obfuscated. In certain cases, derivations are encouraged,
|
|
17 |
as far as you know what you are doing.
|
|
18 |
|
|
19 |
\begin{description}
|
|
20 |
|
|
21 |
\item[fundamental law of programming]
|
|
22 |
Whenever writing code, keep in mind: A program is
|
|
23 |
written once, modified ten times, and read
|
|
24 |
100 times. So simplify its writing,
|
|
25 |
always keep future modifications in mind,
|
|
26 |
and never jeopardize readability. Every second you hesitate
|
|
27 |
to spend on making your code more clear you will
|
|
28 |
have to spend ten times understanding what you have
|
|
29 |
written later on.
|
|
30 |
|
|
31 |
\item[white space matters]
|
|
32 |
Treat white space in your code as if it determines
|
|
33 |
the meaning of code.
|
|
34 |
|
|
35 |
\begin{itemize}
|
|
36 |
|
|
37 |
\item The space bar is the easiest key to find on the keyboard,
|
|
38 |
press it as often as necessary. {\ttfamily 2 + 2} is better
|
|
39 |
than {\ttfamily 2+2}, likewise {\ttfamily f (x, y)}
|
|
40 |
better than {\ttfamily f(x,y)}.
|
|
41 |
|
|
42 |
\item Restrict your lines to \emph{at most} 80 characters.
|
|
43 |
This will allow you to keep the beginning of a line
|
|
44 |
in view while watching its end.
|
|
45 |
|
|
46 |
\item Ban tabs; they are a context-sensitive formatting
|
|
47 |
feature and likely to confuse anyone not using your
|
|
48 |
favourite editor.
|
|
49 |
|
|
50 |
\item Get rid of trailing whitespace. Instead, do not
|
|
51 |
surpess a trailing newline at the end of your files.
|
|
52 |
|
|
53 |
\item Choose a generally accepted style of indentation,
|
|
54 |
then use it systematically throughout the whole
|
|
55 |
application. An indentation of two spaces is appropriate.
|
|
56 |
Avoid dangling indentation.
|
|
57 |
|
|
58 |
\end{itemize}
|
|
59 |
|
|
60 |
\item[cut-and-paste succeeds over copy-and-paste]
|
|
61 |
\emph{Never} copy-and-paste code when programming. If you
|
|
62 |
need the same piece of code twice, introduce a
|
|
63 |
reasonable auxiliary function (if there is no
|
|
64 |
such function, very likely you got something wrong).
|
|
65 |
Any copy-and-paste will turn out to be painful
|
|
66 |
when something has to be changed or fixed later on.
|
|
67 |
|
|
68 |
\item[comments]
|
|
69 |
are a device which requires careful thinking before using
|
|
70 |
it. The best comment for your code should be the code itself.
|
|
71 |
Prefer efforts to write clear, understandable code
|
|
72 |
over efforts to explain nasty code.
|
|
73 |
|
|
74 |
\item[functional programming is based on functions]
|
|
75 |
Avoid ``constructivisms'', e.g. pass a table lookup function,
|
|
76 |
rather than an actual table with lookup in body. Accustom
|
|
77 |
your way of codeing to the level of expressiveness
|
|
78 |
a functional programming language is giving onto you.
|
|
79 |
|
|
80 |
\item[tuples]
|
|
81 |
are often in the way. When there is no striking argument
|
|
82 |
to tuple function arguments, just write your function curried.
|
|
83 |
|
|
84 |
\item[telling names]
|
|
85 |
Any name should tell its purpose as exactly as possible,
|
|
86 |
while keeping its length to the absolutely neccessary minimum.
|
|
87 |
Always give the same name to function arguments which
|
|
88 |
have the same meaning. Separate words by underscores
|
21502
|
89 |
(``@{verbatim int_of_string}'', not ``@{verbatim intOfString}'')
|
21148
|
90 |
|
|
91 |
\end{description}
|
18554
|
92 |
*}
|
18538
|
93 |
|
|
94 |
|
|
95 |
chapter {* Basic library functions *}
|
|
96 |
|
22293
|
97 |
text {*
|
|
98 |
Beyond the proposal of the SML/NJ basis library, Isabelle comes
|
|
99 |
with its own library, from which selected parts are given here.
|
|
100 |
See further files \emph{Pure/library.ML} and \emph{Pure/General/*.ML}.
|
|
101 |
*}
|
|
102 |
|
|
103 |
section {* Linear transformations *}
|
|
104 |
|
|
105 |
text %mlref {*
|
|
106 |
\begin{mldecls}
|
|
107 |
@{index_ML "(op |>)": "'a * ('a -> 'b) -> 'b"} \\
|
|
108 |
@{index_ML fold: "('a -> 'b -> 'b) -> 'a list -> 'b -> 'b"} \\
|
|
109 |
@{index_ML fold_rev: "('a -> 'b -> 'b) -> 'a list -> 'b -> 'b"} \\
|
|
110 |
\end{mldecls}
|
|
111 |
*}
|
|
112 |
|
22322
|
113 |
(*<*)
|
|
114 |
typedecl foo
|
|
115 |
consts foo :: foo
|
|
116 |
ML {*
|
|
117 |
val dummy_const = ("bar", @{typ foo}, NoSyn)
|
|
118 |
val dummy_def = ("bar", @{term foo})
|
|
119 |
val thy = Theory.copy @{theory}
|
|
120 |
*}
|
|
121 |
(*>*)
|
|
122 |
|
|
123 |
text {*
|
|
124 |
Many problems in functional programming can be thought of
|
|
125 |
as linear transformations, i.e.~a caluclation starts with a
|
|
126 |
particular value @{text "x \<Colon> foo"} which is then transformed
|
|
127 |
by application of a function @{text "f \<Colon> foo \<Rightarrow> foo"},
|
|
128 |
continued by an application of a function @{text "g \<Colon> foo \<Rightarrow> bar"},
|
|
129 |
and so on. As a canoncial example, take primitive functions enriching
|
|
130 |
theories by constants and definitions:
|
22550
|
131 |
@{ML "Sign.add_consts_i: (string * typ * mixfix) list -> theory
|
|
132 |
-> theory"}
|
|
133 |
and @{ML "Theory.add_defs_i: bool -> bool
|
|
134 |
-> (bstring * term) list -> theory -> theory"}.
|
22322
|
135 |
Written with naive application, an addition of a constant with
|
|
136 |
a corresponding definition would look like:
|
22550
|
137 |
@{ML "Theory.add_defs_i false false [dummy_def]
|
|
138 |
(Sign.add_consts_i [dummy_const] thy)"}.
|
22322
|
139 |
With increasing numbers of applications, this code gets quite unreadable.
|
|
140 |
Using composition, at least the nesting of brackets may be reduced:
|
22550
|
141 |
@{ML "(Theory.add_defs_i false false [dummy_def] o Sign.add_consts_i
|
|
142 |
[dummy_const]) thy"}.
|
22322
|
143 |
What remains unsatisfactory is that things are written down in the opposite order
|
|
144 |
as they actually ``happen''.
|
|
145 |
*}
|
|
146 |
|
|
147 |
(*<*)
|
|
148 |
ML {*
|
|
149 |
val thy = Theory.copy @{theory}
|
|
150 |
*}
|
|
151 |
(*>*)
|
|
152 |
|
|
153 |
text {*
|
|
154 |
At this stage, Isabelle offers some combinators which allow for more convenient
|
|
155 |
notation, most notably reverse application:
|
|
156 |
@{ML "
|
|
157 |
thy
|
|
158 |
|> Sign.add_consts_i [dummy_const]
|
|
159 |
|> Theory.add_defs_i false false [dummy_def]"}
|
|
160 |
*}
|
|
161 |
|
|
162 |
text {*
|
22550
|
163 |
\noindent When iterating over a list of parameters @{text "[x\<^isub>1, x\<^isub>2, \<dots> x\<^isub>n] \<Colon> 'a list"},
|
22322
|
164 |
the @{ML fold} combinator lifts a single function @{text "f \<Colon> 'a -> 'b -> 'b"}:
|
|
165 |
@{text "y |> fold f [x\<^isub>1, x\<^isub>2, \<dots> x\<^isub>n] \<equiv> y |> f x\<^isub>1 |> f x\<^isub>2 |> \<dots> |> f x\<^isub>n"}
|
|
166 |
*}
|
22293
|
167 |
|
|
168 |
text %mlref {*
|
|
169 |
\begin{mldecls}
|
|
170 |
@{index_ML "(op |->)": "('c * 'a) * ('c -> 'a -> 'b) -> 'b"} \\
|
|
171 |
@{index_ML "(op |>>)": "('a * 'c) * ('a -> 'b) -> 'b * 'c"} \\
|
|
172 |
@{index_ML "(op ||>)": "('c * 'a) * ('a -> 'b) -> 'c * 'b"} \\
|
|
173 |
@{index_ML "(op ||>>)": "('c * 'a) * ('a -> 'd * 'b) -> ('c * 'd) * 'b"} \\
|
|
174 |
@{index_ML fold_map: "('a -> 'b -> 'c * 'b) -> 'a list -> 'b -> 'c list * 'b"} \\
|
|
175 |
\end{mldecls}
|
|
176 |
*}
|
|
177 |
|
22322
|
178 |
text {*
|
22550
|
179 |
\noindent FIXME transformations involving side results
|
22322
|
180 |
*}
|
|
181 |
|
22293
|
182 |
text %mlref {*
|
|
183 |
\begin{mldecls}
|
|
184 |
@{index_ML "(op #>)": "('a -> 'b) * ('b -> 'c) -> 'a -> 'c"} \\
|
|
185 |
@{index_ML "(op #->)": "('a -> 'c * 'b) * ('c -> 'b -> 'd) -> 'a -> 'd"} \\
|
|
186 |
@{index_ML "(op #>>)": "('a -> 'c * 'b) * ('c -> 'd) -> 'a -> 'd * 'b"} \\
|
|
187 |
@{index_ML "(op ##>)": "('a -> 'c * 'b) * ('b -> 'd) -> 'a -> 'c * 'd"} \\
|
|
188 |
@{index_ML "(op ##>>)": "('a -> 'c * 'b) * ('b -> 'e * 'd) -> 'a -> ('c * 'e) * 'd"} \\
|
|
189 |
\end{mldecls}
|
|
190 |
*}
|
|
191 |
|
22322
|
192 |
text {*
|
22550
|
193 |
\noindent All those linear combinators also exist in higher-order
|
|
194 |
variants which do not expect a value on the left hand side
|
|
195 |
but a function.
|
22322
|
196 |
*}
|
|
197 |
|
22293
|
198 |
text %mlref {*
|
|
199 |
\begin{mldecls}
|
|
200 |
@{index_ML "(op `)": "('b -> 'a) -> 'b -> 'a * 'b"} \\
|
|
201 |
@{index_ML tap: "('b -> 'a) -> 'b -> 'b"} \\
|
|
202 |
\end{mldecls}
|
|
203 |
*}
|
|
204 |
|
22550
|
205 |
text {*
|
|
206 |
\noindent FIXME
|
|
207 |
*}
|
|
208 |
|
22293
|
209 |
section {* Options and partiality *}
|
|
210 |
|
|
211 |
text %mlref {*
|
|
212 |
\begin{mldecls}
|
|
213 |
@{index_ML is_some: "'a option -> bool"} \\
|
|
214 |
@{index_ML is_none: "'a option -> bool"} \\
|
|
215 |
@{index_ML the: "'a option -> 'a"} \\
|
|
216 |
@{index_ML these: "'a list option -> 'a list"} \\
|
|
217 |
@{index_ML the_list: "'a option -> 'a list"} \\
|
|
218 |
@{index_ML the_default: "'a -> 'a option -> 'a"} \\
|
|
219 |
@{index_ML try: "('a -> 'b) -> 'a -> 'b option"} \\
|
|
220 |
@{index_ML can: "('a -> 'b) -> 'a -> bool"} \\
|
|
221 |
\end{mldecls}
|
|
222 |
*}
|
|
223 |
|
22550
|
224 |
text {*
|
|
225 |
Standard selector functions on @{text option}s are provided.
|
|
226 |
The @{ML try} and @{ML can} functions provide a convenient
|
|
227 |
interface for handling exceptions -- both take as arguments
|
|
228 |
a function @{text f} together with a parameter @{text x}
|
|
229 |
and catch any exception during the evaluation of the application
|
|
230 |
of @{text f} to @{text x}, either return a lifted result
|
|
231 |
(@{ML NONE} on failure) or a boolean value (@{ML false} on failure).
|
|
232 |
*}
|
22293
|
233 |
|
|
234 |
section {* Common data structures *}
|
|
235 |
|
|
236 |
subsection {* Lists (as set-like data structures) *}
|
18538
|
237 |
|
22293
|
238 |
text {*
|
|
239 |
\begin{mldecls}
|
|
240 |
@{index_ML member: "('b * 'a -> bool) -> 'a list -> 'b -> bool"} \\
|
|
241 |
@{index_ML insert: "('a * 'a -> bool) -> 'a -> 'a list -> 'a list"} \\
|
|
242 |
@{index_ML remove: "('b * 'a -> bool) -> 'b -> 'a list -> 'a list"} \\
|
|
243 |
@{index_ML merge: "('a * 'a -> bool) -> 'a list * 'a list -> 'a list"} \\
|
|
244 |
\end{mldecls}
|
|
245 |
*}
|
|
246 |
|
22503
|
247 |
text {*
|
|
248 |
Lists are often used as set-like data structures -- set-like in
|
|
249 |
then sense that they support notion of @{ML member}-ship,
|
|
250 |
@{ML insert}-ing and @{ML remove}-ing, but are order-sensitive.
|
|
251 |
This is convenient when implementing a history-like mechanism:
|
|
252 |
@{ML insert} adds an element \emph{to the front} of a list,
|
|
253 |
if not yet present; @{ML remove} removes \emph{all} occurences
|
|
254 |
of a particular element. Correspondingly @{ML merge} implements a
|
|
255 |
a merge on two lists suitable for merges of context data
|
|
256 |
(\secref{sec:context-theory}).
|
|
257 |
|
|
258 |
Functions are parametrized by an explicit equality function
|
|
259 |
to accomplish overloaded equality; in most cases of monomorphic
|
|
260 |
equality, writing @{ML "(op =)"} should suffice.
|
|
261 |
*}
|
22293
|
262 |
|
|
263 |
subsection {* Association lists *}
|
|
264 |
|
|
265 |
text {*
|
|
266 |
\begin{mldecls}
|
|
267 |
@{index_ML_exc AList.DUP} \\
|
|
268 |
@{index_ML AList.lookup: "('a * 'b -> bool) -> ('b * 'c) list -> 'a -> 'c option"} \\
|
|
269 |
@{index_ML AList.defined: "('a * 'b -> bool) -> ('b * 'c) list -> 'a -> bool"} \\
|
|
270 |
@{index_ML AList.update: "('a * 'a -> bool) -> ('a * 'b) -> ('a * 'b) list -> ('a * 'b) list"} \\
|
|
271 |
@{index_ML AList.default: "('a * 'a -> bool) -> ('a * 'b) -> ('a * 'b) list -> ('a * 'b) list"} \\
|
|
272 |
@{index_ML AList.delete: "('a * 'b -> bool) -> 'a -> ('b * 'c) list -> ('b * 'c) list"} \\
|
|
273 |
@{index_ML AList.map_entry: "('a * 'b -> bool) -> 'a
|
|
274 |
-> ('c -> 'c) -> ('b * 'c) list -> ('b * 'c) list"} \\
|
|
275 |
@{index_ML AList.map_default: "('a * 'a -> bool) -> 'a * 'b -> ('b -> 'b)
|
|
276 |
-> ('a * 'b) list -> ('a * 'b) list"} \\
|
|
277 |
@{index_ML AList.join: "('a * 'a -> bool) -> ('a -> 'b * 'b -> 'b) (*exception DUP*)
|
|
278 |
-> ('a * 'b) list * ('a * 'b) list -> ('a * 'b) list (*exception AList.DUP*)"} \\
|
|
279 |
@{index_ML AList.merge: "('a * 'a -> bool) -> ('b * 'b -> bool)
|
|
280 |
-> ('a * 'b) list * ('a * 'b) list -> ('a * 'b) list (*exception AList.DUP*)"}
|
|
281 |
\end{mldecls}
|
|
282 |
*}
|
|
283 |
|
22503
|
284 |
text {*
|
|
285 |
Association lists can be seens as an extension of set-like lists:
|
|
286 |
on the one hand, they may be used to implement finite mappings,
|
|
287 |
on the other hand, they remain order-sensitive and allow for
|
|
288 |
multiple key-value-pair with the same key: @{ML AList.lookup}
|
|
289 |
returns the \emph{first} value corresponding to a particular
|
|
290 |
key, if present. @{ML AList.update} updates
|
|
291 |
the \emph{first} occurence of a particular key; if no such
|
|
292 |
key exists yet, the key-value-pair is added \emph{to the front}.
|
|
293 |
@{ML AList.delete} only deletes the \emph{first} occurence of a key.
|
|
294 |
@{ML AList.merge} provides an operation suitable for merges of context data
|
|
295 |
(\secref{sec:context-theory}), where an equality parameter on
|
|
296 |
values determines whether a merge should be considered a conflict.
|
|
297 |
A slightly generalized operation if implementend by the @{ML AList.join}
|
|
298 |
function which allows for explicit conflict resolution.
|
|
299 |
*}
|
22293
|
300 |
|
|
301 |
subsection {* Tables *}
|
|
302 |
|
|
303 |
text {*
|
|
304 |
\begin{mldecls}
|
|
305 |
@{index_ML_type Symtab.key} \\
|
|
306 |
@{index_ML_type "'a Symtab.table"} \\
|
|
307 |
@{index_ML_exc Symtab.DUP: Symtab.key} \\
|
|
308 |
@{index_ML_exc Symtab.DUPS: "Symtab.key list"} \\
|
|
309 |
@{index_ML_exc Symtab.SAME} \\
|
|
310 |
@{index_ML_exc Symtab.UNDEF: Symtab.key} \\
|
|
311 |
@{index_ML Symtab.empty: "'a Symtab.table"} \\
|
|
312 |
@{index_ML Symtab.dest: "'a Symtab.table -> (Symtab.key * 'a) list"} \\
|
|
313 |
@{index_ML Symtab.keys: "'a Symtab.table -> Symtab.key list"} \\
|
|
314 |
@{index_ML Symtab.lookup: "'a Symtab.table -> Symtab.key -> 'a option"} \\
|
|
315 |
@{index_ML Symtab.defined: "'a Symtab.table -> Symtab.key -> bool"} \\
|
|
316 |
@{index_ML Symtab.update: "(Symtab.key * 'a) -> 'a Symtab.table -> 'a Symtab.table"} \\
|
|
317 |
@{index_ML Symtab.default: "Symtab.key * 'a -> 'a Symtab.table -> 'a Symtab.table"} \\
|
|
318 |
@{index_ML Symtab.delete: "Symtab.key
|
|
319 |
-> 'a Symtab.table -> 'a Symtab.table (*exception Symtab.UNDEF*)"} \\
|
|
320 |
@{index_ML Symtab.map_entry: "Symtab.key -> ('a -> 'a)
|
|
321 |
-> 'a Symtab.table -> 'a Symtab.table"} \\
|
|
322 |
@{index_ML Symtab.map_default: "(Symtab.key * 'a) -> ('a -> 'a)
|
|
323 |
-> 'a Symtab.table -> 'a Symtab.table"} \\
|
|
324 |
@{index_ML Symtab.join: "(Symtab.key -> 'a * 'a -> 'a) (*exception Symtab.DUP/Symtab.SAME*)
|
|
325 |
-> 'a Symtab.table * 'a Symtab.table
|
|
326 |
-> 'a Symtab.table (*exception Symtab.DUPS*)"} \\
|
|
327 |
@{index_ML Symtab.merge: "('a * 'a -> bool)
|
|
328 |
-> 'a Symtab.table * 'a Symtab.table
|
|
329 |
-> 'a Symtab.table (*exception Symtab.DUPS*)"}
|
|
330 |
\end{mldecls}
|
|
331 |
*}
|
|
332 |
|
22503
|
333 |
text {*
|
|
334 |
Tables are an efficient representation of finite mappings without
|
|
335 |
any notion of order; due to their efficiency they should be used
|
|
336 |
whenever such pure finite mappings are neccessary.
|
|
337 |
|
|
338 |
The key type of tables must be given explicitly by instantiating
|
|
339 |
the @{ML_functor TableFun} functor which takes the key type
|
|
340 |
together with its @{ML_type order}; for convience, we restrict
|
|
341 |
here to the @{ML_struct Symtab} instance with @{ML_type string}
|
|
342 |
as key type.
|
|
343 |
|
|
344 |
Most table functions correspond to those of association lists.
|
|
345 |
*}
|
20489
|
346 |
|
|
347 |
chapter {* Cookbook *}
|
|
348 |
|
20491
|
349 |
section {* A method that depends on declarations in the context *}
|
20489
|
350 |
|
|
351 |
text FIXME
|
|
352 |
|
18538
|
353 |
end
|