Merge.
3 \def\isabellecontext{ML}%
10 \isacommand{theory}\isamarkupfalse%
11 \ {\isachardoublequoteopen}ML{\isachardoublequoteclose}\isanewline
12 \isakeyword{imports}\ Base\isanewline
21 \isamarkupchapter{Advanced ML programming%
25 \isamarkupsection{Style%
29 \begin{isamarkuptext}%
30 Like any style guide, also this one should not be interpreted dogmatically, but
31 with care and discernment. It consists of a collection of
32 recommendations which have been turned out useful over long years of
33 Isabelle system development and are supposed to support writing of readable
34 and managable code. Special cases encourage derivations,
35 as far as you know what you are doing.
36 \footnote{This style guide is loosely based on
37 \url{http://caml.inria.fr/resources/doc/guides/guidelines.en.html}}
41 \item[fundamental law of programming]
42 Whenever writing code, keep in mind: A program is
43 written once, modified ten times, and read
44 hundred times. So simplify its writing,
45 always keep future modifications in mind,
46 and never jeopardize readability. Every second you hesitate
47 to spend on making your code more clear you will
48 have to spend ten times understanding what you have
51 \item[white space matters]
52 Treat white space in your code as if it determines
57 \item The space bar is the easiest key to find on the keyboard,
58 press it as often as necessary. \verb|2 + 2| is better
59 than \verb|2+2|, likewise \verb|f (x, y)| is
60 better than \verb|f(x,y)|.
62 \item Restrict your lines to 80 characters. This will allow
63 you to keep the beginning of a line in view while watching
64 its end.\footnote{To acknowledge the lax practice of
65 text editing these days, we tolerate as much as 100
66 characters per line, but anything beyond 120 is not
67 considered proper source text.}
69 \item Ban tabulators; they are a context-sensitive formatting
70 feature and likely to confuse anyone not using your favorite
71 editor.\footnote{Some modern programming language even
72 forbid tabulators altogether according to the formal syntax
75 \item Get rid of trailing whitespace. Instead, do not
76 suppress a trailing newline at the end of your files.
78 \item Choose a generally accepted style of indentation,
79 then use it systematically throughout the whole
80 application. An indentation of two spaces is appropriate.
81 Avoid dangling indentation.
85 \item[cut-and-paste succeeds over copy-and-paste]
86 \emph{Never} copy-and-paste code when programming. If you
87 need the same piece of code twice, introduce a
88 reasonable auxiliary function (if there is no
89 such function, very likely you got something wrong).
90 Any copy-and-paste will turn out to be painful
91 when something has to be changed later on.
94 are a device which requires careful thinking before using
95 it. The best comment for your code should be the code itself.
96 Prefer efforts to write clear, understandable code
97 over efforts to explain nasty code.
99 \item[functional programming is based on functions]
100 Model things as abstract as appropriate. Avoid unnecessarrily
101 concrete datatype representations. For example, consider a function
102 taking some table data structure as argument and performing
103 lookups on it. Instead of taking a table, it could likewise
104 take just a lookup function. Accustom
105 your way of coding to the level of expressiveness a functional
106 programming language is giving onto you.
109 are often in the way. When there is no striking argument
110 to tuple function arguments, just write your function curried.
113 Any name should tell its purpose as exactly as possible, while
114 keeping its length to the absolutely necessary minimum. Always
115 give the same name to function arguments which have the same
116 meaning. Separate words by underscores (\verb|int_of_string|, not \verb|intOfString|).\footnote{Some
117 recent tools for Emacs include special precautions to cope with
118 bumpy names in \isa{camelCase}, e.g.\ for improved on-screen
119 readability. It is easier to abstain from using such names in the
126 \isamarkupsection{Thread-safe programming%
130 \begin{isamarkuptext}%
131 Recent versions of Poly/ML (5.2.1 or later) support robust
132 multithreaded execution, based on native operating system threads of
133 the underlying platform. Thus threads will actually be executed in
134 parallel on multi-core systems. A speedup-factor of approximately
135 1.5--3 can be expected on a regular 4-core machine.\footnote{There
136 is some inherent limitation of the speedup factor due to garbage
137 collection, which is still sequential. It helps to provide initial
138 heap space generously, using the \texttt{-H} option of Poly/ML.}
139 Threads also help to organize advanced operations of the system,
140 with explicit communication between sub-components, real-time
141 conditions, time-outs etc.
143 Threads lack the memory protection of separate processes, and
144 operate concurrently on shared heap memory. This has the advantage
145 that results of independent computations are immediately available
146 to other threads, without requiring untyped character streams,
147 awkward serialization etc.
149 On the other hand, some programming guidelines need to be observed
150 in order to make unprotected parallelism work out smoothly. While
151 the ML system implementation is responsible to maintain basic
152 integrity of the representation of ML values in memory, the
153 application programmer needs to ensure that multithreaded execution
154 does not break the intended semantics.
156 \medskip \paragraph{Critical shared resources.} Actually only those
157 parts outside the purely functional world of ML are critical. In
158 particular, this covers
162 \item global references (or arrays), i.e.\ those that persist over
163 several invocations of associated operations,\footnote{This is
164 independent of the visibility of such mutable values in the toplevel
167 \item direct I/O on shared channels, notably \isa{stdin}, \isa{stdout}, \isa{stderr}.
171 The majority of tools implemented within the Isabelle/Isar framework
172 will not require any of these critical elements: nothing special
173 needs to be observed when staying in the purely functional fragment
174 of ML. Note that output via the official Isabelle channels does not
175 count as direct I/O, so the operations \verb|writeln|, \verb|warning|, \verb|tracing| etc.\ are safe.
177 Moreover, ML bindings within the toplevel environment (\verb|type|, \verb|val|, \verb|structure| etc.) due to
178 run-time invocation of the compiler are also safe, because
179 Isabelle/Isar manages this as part of the theory or proof context.
181 \paragraph{Multithreading in Isabelle/Isar.} The theory loader
182 automatically exploits the overall parallelism of independent nodes
183 in the development graph, as well as the inherent irrelevance of
184 proofs for goals being fully specified in advance. This means,
185 checking of individual Isar proofs is parallelized by default.
186 Beyond that, very sophisticated proof tools may use local
187 parallelism internally, via the general programming model of
188 ``future values'' (see also \hyperlink{file.~~/src/Pure/Concurrent/future.ML}{\mbox{\isa{\isatt{{\isachartilde}{\isachartilde}{\isacharslash}src{\isacharslash}Pure{\isacharslash}Concurrent{\isacharslash}future{\isachardot}ML}}}}).
190 Any ML code that works relatively to the present background theory
191 is already safe. Contextual data may be easily stored within the
192 theory or proof context, thanks to the generic data concept of
193 Isabelle/Isar (see \secref{sec:context-data}). This greatly
194 diminishes the demand for global state information in the first
197 \medskip In rare situations where actual mutable content needs to be
198 manipulated, Isabelle provides a single \emph{critical section} that
199 may be entered while preventing any other thread from doing the
200 same. Entering the critical section without contention is very
201 fast, and several basic system operations do so frequently. This
202 also means that each thread should leave the critical section
203 quickly, otherwise parallel execution performance may degrade
206 Despite this potential bottle-neck, centralized locking is
207 convenient, because it prevents deadlocks without demanding special
208 precautions. Explicit communication demands other means, though.
209 The high-level abstraction of synchronized variables \hyperlink{file.~~/src/Pure/Concurrent/synchronized.ML}{\mbox{\isa{\isatt{{\isachartilde}{\isachartilde}{\isacharslash}src{\isacharslash}Pure{\isacharslash}Concurrent{\isacharslash}synchronized{\isachardot}ML}}}} enables parallel
210 components to communicate via shared state; see also \hyperlink{file.~~/src/Pure/Concurrent/mailbox.ML}{\mbox{\isa{\isatt{{\isachartilde}{\isachartilde}{\isacharslash}src{\isacharslash}Pure{\isacharslash}Concurrent{\isacharslash}mailbox{\isachardot}ML}}}} as canonical example.
212 \paragraph{Good conduct of impure programs.} The following
213 guidelines enable non-functional programs to participate in
218 \item Minimize global state information. Using proper theory and
219 proof context data will actually return to functional update of
220 values, without any special precautions for multithreading. Apart
221 from the fully general functors for theory and proof data (see
222 \secref{sec:context-data}) there are drop-in replacements that
223 emulate primitive references for common cases of \emph{configuration
224 options} for type \verb|bool|/\verb|int|/\verb|string| (see structure \verb|Config| and \verb|Attrib.config_bool| etc.), and lists of theorems (see functor
225 \verb|NamedThmsFun|).
227 \item Keep components with local state information
228 \emph{re-entrant}. Instead of poking initial values into (private)
229 global references, create a new state record on each invocation, and
230 pass that through any auxiliary functions of the component. The
231 state record may well contain mutable references, without requiring
232 any special synchronizations, as long as each invocation sees its
233 own copy. Occasionally, one might even return to plain functional
234 updates on non-mutable record values here.
236 \item Isolate process configuration flags. The main legitimate
237 application of global references is to configure the whole process
238 in a certain way, essentially affecting all threads. A typical
239 example is the \verb|show_types| flag, which tells the pretty printer
240 to output explicit type information for terms. Such flags usually
241 do not affect the functionality of the core system, but only the
242 view being presented to the user.
244 Occasionally, such global process flags are treated like implicit
245 arguments to certain operations, by using the \verb|setmp| combinator
246 for safe temporary assignment. Its traditional purpose was to
247 ensure proper recovery of the original value when exceptions are
248 raised in the body, now the functionality is extended to enter the
249 \emph{critical section} (with its usual potential of degrading
252 Note that recovery of plain value passing semantics via \verb|setmp|~\isa{ref\ value} assumes that this \isa{ref} is
253 exclusively manipulated within the critical section. In particular,
254 any persistent global assignment of \isa{ref\ {\isacharcolon}{\isacharequal}\ value} needs to
255 be marked critical as well, to prevent intruding another threads
256 local view, and a lost-update in the global scope, too.
260 Recall that in an open ``LCF-style'' system like Isabelle/Isar, the
261 user participates in constructing the overall environment. This
262 means that state-based facilities offered by one component will
263 require special caution later on. So minimizing critical elements,
264 by staying within the plain value-oriented view relative to theory
265 or proof contexts most of the time, will also reduce the chance of
266 mishaps occurring to end-users.%
276 \begin{isamarkuptext}%
278 \indexdef{}{ML}{NAMED\_CRITICAL}\verb|NAMED_CRITICAL: string -> (unit -> 'a) -> 'a| \\
279 \indexdef{}{ML}{CRITICAL}\verb|CRITICAL: (unit -> 'a) -> 'a| \\
280 \indexdef{}{ML}{setmp}\verb|setmp: 'a ref -> 'a -> ('b -> 'c) -> 'b -> 'c| \\
285 \item \verb|NAMED_CRITICAL|~\isa{name\ f} evaluates \isa{f\ {\isacharparenleft}{\isacharparenright}}
286 while staying within the critical section of Isabelle/Isar. No
287 other thread may do so at the same time, but non-critical parallel
288 execution will continue. The \isa{name} argument serves for
289 diagnostic purposes and might help to spot sources of congestion.
291 \item \verb|CRITICAL| is the same as \verb|NAMED_CRITICAL| with empty
294 \item \verb|setmp|~\isa{ref\ value\ f\ x} evaluates \isa{f\ x}
295 while staying within the critical section and having \isa{ref\ {\isacharcolon}{\isacharequal}\ value} assigned temporarily. This recovers a value-passing
296 semantics involving global references, regardless of exceptions or
310 \isamarkupchapter{Basic library functions%
314 \begin{isamarkuptext}%
315 Beyond the proposal of the SML/NJ basis library, Isabelle comes
316 with its own library, from which selected parts are given here.
317 These should encourage a study of the Isabelle sources,
318 in particular files \emph{Pure/library.ML} and \emph{Pure/General/*.ML}.%
322 \isamarkupsection{Linear transformations \label{sec:ML-linear-trans}%
332 \begin{isamarkuptext}%
334 \indexdef{}{ML}{op $\mid$$>$ }\verb|op |\verb,|,\verb|> : 'a * ('a -> 'b) -> 'b| \\
359 \begin{isamarkuptext}%
360 \noindent Many problems in functional programming can be thought of
361 as linear transformations, i.e.~a caluclation starts with a
362 particular value \verb|x : foo| which is then transformed
363 by application of a function \verb|f : foo -> foo|,
364 continued by an application of a function \verb|g : foo -> bar|,
365 and so on. As a canoncial example, take functions enriching
366 a theory by constant declararion and primitive definitions:
368 \smallskip\begin{mldecls}
369 \verb|Sign.declare_const: Properties.T -> (binding * typ) * mixfix|\isasep\isanewline%
370 \verb| -> theory -> term * theory| \\
371 \verb|Thm.add_def: bool -> bool -> binding * term -> theory -> thm * theory|
374 \noindent Written with naive application, an addition of constant
375 \isa{bar} with type \isa{foo\ {\isasymRightarrow}\ foo} and
376 a corresponding definition \isa{bar\ {\isasymequiv}\ {\isasymlambda}x{\isachardot}\ x} would look like:
378 \smallskip\begin{mldecls}
379 \verb|(fn (t, thy) => Thm.add_def false false|\isasep\isanewline%
380 \verb| (Binding.name "bar_def", Logic.mk_equals (t, @{term "%x. x"})) thy)|\isasep\isanewline%
381 \verb| (Sign.declare_const []|\isasep\isanewline%
382 \verb| ((Binding.name "bar", @{typ "foo => foo"}), NoSyn) thy)|
385 \noindent With increasing numbers of applications, this code gets quite
386 unreadable. Further, it is unintuitive that things are
387 written down in the opposite order as they actually ``happen''.%
391 \begin{isamarkuptext}%
392 \noindent At this stage, Isabelle offers some combinators which allow
393 for more convenient notation, most notably reverse application:
395 \smallskip\begin{mldecls}
396 \verb|thy|\isasep\isanewline%
397 \verb||\verb,|,\verb|> Sign.declare_const [] ((Binding.name "bar", @{typ "foo => foo"}), NoSyn)|\isasep\isanewline%
398 \verb||\verb,|,\verb|> (fn (t, thy) => thy|\isasep\isanewline%
399 \verb||\verb,|,\verb|> Thm.add_def false false|\isasep\isanewline%
400 \verb| (Binding.name "bar_def", Logic.mk_equals (t, @{term "%x. x"})))|
411 \begin{isamarkuptext}%
413 \indexdef{}{ML}{op $\mid$-$>$ }\verb|op |\verb,|,\verb|-> : ('c * 'a) * ('c -> 'a -> 'b) -> 'b| \\
414 \indexdef{}{ML}{op $\mid$$>$$>$ }\verb|op |\verb,|,\verb|>> : ('a * 'c) * ('a -> 'b) -> 'b * 'c| \\
415 \indexdef{}{ML}{op $\mid$$\mid$$>$ }\verb|op |\verb,|,\verb||\verb,|,\verb|> : ('c * 'a) * ('a -> 'b) -> 'c * 'b| \\
416 \indexdef{}{ML}{op $\mid$$\mid$$>$$>$ }\verb|op |\verb,|,\verb||\verb,|,\verb|>> : ('c * 'a) * ('a -> 'd * 'b) -> ('c * 'd) * 'b| \\
428 \begin{isamarkuptext}%
429 \noindent Usually, functions involving theory updates also return
430 side results; to use these conveniently, yet another
431 set of combinators is at hand, most notably \verb|op |\verb,|,\verb|->|
432 which allows curried access to side results:
434 \smallskip\begin{mldecls}
435 \verb|thy|\isasep\isanewline%
436 \verb||\verb,|,\verb|> Sign.declare_const [] ((Binding.name "bar", @{typ "foo => foo"}), NoSyn)|\isasep\isanewline%
437 \verb||\verb,|,\verb|-> (fn t => Thm.add_def false false|\isasep\isanewline%
438 \verb| (Binding.name "bar_def", Logic.mk_equals (t, @{term "%x. x"})))|\isasep\isanewline%
442 \noindent \verb|op |\verb,|,\verb|>>| allows for processing side results on their own:
444 \smallskip\begin{mldecls}
445 \verb|thy|\isasep\isanewline%
446 \verb||\verb,|,\verb|> Sign.declare_const [] ((Binding.name "bar", @{typ "foo => foo"}), NoSyn)|\isasep\isanewline%
447 \verb||\verb,|,\verb|>> (fn t => Logic.mk_equals (t, @{term "%x. x"}))|\isasep\isanewline%
448 \verb||\verb,|,\verb|-> (fn def => Thm.add_def false false (Binding.name "bar_def", def))|\isasep\isanewline%
452 \noindent Orthogonally, \verb|op |\verb,|,\verb||\verb,|,\verb|>| applies a transformation
453 in the presence of side results which are left unchanged:
455 \smallskip\begin{mldecls}
456 \verb|thy|\isasep\isanewline%
457 \verb||\verb,|,\verb|> Sign.declare_const [] ((Binding.name "bar", @{typ "foo => foo"}), NoSyn)|\isasep\isanewline%
458 \verb||\verb,|,\verb||\verb,|,\verb|> Sign.add_path "foobar"|\isasep\isanewline%
459 \verb||\verb,|,\verb|-> (fn t => Thm.add_def false false|\isasep\isanewline%
460 \verb| (Binding.name "bar_def", Logic.mk_equals (t, @{term "%x. x"})))|\isasep\isanewline%
461 \verb||\verb,|,\verb||\verb,|,\verb|> Sign.restore_naming thy|\isasep\isanewline%
465 \noindent \verb|op |\verb,|,\verb||\verb,|,\verb|>>| accumulates side results:
467 \smallskip\begin{mldecls}
468 \verb|thy|\isasep\isanewline%
469 \verb||\verb,|,\verb|> Sign.declare_const [] ((Binding.name "bar", @{typ "foo => foo"}), NoSyn)|\isasep\isanewline%
470 \verb||\verb,|,\verb||\verb,|,\verb|>> Sign.declare_const [] ((Binding.name "foobar", @{typ "foo => foo"}), NoSyn)|\isasep\isanewline%
471 \verb||\verb,|,\verb|-> (fn (t1, t2) => Thm.add_def false false|\isasep\isanewline%
472 \verb| (Binding.name "bar_def", Logic.mk_equals (t1, t2)))|\isasep\isanewline%
484 \begin{isamarkuptext}%
486 \indexdef{}{ML}{fold}\verb|fold: ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b| \\
487 \indexdef{}{ML}{fold\_map}\verb|fold_map: ('a -> 'b -> 'c * 'b) -> 'a list -> 'b -> 'c list * 'b| \\
499 \begin{isamarkuptext}%
500 \noindent This principles naturally lift to \emph{lists} using
501 the \verb|fold| and \verb|fold_map| combinators.
502 The first lifts a single function
503 \begin{quote}\footnotesize
504 \verb|f : 'a -> 'b -> 'b| to \verb|'a list -> 'b -> 'b|
507 \begin{quote}\footnotesize
508 \verb|y |\verb,|,\verb|> fold f [x1, x2, ..., x_n]| \\
509 \hspace*{2ex}\isa{{\isasymleadsto}} \verb|y |\verb,|,\verb|> f x1 |\verb,|,\verb|> f x2 |\verb,|,\verb|> ... |\verb,|,\verb|> f x_n|
511 \noindent The second accumulates side results in a list by lifting
513 \begin{quote}\footnotesize
514 \verb|f : 'a -> 'b -> 'c * 'b| to \verb|'a list -> 'b -> 'c list * 'b|
517 \begin{quote}\footnotesize
518 \verb|y |\verb,|,\verb|> fold_map f [x1, x2, ..., x_n]| \\
519 \hspace*{2ex}\isa{{\isasymleadsto}} \verb|y |\verb,|,\verb|> f x1 |\verb,|,\verb||\verb,|,\verb|>> f x2 |\verb,|,\verb||\verb,|,\verb|>> ... |\verb,|,\verb||\verb,|,\verb|>> f x_n| \\
520 \hspace*{6ex}\verb||\verb,|,\verb||\verb,|,\verb|> (fn ((z1, z2), ..., z_n) => [z1, z2, ..., z_n])|
525 \smallskip\begin{mldecls}
526 \verb|let|\isasep\isanewline%
527 \verb| val consts = ["foo", "bar"];|\isasep\isanewline%
528 \verb|in|\isasep\isanewline%
529 \verb| thy|\isasep\isanewline%
530 \verb| |\verb,|,\verb|> fold_map (fn const => Sign.declare_const []|\isasep\isanewline%
531 \verb| ((Binding.name const, @{typ "foo => foo"}), NoSyn)) consts|\isasep\isanewline%
532 \verb| |\verb,|,\verb|>> map (fn t => Logic.mk_equals (t, @{term "%x. x"}))|\isasep\isanewline%
533 \verb| |\verb,|,\verb|-> (fn defs => fold_map (fn def =>|\isasep\isanewline%
534 \verb| Thm.add_def false false (Binding.empty, def)) defs)|\isasep\isanewline%
546 \begin{isamarkuptext}%
548 \indexdef{}{ML}{op \#$>$ }\verb|op #> : ('a -> 'b) * ('b -> 'c) -> 'a -> 'c| \\
549 \indexdef{}{ML}{op \#-$>$ }\verb|op #-> : ('a -> 'c * 'b) * ('c -> 'b -> 'd) -> 'a -> 'd| \\
550 \indexdef{}{ML}{op \#$>$$>$ }\verb|op #>> : ('a -> 'c * 'b) * ('c -> 'd) -> 'a -> 'd * 'b| \\
551 \indexdef{}{ML}{op \#\#$>$ }\verb|op ##> : ('a -> 'c * 'b) * ('b -> 'd) -> 'a -> 'c * 'd| \\
552 \indexdef{}{ML}{op \#\#$>$$>$ }\verb|op ##>> : ('a -> 'c * 'b) * ('b -> 'e * 'd) -> 'a -> ('c * 'e) * 'd| \\
564 \begin{isamarkuptext}%
565 \noindent All those linear combinators also exist in higher-order
566 variants which do not expect a value on the left hand side
577 \begin{isamarkuptext}%
579 \indexdef{}{ML}{op ` }\verb|op ` : ('b -> 'a) -> 'b -> 'a * 'b| \\
580 \indexdef{}{ML}{tap}\verb|tap: ('b -> 'a) -> 'b -> 'b| \\
592 \begin{isamarkuptext}%
593 \noindent These operators allow to ``query'' a context
594 in a series of context transformations:
596 \smallskip\begin{mldecls}
597 \verb|thy|\isasep\isanewline%
598 \verb||\verb,|,\verb|> tap (fn _ => writeln "now adding constant")|\isasep\isanewline%
599 \verb||\verb,|,\verb|> Sign.declare_const [] ((Binding.name "bar", @{typ "foo => foo"}), NoSyn)|\isasep\isanewline%
600 \verb||\verb,|,\verb||\verb,|,\verb|>> `(fn thy => Sign.declared_const thy|\isasep\isanewline%
601 \verb| (Sign.full_name thy (Binding.name "foobar")))|\isasep\isanewline%
602 \verb||\verb,|,\verb|-> (fn (t, b) => if b then I|\isasep\isanewline%
603 \verb| else Sign.declare_const []|\isasep\isanewline%
604 \verb| ((Binding.name "foobar", @{typ "foo => foo"}), NoSyn) #> snd)|\isasep\isanewline%
610 \isamarkupsection{Options and partiality%
620 \begin{isamarkuptext}%
622 \indexdef{}{ML}{is\_some}\verb|is_some: 'a option -> bool| \\
623 \indexdef{}{ML}{is\_none}\verb|is_none: 'a option -> bool| \\
624 \indexdef{}{ML}{the}\verb|the: 'a option -> 'a| \\
625 \indexdef{}{ML}{these}\verb|these: 'a list option -> 'a list| \\
626 \indexdef{}{ML}{the\_list}\verb|the_list: 'a option -> 'a list| \\
627 \indexdef{}{ML}{the\_default}\verb|the_default: 'a -> 'a option -> 'a| \\
628 \indexdef{}{ML}{try}\verb|try: ('a -> 'b) -> 'a -> 'b option| \\
629 \indexdef{}{ML}{can}\verb|can: ('a -> 'b) -> 'a -> bool| \\
641 \begin{isamarkuptext}%
642 Standard selector functions on \isa{option}s are provided. The
643 \verb|try| and \verb|can| functions provide a convenient interface for
644 handling exceptions -- both take as arguments a function \verb|f|
645 together with a parameter \verb|x| and handle any exception during
646 the evaluation of the application of \verb|f| to \verb|x|, either
647 return a lifted result (\verb|NONE| on failure) or a boolean value
648 (\verb|false| on failure).%
652 \isamarkupsection{Common data structures%
656 \isamarkupsubsection{Lists (as set-like data structures)%
660 \begin{isamarkuptext}%
662 \indexdef{}{ML}{member}\verb|member: ('b * 'a -> bool) -> 'a list -> 'b -> bool| \\
663 \indexdef{}{ML}{insert}\verb|insert: ('a * 'a -> bool) -> 'a -> 'a list -> 'a list| \\
664 \indexdef{}{ML}{remove}\verb|remove: ('b * 'a -> bool) -> 'b -> 'a list -> 'a list| \\
665 \indexdef{}{ML}{merge}\verb|merge: ('a * 'a -> bool) -> 'a list * 'a list -> 'a list| \\
670 \begin{isamarkuptext}%
671 Lists are often used as set-like data structures -- set-like in
672 the sense that they support a notion of \verb|member|-ship,
673 \verb|insert|-ing and \verb|remove|-ing, but are order-sensitive.
674 This is convenient when implementing a history-like mechanism:
675 \verb|insert| adds an element \emph{to the front} of a list,
676 if not yet present; \verb|remove| removes \emph{all} occurences
677 of a particular element. Correspondingly \verb|merge| implements a
678 a merge on two lists suitable for merges of context data
679 (\secref{sec:context-theory}).
681 Functions are parametrized by an explicit equality function
682 to accomplish overloaded equality; in most cases of monomorphic
683 equality, writing \verb|op =| should suffice.%
687 \isamarkupsubsection{Association lists%
691 \begin{isamarkuptext}%
693 \indexdef{}{ML exception}{AList.DUP}\verb|exception AList.DUP| \\
694 \indexdef{}{ML}{AList.lookup}\verb|AList.lookup: ('a * 'b -> bool) -> ('b * 'c) list -> 'a -> 'c option| \\
695 \indexdef{}{ML}{AList.defined}\verb|AList.defined: ('a * 'b -> bool) -> ('b * 'c) list -> 'a -> bool| \\
696 \indexdef{}{ML}{AList.update}\verb|AList.update: ('a * 'a -> bool) -> ('a * 'b) -> ('a * 'b) list -> ('a * 'b) list| \\
697 \indexdef{}{ML}{AList.default}\verb|AList.default: ('a * 'a -> bool) -> ('a * 'b) -> ('a * 'b) list -> ('a * 'b) list| \\
698 \indexdef{}{ML}{AList.delete}\verb|AList.delete: ('a * 'b -> bool) -> 'a -> ('b * 'c) list -> ('b * 'c) list| \\
699 \indexdef{}{ML}{AList.map\_entry}\verb|AList.map_entry: ('a * 'b -> bool) -> 'a|\isasep\isanewline%
700 \verb| -> ('c -> 'c) -> ('b * 'c) list -> ('b * 'c) list| \\
701 \indexdef{}{ML}{AList.map\_default}\verb|AList.map_default: ('a * 'a -> bool) -> 'a * 'b -> ('b -> 'b)|\isasep\isanewline%
702 \verb| -> ('a * 'b) list -> ('a * 'b) list| \\
703 \indexdef{}{ML}{AList.join}\verb|AList.join: ('a * 'a -> bool) -> ('a -> 'b * 'b -> 'b) (*exception DUP*)|\isasep\isanewline%
704 \verb| -> ('a * 'b) list * ('a * 'b) list -> ('a * 'b) list (*exception AList.DUP*)| \\
705 \indexdef{}{ML}{AList.merge}\verb|AList.merge: ('a * 'a -> bool) -> ('b * 'b -> bool)|\isasep\isanewline%
706 \verb| -> ('a * 'b) list * ('a * 'b) list -> ('a * 'b) list (*exception AList.DUP*)|
711 \begin{isamarkuptext}%
712 Association lists can be seens as an extension of set-like lists:
713 on the one hand, they may be used to implement finite mappings,
714 on the other hand, they remain order-sensitive and allow for
715 multiple key-value-pair with the same key: \verb|AList.lookup|
716 returns the \emph{first} value corresponding to a particular
717 key, if present. \verb|AList.update| updates
718 the \emph{first} occurence of a particular key; if no such
719 key exists yet, the key-value-pair is added \emph{to the front}.
720 \verb|AList.delete| only deletes the \emph{first} occurence of a key.
721 \verb|AList.merge| provides an operation suitable for merges of context data
722 (\secref{sec:context-theory}), where an equality parameter on
723 values determines whether a merge should be considered a conflict.
724 A slightly generalized operation if implementend by the \verb|AList.join|
725 function which allows for explicit conflict resolution.%
729 \isamarkupsubsection{Tables%
733 \begin{isamarkuptext}%
735 \indexdef{}{ML type}{'a Symtab.table}\verb|type 'a Symtab.table| \\
736 \indexdef{}{ML exception}{Symtab.DUP}\verb|exception Symtab.DUP of string| \\
737 \indexdef{}{ML exception}{Symtab.SAME}\verb|exception Symtab.SAME| \\
738 \indexdef{}{ML exception}{Symtab.UNDEF}\verb|exception Symtab.UNDEF of string| \\
739 \indexdef{}{ML}{Symtab.empty}\verb|Symtab.empty: 'a Symtab.table| \\
740 \indexdef{}{ML}{Symtab.lookup}\verb|Symtab.lookup: 'a Symtab.table -> string -> 'a option| \\
741 \indexdef{}{ML}{Symtab.defined}\verb|Symtab.defined: 'a Symtab.table -> string -> bool| \\
742 \indexdef{}{ML}{Symtab.update}\verb|Symtab.update: (string * 'a) -> 'a Symtab.table -> 'a Symtab.table| \\
743 \indexdef{}{ML}{Symtab.default}\verb|Symtab.default: string * 'a -> 'a Symtab.table -> 'a Symtab.table| \\
744 \indexdef{}{ML}{Symtab.delete}\verb|Symtab.delete: string|\isasep\isanewline%
745 \verb| -> 'a Symtab.table -> 'a Symtab.table (*exception Symtab.UNDEF*)| \\
746 \indexdef{}{ML}{Symtab.map\_entry}\verb|Symtab.map_entry: string -> ('a -> 'a)|\isasep\isanewline%
747 \verb| -> 'a Symtab.table -> 'a Symtab.table| \\
748 \indexdef{}{ML}{Symtab.map\_default}\verb|Symtab.map_default: (string * 'a) -> ('a -> 'a)|\isasep\isanewline%
749 \verb| -> 'a Symtab.table -> 'a Symtab.table| \\
750 \indexdef{}{ML}{Symtab.join}\verb|Symtab.join: (string -> 'a * 'a -> 'a) (*exception Symtab.DUP/Symtab.SAME*)|\isasep\isanewline%
751 \verb| -> 'a Symtab.table * 'a Symtab.table|\isasep\isanewline%
752 \verb| -> 'a Symtab.table (*exception Symtab.DUP*)| \\
753 \indexdef{}{ML}{Symtab.merge}\verb|Symtab.merge: ('a * 'a -> bool)|\isasep\isanewline%
754 \verb| -> 'a Symtab.table * 'a Symtab.table|\isasep\isanewline%
755 \verb| -> 'a Symtab.table (*exception Symtab.DUP*)|
760 \begin{isamarkuptext}%
761 Tables are an efficient representation of finite mappings without
762 any notion of order; due to their efficiency they should be used
763 whenever such pure finite mappings are neccessary.
765 The key type of tables must be given explicitly by instantiating
766 the \verb|TableFun| functor which takes the key type
767 together with its \verb|order|; for convience, we restrict
768 here to the \verb|Symtab| instance with \verb|string|
771 Most table functions correspond to those of association lists.%
780 \isacommand{end}\isamarkupfalse%
792 %%% TeX-master: "root"