[m-rev.] Book updates
Ralph Becket
rafe at cs.mu.OZ.AU
Fri Nov 15 18:11:05 AEDT 2002
Estimated hours taken: many
Branches: main
books/tutorial/book.tex:
Added includes for std-util and assoc-lists.
books/tutorial/type-classes.tex:
books/tutorial/syntax-and-terminology.tex:
books/tutorial/io.tex:
Minor changes.
books/tutorial/maps.tex:
Added. Nearly done.
books/tutorial/exceptions.tex:
Quite complete.
books/tutorial/std-util.tex:
books/tutorial/assoc-lists.tex:
Added (not written.)
diff -u book.tex book.tex
--- book.tex 11 Oct 2002 03:38:48 -0000
+++ book.tex 14 Nov 2002 10:51:00 -0000
@@ -10,9 +10,9 @@
%- Preamble -------------------------------------------------------------------%
-\documentclass[a4paper,11pt,notitlepage,onecolumn]{book}
+\documentclass[a4paper,11pt,notitlepage,onecolumn]{article}
%
- % [options]
+ % [options]
% (10|11|12)pt -- (default 10pt)
% (a4|letter)paper -- (default letterpaper)
% fleqn -- (default centred) left-align formulae as
@@ -172,7 +172,9 @@
\include{modules}
\include{higher-order}
\include{type-classes}
+\include{std-util}
\include{lists}
+\include{assoc-lists}
\include{maps}
\include{arrays}
\include{compiling-programs}
diff -u type-classes.tex type-classes.tex
--- type-classes.tex 11 Oct 2002 03:39:16 -0000
+++ type-classes.tex 14 Nov 2002 10:51:09 -0000
@@ -78,15 +78,14 @@
operations (or methods) we require:
\begin{verbatim}
:- typeclass number(T) where [
- func zero = T,
- func one = T,
- func from_int(int) = T,
- func -T = T,
- func T + T = T,
- func T - T = T,
- func T * T = T,
- func T / T = T
-].
+ func zero = T,
+ func one = T,
+ func from_int(int) = T,
+ func -T = T,
+ func T + T = T,
+ func T - T = T,
+ func T * T = T,
+ func T / T = T
\end{verbatim}
We include the nullary methods @zero@ and @one@ because they are so
useful and will have different representations in each \emph{instance}
@@ -122,7 +121,7 @@
Next, let's look at how we define @int@ as an instance of @number@:
\begin{verbatim}
:- instance number(int) where [
- zero = 0,
+ zero = 0,
one = 1,
from_int(X) = X,
-X = 'int__-'(X),
@@ -155,7 +154,7 @@
Making @float@ an instance of @number@ is very similar:
\begin{verbatim}
:- instance number(float) where [
- zero = 0.0,
+ zero = 0.0,
one = 1.0,
from_int(X) = X,
-X = 'float__-'(X),
@@ -240,7 +239,7 @@
index(K, HT) = hash(K) `mod` size(HT).
\end{verbatim}
-\XXX{Make sure we add @elem@ and @det\_elem@ to @assoc\_list at .}
+\XXX{Make sure we add @elem@ and @det_elem@ to @assoc_list at .}
We can construct hash functions for all our favourite types:
\begin{verbatim}
@@ -284,10 +283,10 @@
As an example, for many applications, the most efficient type of hash
table uses double hashing, rather than chaining buckets off a single
-hash generated index. For double hashing we probe at indices
- at h1(K) + I * h2(K)@ (modulo the size of the hash table) for
-$@I@ \in \{0, 1, 2, \ldots\}$, looking for the correct entry or an empty
-slot, depending upon whether we are performing an insertion or a lookup.
+hash generated index. For double hashing we probe at indices @h1(K) + I
+* h2(K)@ (modulo the size of the hash table) for $@I@ \in \{0, 1, 2,
+\ldots\}$, looking for the correct entry or an empty slot, depending
+upon whether we are performing an insertion or a lookup.
We want to add a new type class for types with a second hash function:
\begin{verbatim}
@@ -423,7 +422,7 @@
use it) and can lead to real code maintenance problems.
\XXX{Do I need to substantiate these claims?}
-Several languages, such as Java and \Csharp, have included the notions of
+Several languages, such as Java and C#, have included the notions of
\emph{interfaces}, which serve much the same purpose as type classes.
Since we are only allowed to inherit method signatures, there is no
problem (provided we insist that no method in a sub-type class may have the
@@ -629,7 +628,7 @@
\end{verbatim}
because this would restrict the first argument to all members of the
same type. What we want to be able to say is, given @X = 10@,
- at Y = " green bottle"@, Z = @'s'@ is to just call
+ at Y = " green bottle", Z = @'s'@ is to just call
@write_strings([X, Y, Z])@ and see @10 green bottles@ appear in the
output.
@@ -659,7 +658,7 @@
collections of @stringable@ instance values.
The constraint @=> stringable(T)@ has the arrow pointing in a different
-direction, because existentially quantified types place a burden on the
+deirection, because existentially quantified types place a burden on the
\emph{caller's} ability to handle a value, rather than the
\emph{callee's}. Because of this directionality, existentially
quantified types are generally ``outputs'' since a caller has no way of
@@ -670,7 +669,7 @@
just hard or just a SMOP?)} whether an occurrence of an existentially
quantified data constructor is meant as a construction or
deconstruction. To solve this problem, we insist that
-\emph{constructions} be preceeded with `@new @' (note the space), while
+\emph{constructions} be preceeded with `@new ' (note the space), while
\emph{deconstructions} are not. Thus, to construct our heterogeneous
list of @stringable at s, we would write
\begin{verbatim}
@@ -694,0 +693 @@
+
only in patch2:
--- syntax-and-terminology.tex 11 Oct 2002 02:22:11 -0000 1.2
+++ syntax-and-terminology.tex 18 Oct 2002 01:31:09 -0000
@@ -87,16 +87,80 @@
(We will see that in Mercury it is useful to further subdivide the
determinism categories.)
+Informally, we refer to the arguments with given values as inputs and
+those whose value is not fixed as outputs.
+
For example, @father@ is deterministic if we fix only @C@ since every child
has exactly one father. However, if we fix only @F@ we may get any
number of possible bindings for @C@ depending upon how many children @F@
has had, hence this mode of @father@ is nondeterministic.
+We use the term ``procedure'' (or sometimes overload ``mode'') to refer
+to a predicate restricted to a given set of argument modes.
+
+\subsection{Syntax}
+
+Mercury understands several determinisms: @erroneous@, @semidet@, @det@,
+ at nondet@, @multi@, @cc_nondet@ and @cc_multi at . These will be explained
+in detail in \XXX{}; for now it suffices to know that @semidet@ and
+ at nondet@ can fail (i.e. have no solutions), @semidet@ may have a single
+solution, @det@ has exactly one solution (i.e. it describes a
+\emph{functional} relationship -- see below), and @nondet@ and @multi@
+may have more than one solution.
+
+The two most important built-in modes are @in@ and @out@, corresponding
+to input and output arguments respectively. Modes are discussed in
+\XXX{}.
+
+The mode declarations (one per procedure) for the @father@ predicate
+described above would look like this:
+\begin{verbatim}
+ % father(Child, Father).
+ %
+:- mode father(in, out) is det.
+:- mode father(out, in ) is nondet.
+:- mode father(in, in ) is semidet.
+\end{verbatim}
+
+\XXX{I'm not sure how/when/where to introduce syntax in this chapter.
+It may be best to merge this chapter with the main Mercury-as-it-is-
+written chapter.}
+
\section{Functions and Expressions}
+A deterministic procedure is said to describe a \emph{functional}
+relationship between its inputs and its outputs (that is, the output is
+uniquely determined for each possible input.) For instance, the
+sum @X = Y + Z@ is functional given any two of @X@, @Y@ or @Z at .
+
+Special syntax exists for functions with a single (last) output
+argument. The main reason for this is that it supports \emph{functional
+composition}, which allows us to avoid naming intermediate results. For
+example, rather than writing
+\begin{verbatim}
+ Tmp1 = A + B,
+ Tmp2 = Tmp1 - C,
+ Tmp3 = Tmp2 * D,
+ X = Tmp3 / E
+\end{verbatim}
+we can simply write
+\begin{verbatim}
+ X = (((A + B) - C) * D) / E
+\end{verbatim}
+(in fact the precedence and associativity of the operators @+@, @-@,
+@*@, @/@ etc. has been chosen so that parentheses can often be
+avoided.)
+
+An \emph{expression} describes either a simple value or the
+\emph{application} of a function to other expressions.
+
+
+
+\section{Goals}
+A goal describes either a simple \emph{predicate call} or XXX HERE!
only in patch2:
--- maps.tex 11 Oct 2002 02:22:02 -0000 1.2
+++ maps.tex 14 Nov 2002 10:50:57 -0000
@@ -2,5 +2,270 @@
\chapter{Maps}
+The @map@ data type is provided by the @map@ module in the standard
+Mercury library.
+After @list at s, @map at s are perhaps the most widely used non-trivial
+Mercury data type. A @map@ is essentially a dictionary structure
+(or \emph{associative array})
+mapping \emph{keys} to \emph{values}. The core operations involve
+setting up a mapping from key to value, changing the mapping for a
+given key, and looking up the value associated with a given key.
+The @map@ data type is parameterised by the types of keys and values:
+\begin{verbatim}
+:- type map(K, V).
+\end{verbatim}
+Maps have efficient $O(log n)$ cost bounds on all the basic
+operations for a @map@ containing $n$ mappings (the reader may be
+interested to know they are currently implemented using 234-trees
+\XXX{ref}).
+
+Here is a small example of a very basic telephone directory
+application using a @map@ to store the mapping from names to
+phone numbers:
+\begin{verbatim}
+:- import_module map, list, string, std_util, assoc_list, exception.
+
+:- pred main(io, io).
+:- mode main(di, uo) is det.
+
+main(!IO) :-
+ io__read_line_as_string(Result, !IO),
+ (
+ Result = eof
+ ;
+ Result = error(_),
+ throw(Result)
+ ;
+ Result = ok(Name0),
+
+ % Chop off the trailing new line character and
+ % convert to lower case.
+ %
+ Name = to_lower(substring(Name0, 0, length(Name0) - 1)),
+
+ ( if phone_book ^ elem(Name) = Number
+ then io__format("%d\n", [s(Number)], !IO)
+ else io__format("`%s' is not in the phone book.\n",
+ [s(Name0)], !IO)
+ ),
+ main(!IO)
+ ).
+
+ % We memoize the result of this function since we only
+ % want to build it once.
+ %
+:- func phone_book = map(string, string).
+:- pragma memo(phone_book/0).
+
+phone_book = map__from_assoc_list([
+ "ralph" - "9873 1234",
+ "tyson" - "9873 4342",
+ "fergus" - "9873 1237",
+ "zoltan" - "9876 8754",
+ ...
+ ]).
+\end{verbatim}
+\XXX{Is this a bit too ``clever'' for a tutorial example?}
+\XXX{There's probably a better example.}
+
+\section{The Main Map Operations}
+
+An empty map is constructed by calling the nullary @init@ function:
+\begin{verbatim}
+:- func init = map(K, V).
+\end{verbatim}
+There are predicates to decide whether a given map is empty or
+contains a mapping for a particular key:
+\begin{verbatim}
+:- pred map__is_empty(map(K, V)).
+:- mode map__is_empty(in) is semidet.
+
+:- pred map__contains_key(map(K, V), K).
+:- mode map__contains_key(in, in) is semidet.
+\end{verbatim}
+We have two field-access like functions for lookup up values
+associated with keys. The first, @elem@, simply fails if there
+is no mapping for the given key. The second, @det_elem@, will
+throw an exception if this is the case.
+\begin{verbatim}
+:- func elem(K, map(K, V)) = V is semidet.
+
+:- func det_elem(K, map(K, V)) = V.
+\end{verbatim}
+So the expression @Map ^ elem(Key)@ denotes the value associated
+with @key@, if any.
+
+Mappings can be added or changed using the field assignment-like
+functions @'elem :='@ and @'det_elem :='@. The expression
+ at Map ^ elem(Key) := Value@ always succeeds, returning an updated
+version of @Map@ overwriting the mapping for @Key@, if any, in @Map@
+or adding a new mapping if @Map@ does not contain one. The expression
+ at Map ^ det_elem(Key) := Value@ is similar, except that it will throw
+an exception if @Map@ does not already contain a mapping for @Key at .
+\begin{verbatim}
+:- func 'elem :='(K, map(K, V), V) = map(K, V).
+
+:- func 'det_elem :='(K, map(K, V), V) = map(K, V).
+\end{verbatim}
+
+\section{Bulk Initialisation and Update}
+
+The @map@ module provides several means of initialising and updating
+ at map@s from other structures relating keys to values.
+
+\subsection{Association Lists}
+
+The simplest dictionary type is @assoc_list at .
+\begin{verbatim}
+:- func from_assoc_list(assoc_list(K,V)) = map(K,V).
+
+:- func from_sorted_assoc_list(assoc_list(K,V)) = map(K,V).
+\end{verbatim}
+These two functions both construct a new map from the @Key - Value@
+mappings in the @assoc_list@ argument. Mappings are inserted in the
+order in which the @Key - Value@ pairs appear in the @assoc_list at .
+
+Example (the 1926 estimates of Dr Catherine Morris Cox):
+\begin{verbatim}
+ IQs = from_assoc_list([
+ "Bobby Fischer" - 187,
+ "Galileo Galilei" - 185,
+ "Rene Descartes" - 180,
+ "Immanuel Kant" - 175,
+ "Charles Darwin" - 165,
+ "Albert Einstein" - 160
+ ])
+\end{verbatim}
+If the @assoc_list@ in question is already sorted with distinct keys in
+ascending order then using @from_sorted_assoc_list@ \emph{may} be faster
+(but there's certainly no point in separately sorting the @assoc_list@
+just to use this function instead!) \XXX{It's not clear to me that we
+really want to mention this one at all, especially since they're
+currently implemented identically.}
+
+The following function allows one to make several updates to a @map@
+from an @assoc_list@:
+\begin{verbatim}
+:- func set_from_assoc_list(map(K,V), assoc_list(K, V)) = map(K,V).
+\end{verbatim}
+
+Example (wild guesses):
+\begin{verbatim}
+ NewIQs = set_from_assoc_list(IQs, [
+ "Ralph Becket" - 253,
+ "Fergus Henderson" - 211,
+ "Albert Einstein" - 161, % Revised estimate.
+ "Tyson Dowd" - 86
+ ])
+\end{verbatim}
+
+\subsection{Corresponding Pairs in Lists}
+
+Occasionally one has keys and values in separate @list at s. One can
+construct a @map@ from them using the following function:
+\begin{verbatim}
+:- func from_corresponding_lists(list(K), list(V)) = map(K, V).
+\end{verbatim}
+The @list at s must be the same length; if they aren't then this
+function will throw an exception.
+
+Example:
+\begin{verbatim}
+ QualityOfPet =
+ from_corresponding_lists(
+ [cat, dog, snake], [good, bad, inadvisable]
+ )
+\end{verbatim}
+giving @QualityOfPet ^ elem(cat) = good@ and
+ at QualityOfPet ^ elem(dog) = bad@ and
+ at QualityOfPet ^ elem(snake) = inadvisable at .
+\XXX{This example may also need a little work.}
+
+\subsection{Other Maps}
+
+One can use the following functions to merge @map at s together:
+\begin{verbatim}
+:- func merge(map(K, V), map(K, V)) = map(K, V).
+
+:- func overlay(map(K,V), map(K,V)) = map(K,V).
+\end{verbatim}
+The @merge@ function will throw an exception if the two maps have a key
+in common. The @overlay@ function will not, taking the values for
+common keys from the second @map@ argument in the resulting @map at .
+
+Example:
+\begin{verbatim}
+ RoutesA = from_assoc_list([
+ adelaide - melbourne,
+ perth - adelaide,
+ melbourne - canberra
+ ]),
+ RoutesB = from_assoc_list([
+ canberra - sydney,
+ sydney - brisbane,
+ brisbane - darwin,
+ melbourne - alice_springs
+ ]),
+ Routes = overlay(RoutesA, RoutesB)
+\end{verbatim}
+will result in @Routes ^ elem(perth) = adelaide@ and
+ at Routes ^ elem(sydney) = brisbane@ and
+ at Routes ^ elem(melbourne) = alice_springs at .
+\XXX{Another bad example. Should use this one for @multi_map at .}
+
+\section{Miscellaneous Operations}
+
+\XXX{This section needs examples throughout.}
+
+One can delete the mappings for one or a @list@ of keys using the
+following:
+\begin{verbatim}
+:- func delete(map(K,V), K) = map(K,V).
+
+:- func delete_list(map(K,V), list(K)) = map(K,V).
+
+:- pred map__remove(map(K,V), K, V, map(K,V)).
+:- mode map__remove(in, in, out, out) is semidet.
+
+:- pred map__det_remove(map(K,V), K, V, map(K,V)).
+:- mode map__det_remove(in, in, out, out) is det.
+\end{verbatim}
+The @delete@ and @delete_list@ functions simply ignore key arguments
+that do not have mappings in the @map@ argument.
+
+The predicate @map__remove@ will fail if the given key is not present,
+otherwise it returns both the value mapping of the key and a version of
+the @map@ that does not contain a mapping for the key.
+
+The present @map__det_remove@ is similar, except that it will throw an
+exception if the given @map@ does not have a mapping for the key in
+question.
+
+One can obtain a count of the number of mappings in a map with
+\begin{verbatim}
+:- func count(map(K, V)) = int.
+\end{verbatim}
+
+One can obtain (sorted) lists of keys and values stored in a @map@:
+\begin{verbatim}
+:- func keys(map(K, V)) = list(K).
+
+:- func sorted_keys(map(K, V)) = list(K).
+
+:- func values(map(K, V)) = list(V).
+\end{verbatim}
+The functions @keys@ and @sorted_keys@ are identical, except that the
+latter guarantees to return the keys in ascending order. The values
+returned by @values@ are not guaranteed to be in any order.
+
+The following convert @map at s to @assoc_list at s:
+\begin{verbatim}
+:- func to_assoc_list(map(K,V)) = assoc_list(K,V).
+:- func to_sorted_assoc_list(map(K,V)) = assoc_list(K,V).
+\end{verbatim}
+ at to_sorted_assoc_list@ returns the corresponding @assoc_list@ with keys
+in ascending order.
+
+XXX HERE!
only in patch2:
--- io.tex 11 Oct 2002 02:21:58 -0000 1.2
+++ io.tex 6 Nov 2002 00:25:52 -0000
@@ -1,12 +1,12 @@
% vim: ft=tex ff=unix ts=4 sw=4 et wm=8 tw=0
-\section{Input and Output}
+\chapter{Input and Output}
One unfortunate consequence of being a pure declarative language
is that IO becomes somewhat more complex than is the case for
imperative languages.
-\subsection{IO \emph{Is} a Side-Effect}
+\section{IO \emph{Is} a Side-Effect}
One problem is that performing IO necessarily has an effect on the
outside world that cannot be backtracked over or undone -- there is
@@ -15,7 +15,7 @@
where there is no concept of a value (such as the state of the
world) ``changing'', only one of new such values being computed.
-\subsection{Order is Important}
+\section{Order is Important}
Another problem is that since logically there is no difference
between the goal @(G1, G2)@ and the goal @(G2, G1)@, we also need to
@@ -23,7 +23,7 @@
intended order and are not mixed up as a consequence of the
compiler reordering goals for optimization purposes and so forth.
-\subsection{Uniqueness}
+\section{Uniqueness}
A number of solutions to the IO problem have been adopted by
the pure, declarative languages, the main contenders being the
@@ -112,7 +112,7 @@
value can never be accessed), which is exactly what happens
for the data types just mentioned.
-\subsection{Stylistic Considerations}
+\section{Stylistic Considerations}
Since passing the IO state around everywhere is a little
cumbersome and also quite restrictive (it can only be passed
@@ -126,7 +126,7 @@
real dividends in terms of reusability, maintainability, ease
of debugging and so forth.
-\subsection{* Determinism Restrictions}
+\section{* Determinism Restrictions}
Since IO operations cannot be backtracked across, the IO state
(and, indeed, unique objects in general) cannot be passed to
@@ -134,7 +134,7 @@
predicates can take unique IO states as arguments.\footnote{This is not strictly true; there is another
determinism, cc-multi, which is compatible with uniqueness.}
-\subsection{* State Variable Syntax}
+\section{* State Variable Syntax}
Having to name and pass two variables around for every IO
operation quickly becomes tiresome. Mercury has a special
@@ -188,7 +188,7 @@
Henceforth we will use state variable syntax rather than
explicitly numbered IO states.
-\subsection{Common IO Operations}
+\section{Common IO Operations}
The @io@ library module defines a plethora of useful IO
operations and as usual with libraries, the reader is
@@ -196,7 +196,7 @@
Here we will present some basic IO operations to help get the
ball rolling.
-\subsubsection{Output}
+\subsection{Output}
Output is generally simpler to deal with than input,
because, by and large, there are no error codes to deal
@@ -279,7 +279,7 @@
value of the expression.) This is subtle stuff and will
be dealt with in a later chapter. \XXX{}
-\subsubsection{Input}
+\subsection{Input}
Input is marginally more complex than output since
typically on of three things can happen:
only in patch2:
--- exceptions.tex 11 Oct 2002 02:21:51 -0000 1.2
+++ exceptions.tex 14 Nov 2002 10:51:17 -0000
@@ -1,10 +1,472 @@
% vim: ft=tex ff=unix ts=4 sw=4 et wm=8 tw=0
\chapter{* Exceptions}
-\section{Throwing}
-\section{Catching}
-\subsection{Effect On Determinism}
-\subsection{Restoring (Plain) Determinism (promise\_only\_solution)}
+There are two ways of dealing with error conditions that are detected at
+run-time. The first is for the operation which detected the error to
+return an error code of some sort. This is what happens in the @io@
+library with predicates that return an @io__result at . Return codes
+generally have to be dealt with as soon as the operation returns; in
+some situations this can mean that the underlying algorithm ends up
+hidden beneath a slew of error handling code.
+The other option is to \emph{throw an exception} (sometimes called
+\emph{raising} an exception). An exception causes execution to
+immediately return to the nearest \emph{exception handler} in the call
+stack. The exception handler must decide what to do from that point on.
+Exceptions are useful when the best place to handle an error (or rather,
+an exceptional situation) is at some higher level of abstraction -- that
+is, further up the call stack -- rather than having to worry about
+unlikely events at every point in the program.
+
+Exception based code in Mercury makes use of the modules @exception@ and
+ at std_util@, the latter because exceptions are ``transmitted'' as values
+of type @univ at .
+
+\section{An Example}
+
+\XXX{I use an IO based example. Perhaps it would be better to use a
+non-IO example and afterwards mention @try\_io@ and relatives.}
+
+In this example we want to ``translate'' one file into another. The
+obvious code using error code handling is unfortunately ugly:
+\begin{verbatim}
+:- import_module io, string, list.
+
+main(!IO) :-
+ io__open_input("input_file", OpenInputResult, !IO),
+ (
+ OpenInputResult = error(_),
+ report_error("Couldn't open input_file", !IO)
+ ;
+ OpenInputResult = ok(Input),
+ io__open_output("output_file", OpenOutputResult, !IO),
+ (
+ OpenOutputResult = error(_),
+ io__close_input(Input, !IO),
+ report_error("Couldn't open output_file", !IO)
+ ;
+ OpenOutputResult = ok(Output),
+ translate(Input, Output, TranslateResult, !IO),
+ io__close_output(Output, !IO),
+ io__close_input(Input, !IO),
+ (
+ TranslateResult = error(_),
+ report_error("Something went wrong in translation", !IO)
+ ;
+ TranslateResult = ok
+ )
+ )
+ ).
+
+:- pred report_error(string, io, io).
+:- mode report_error(in, di, uo) is det.
+
+report_error(ErrMsg, !IO) :-
+ io__stderr_stream(StdErr, !IO),
+ io__format(, StdErr, "%s\n", [s(ErrMsg)], !IO),
+ io__set_exit_status(1, !IO).
+
+:- pred translate(input_stream, output_stream, io__res, io, io).
+:- mode translate(in, in, out, di, uo) is det.
+
+translate(Input, Output, Result, !IO) :- ...
+\end{verbatim}
+We can write more concise code that handles all the possible errors in
+one place by using exceptions:
+\begin{verbatim}
+:- import_module io, string, list, unit, exception, univ.
+
+:- pred main(io, io).
+:- mode main(di, uo) is cc_multi.
+
+main(!IO) :-
+ try_io(open_files_and_translate, Result, !IO),
+ (
+ Result = succeeded(_)
+ ;
+ Result = exception(Exception),
+
+ % Here we use mode univ(out) = in is semidet.
+ %
+ ( if Exception = univ(ErrMsg)
+ then report_error(ErrMsg, !IO)
+ else rethrow(Result) % These are not the droids
+ % we're looking for.
+ )
+ ).
+
+:- pred open_files_and_translate(unit, io, io).
+:- mode open_files_and_translate(out, di, uo) is det.
+
+open_files_and_translate(unit, !IO) :-
+ open_in("input_file", Input, !IO),
+ open_out("output_file", Input, Output, !IO),
+ translate(Input, Output, !IO),
+ io__close_output(Output),
+ io__close_input(Input).
+
+:- pred open_in(string, input_stream, io, io).
+:- mode open_in(in, in, di, uo) is det.
+
+open_in(File, Input, !IO) :-
+ io__open_input(File, Result, !IO),
+ (
+ Result = ok(Input)
+ ;
+ Result = error(_),
+ throw("Couldn't open " ++ File)
+ ).
+
+:- pred open_out(string, input_stream, output_stream, io, io).
+:- mode open_out(in, in, out, di, uo) is det.
+
+open_out(File, Output, !IO) :-
+ io__open_output(File, Result, !IO),
+ (
+ Result = ok(Output)
+ ;
+ Result = error(_),
+ io__close_input(Input),
+ throw("Couldn't open " ++ File)
+ ).
+\end{verbatim}
+We can see that the code in the version that uses exceptions has
+better structure, although the exception handler (the @try_io@ code) is
+forced to use some advanced mechanisms, most notably @univ@ values. The
+code here \emph{is} slightly longer, but that is mainly an artefact of
+using a toy example. In a real application we would expect the
+situation to be reversed (otherwise there would be little point in using
+exceptions.)
+
+It is important to observe that every exception-throwing site is
+responsible for performing clean-up operations that are not dealt with
+by the exception handler. In this case we have to pass the @Input@
+stream handle to the @open_out@ predicate so that we can close it if we
+fail to successfully open the @Output@ stream (and, similarly, the
+ at translate@ predicate should close both streams before throwing an
+exception.)
+
+
+
+\section{Throwing Exceptions}
+
+An exception @X@ is thrown by calling @throw(X)@ from the @exception@
+module (@throw/1@ exists in both predicate and function versions and, in
+the normal course of things, the compiler will be able to work out from
+context which is meant.)
+
+ at throw/1@ has determinism @erroneous@, indicating to the compiler that
+this predicate does not terminate normally (@erroneous@ can also be used
+for predicates that do not return at all), hence it is not necessary to
+tie-up all loose ends. For instance, in
+\begin{verbatim}
+ p(A, X0, X1),
+ (
+ A = ok,
+ q(X1, X2)
+ ;
+ A = ouch,
+ throw(...)
+ ),
+ r(X2, X)
+\end{verbatim}
+we do not have to include the unification @X2 = X1@ in the second
+disjunct of the switch, as would be required if @throw/1@ did not have
+determinism @erroneous@ since @X2@ is required by the call to @r/2 at .
+
+Any value at all can be thrown as an exception; it is up to the
+enclosing exception handler to decide if and how to handle matters.
+
+If, in an exception handler, one has to pass the exception back up to an
+exception handler even further up the call stack then one should use
+ at rethrow@. The reason for this will be explained in the next section
+\XXX{}.
+
+\section{Handling Exceptions}
+
+Exception handling works via a call to @try@ or one of its variants:
+\begin{verbatim}
+ % try(Goal, Result)
+ %
+:- pred try(pred(T), exception_result(T)).
+:- mode try(pred(out) is det, out(cannot_fail)) is cc_multi.
+:- mode try(pred(out) is semidet, out ) is cc_multi.
+:- mode try(pred(out) is cc_multi, out(cannot_fail)) is cc_multi.
+:- mode try(pred(out) is cc_nondet, out ) is cc_multi.
+\end{verbatim}
+where
+\begin{verbatim}
+:- type exception_result(T)
+ ---> succeeded(T)
+ ; failed
+ ; exception(univ).
+
+:- inst cannot_fail
+ ---> succeeded(ground)
+ ; exception(ground).
+\end{verbatim}
+and @univ@ is the universal type defined in the @std_util@ standard
+library module.
+
+What happens operationally with a call @try(Goal, Result)@ is that the
+closure @Goal@ is executed and @Result@ instantiated according to what
+happened:
+if @Goal@ succeeded, returning @X@, then @Result = succeeded(X)@;
+if @Goal@ failed then @Result = failed@;
+otherwise @Goal@ must have thrown an exception @E@, in which case
+ at Result = exception(U)@ where @U = univ(E)@ (i.e. the encapsulation of
+the abitrary type of @E@ in the universal type @univ at .)
+
+The code that follows the call to @try@ must decide what to do depending
+upon @Result at .
+
+If @Result = succeeded(X)@ or @Result = failed@ then we can proceed as
+if we had simply called @Goal at . Note that if @Goal@ has determinism
+ at det@ or @cc_multi@ then it cannot fail, in which case the argument mode
+of @Result@ is @out(cannot_fail)@ which, in turn, means that we do not
+need to test for @Result = failed at .
+
+If @Result = exception(U)@ then we need to handle the exception.
+Sometimes this can be as simple as performing some clean-up operations
+and calling @rethrow(Result)@. Usually, however, we are interested in
+exactly what exception was thrown, which requires a checked, dynamic
+(i.e. run-time) \emph{cast} of @U@ from type @univ@ to the expected
+type for @E at .
+
+The @univ@ function in @std_util@ has the following signature:
+\begin{verbatim}
+:- func univ(T ) = univ.
+:- mode univ(in ) = out is det.
+:- mode univ(out) = in is semidet.
+\end{verbatim}
+Going in the ``forwards'' direction, any value of any type can be
+converted in a value of type @univ@, as one might expect. In the
+``reverse'' direction, however, a value of type @univ@ may or may not be
+convertible into a value of some given type @T at .
+
+So the code for handling an exception looks like this:
+\begin{verbatim}
+ try(Goal, Result),
+ (
+ Result = succeeded(X), ...
+ ;
+ Result = failed, ...
+ ;
+ Result = exception(U),
+ ( if U = univ(E) then
+ % E is the value of the exception in whatever
+ % type which deal_with_exception/1 below expects.
+ %
+ deal_with_exception(E),
+ ...
+ else
+ % Otherwise the exception is of a different type
+ % to that which we were prepared to handle, so the
+ % exception cannot be intended for us to handle.
+ % Therefore we pass it on the the next exception
+ % handler up the call stack.
+ %
+ rethrow(Result)
+ )
+ )
+\end{verbatim}
+Note that our if-then-else goal could have several arms if we are
+prepared to deal with exceptions of several different types, but we must
+still be prepared to @rethrow@ a result which we cannot handle -- simply
+dropping such things on the floor means that higher-level exception
+handlers cannot do their job. This is particularly important for
+higher order code that deals with exceptions.
+
+\section{Effect On Determinism}
+
+To throw an exception is to effect an abnormal exit from a procedure.
+Thanks to the halting problem \XXX{} it is impossible for a compiler to
+decide whether an arbitrary piece of code will throw an exception or
+even what exceptions it may throw. The only way to find out in general
+is to run the code and see what happens. As a consequence, the
+determinism of @try@ is @cc_multi@: it always returns a result, but we
+have no way of knowing, analytically, whether the result will be an
+exception or a ``normal'' return. Either way, we only get the one
+result and cannot backtrack into the computation.
+
+\section{Er, Something}
+
+\XXX{There was something I was going to say here\ldots}
+
+\section{IO States and Stores}
+
+The @io@ state and @store@ types play a special role in Mercury in as
+much as they are the main exploiters of uniqueness. \XXX{What a
+horrible way to put it.}
+
+The usual exception handling method is not sufficient for handling
+computations that manipulate @io@ states and @store at s. The problem is
+that we do not want an exception to cause us to lose the @io@ state or
+ at store@ -- the former because then our program could no longer perform
+any IO at all (and hence not report the results of any computation) and
+the latter because we do not want to lose access to the information
+in the @store at .
+
+One might imagine that these problems could be remedied by including the
+ at io@ state or @store@ as part of the exception result -- for example
+\begin{verbatim}
+:- type excn_with_io ---> excn_with_io(string, io).
+
+p(!IO) :-
+ do_something(X, !IO),
+ if something_went_wrong(X)
+ then throw(excn_with_io("Aieee!", !.IO))
+ else carry_on_as_usual(X, !IO).
+\end{verbatim}
+The first difficulty here is that the argument to @throw@ has mode @in@,
+which means the @io@ state contained in the @excn_with_io@ will not be
+seen as @unique@ by the exception handler.
+
+The second objection is that the predicate that throws the exception may
+not be in posession of the @io@ state or @store at . Higher order code is
+most likely to have this problem:
+\begin{verbatim}
+p(P, !IO) :-
+ P(X), % P may throw an exception, but
+ % does not have the IO state.
+ ...
+\end{verbatim}
+while we could conceivably place our own exception handler around the
+call to @P@, catch any exception thrown by P and wrap that up in
+another exception that included the @io@ state, we then have the
+problem that any exception handler further up the call stack looking
+for exceptions thrown by @P@ will not recognise them because of our
+wrapper. One could probably find a solution to the conundrum, but
+it seems unlikely that it would be elegant.
+
+The third problem is that the current version of the Mercury compiler
+does not yet handle nested unique objects -- that is, even if we could
+place an @io@ state or @store@ inside an exception value \emph{and}
+arrange for a mode of @try@ that preserved its @inst@ \emph{and}
+came up with a means of transmitting the requisite @inst@
+information to the exception handler, we would still have to wait for
+a version of the compiler to come along that handled nested @unique@
+objects. \XXX{To our shame!}
+
+Unfortunately, no general solution to all these problems presents
+itself -- there remains research to be done. It should be recognised
+that these problems are not specific to Mercury; they exist in all
+exception systems that have code that performs destructive update.
+The problems are merely highlighted by Mercury's strict type and mode
+systems, which the designers do not consider worth compromising for
+the sake of a friendlier exception system. \XXX{Could probably put
+that more diplomatically.}
+
+The pragmatic solution currently adopted is to supply two extra
+versions of @try@:
+\begin{verbatim}
+:- pred try_io(pred(T, io, io), exception_result(T),
+ io, io).
+:- mode try_io(pred(out, di, uo) is det, out(cannot_fail),
+ di, uo) is cc_multi.
+:- mode try_io(pred(out, di, uo) is cc_multi, out(cannot_fail),
+ di, uo) is cc_multi.
+
+:- pred try_store(pred(T, store, store), exception_result(T),
+ store, store).
+:- mode try_store(pred(out, di, uo) is det, out(cannot_fail),
+ di, uo) is cc_multi.
+:- mode try_store(pred(out, di, uo) is cc_multi, out(cannot_fail),
+ di, uo) is cc_multi.
+\end{verbatim}
+These work very much like @try@, except that in this case the goal
+argument takes two extra arguments for the @io@ state or @store@ as
+appropriate and that, of course, the @io@ state or @store@ is
+preserved across the exception.
+
+So, say we have a @io@ based predicate @parse_input@ that throws
+an exception on detecting an error rather than returning an error
+code, we could handle it like this:
+\begin{verbatim}
+:- pred parse_input(parse_result, io, io).
+:- mode parse_input(out, di, uo) is det.
+...
+ try_io(parse_input, Result, !IO),
+ (
+ Result = succeeded(Parse),
+ io__format("Parsing succeeded\n", [], !IO),
+ ...
+ ;
+ Result = exception(U),
+ io__format("Parsing exception\n", [], !IO),
+ ( if U = univ(E)
+ then handle_parser_exception(E)
+ else rethrow(Result)
+ )
+ )
+...
+\end{verbatim}
+As pointed out earlier, were it not for @try_io@ returning the @io@
+state after catching the exception, we could not make the call to
+ at io__format@ in the exception handler.
+
+It is important to be aware that it is the programmer's
+responsibility to ensure that @store at s and various aspects of the
+ at io@ state are consistent with the program's logic after catching
+an exception. That is, they will be consistent as far as Mercury
+is concerned, but various program-specific invariants concerning
+them may or may not be preserved. This is a difficult problem
+and is what makes exception handling less attractive than it would
+at first seem.
+
+\section{All Solutions Predicates}
+
+Occasionally one may want to enumerate all the solutions of a
+nondeterministic predicate up to the point that all solutions
+have been generated or the predicate in question throws an
+exception. This is what @try_all@ is for:
+\begin{verbatim}
+:- pred try_all(pred(T), list(exception_result(T))).
+:- mode try_all(pred(out) is det, out(try_all_det)) is cc_multi.
+:- mode try_all(pred(out) is semidet, out(try_all_semidet)) is cc_multi.
+:- mode try_all(pred(out) is multi, out(try_all_multi)) is cc_multi.
+:- mode try_all(pred(out) is nondet, out(try_all_nondet)) is cc_multi.
+\end{verbatim}
+the output argument is a list of the @exception_result at s and the last
+element in the list will contain the exception, if any was thrown.
+Otherwise, this predicate is very similar to the @builtin@
+predicate @unsorted_solutions at .
+
+Just as @unsorted_solutions@ has a companion, @unsorted_aggregate@,
+that supports interleaving processing of the results of the
+nondeterministic predicate, @try_all@ has a companion,
+ at incremental_try_all@:
+\begin{verbatim}
+:- pred incremental_try_all(
+ pred(T1),
+ pred(exception_result(T1), T2, T2),
+ T2, T2).
+:- mode incremental_try_all(
+ pred(out) is nondet,
+ pred(in, di, uo) is det,
+ di, uo) is cc_multi.
+:- mode incremental_try_all(
+ pred(out) is nondet,
+ pred(in, in, out) is det,
+ in, out) is cc_multi.
+\end{verbatim}
+
+\XXX{Do I need more examples in this section?}
+
+\section{The Down Side}
+
+From the discussion above, it should be clear that exceptions are not
+silver bullets. The cases where they \emph{may} simplify your code are
+those where there is some distance between the point where an exceptional
+case may be detected and the point where it is best handled. Even then,
+one must be careful to ensure that the programs ``state'' (in the sense
+of unique values such as @store at s and the @io@ state) are consistent with
+the invariants of the program before leaving the exception handler.
+
+In many cases, it turns out to be simpler to return error codes and
+handle problems as locally as possible.
+
+As always, it takes experience and a little experimentation to work out
+which is the best solution in each particular situation.
Index: std-util.tex
===================================================================
RCS file: std-util.tex
diff -N std-util.tex
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ std-util.tex 14 Nov 2002 10:51:03 -0000
@@ -0,0 +1,6 @@
+% vim: ft=tex ff=unix ts=4 sw=4 et wm=8 tw=0
+
+\chapter{The Standard Utility Library Module}
+
+
+
Index: assoc-lists.tex
===================================================================
RCS file: assoc-lists.tex
diff -N assoc-lists.tex
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ assoc-lists.tex 14 Nov 2002 10:51:01 -0000
@@ -0,0 +1,6 @@
+% vim: ft=tex ff=unix ts=4 sw=4 et wm=8 tw=0
+
+\chapter{Association Lists}
+
+
+
--------------------------------------------------------------------------
mercury-reviews mailing list
post: mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the reviews
mailing list