This is mercury_ref.info, produced by makeinfo version 4.11 from
reference_manual.texi_pp.

INFO-DIR-SECTION The Mercury Programming Language
START-INFO-DIR-ENTRY
* Mercury Language: (mercury_ref).  The Mercury Language Reference Manual.
END-INFO-DIR-ENTRY

   This file documents the Mercury programming language, version 11.07.

   Copyright (C) 1995-2011 The University of Melbourne.

   Permission is granted to make and distribute verbatim copies of this
manual provided the copyright notice and this permission notice are
preserved on all copies.

   Permission is granted to copy and distribute modified versions of
this manual under the conditions for verbatim copying, provided also
that the entire resulting derived work is distributed under the terms
of a permission notice identical to this one.

   Permission is granted to copy and distribute translations of this
manual into another language, under the above conditions for modified
versions.


File: mercury_ref.info,  Node: Using pragma foreign_decl for C#,  Next: Using pragma foreign_code for C#,  Prev: Using pragma foreign_export for C#,  Up: Interfacing with C#

14.9.2.6 Using pragma foreign_decl for C#
.........................................

`pragma foreign_decl' declarations for C# can be used to provide any
top-level C# declarations (e.g. `using' declarations or auxiliary class
definitions) which are needed by C# code in `pragma foreign_proc'
declarations in that module.

   For example:

     :- pragma foreign_decl("C#", "
     	using System;
     ").
     :- pred hello(io.state::di, io.state::uo) is det.
     :- pragma foreign_proc("C#",
     	hello(_IO0::di, _IO::uo),
     	[will_not_call_mercury],
     "
     	// here we can refer directly to Console rather than System.Console
     	Console.WriteLine(""hello world"");
     ").


File: mercury_ref.info,  Node: Using pragma foreign_code for C#,  Prev: Using pragma foreign_decl for C#,  Up: Interfacing with C#

14.9.2.7 Using pragma foreign_code for C#
.........................................

The C# code from `pragma foreign_proc' declarations for C# will be
placed in the bodies of static member functions of an
automatically-generated C# class.  `pragma foreign_code' can be used to
define additional members of this automatically-generated class, which
can then be referenced by `pragma foreign_proc' declarations for C#
from that module.

   For example:

     :- pragma foreign_code("C#", "
     	static int counter = 0;
     ").

     :- impure pred incr_counter is det.
     :- pragma foreign_proc("C#", incr_counter,
     	[will_not_call_mercury], "counter++;").

     :- semipure func get_counter = int.
     :- pragma foreign_proc("C#",
     	get_counter = (Result::out),
     	[will_not_call_mercury, promise_semipure],
     	"Result = counter;").


File: mercury_ref.info,  Node: Interfacing with Java,  Next: Interfacing with Erlang,  Prev: Interfacing with C#,  Up: Language specific bindings

14.9.3 Interfacing with Java
----------------------------

* Menu:

* Using pragma foreign_type for Java :: Declaring Java types in Mercury
* Using pragma foreign_export_enum for Java :: Using Mercury enumerations in
                                               Java
* Using pragma foreign_enum for Java :: Assigning Mercury enumerations
                                        values in Java
* Using pragma foreign_proc for Java :: Calling Java code from Mercury
* Using pragma foreign_export for Java :: Calling Mercury from Java code
* Using pragma foreign_decl for Java :: Including Java declarations in Mercury
* Using pragma foreign_code for Java :: Including Java code in Mercury


File: mercury_ref.info,  Node: Using pragma foreign_type for Java,  Next: Using pragma foreign_export_enum for Java,  Up: Interfacing with Java

14.9.3.1 Using pragma foreign_type for Java
...........................................

A Java `pragma foreign_type' declaration has the form:

     :- pragma foreign_type("Java", MERCURYTYPENAME, "JAVATYPE").

   The JAVATYPE can be any accessible non-primitive Java type.

   The effect of this declaration is that Mercury values of type
MERCURYTYPENAME will be passed to and from Java foreign_procs as having
type JAVATYPE.

   Furthermore, any Mercury procedure exported with `pragma
foreign_export' will use JAVATYPE as the type for any parameters whose
Mercury type is MERCURYTYPENAME.


File: mercury_ref.info,  Node: Using pragma foreign_export_enum for Java,  Next: Using pragma foreign_enum for Java,  Prev: Using pragma foreign_type for Java,  Up: Interfacing with Java

14.9.3.2 Using pragma foreign_export_enum for Java
..................................................

For Java the symbolic names generated by a `pragma foreign_export_enum'
must form valid Java identifiers.  These identifiers are used as the
names of static class members which are assigned instances of the
enumeration class.

   The `equals' method should be used for equality testing of
enumeration values in Java code.

   The default mapping used by `pragma foreign_export_enum'
declarations for Java is to use the Mercury constructor name as the
base of the symbolic name.  For example, the symbolic name for the
Mercury constructor `foo' would be `foo'.


File: mercury_ref.info,  Node: Using pragma foreign_enum for Java,  Next: Using pragma foreign_proc for Java,  Prev: Using pragma foreign_export_enum for Java,  Up: Interfacing with Java

14.9.3.3 Using pragma foreign_enum for Java
...........................................

`pragma foreign_enum' is currently not supported for Java.


File: mercury_ref.info,  Node: Using pragma foreign_proc for Java,  Next: Using pragma foreign_export for Java,  Prev: Using pragma foreign_enum for Java,  Up: Interfacing with Java

14.9.3.4 Using pragma foreign_proc for Java
...........................................

The Java code from Java pragma foreign_proc declarations will be placed
in the bodies of static member functions of an automatically-generated
Java class.  Since such Java code will become part of a static member
function, it must not refer to the `this' keyword.  It may however
refer to static member variables or static member functions declared
with `pragma foreign_code'.

   The input and output variables for a Java `pragma foreign_proc' will
have Java types corresponding to their Mercury types.  The exact rules
for mapping Mercury types to Java types are described in *note Java
data passing conventions::.

   The Java code in a `pragma foreign_proc' declaration for a procedure
whose determinism indicates that it can fail must assign a value of
type `boolean' to the variable `SUCCESS_INDICATOR'.  For example:

     :- pred string.contains_char(string, character).
     :- mode string.contains_char(in, in) is semidet.

     :- pragma foreign_proc("Java",
     	string.contains_char(Str::in, Ch::in),
             [will_not_call_mercury, promise_pure],
             "SUCCESS_INDICATOR = (Str.IndexOf(Ch) != -1);").

Java code for procedures whose determinism indicates that they cannot
fail should not refer to the `SUCCESS_INDICATOR' variable.

   Arguments whose mode is input will have their values set by the
Mercury implementation on entry to the Java code.  With our current
implementation, the Java code must set the values of all output
variables, even if the procedure fails (i.e. sets the
`SUCCESS_INDICATOR' variable to `false').


File: mercury_ref.info,  Node: Using pragma foreign_export for Java,  Next: Using pragma foreign_decl for Java,  Prev: Using pragma foreign_proc for Java,  Up: Interfacing with Java

14.9.3.5 Using pragma foreign_export for Java
.............................................

A `pragma foreign_export' declaration for Java has the form:

     :- pragma foreign_export("Java", MERCURYMODE, "JAVA_NAME").

   For example,

     :- pragma foreign_export("Java", foo(in, in, out), "FOO").

   The type signature of the Java interface to a Mercury procedure is as
described in *note Java data passing conventions::.

   Calling polymorphically typed Mercury procedures from Java is a
little bit more difficult than calling ordinary (monomorphically typed)
Mercury procedures.  The simplest method is to just create monomorphic
forwarding procedures that call the polymorphic procedures, and export
them, rather than exporting the polymorphic procedures.

   If you do export a polymorphically typed Mercury procedure, the
compiler will prepend one `type_info' argument to the parameter list of
the Java interface function for each distinct type variable in the
Mercury procedure's type signature.  The caller must arrange to pass in
appropriate `type_info' values corresponding to the types of the other
arguments passed.  These `type_info' arguments can be obtained using
the Mercury `type_of' function in the Mercury standard library module
`type_desc'.


File: mercury_ref.info,  Node: Using pragma foreign_decl for Java,  Next: Using pragma foreign_code for Java,  Prev: Using pragma foreign_export for Java,  Up: Interfacing with Java

14.9.3.6 Using pragma foreign_decl for Java
...........................................

`pragma foreign_decl' declarations for Java can be used to provide any
top-level Java declarations (e.g. `import' declarations or auxiliary
class definitions) which are needed by Java code in `pragma
foreign_proc' declarations in that module.

   For example:

     :- pragma foreign_decl("Java", "
     import javax.swing.*;
     import java.awt.*;

     class MyApplet extends JApplet {
         public void init() {
             JLabel label = new JLabel(""Hello, world"");
             label.setHorizontalAlignment(JLabel.CENTER);
             getContentPane().add(label);
         }
     }
     ").
     :- pred hello(io.state::di, io.state::uo) is det.
     :- pragma foreign_proc("Java",
     	hello(_IO0::di, _IO::uo),
     	[will_not_call_mercury],
     "
     	MyApplet app = new MyApplet();
     	// ...
     ").


File: mercury_ref.info,  Node: Using pragma foreign_code for Java,  Prev: Using pragma foreign_decl for Java,  Up: Interfacing with Java

14.9.3.7 Using pragma foreign_code for Java
...........................................

The Java code from `pragma foreign_proc' declarations for Java will be
placed in the bodies of static member functions of an
automatically-generated Java class.  `pragma foreign_code' can be used
to define additional members of this automatically-generated class,
which can then be referenced by `pragma foreign_proc' declarations for
Java from that module.

   For example:

     :- pragma foreign_code("Java", "
     	static int counter = 0;
     ").

     :- impure pred incr_counter is det.
     :- pragma foreign_proc("Java", incr_counter,
     	[will_not_call_mercury], "counter++;").

     :- semipure func get_counter = int.
     :- pragma foreign_proc("Java",
     	get_counter = (Result::out),
     	[will_not_call_mercury, promise_semipure],
     	"Result = counter;").


File: mercury_ref.info,  Node: Interfacing with Erlang,  Prev: Interfacing with Java,  Up: Language specific bindings

14.9.4 Interfacing with Erlang
------------------------------

* Menu:

* Using pragma foreign_type for Erlang :: Declaring Erlang types in Mercury
* Using pragma foreign_proc for Erlang :: Calling Erlang code from Mercury
* Using pragma foreign_export for Erlang :: Calling Mercury from Erlang code
* Using pragma foreign_decl for Erlang :: Including Erlang declarations in Mercury
* Using pragma foreign_code for Erlang :: Including Erlang code in Mercury


File: mercury_ref.info,  Node: Using pragma foreign_type for Erlang,  Next: Using pragma foreign_proc for Erlang,  Up: Interfacing with Erlang

14.9.4.1 Using pragma foreign_type for Erlang
.............................................

An Erlang `pragma foreign_type' declaration has the form:

     :- pragma foreign_type("Erlang", MERCURYTYPENAME, "").

   The effect of this declaration is that Mercury values of type
MERCURYTYPENAME will be passed to and from Erlang foreign_procs as
having some representation unknown to Mercury.


File: mercury_ref.info,  Node: Using pragma foreign_proc for Erlang,  Next: Using pragma foreign_export for Erlang,  Prev: Using pragma foreign_type for Erlang,  Up: Interfacing with Erlang

14.9.4.2 Using pragma foreign_proc for Erlang
.............................................

The input and output variables for a Erlang `pragma foreign_proc' will
be the Erlang representations as described in *note Erlang data passing
conventions::.

   The Erlang code in a `pragma foreign_proc' declaration for a
procedure whose determinism indicates that it can fail must assign
either `true' or `false' to the variable `SUCCESS_INDICATOR'.  For
example:

     :- pred contains_char(list(char)::in, char::in) is semidet.

     :- pragma foreign_proc("Erlang",
     	contains_char(Str::in, Ch::in),
             [will_not_call_mercury, promise_pure, thread_safe],
             "SUCCESS_INDICATOR = (string:chr(Str, Ch) =/= 0)").

   Arguments whose mode is input will have their values set by the
Mercury implementation on entry to the Erlang code.  The Erlang code
must set the values of all output variables, even if the procedure fails
(i.e. sets the `SUCCESS_INDICATOR' variable to `false').


File: mercury_ref.info,  Node: Using pragma foreign_export for Erlang,  Next: Using pragma foreign_decl for Erlang,  Prev: Using pragma foreign_proc for Erlang,  Up: Interfacing with Erlang

14.9.4.3 Using pragma foreign_export for Erlang
...............................................

A `pragma foreign_export' declaration for Erlang has the form:

     :- pragma foreign_export("Erlang", MERCURYMODE, "ERLANG_NAME").

   For example,

     :- pragma foreign_export("Erlang", foo(in, in, out), "foo").

   The type signature of the Erlang interface to a Mercury procedure is
described in *note Erlang data passing conventions::.

   Calling polymorphically typed Mercury procedures from Erlang is a
little bit more difficult than calling ordinary (monomorphically typed)
Mercury procedures.  The simplest method is to just create monomorphic
forwarding procedures that call the polymorphic procedures, and export
them, rather than exporting the polymorphic procedures.

   If you do export a polymorphically typed Mercury procedure, the
compiler will prepend one `type_info' argument to the parameter list of
the Erlang interface function for each distinct type variable in the
Mercury procedure's type signature.  The caller must arrange to pass in
appropriate `type_info' values corresponding to the types of the other
arguments passed.  These `type_info' arguments can be obtained using
the Mercury `type_of' function in the Mercury standard library module
`type_desc'.


File: mercury_ref.info,  Node: Using pragma foreign_decl for Erlang,  Next: Using pragma foreign_code for Erlang,  Prev: Using pragma foreign_export for Erlang,  Up: Interfacing with Erlang

14.9.4.4 Using pragma foreign_decl for Erlang
.............................................

`pragma foreign_decl' declarations for Erlang can be used to provide
any top-level Erlang declarations (e.g. `-define' macro declarations)
which are needed by Erlang code.

   `pragma foreign_decl' blocks which do not have the `local' attribute
will be copied into the `.hrl' header file for that module, and
automatically included by other modules that import the module.
Therefore `-export' directives and Erlang module attributes should only
appear in `local' blocks.

   For example:

     :- pragma foreign_decl("Erlang", "
     	-define(FOO, 42).
     ").
     :- pred hello(io.state::di, io.state::uo) is det.
     :- pragma foreign_proc("Erlang",
     	hello(_IO0::di, _IO::uo),
     	[will_not_call_mercury],
     "
     	io:format(""FOO = ~w~n"", [?FOO])
     ").


File: mercury_ref.info,  Node: Using pragma foreign_code for Erlang,  Prev: Using pragma foreign_decl for Erlang,  Up: Interfacing with Erlang

14.9.4.5 Using pragma foreign_code for Erlang
.............................................

`pragma foreign_code' can be used to define additional Erlang functions
which can then be referenced by `pragma foreign_proc' declarations for
Erlang from that module.  By adding `-export' directives inside `pragma
foreign_decl' declarations, those functions can additionally be called
from outside the defining module.

   For example:

     :- pragma foreign_code("Erlang", "
     	foo() -> io:put_chars(""Foo."").
     ").

     :- impure pred say_foo is det.
     :- pragma foreign_proc("Erlang", say_foo,
     	[will_not_call_mercury], "foo()").


File: mercury_ref.info,  Node: Impurity,  Next: Solver types,  Prev: Foreign language interface,  Up: Top

15 Impurity declarations
************************

In order to efficiently implement certain predicates, it is occasionally
necessary to venture outside pure logic programming.  Other predicates
cannot be implemented at all within the paradigm of logic programming,
for example, all solutions predicates.  Such predicates are often
written using the foreign language interface.  Sometimes, however, it
would be more convenient, or more efficient, to write such predicates
using the facilities of Mercury.  For example, it is much more
convenient to access arguments of compound Mercury terms in Mercury
than in C, and the ability of the Mercury compiler to specialize code
can make higher-order predicates written in Mercury significantly more
efficient than similar C code.

   One important aim of Mercury's impurity system is to make the
distinction between the pure and impure code very clear.  This is done
by requiring every impure predicate or function to be so declared, and
by requiring every call to an impure predicate or function to be
flagged as such.  Predicates or functions that are implemented in terms
of impure predicates or functions are assumed to be impure themselves
unless they are explicitly promised to be pure.

   Please note that the facilities described here are needed only very
rarely.  The main intent is for implementing language primitives such as
the all solutions predicates, or for implementing interfaces to foreign
language libraries using the foreign language interface.  Any other use
of `impure' or `semipure' probably indicates either a weakness in the
Mercury standard library, or the programmer's lack of familiarity with
the standard library.  Newcomers to Mercury are hence encouraged to
*skip this section*.

* Menu:

* Purity levels::       	Choosing the right level of purity.
* Purity ordering::     	How purity levels are ordered
* Impurity semantics::  	What impure code means.
* Declaring impurity::  	Declaring predicates impure.
* Impure goals::        	Marking a goal as impure.
* Promising purity::    	Promising that a predicate is pure.
* Impurity Example::    	A simple example using impurity.
* Higher-order impurity::    	Using impurity with higher-order code.


File: mercury_ref.info,  Node: Purity levels,  Next: Purity ordering,  Up: Impurity

15.1 Choosing the right level of purity
=======================================

Mercury distinguishes three "levels" of purity:

"pure"
     For pure procedures, the set of solutions depends only on the
     values of the input arguments.  They do not interact with the
     "real" world (i.e., do any input/output) without taking an
     io.state (*note Types::) as input and returning one as output, and
     do not change the value of any data structure that will not be
     undone on backtracking (unless the data structure would be
     unreachable on backtracking).  Note that equality axioms are
     important when considering the value of data structures.  The
     declarative semantics of pure predicates is never affected by the
     invocation of other predicates.  It is possible for the invocation
     of pure predicates to affect the operational behaviour of non-pure
     predicates and vice versa.

     By default, Mercury predicates and functions are pure.  Without
     using the foreign language interface, writing mode-specific
     clauses or calling other impure predicates and functions it is
     impossible to write impure code in Mercury.

"semipure"
     Semipure predicates are just like pure predicates, except that
     their declarative semantics may be affected by the invocation of
     impure predicates.  That is, they are sensitive to the state of
     the computation other than as reflected by their input arguments,
     though they do not affect the state themselves.

"impure"
     Impure predicates may perform I/O or modify hidden state, even if
     these side effects alter the operational semantics of other code.
     However, impure predicates may not change the declarative
     semantics of pure code.  They must be type-, mode-, determinism-
     and uniqueness correct.



File: mercury_ref.info,  Node: Purity ordering,  Next: Impurity semantics,  Prev: Purity levels,  Up: Impurity

15.2 Purity ordering
====================

The three levels of purity have a total ordering defined upon them
(which we will simply call the purity), where `pure > semipure >
impure'.


File: mercury_ref.info,  Node: Impurity semantics,  Next: Declaring impurity,  Prev: Purity ordering,  Up: Impurity

15.3 Semantics
==============

It is important to the proper operation of impure and semipure code, to
the flexibility of the compiler to optimize pure code, and to the
semantics of the Mercury language, that a clear distinction be drawn
between ordinary Mercury code and imperative code written with Mercury
syntax.  How this distinction is drawn will be explained below; the
purpose of this section is to explain the semantics of programs with
impure predicates.

   A _declarative_ semantics of impure Mercury code would be largely
useless, because the declarative semantics cannot capture the intent of
the programmer.  Impure predicates are executed for their side-effects,
which by definition are not part of their declarative semantics.  Thus
it is the _operational_ semantics of impure predicates that Mercury
must specify, and Mercury compilers must respect.

   The operational semantics of a Mercury predicate which invokes
_impure_ code is a modified form of the _strict sequential_ semantics
(*note Semantics::).  _Impure_ goals may not be reordered relative to
any other goals; not even "minimal" reordering as implied by the modes
is permitted.  If any such reordering is needed, this is a mode error.
However, _pure_ and _semipure_ goals may be reordered as the compiler
desires (within the bounds of the semantics the user has specified for
the program) as long as they are not moved across an impure goal.
Execution of impure goals is strict: they must be executed if they are
reached, even if it can be determined that the computation cannot lead
to successful termination.

   Semipure goals can be given a "contextual" declarative semantics.
They cannot have any side-effects, so it is expected that, given the
context in which they are called (relative to any impure goals in the
program), their declarative semantics fully captures the intent of the
programmer.  Thus a semipure goal has a perfectly consistent declarative
semantics, until an impure goal is reached.  After that, it has another
(possibly different) declarative semantics, until the next impure goal
is executed, and so on.  Mercury compilers must respect this contextual
nature of the semantics of semipure goals; within a single context, a
compiler may treat a semipure goal as if it were pure.


File: mercury_ref.info,  Node: Declaring impurity,  Next: Impure goals,  Prev: Impurity semantics,  Up: Impurity

15.4 Declaring impure functions and predicates
==============================================

Every Mercury predicate or function has exactly two purity values
associated with it.  One is the _declared_ purity of the predicate or
function, which is given by the programmer.  The other value is the
_inferred_ purity, which is calculated from the purity of goals in the
body of the predicate or function.

   A predicate is declared to be impure or semipure by preceding the
word `pred' in its `pred' declaration with `impure' or `semipure',
respectively.  Similarly, a function is declared impure or semipure by
preceding the word `func' in its `func' declaration with `impure' or
`semipure'.  That is, a declaration of the form:

     :- impure pred PRED(ARGUMENTS...).
     :- semipure pred PRED(ARGUMENTS...).

or

     :- impure func FUNC(ARGUMENTS...) = Result.
     :- semipure func FUNC(ARGUMENTS...) = Result.

declares the predicate PRED to be impure and the function FUNC to be
semipure, respectively.

   Type class methods may also be declared as `impure' or `semipure' by
preceding the word `pred' or `func' with the appropriate purity level.
An instance of the type class must provide method implementations that
are at least as pure as the method declaration.


File: mercury_ref.info,  Node: Impure goals,  Next: Promising purity,  Prev: Declaring impurity,  Up: Impurity

15.5 Marking a goal as impure
=============================

If predicate `p/N' is declared to be `impure' (`semipure') then all
calls to `p/N' must be annotated with `impure' (`semipure'):

     	impure p(X1, X2, ..., XN)

   If function `f/N' is declared to be `impure' (`semipure') then all
applications of `f/N' must be obtained by unification with a variable
and the unification goal as a whole be annotated with `impure'

     	impure X = f(X1, X2, ..., XN)

   Any call or unification goal containing a non-local variable with
inst any that appears in a negated context (i.e., in a negation or the
condition of an if-then-else goal) must be given an `impure' annotation
because it may violate referential transparency.

   Compound goals should not have purity annotations.

   The compiler will report an error if a required purity annotation is
omitted from a call or unification goal or if a `semipure' annotation
is used where an `impure' annotation is required.  The compiler will
report a warning if a semipure goal is annotated with `impure' or a
pure goal is annotated with `semipure'

   The requirement that impure or semipure calls be marked with
`impure' or `semipure' allows someone reading the code to tell which
goals are not pure, making code which relies on side effects somewhat
less mysterious.  Furthermore, it means that if a call is _not_
preceded by `impure' or `semipure', then the reader can rely on the
call having a proper declarative semantics, without hidden side-effects.


File: mercury_ref.info,  Node: Promising purity,  Next: Impurity Example,  Prev: Impure goals,  Up: Impurity

15.6 Promising that a predicate is pure
=======================================

Predicates that are implemented in terms of impure or semipure
predicates are assumed to have the least of the purity of the goals in
their body.  The declared purity of a predicate must not be more pure
than the inferred purity; if it is, the compiler must generate an error.
If the declared purity is less pure than the inferred purity, the
compiler should issue a warning (this is similar to the above case for
goals).  Because the inferred purity of the predicate is calculated
from the declared purity of the calls it executes,  the lowest purity
bound is propagated up from callee to caller through the program.

   In some cases the impurity of a predicate's body is an implementation
detail which should not be exposed to callers. These predicates are
pure or semipure even though they call impure or semipure predicates.
The only way for the programmer to stop the propagation of impurity is
to explicitly promise that the predicate or function is pure or
semipure.

   Of course, the Mercury compiler cannot verify that the predicate's
purity matches the promise, so it is the programmer's responsibility to
ensure this.  If a predicate is promised pure or semipure and is not,
the behaviour of the program is undefined.

   The programmer may promise that a predicate or function is pure or
semipure using the `promise_pure' and `promise_semipure' pragmas:

     :- pragma promise_pure(NAME/ARITY).
     :- pragma promise_semipure(NAME/ARITY).

   Programmers should be very careful about mixing code that is promised
pure with impure predicates or functions that may manipulate the same
hidden state (for example, the impure predicates used to implement a
predicate that is promised pure); the `promise_pure' declaration is
supposed to promise that impure code cannot change the declarative
semantics of pure code.  The module system can be used to minimize the
possibility of making errors with such code, by keeping impure
predicates or functions behind the interface where code is promised
pure.

   Note that the `promise_pure', `promise_semipure', and
`promise_impure' scopes described in *note Goals:: may be used to
promise purity at the finer level of goals within clauses.


File: mercury_ref.info,  Node: Impurity Example,  Next: Higher-order impurity,  Prev: Promising purity,  Up: Impurity

15.7 An example using impurity
==============================

The following example illustrates how a pure predicate may be
implemented using impure code.  Note that this code is not reentrant,
and so is not useful as is.  It is meant only as an example.

     :- pragma foreign_decl("C", "#include <limits.h>").
     :- pragma foreign_decl("C", "extern MR_Integer max;").

     :- pragma foreign_code("C", "MR_Integer max;").

     :- impure pred init_max is det.
     :- pragma foreign_proc("C",
         init_max,
         [will_not_call_mercury],
     "
         max = INT_MIN;
     ").

     :- impure pred set_max(int::in) is det.
     :- pragma foreign_proc("C",
        set_max(X::in),
        [will_not_call_mercury],
     "
         if (X > max) max = X;
     ").

     :- semipure func get_max = (int::out) is det.
     :- pragma foreign_proc("C",
         get_max = (X::out),
         [promise_semipure, will_not_call_mercury],
     "
         X = max;
     ").

     :- pragma promise_pure(max_solution/2).
     :- pred max_solution(pred(int), int).
     :- mode max_solution(pred(out) is multi, out) is det.

     max_solution(Generator, Max) :-
         impure init_max,
         (
             Generator(X),
             impure set_max(X),
             fail
         ;
             semipure Max = get_max
         ).


File: mercury_ref.info,  Node: Higher-order impurity,  Prev: Impurity Example,  Up: Impurity

15.8 Using impurity with higher-order code
==========================================

Higher-order code can manipulate impure or semipure predicates and
functions, provided that explicit purity annotations are used in three
places: on the higher-order types, on lambda expressions, and on
higher-order calls.  (There are no purity annotations on higher-order
insts and modes, however.)

* Menu:

* Purity annotations on higher-order types::
* Purity annotations on lambda expressions::
* Purity annotations on higher-order calls::


File: mercury_ref.info,  Node: Purity annotations on higher-order types,  Next: Purity annotations on lambda expressions,  Up: Higher-order impurity

15.8.1 Purity annotations on higher-order types
-----------------------------------------------

Ordinary higher-order types, such as `pred(T1, T2)' and `func(T1, T2) =
T', represent only pure predicates or pure functions.  But for each
ordinary higher-order type FOO, there are two corresponding types
`semipure FOO' and `impure FOO'.  These types can be used for
higher-order code that needs to manipulate impure or semipure
procedures.  For example the type `impure func(int) = int' represents
impure functions from `int' to `int'.

   There are no implicit conversions and no subtyping relationship
between ordinary higher-order types and the corresponding impure or
semipure higher-order types.  However, a value of an ordinary
higher-order type can be explicit "converted" to a value of an impure
(or semipure) higher-order type by wrapping it in an impure (or
semipure) lambda expression that just calls the pure higher-order term.


File: mercury_ref.info,  Node: Purity annotations on lambda expressions,  Next: Purity annotations on higher-order calls,  Prev: Purity annotations on higher-order types,  Up: Higher-order impurity

15.8.2 Purity annotations on lambda expressions
-----------------------------------------------

Purity annotations are required on lambda expressions that call
semipure or impure code.  Lambda expressions can be declared as
`semipure' or `impure' by including such an annotation before the
`pred' or `func' identifier in the lambda expression.  Such lambda
expressions have the corresponding `semipure' or `impure' higher-order
type.  For example, the expression

     	(impure func(X) = Y :- semipure get_max(Y), impure set_max(X))

is an example of an impure function lambda expression with type
`(impure func(int) = int)', and the expression

     	(impure pred(X::in, Y::out) is det :-
     		semipure get_max(Y),
     		impure set_max(X))
   is an example of an impure predicate lambda expression with type
`impure pred(int, int)'.


File: mercury_ref.info,  Node: Purity annotations on higher-order calls,  Prev: Purity annotations on lambda expressions,  Up: Higher-order impurity

15.8.3 Purity annotations on higher-order calls
-----------------------------------------------

Any calls to impure or semipure higher-order terms must be explicitly
annotated as such.  For impure or semipure higher-order predicates, the
annotation is indicated by putting `impure' or `semipure' before the
call.  For example:

     	:- func foo(impure pred(int)) = int.
     	:- mode foo(in(pred(out) is det)) = out is det.

     	foo(ImpurePred) = X1 + X2 :-
     		% using higher-order syntax
     		impure ImpurePred(X1),
     		% using the call/N syntax
     		impure call(ImpurePred, X2).

   For calling impure or semipure higher-order functions, the notation
is different than what you might expect.  In addition to using an
`impure' or `semipure' operator on the unification which invokes the
higher-order function application, you must also use `impure_apply' or
`semipure_apply' rather than using `apply' or higher-order syntax.  For
example:

     	:- func map(impure func(T1) = T2, list(T1)) = list(T2).

     	map(_ImpureFunc, []) = [].
     	map(ImpureFunc, [X|Xs]) = [Y|Ys] :-
     		impure Y = impure_apply(ImpureFunc, X),
     		impure Ys = map(ImpureFunc, Ys).


File: mercury_ref.info,  Node: Solver types,  Next: Trace goals,  Prev: Impurity,  Up: Top

16 Solver types
***************

* Menu:

* The any inst::
* Abstract solver type declarations::
* Solver type definitions::
* Implementing solver types::
* Solver types and negated contexts::

   Solver types are an experimental addition to the language supporting
the implementation of constraint solvers.  A program may place
constraints on and between variables of a solver type, limiting the
values those variables may take on before they are actually bound.  For
example, if `X' and `Y' are variables belonging to a constrained integer
solver type, we might place constraints upon them such that `X > 3 + Y'
and `Y =< 7'.  A later attempt to unify `Y' with `10' will fail (it
would violate the second constraint); similarly an attempt to unify `X'
with `5' and `Y' with `4' would fail (it would violate the first
constraint).


File: mercury_ref.info,  Node: The any inst,  Next: Abstract solver type declarations,  Up: Solver types

16.1 The `any' inst
===================

Variables with solver types can have one of three possible insts:
`free', `ground' or `any'.  A variable with a solver type with inst
`any' may not (yet) be semantically ground, in the following sense: if
a variable is semantically ground then the set of values it unifies
with form an equivalence class; if a variable is non-ground then the
set of values it unifies with do not form an equivalence class.

   More formally, `X' is ground if for values `Y' and `Z' that unify
with `X', it is the case that `Y' and `Z' also unify with each other.
`X' is non-ground if there are values `Y' and `Z' that unify with `X',
but which do not unify with each other.

   A non-solver type value will have inst `any' if it is constructed
using one or more inst `any' values.

   The built-in modes `ia' and `oa' are equivalent to `in(any)' and
`out(any)' respectively.


File: mercury_ref.info,  Node: Abstract solver type declarations,  Next: Solver type definitions,  Prev: The any inst,  Up: Solver types

16.2 Abstract solver type declarations
======================================

The type declarations

     :- solver type t1.
     :- solver type t2(T1, T2).

declare types `t1/0' and `t2/2' to be abstract solver types.  Abstract
solver type declarations are identical to ordinary abstract type
declarations except for the solver keyword.


File: mercury_ref.info,  Node: Solver type definitions,  Next: Implementing solver types,  Prev: Abstract solver type declarations,  Up: Solver types

16.3 Solver type definitions
============================

A solver type definition takes the following form:

     :- solver type solver_type
             where   representation   is representation_type,
                     ground           is ground_inst,
                     any              is any_inst,
                     constraint_store is mutable_decls,
                     equality         is equality_pred,
                     comparison       is comparison_pred.

   The `representation' attribute is mandatory `ground_inst' and
`any_inst' default to `ground', `mutable_decls' is either a single
mutable declaration (*note Module-local mutable variables::) or a comma
separated list of mutable declarations in brackets, the equality and
comparison attributes are optional (although a solver type without
equality would not be very useful), and attributes must appear in the
order shown.

   The `representation_type' is the type used to implement the
`solver_type'.  A two-tier scheme of this kind is necessary for a
number of reasons, including
   * a semantic gap is necessary to accommodate the fact that non-ground
     `solver_type' values may be represented by ground
     `representation_type' values (in the context of the corresponding
     constraint solver state);

   * this approach greatly simplifies the definition of equality and
     comparison predicates for the `solver_type'.

   The `ground_inst' is the inst associated with `representation_type'
values denoting `ground' `solver_type' values.

   The `any_inst' is the inst associated with `representation_type'
values denoting `any' `solver_type' values.

   The compiler constructs four impure functions for converting between
`solver_type' values and `representation_type' values (`name' is the
function symbol used to name `solver_type' and `arity' is the number of
type parameters it takes):

     :- impure func 'representation of ground name/arity'(solver_type) =
                             representation_type.
     :-        mode 'representation of ground name/arity'(in) =
                             out(ground_inst) is det.

     :- impure func 'representation of any name/arity'(solver_type) =
                             representation_type.
     :-        mode 'representation of any name/arity'(in(any)) =
                             out(any_inst) is det.

     :- impure func 'representation to ground name/arity'(representation_type) =
                             solver_type.
     :-        mode 'representation to ground name/arity'(in(ground_inst)) =
                             out is det.

     :- impure func 'representation to any name/arity'(representation_type) =
                             solver_type.
     :-        mode 'representation to any name/arity'(in(any_inst)) =
                             out(any) is det.

   These functions are impure because of the semantic gap issue
mentioned above.

   These functions are constructed in-line as part of a source-to-source
transformation, hence it is an error to define a solver type in the
interface section of a module.

   If `solver_type' is exported then it is a requirement that
`representation_type', `initialisation_pred', and, if specified,
`equality_pred' and `comparison_pred' are also exported from the same
module.

   If `equality_pred' is not specified then the compiler will generate
an equality predicate that throws an exception of type
`exception.software_error/0' when called.

   Likewise, if `comparison_pred' is not specified then the compiler
will generate a comparison predicate that throws an exception of type
`exception.software_error/0' when called.

   If provided, any mutable declarations given for the
`constraint_store' attribute are equivalent to separate mutable
declarations; their association with the solver type is for the
purposes of documentation.  That is,

     :- solver type t
     	where ... constraint_store is [ mutable(a, int, 42, ground, []),
     					mutable(b, string, "Hi", ground, [])
     		  ],
     	      ...

is equivalent to

     :- solver type t
     	where ...
     :- mutable(a, int, 42, ground, []).
     :- mutable(b, string, "Hi", ground, []).


File: mercury_ref.info,  Node: Implementing solver types,  Next: Solver types and negated contexts,  Prev: Solver type definitions,  Up: Solver types

16.4 Implementing solver types
==============================

A solver type is an abstraction, implemented using a combination of a
private representation type and a constraint store.

   The constraint store is an (impure) piece of state used to keep
track of the extant constraints on variables of the solver type.  This
will typically be implemented using foreign code.

   It is important that changes to the constraint store are properly
trailed (see *note Trailing::) so that changes can be undone on
backtracking.

   The solver type implementation should provide functions and
predicates to
   * construct and deconstruct solver type values,

   * to place constraints on solver type variables,

   * to convert `any' solver type variables to `ground' if possible
     (this is obviously an impure operation -- see *note Impurity::),

   * to convert solver type values to non-solver type values (again,
     this is impure and requires the argument solver type values be
     sufficiently ground),

   * to ask questions about the extant constraints on solver type
     variables without constraining them further (this too is impure
     because the set of constraints on a variable may change during
     execution of the program).


File: mercury_ref.info,  Node: Solver types and negated contexts,  Prev: Implementing solver types,  Up: Solver types

16.5 Solver types and negated contexts
======================================

Mercury's negation and if-then-else goals (and hence also inequalities
and universal quantifications) are implemented using _negation as
failure_, meaning that the failure to find a proof of one statement is
regarded as a proof of its negation.  Negation as failure is sound
provided that no non-local variable becomes further bound during the
execution of a goal which may be negated.  This includes negated goals
themselves, as well as the conditions of if-then-elses, which are
negated iff they fail without producing any solution, and the bodies of
pred or func expressions, which may be called or applied in one of the
other contexts, or indeed in another pred or func expression.

   Mercury checks that any solver variables that are used in the above
contexts are used in such a way that negation as failure remains sound.
In the case of negation and if-then-else goals, if any non-local solver
type variable or higher order variable with inst `any' is used in a
negated context, the goal must be placed inside a `promise_pure',
`promise_semipure', or `promise_impure' scope.  The first two promises
assert that (among other things) no solver variable becomes further
bound in the negated context.  The third promise makes the weaker
assertion that the goal satisfies the requirements of all impure goals
(namely, that it doesn't interfere with the semantics of other pure
goals).

   In the case of pred and func expressions, Mercury allows three
possibilities.  The higher order value may be considered `ground',
which means that all non-local variables used in the body of the
expression (including those with other higher order values) must
themselves be ground.  Higher order values that are ground can be
safely called or applied in any context, including negated contexts,
since none of their (ground) non-local variables can become further
bound by doing so.  Alternatively, the higher order value may be
considered to have inst `any', which allows non-local variables used in
the body of the expression to have inst `any'.  Calling or applying
these values _may_ further bind non-local variables, so if this occurs
in a negated context then, as in the case of solver variables, a
promise will be required around the negation or if-then-else.

   Pred and func expressions with inst `any' are written using
`any_pred' and `any_func' in place of `pred' and `func', respectively.

   The third possibility is that the higher order value can be given an
impure type (*note Higher-order impurity::).


File: mercury_ref.info,  Node: Trace goals,  Next: Pragmas,  Prev: Solver types,  Up: Top

17 Trace goals
**************

Sometimes, programmers find themselves needing to perform some
side-effects in the middle of declarative code.  One example is an
operation that takes so long that users may think the program has gone
into an infinite loop: periodically printing a progress message can
give them reassurance.  Another example is a program that is too
long-running for its behaviour to be analyzed via debuggers and too
complex for analysis via profilers; a programmable logging facility
generating data for analysis by a specially-written program may be the
best option.  However, inserting arbitrary side effects into
declarative code is against the spirit of Mercury.  Trace goals exist
to provide a mechanism to code these side effects in a disciplined
fashion.

   The format of trace goals is `trace PARAMS GOAL'.  GOAL must be a
valid goal; PARAMS must be a valid list of one or more trace parameters.
The following example shows all four of the available kinds of
parameters: `compile_time', `run_time', `io' and `state'.  (In
practice, it is far more typical to have just one parameter, `io'.)

     :- mutable(logging_level, int, 0, ground, []).

     :- pred time_consuming_task(data::in, result::out) is det.

     time_consuming_task(In, Out) :-
             trace [
                     compile_time(flag("do_logging") or grade(debug)),
                     run_time(env("VERBOSE")),
                     io(!IO),
                     state(logging_level, !LoggingLevel)
             ] (
                     io.write_string("Time_consuming_task start\n", !IO),
                     ( !.LoggingLevel > 1 ->
                             io.write_string("Input is ", !IO),
                             io.write(In, !IO),
                             io.nl(!IO)
                     ;
                             true
                     )
             ),
             ...
             % perform the actual task

   The `compile_time' parameter says under what circumstances the trace
goal should be included in the executable program.  In the example, at
least one of two conditions has to be true: either this module has to
be compiled with the option `--trace-flag=do_logging', or it has to be
compiled in a debugging grade.

   In general, the single argument of the `compile_time' function symbol
is a boolean expression of primitive compile-time conditions. Valid
boolean operators in these expressions are `and', `or' and `not'.
There are three kinds of primitive compile-time conditions.  The first
has the form `flag(FLAGNAME)', where FLAGNAME is an arbitrary name
picked by the programmer; this condition is true if the module is
compiled with the option `--trace-flag=FLAGNAME'.  The second has the
form `tracelevel(shallow)', or `tracelevel(deep)'; this condition is
true (irrespective of grade) if the module is compiled with at least
the specified trace level.  The third has the form `grade(GradeTest)'.
The supported `GradeTests's and their meanings are as follows.

`debug'
     True if the module is compiled with execution tracing enabled.

`ssdebug'
     True if the module is compiled with source-to-source debugging
     enabled.

`prof'
     True if the module is compiled with non-deep profiling enabled.

`profdeep'
     True if the module is compiled with deep profiling enabled.

`par'
     True if the module is compiled with parallel execution enabled.

`trail'
     True if the module is compiled with trailing enabled.

`rbmm'
     True if the module is compiled with region based memory management
     enabled.

`llds'
     True if the module is compiled with -highlevel-code disabled.

`mlds'
     True if the module is compiled with -highlevel-code enabled.

`c'
     True if the target language of the compilation is C.

`il'
     True if the target language of the compilation is MS IL.

`csharp'
     True if the target language of the compilation is C#.

`java'
     True if the target language of the compilation is Java.

`erlang'
     True if the target language of the compilation is Erlang.

   The `run_time' parameter says under what circumstances the trace
goal, if included in the executable program, should actually be
executed.  In this case, the environment variable `VERBOSE' has be to
set when the program starts execution.  (It doesn't matter what value
it is set to.)

   In general, the single argument of the `run_time' function symbol is
a boolean expression of primitive run-time conditions. Valid boolean
operators in these expressions are `and', `or' and `not'.  There is
just one primitive run-time condition.  It has the form
`env(ENVVARNAME)', this condition is true if the environment variable
ENVVARNAME exists when the program starts execution.

   The `compile_time' and `run_time' parameters may not appear in the
parameter list more than once; programmers who want more than one
condition have to specify how (with what boolean operators) their
values should be combined.  However, it is ok for them not to appear in
the parameter list at all.  If there is no `compile_time' parameter,
the trace goal is always compiled into the executable; if there is no
`run_time' parameter, the trace goal is always executed (if it is
compiled into the executable).

   Since the trace goal may end up either not compiled into the
executable or just not executed, it cannot bind any variables that
occur in the surrounding code.  (If it were allowed to bind such
variables, then those variables would stay unbound if either the
compile time or the run time condition were false.)  This greatly
restricts what trace goals can do.

   The usual reason for including a trace goal in a procedure body is
to perform some I/O, which requires access to the I/O state.  The `io'
parameter supplies this access.  Its argument must be the name of a
state variable prefixed by `!'; by convention, it is usually `!IO'.
The language implementation supplies the initial unique value of the
I/O state as the value of `!.IO' at the start of the trace goal; it
requires the trace goal to give back the final unique value of the I/O
state as the value of `!.IO' current at the end of the trace goal.

   Note that trace goals that wish to do I/O must include this
parameter in their parameter list _even if_ the surrounding code
already has access to an I/O state.  This is because otherwise, doing
any I/O inside the trace goal would destroy the value of the current
I/O state, changing the instantiation state of the variable holding it,
and trace goals are not allowed to do that.

   The `io' parameter may appear in the parameter list at most once,
since it doesn't make sense to have two copies of the I/O state
available to the trace goal.

   Besides doing I/O, trace goals may read and possibly write the
values of mutable variables.  Each mutable the trace goal wants access
to should be listed in its own `state' parameter (which may therefore
appear in the parameter list more than once).  Each `state' parameter
has two arguments: the first gives the name of the mutable, while the
second must be the name of a state variable prefixed by `!', e.g.
`!LoggingLevel'.  The language implementation supplies the initial
value of the mutable as the value of (in this case) `!.LoggingLevel' at
the start of the trace goal; at the end of the trace goal, it puts the
value of `!.LoggingLevel' current then back into the mutable.

   The intention here is that trace goals should be able to access
mutables that give them information about the parameters within which
they should operate.  The ability of trace goals to actually _update_
the values of mutables is intended to allow the implementation of trace
goals whose actions depend on the actions executed by previous trace
goals.  For example, a trace goal could test whether the current input
value is the same as the previous input value, and if it is, then it
can say so instead of printing the value out again.  Another
possibility is a progress message which is printed not for every item
processed, but for every 1000th item, reassuring users without
overwhelming them with a deluge of output.

   This kind of code is the _only_ intended use of this ability.  Any
program in which the value of a mutable set by a trace goal is
inspected by code that is not itself within a trace goal is explicitly
violating the intended uses of trace goals.  Only the difficulty of
implementing the required global program analysis prevents the language
design from outlawing such programs in the first place.

   The compiler will not delete trace goals from the bodies of the
procedures containing them.  However, trace goals inside a procedure
don't prevent calls to that procedure from being optimized away, if
such optimization is otherwise possible.  (There is no point in
debugging or logging operations that don't actually occur.)  In their
effect on program optimizations, trace goals function as a kind of
impure code, but one with an implicit promise_pure around the clause in
which they occur.


File: mercury_ref.info,  Node: Pragmas,  Next: Implementation-dependent extensions,  Prev: Trace goals,  Up: Top

18 Pragmas
**********

The pragma declarations described below are a standard part of the
Mercury language, as are the pragmas for controlling the foreign
language interface (*note Foreign language interface::) and impurity
(*note Impurity::).  As an extension, implementations may also choose
to support additional pragmas with implementation-dependent semantics
(*note Implementation-dependent extensions::).

* Menu:

* Inlining::                    Pragmas can be used to suggest or prevent
                                procedure inlining.
* Type specialization::         Pragmas can be used to produce specialized
                                versions of polymorphic procedures.
* Obsolescence::                Library developers can declare old versions
                                of predicates or functions to be obsolete.
* No determinism warnings::     Pragmas can be used to suppress warnings
                                about too loose determinism declarations.
* Source file name::            The `source_file' pragma and
                                `#LINE' directives provide support
                                for preprocessors and other tools that
                                generate Mercury code.


File: mercury_ref.info,  Node: Inlining,  Next: Type specialization,  Up: Pragmas

18.1 Inlining
=============

A declaration of the form

     :- pragma inline(NAME/ARITY).

is a hint to the compiler that all calls to the predicate(s) or
function(s) with name NAME and arity ARITY should be inlined.

   The current Mercury implementation is smart enough to inline simple
predicates even without this hint.

   A declaration of the form

     :- pragma no_inline(NAME/ARITY).

ensures the compiler will not inline this predicate.  This may be used
simply for performance concerns (inlining can cause unwanted code bloat
in some cases) or to prevent possibly dangerous inlining when using
low-level C code.


File: mercury_ref.info,  Node: Type specialization,  Next: Obsolescence,  Prev: Inlining,  Up: Pragmas

18.2 Type specialization
========================

The overhead of polymorphism can in some cases be significant,
especially where polymorphic predicates make heavy use of class method
calls or the built-in unification and comparison routines. To avoid
this, the programmer can suggest to the compiler that a specialized
version of a procedure should be created for a specific set of argument
types.

* Menu:

* Syntax and semantics of type specialization pragmas::
* When to use type specialization::
* Implementation specific details::


File: mercury_ref.info,  Node: Syntax and semantics of type specialization pragmas,  Next: When to use type specialization,  Up: Type specialization

18.2.1 Syntax and semantics of type specialization pragmas
----------------------------------------------------------

A declaration of the form

     :- pragma type_spec(NAME/ARITY, SUBST).
     :- pragma type_spec(NAME(MODES), SUBST).

suggests to the compiler that a specialized version of predicate(s) or
function(s) with name NAME and arity ARITY should be created with the
type substitution given by SUBST applied to the argument types. The
second form of the declaration only suggests specialization of the
specified mode of the predicate or function.

   The substitution is written as a conjunction of bindings of the form
`TYPEVAR = TYPE', for example `K = int' or `(K = int, V = list(int))'.

   The declarations

     :- pred map.lookup(map(K, V), K, V).
     :- pragma type_spec(map.lookup/3, K = int).

give a hint to the compiler that a version of `map.lookup/3' should be
created for integer keys.

   Implementations are free to ignore `pragma type_spec' declarations.
Implementations are also free to perform type specialization even in
the absence of any `pragma type_spec' declarations.


File: mercury_ref.info,  Node: When to use type specialization,  Next: Implementation specific details,  Prev: Syntax and semantics of type specialization pragmas,  Up: Type specialization

18.2.2 When to use type specialization
--------------------------------------

The set of types for which a predicate or function should be
specialized is best determined by profiling your application. Overuse
of type specialization will result in code bloat.

   Type specialization of predicates or functions which unify or
compare polymorphic variables is most effective when the specialized
types are built-in types such as `int', `float' and `string', or
enumeration types, since their unification and comparison procedures
are simple and can be inlined.

   Predicates or functions which make use of type class method calls
may also be candidates for specialization. Again, this is most effective
when the called type class methods are simple enough to be inlined.


File: mercury_ref.info,  Node: Implementation specific details,  Prev: When to use type specialization,  Up: Type specialization

18.2.3 Implementation specific details
--------------------------------------

The University of Melbourne Mercury compiler performs user-requested
type specializations when invoked with
`--user-guided-type-specialization', which is enabled at optimization
level `-O2' or higher.  However, for the Java back-end, user-requested
type specializations are ignored.


File: mercury_ref.info,  Node: Obsolescence,  Next: No determinism warnings,  Prev: Type specialization,  Up: Pragmas

18.3 Obsolescence
=================

A declaration of the form

     :- pragma obsolete(NAME/ARITY).

declares that the predicate(s) or function(s) with name NAME and arity
ARITY are "obsolete": it instructs the compiler to issue a warning
whenever the named predicate(s) or function(s) are used.

   `pragma obsolete' declarations are intended for use by library
developers, to allow gradual (rather than abrupt) evolution of library
interfaces.  If a library developer changes the interface of a library
predicate, they should leave the old version of that predicate in the
library, but mark it as obsolete using a `pragma obsolete' declaration,
and document how library users should modify their code to suit the new
interface.  The users of the library will then get a warning if they
use obsolete features, and can consult the library documentation to
determine how to fix their code.  Eventually, when the library
developer deems that users have had sufficient warning, they can remove
the old version entirely.


File: mercury_ref.info,  Node: No determinism warnings,  Next: Source file name,  Prev: Obsolescence,  Up: Pragmas

18.4 No determinism warnings
============================

A declaration of the form

     :- pragma no_determinism_warning(NAME/ARITY).

tells the compiler not to generate any warnings that the determinism
declarations of procedures of the predicate or function with name NAME
and arity ARITY are not as tight as they could be.

   `pragma no_determinism_warning' declarations are intended for use in
situations in which the code of a predicate has one determinism, but
the declared determinism of the procedure must be looser due to some
outside requirement.  One such situation is when a set of procedures
are all possible values of the same higher order variable, which
requires them to have the same argument types, modes, and determinisms.
If (say) most of the procedures are det but some are erroneous (that
is, they always throws an exception), the procedures that are declared
det but whose bodies have determinism erroneous will get a warning
saying their determinism declaration could be tighter, unless the
programmer specifies this pragma for them.


File: mercury_ref.info,  Node: Source file name,  Prev: No determinism warnings,  Up: Pragmas

18.5 Source file name
=====================

The `source_file' pragma and `#LINE' directives provide support for
preprocessors and other tools that generate Mercury code.  The tool can
insert these directives into the generated Mercury code to allow the
Mercury compiler to report diagnostics (error and warning messages) at
the original source code location, rather than at the location in the
automatically generated Mercury code.

   A `source_file' pragma is a declaration of the form

     :- pragma source_file(NAME).

where NAME is a string that specifies the name of the source file.

   For example, if a preprocessor generated a file `foo.m' based on a
input file `foo.m.in', and it copied lines 20, 30, and 31 from
`foo.m.in', the following directives would ensure that any error or
warnings for those lines copied from `foo.m' were reported at their
original source locations in `foo.m.in'.

     :- module foo.
     :- pragma source_file("foo.m.in").
     #20
     % this line comes from line 20 of foo.m
     #30
     % this line comes from line 30 of foo.m
     % this line comes from line 31 of foo.m
     :- pragma source_file("foo.m").
     #10
     % this automatically generated line is line 10 of foo.m

   Note that if a generated file contains some text which is copied
from a source file, and some which is automatically generated, it is a
good idea to use `pragma source_file' and `#LINE' directives to reset
the source file name and line number to point back to the generated
file for the automatically generated text, as in the above example.


File: mercury_ref.info,  Node: Implementation-dependent extensions,  Next: Bibliography,  Prev: Pragmas,  Up: Top

19 Implementation-dependent extensions
**************************************

The University of Melbourne Mercury implementation supports the
following extensions to the Mercury language:

* Menu:

* Fact tables::                 Support for very large tables of facts.
* Tabled evaluation::           Support for automatically recording previously
                                calculated results and detecting or avoiding
                                certain kinds of infinite loops.
* Termination analysis::        Support for automatic proofs of termination.
* Feature sets::                Support for checking that optional features of
                                the implementation are supported at compile
                                time.
* Trailing::                    Undoing side-effects on backtracking.


File: mercury_ref.info,  Node: Fact tables,  Next: Tabled evaluation,  Up: Implementation-dependent extensions

19.1 Fact tables
================

Large tables of facts can be compiled using a different algorithm that
is more efficient and produces more efficient code.

   A declaration of the form

     :- pragma fact_table(NAME/ARITY, FILENAME).

tells the compiler that the predicate or function with name NAME and
arity ARITY is defined by a set of facts in an external file FILENAME.
Defining large tables of facts in this way allows the compiler to use a
more efficient algorithm for compiling them.  This algorithm uses less
memory than would normally be required to compile the facts so much
larger tables are possible.

   Each mode is indexed on all its input arguments so the compiler can
produce very efficient code using this technique.

   In the current implementation, the table of facts is compiled into a
separate C file named `FILENAME.c'.  The compiler will automatically
generate the correct dependencies for this file when the command `mmake
MAIN_MODULE.depend' is invoked.  This ensures that the C file will be
compiled to `FILENAME.o' and then linked with the other object files
when `mmake MAIN_MODULE' is invoked.

   The main limitation of the `fact_table' pragma is that in the
current implementation, predicates or functions defined as fact tables
can only have arguments of types `string', `int' or `float'.

   Another limitation is that the `--high-level-code' back-end does not
support `pragma fact_table' for procedures with determinism `nondet' or
`multi'.


File: mercury_ref.info,  Node: Tabled evaluation,  Next: Termination analysis,  Prev: Fact tables,  Up: Implementation-dependent extensions

19.2 Tabled evaluation
======================

(Note: "Tabled evaluation" has no relation to the "fact tables"
described above.)

   Ordinarily, the results of each procedure call are not recorded; if
the same procedure is called with the same arguments, then the
answer(s) must be recomputed again.  For some procedures, this
recomputation can be very wasteful.

   With tabled evaluation, the implementation keeps a table containing
the previously computed results of the specified procedure; this table
is sometimes called the memo table (since it "remembers" previous
answers).  At each procedure call, the implementation will search the
memo table to check whether the answer(s) have already been computed,
and if so, the answers will be returned directly from the memo table
rather than being recomputed.  This can result in much faster
execution, at the cost of additional space to record answers in the
table.

   The implementation can also check at runtime for the situation where
a procedure calls itself recursively with the same arguments, which
would normally result in a infinite loop; if this situation is
encountered, it can (at the programmer's option) either throw an
exception, or avoid the infinite loop by computing solutions using a
"minimal model" semantics.  (Specifically, the minimal model computed
by our implementation is the perfect model.)

   The current Mercury implementation supports three different pragmas
for tabling, to cover these three cases: `loop_check', `memo', and
`minimal_model'.  The `loop_check' pragma asks only for loop checking.
With this pragma, the memo table will map each distinct set of input
arguments only to a single boolean saying whether a call with those
arguments is currently active or not; the pragma's only effect is to
cause the predicate to throw an exception if this boolean says that the
current call has the same arguments as one of its ancestors, which
indicates an infinite recursive loop.  The `memo' pragma asks for both
loop checking and memoization.  With this pragma, the memo table will
map each distinct set of input arguments either to the set of results
computed previously for those arguments, or to an indication that the
call is still active and thus those results are still being computed.
This predicate will thus look for infinite recursive loops (and throw
an exception if and when it finds one) but it will also record all its
solutions in the memo table, and will avoid recomputing solutions that
are already available in the memo table.  The `minimal_model' pragma
asks for the computation of a "minimal model" semantics.  These differ
from the `memo' pragma in that the detection of what appears to be an
infinite recursive loop is not fatal.  The implementation will consider
the apparently infinitely recursive calls to fail if the call concerned
has no way of computing any solutions it hasn't already computed and
recorded, and it does have such a way, then it switches the execution
to explore those ways before coming back to the apparently infinitely
recursive call.

   The syntax for each of these declarations is

     :- pragma memo(NAME/ARITY).
     :- pragma memo(NAME/ARITY, [LIST OF TABLING ATTRIBUTES]).
     :- pragma loop_check(NAME/ARITY).
     :- pragma loop_check(NAME/ARITY, [LIST OF TABLING ATTRIBUTES]).
     :- pragma minimal_model(NAME/ARITY).
     :- pragma minimal_model(NAME/ARITY, [LIST OF TABLING ATTRIBUTES]).

where NAME/ARITY specifies the predicate or function to which the
declaration applies.  The declaration applies to all modes of the
predicate and/or function named.  At most one of these declarations may
be specified for any given predicate or function.

   Programmers can also request the application of tabling only to one
particular mode of a predicate or function, via declarations such as
these:

     :- pragma memo(NAME(in, in, out)).
     :- pragma memo(NAME(in, in, out), [LIST OF TABLING ATTRIBUTES]).
     :- pragma loop_check(NAME(in, out)).
     :- pragma loop_check(NAME(in, out), [LIST OF TABLING ATTRIBUTES]).
     :- pragma minimal_model(NAME(in, in, out, out)).
     :- pragma minimal_model(NAME(in, in, out, out), [LIST OF TABLING ATTRIBUTES]).

   Because all variants of tabling record the values of input arguments,
and all except `loop_check' also record the values of output arguments,
you cannot apply any of these pragmas to procedures whose arguments'
modes include any unique component.

   Tabled evaluation of a predicate or function that has an argument
whose type is a foreign type will result in a run-time error unless the
foreign type is one for which the `can_pass_as_mercury_type' and
`stable' assertions have been made (*note Using foreign types from
Mercury::).

   The optional list of attributes allows programmers to control some
aspects of the management of the memo table(s) of the procedure(s)
affected by the pragma.

   The `allow_reset' attribute asks the compiler to define a predicate
that, when called, resets the memo table.  The name of this predicate
will be "table_reset_for", followed by the name of the tabled
predicate, followed by its arity, and (if the predicate has more than
one mode) by the mode number (the first declared mode is mode 0, the
second is mode 1, and so on).  These three or four components are
separated by underscores.  The reset predicate takes a di/uo pair of
I/O states as arguments.  The presence of these I/O state arguments in
the reset predicate, and the fact that tabled predicates cannot have
unique arguments together imply that a memo table cannot be reset while
a call using that memo table is active.

   The `statistics' attribute asks the compiler to define a predicate
that, when called, returns statistics about the memo table.  The name
of this predicate will be "table_statistics_for", followed by the name
of the tabled predicate, followed by its arity, and (if the predicate
has more than one mode) by the mode number (the first declared mode is
mode 0, the second is mode 1, and so on).  These three or four
components are separated by underscores.  The statistics predicate
takes three arguments.  The second and third are a di/uo pair of I/O
states, while the first is an output argument that contains information
about accesses to and modifications of the procedure's memo table, both
since the creation of the table, and since the last call to this
predicate.  The type of this argument is defined in the file
table_builtin.m in the Mercury standard library.  That module also
contains a predicate for printing out this information in a
programmer-friendly format.

   The remaining two attributes, `fast_loose' and `specified', control
how arguments are looked up in the memo table.  The default
implementation looks up the _value_ of each input argument, and thus
requires time proportional to the number of function symbols in the
input arguments.  This is the only implementation allowed for minimal
model tabling, but for predicates tabled with the `loop_check' and
`memo' pragmas, programmers can also choose some other tabling methods.

   The `fast_loose' attribute asks the compiler to generate code that
looks up only the _address_ of each input argument in the memo table,
which means that the time required is linear only in the _number_ of
input arguments, not their _size_.  The tradeoff is that `fast_loose'
does not recognize calls as duplicates if they involve input arguments
that are logically equal but are stored at different locations in
memory.  The following declaration calls for this variant of tabling.

     :- pragma memo(NAME(in, in, in, out),
     	[allow_reset, statistics, fast_loose]).

   The `specified' attribute allows programmers to choose individually,
for each input argument, whether that argument should be looked up in
the memo table by value or by address, or whether it should be looked
up at all:

     :- pragma memo(NAME(in, in, in, out), [allow_reset, statistics,
     	specified([value, addr, promise_implied, output])]).

   The `specified' attribute should have an argument which is a list,
and this list should contain one element for each argument of the
predicate or function concerned (if a function, the last element is for
the return value).  For output arguments, the list element should be
`output'.  For input arguments, the list element may be `value', `addr'
or `promise_implied'.  The first calls for tabling the argument by
value, the second calls for tabling the argument by address, and the
third calls for not tabling the argument at all.  This last course of
action promises that any two calls that agree on the values of the
value-tabled input arguments and on the addresses of the address-tabled
input arguments will behave the same regardless of the values of the
untabled input arguments.  In most cases, this will mean that the
values of the untabled arguments are implied by the values of the
value-tabled arguments and the addresses of the address-tabled
arguments, though the promise can also be fulfilled if the table
predicate or function does not actually use the untabled argument for
computing any of its output.  (It is ok for it to use the untabled
argument to decide what exception to throw.)

   If the tabled predicate or function has only one mode, then this
declaration can also be specified without giving the argument modes:

     :- pragma memo(NAME/ARITY, [allow_reset, statistics,
     	specified([value, addr, promise_implied, output])]).

   Note that a `pragma minimal_model' declaration changes the
declarative semantics of the specified predicate or function: instead
of using the completion of the clauses as the basis for the semantics,
as is normally the case in Mercury, the declarative semantics that is
used is a "minimal model" semantics, specifically, the perfect model
semantics.  Anything which is true or false in the completion semantics
is also true or false (respectively) in the perfect model semantics,
but there are goals for which the perfect model specifies that the
result is true or false, whereas the completion semantics leaves the
result unspecified.  For these goals, the usual Mercury semantics
requires the implementation to either loop or report an error message,
but the perfect model semantics requires a particular answer to be
returned.  In particular, the perfect model semantics says that any
call that is not true in _all_ models is false.

   Programmers should therefore use a `pragma minimal_model' declaration
only in cases where their intended interpretation for a procedure
coincides with the perfect model for that procedure.  Fortunately,
however, this is usually what programmers intend.

   For more information on tabling, see K. Sagonas's PhD thesis `The
SLG-WAM: A Search-Efficient Engine for Well-Founded Evaluation of
Normal Logic Programs.' *Note [4]::.  The operational semantics of
procedures with a `pragma minimal_model' declaration corresponds to
what Sagonas calls "SLGd resolution".

   In the general case, the execution mechanism required by minimal
model tabling is quite complicated, requiring the ability to delay
goals and then wake them up again.  The Mercury implementation uses a
technique based on copying relevant parts of the stack to the heap when
delaying goals.  It is described in `Tabling in Mercury: design and
implementation' by Z. Somogyi and K. Sagonas, Proceedings of the Eight
International Symposium on Practical Aspects of Declarative Languages.

   *Please note:* the current implementation of tabling does not support
all the possible compilation grades (see the "Compilation model
options" section of the Mercury User's Guide) allowed by the Mercury
implementation.  In particular, minimal model tabling is incompatible
with high level code, the use of trailing, and accurate garbage
collection.


File: mercury_ref.info,  Node: Termination analysis,  Next: Feature sets,  Prev: Tabled evaluation,  Up: Implementation-dependent extensions

19.3 Termination analysis
=========================

The compiler includes a termination analyser which can be used to prove
termination of predicates and functions.  Details of the analysis is
available in "Termination Analysis for Mercury" by Chris Speirs, Zoltan
Somogyi and Harald Sondergaard.  *Note [1]::.

   The analysis is based around an algorithm proposed by Gerhard Groger
and Lutz Plumer in their paper "Handling of mutual recursion in
automatic termination proofs for logic programs." *Note [2]::.

   For an introduction to termination analysis for logic programs,
please refer to "Termination Analysis for Logic Programs" by Chris
Speirs.  *Note [3]::.

   Information about the termination properties of a predicate or
function can be given to the compiler.  Pragmas are also available to
require the compiler to prove termination of a given predicate or
function, or to give an error message if it cannot do so.

   The analyser is enabled by the option `--enable-termination', which
can be abbreviated to `--enable-term'.  When termination analysis is
enabled, any predicates or functions with a `check_termination' pragma
defined on them will have their termination checked, and if termination
cannot be proved, the compiler will emit an error message detailing the
reason that termination could not be proved.

   The option `--check-termination', which may be abbreviated to
`--check-term' or `--chk-term', forces the compiler to check the
termination of all predicates in the module.  It is common for the
compiler to be unable to prove termination of some predicates and
functions because they call other predicates which could not be proved
to terminate or because they use language features (such as higher
order calls) which cannot be usefully analysed.  In this case, the
compiler only emits a warning for these predicates and functions if the
`--verbose-check-termination' option is enabled.  For every predicate
or function that the compiler cannot prove the termination of, a
warning message is emitted, but compilation continues.  The
`--check-termination' option implies the `--enable-termination' option.

   The accuracy of the termination analysis is substantially degraded if
intermodule optimization is not enabled.  Unless intermodule
optimization is enabled, the compiler must assume that any imported
predicate may not terminate.

   By default, the compiler assumes that a procedure defined using the
foreign language interface will terminate for all input if it does not
call Mercury.  If it does call Mercury then by default the compiler
will assume that it may not terminate.

   The foreign code attributes `terminates'/`does_not_terminate' may be
used to force the compiler to treat a foreign_proc as
terminating/non-terminating irrespective of whether it calls Mercury.
As a matter of style, it is preferable to use foreign code attributes
for foreign_procs rather than the termination pragmas described below.

   The following declarations can be used to inform the compiler of the
termination properties of a predicate or function.

     :- pragma terminates(NAME/ARITY).

   This declaration may be used to inform the compiler that this
predicate or function is guaranteed to terminate for any input.  This
is useful when the compiler cannot prove termination of some predicates
or functions which are in turn preventing the compiler from proving
termination of other predicates or functions.  This declaration affects
not only the predicate specified but also any other predicates that are
mutually recursive with it.

     :- pragma does_not_terminate(NAME/ARITY).

   This declaration may be used to inform the compiler that this
predicate may not terminate.  This declaration affects not only the
predicate specified but also any other predicates that are mutually
recursive with it.

     :- pragma check_termination(NAME/ARITY).

   This pragma forces the compiler to prove termination of this
predicate.  If it cannot prove the termination of the specified
predicate or function then the compiler will quit with an error message.


File: mercury_ref.info,  Node: Feature sets,  Next: Trailing,  Prev: Termination analysis,  Up: Implementation-dependent extensions

19.4 Feature sets
=================

The University of Melbourne Mercury implementation supports a number of
optional compilation model features, such as *note Trailing:: or *note
Tabled evaluation::.  Feature sets allow the programmer to assert that
a module requires the presence of one or more optional features in the
compilation model.  These assertions can be made use a `pragma
require_feature_set' declaration.

   The `require_feature_set' pragma declaration has the following form:
     :- pragma require_feature_set(FEATURES).

   where `Features' is a (possibly empty) list of features.

   The supported features are:
`concurrency'
     This specifies that the compilation model must support concurrent
     execution of multiple threads.

`single_prec_float'
     This specifies that the compilation model must use single
     precision floats.  This feature cannot be specified together with
     the `double_prec_float' feature.

`double_prec_float',
     This feature specifies that the compilation model must use double
     precision floats.  This feature cannot be specified together with
     the `single_prec_float' feature.

`memo'
     This feature specifies that the compilation model must support
     memoisation (see *note Tabled evaluation::).

`parallel_conj'
     This feature specifies that the compilation model must support
     parallel execution of conjunctions.  This feature cannot be
     specified together with the `trailing' feature.

`trailing'
     This feature specifies that the compilation model must support
     trailing, see *note Trailing::.  This feature cannot be specified
     together with the `parallel_conj' feature.

`strict_sequential'
     This feature specifies that a semantics that is equivalent to the
     strict sequential operational semantics must be used.

`conservative_gc'
     This feature specifies that a module requires conservative garbage
     collection.  This feature is only checked when using the C backends
     It is ignored by the non-C backends.


   When a module containing a `pragma require_feature_set' declaration
is compiled, the implementation checks to see that the specified
features are supported by the compilation model.  It emits an error if
they are not.

   A `pragma require_feature_set' may only occur in the implementation
section of a module.

   A `pragma require_feature_set' affects only the module in which it
occurs; in particular it does not affect any sub-modules

   If a module contains multiple `pragma require_feature_set'
declarations then the implementation should emit an error if any of
them specifies a feature that is not supported by the compilation model.


File: mercury_ref.info,  Node: Trailing,  Prev: Feature sets,  Up: Implementation-dependent extensions

19.5 Trailing
=============

In certain compilation grades (see the "Compilation model options"
section of the Mercury User's Guide), the University of Melbourne
Mercury implementation supports trailing.  Trailing is a means of
having side-effects, such as destructive updates to data structures,
undone on backtracking.  The basic idea is that during forward
execution, whenever you perform a destructive modification to a data
structure that may still be live on backtracking, you should record
whatever information is necessary to restore it on a stack-like data
structure called the "trail".  Then, if a computation fails, and
execution backtracks to before those updates were performed, the
Mercury runtime engine will traverse the trail back to the most recent
choice point, undoing all those updates.

   The interface used is a set of C functions (which are actually
implemented as macros) and types.  Typically these will be called from
C code within `pragma foreign_proc' or `pragma foreign_code'
declarations in Mercury code.

   For an example of the use of this interface, see the module
`extras/trailed_update/tr_array.m' in the Mercury extras distribution.

* Menu:

* Choice points::
* Value trailing::
* Function trailing::
* Delayed goals and floundering::
* Avoiding redundant trailing::


File: mercury_ref.info,  Node: Choice points,  Next: Value trailing,  Up: Trailing

19.5.1 Choice points
--------------------

A "choice point" is a point in the computation to which execution might
backtrack when a goal fails or throws an exception.  The "current"
choice point is the one that was most recently encountered; that is
also the one to which execution will branch if the current computation
fails.

   When you trail an update, the Mercury engine will ensure that if
execution ever backtracks to the choice point that was current at the
time of trailing, then the update will be undone.

   If the Mercury compiler determines that it will never need to
backtrack to a particular choice point, then it will "prune" away that
choice point.  If a choice point is pruned, the trail entries for those
updates will not necessarily be discarded, because in general they may
still be necessary in case we backtrack to a prior choice point.


File: mercury_ref.info,  Node: Value trailing,  Next: Function trailing,  Prev: Choice points,  Up: Trailing

19.5.2 Value trailing
---------------------

The simplest form of trailing is value trailing.  This allows you to
trail updates to memory and have the Mercury runtime engine
automatically undo them on backtracking.

* `MR_trail_value()'
     Prototype:
          void MR_trail_value(MR_Word *ADDRESS, MR_Word VALUE);

     Ensures that if future execution backtracks to the current choice
     point, then VALUE will be placed in ADDRESS.

* `MR_trail_current_value()'
     Prototype:
          void MR_trail_current_value(MR_Word *ADDRESS);

     Ensures that if future execution backtracks to the current choice
     point, the value currently in ADDRESS will be restored.

     `MR_trail_current_value(ADDRESS)' is equivalent to
     `MR_trail_value(ADDRESS, *ADDRESS)'.


   Note that ADDRESS must be word aligned for both
`MR_trail_current_value()' and `MR_trail_value()'.  (The address of
Mercury data structures that have been passed to C via the foreign
language interface are guaranteed to be appropriately aligned.)


File: mercury_ref.info,  Node: Function trailing,  Next: Delayed goals and floundering,  Prev: Value trailing,  Up: Trailing

19.5.3 Function trailing
------------------------

For more complicated uses of trailing, you can store the address of a C
function on the trail and have the Mercury runtime call your function
back whenever future execution backtracks to the current choice point
or earlier, or whenever that choice point is pruned, because execution
commits to never backtracking over that point, or whenever that choice
point is garbage collected.

   Note the garbage collector in the current Mercury implementation
does not garbage-collect the trail; this case is mentioned only so that
we can cater for possible future extensions.

* `MR_trail_function()'
     Prototype:
          typedef enum {
                  MR_undo,
                  MR_exception,
                  MR_retry,
                  MR_commit,
                  MR_solve,
                  MR_gc
          } MR_untrail_reason;

          void MR_trail_function(
                  void (*UNTRAIL_FUNC)(void *, MR_untrail_reason),
                  void *VALUE
          );
     A call to `MR_trail_function(UNTRAIL_FUNC, VALUE)' adds an entry
     to the function trail.  The Mercury implementation ensures that if
     future execution ever backtracks to current choicepoint, or
     backtracks past the current choicepoint to some earlier
     choicepoint, then `(*UNTRAIL_FUNC)(VALUE, REASON)' will be called,
     where REASON will be `MR_undo' if the backtracking was due to a
     goal failing, `MR_exception' if the backtracking was due to a goal
     throwing an exception, or `MR_retry' if the backtracking was due
     to the use of the "retry" command in `mdb', the Mercury debugger,
     or any similar user request in a debugger.  The Mercury
     implementation also ensures that if the current choice point is
     pruned because execution commits to never backtracking to it, then
     `(*UNTRAIL_FUNC)(VALUE, MR_commit)' will be called.  It also
     ensures that if execution requires that the current goal be
     solvable, then `(*UNTRAIL_FUNC)(VALUE, MR_solve)' will be called.
     This happens in calls to `solutions/2', for example.  (`MR_commit'
     is used for "hard" commits, i.e. when we commit to a solution and
     prune away the alternative solutions; `MR_solve' is used for
     "soft" commits, i.e. when we must commit to a solution but do not
     prune away all the alternatives.)

     MR_gc is currently not used -- it is reserved for future use.


   Typically if the UNTRAIL_FUNC is called with REASON being `MR_undo',
`MR_exception', or `MR_retry', then it should undo the effects of the
update(s) specified by VALUE, and then free any resources associated
with that trail entry.  If it is called with REASON being `MR_commit'
or `MR_solve', then it should not undo the update(s); instead, it may
check for floundering (see the next section).  In the `MR_commit' case
it may, in some cases, be possible to also free resources associated
with the trail entry.  If it is called with anything else (such as
`MR_gc'), then it should probably abort execution with an error message.

   Note that the address of the C function passed as the first argument
of `MR_trail_function()' must be word aligned.


File: mercury_ref.info,  Node: Delayed goals and floundering,  Next: Avoiding redundant trailing,  Prev: Function trailing,  Up: Trailing

19.5.4 Delayed goals and floundering
------------------------------------

Another use for the function trail is check for floundering in the
presence of delayed goals.

   Often, when implementing certain kinds of constraint solvers, it may
not be possible to actually solve all of the constraints at the time
they are added.  Instead, it may be necessary to simply delay their
execution until a later time, in the hope the constraints may become
solvable when more information is available.  If you do implement a
constraint solver with these properties, then at certain points in the
computation -- for example, after executing a negated goal -- it is
important for the system to check that their are no outstanding delayed
goals which might cause failure, before execution commits to this
execution path.  If there are any such delayed goals, the computation
is said to "flounder".  If the check for floundering was omitted, then
it could lead to unsound behaviour,  such as a negation failing even
though logically speaking it ought to have succeeded.

   The check for floundering can be implemented using the function
trail, by simply calling `MR_trail_function()' to add a function trail
entry whenever you create a delayed goal, and putting the appropriate
check for floundering in the `MR_commit' and `MR_solve' cases of your
function.  The Mercury extras distribution includes an example of this:
see the `ML_var_untrail_func()' function in the file
`extras/trailed_update/var.m'.)  If your function does detect
floundering, then it should print an error message and then abort
execution.


File: mercury_ref.info,  Node: Avoiding redundant trailing,  Prev: Delayed goals and floundering,  Up: Trailing

19.5.5 Avoiding redundant trailing
----------------------------------

If a mutable data structure is updated multiple times, and each update
is recorded on the trail using the functions described above, then some
of this trailing may be redundant.  It is generally not necessary to
record enough information to recover the original state of the data
structure for _every_ update on the trail; instead, it is enough to
record the original state of each updated data structure just once for
each choice point occurring after the data structure is allocated,
rather than once for each update.

   The functions described below provide a means to avoid redundant
trailing.

* `MR_ChoicepointId'
     Declaration:
          typedef ... MR_ChoicepointId;

     The type `MR_ChoicepointId' is an abstract type used to hold the
     identity of a choice point.  Values of this type can be compared
     using C's `==' operator or using `MR_choicepoint_newer()'.

* `MR_current_choicepoint_id()'
     Prototype:
          MR_ChoicepointId MR_current_choicepoint_id(void);

     `MR_current_choicepoint_id()' returns a value indicating the
     identity of the most recent choice point; that is, the point to
     which execution would backtrack if the current computation failed.
     The value remains meaningful if the choicepoint is pruned away by
     a commit, but is not meaningful after backtracking past the point
     where the choicepoint was created (since choicepoint ids may be
     reused after backtracking).

* `MR_null_choicepoint_id()'
     Prototype:
          MR_ChoicepointId MR_null_choicepoint_id(void);

     `MR_null_choicepoint_id()' returns a "null" value that is distinct
     from any value ever returned by `MR_current_choicepoint_id'.
     (Note that `MR_null_choicepoint_id()' is a macro that is
     guaranteed to be suitable for use as a static initializer, so that
     it can for example be used to provide the initial value of a C
     global variable.)

* `MR_choicepoint_newer()'
     Prototype:
          bool MR_choicepoint_newer(MR_ChoicepointId, MR_ChoicepointId);

     `MR_choicepoint_newer(x, y)' true iff the choicepoint indicated by
     `x' is newer than (i.e. was created more recently than) the
     choicepoint indicated by `y'.  The null ChoicepointId is considered
     older than any non-null ChoicepointId.  If either of the choice
     points have been backtracked over, the behaviour is undefined.


   The way these functions are generally used is as follows.  When you
create a mutable data structure, you should call
`MR_current_choicepoint_id()' and save the value it returns as a
`prev_choicepoint' field in your data structure.  When you are about to
modify your mutable data structure, you can then call
`MR_current_choicepoint_id()' again and compare the result from that
call with the value saved in the `prev_choicepoint' field in the data
structure using `MR_choicepoint_newer()'.  If the current choicepoint
is newer, then you must trail the update, and update the
`prev_choicepoint' field with the new value; furthermore, you must also
take care that on backtracking the previous value of the
`prev_choicepoint' field in your data structure is restored to its
previous value, by trailing that update too.  But if
`MR_current_choice_id()' is not newer than the `prev_choicepoint'
field, then you can safely perform the update to your data structure
without trailing it.

   If your mutable data structure is a C global variable, then you can
use `MR_null_choicepoint_id()' for the initial value of the
`prev_choicepoint' field.  If on the other hand your mutable data
structure is created by a predicate or function that uses tabled
evaluation (*note Tabled evaluation::), then you _should_ use
`MR_null_choicepoint_id()' for the initial value of the field.  Doing
so will ensure that the data will be reset to its initial value if
execution backtracks to a point before the mutable data structure was
created, which is important because this copy of the mutable data
structure will be tabled and will therefore be produced again if later
execution attempts to create another instance of it.

   For an example of avoiding redundant trailing, see the sample module
below.

   Note that there is a cost to this -- you have to include an extra
field in your data structure for each part of the data structure which
you might update, you need to perform a test for each update to decide
whether or not to trail it, and if you do need to trail the update,
then you have an extra field that you need to trail.  Whether or not
the benefits from avoiding redundant trailing outweigh these costs will
depend on your application.

     :- module trailing_example.
     :- interface.

     :- type int_ref.

         % Create a new int_ref with the specified value.
         %
     :- pred new_int_ref(int_ref::uo, int::in) is det.

         % update_int_ref(Ref0, Ref, OldVal, NewVal).
         % Ref0 has value OldVal and Ref has value NewVal.
         %
     :- pred update_int_ref(int_ref::mdi, int_ref::muo, int::out, int::in)
         is det.

     :- implementation.

     :- pragma foreign_decl("C", "

     typedef struct {
         MR_ChoicepointId prev_choicepoint;
         MR_Integer data;
     } C_IntRef;

     ").

     :- pragma foreign_type("C", int_ref, "C_IntRef *").

     :- pragma foreign_proc("C",
         new_int_ref(Ref::uo, Value::in),
         [will_not_call_mercury, promise_pure],
     "
         C_Intref *x = malloc(sizeof(C_IntRef));
         x->prev_choicepoint = MR_current_choicepoint_id();
         x->data = Value;
         Ref = x;
     ").

     :- pragma foreign_proc("C",
         update_int_ref(Ref0::mdi, Ref::muo, OldValue::out, NewValue::in),
         [will_not_call_mercury, promise_pure],
     "
         C_IntRef *x = Ref0;
         OldValue = x->data;

         /* Check whether we need to trail this update. */
         if (MR_choicepoint_newer(MR_current_choicepoint_id(),
             x->prev_choicepoint))
         {
             /*
             ** Trail both x->data and x->prev_choicepoint,
             ** since we're about to update them both.
             */
             assert(sizeof(x->data) == sizeof(MR_Word));
             assert(sizeof(x->prev_choicepoint) == sizeof(MR_Word));
             MR_trail_current_value((MR_Word *)&x->data);
             MR_trail_current_value((MR_Word *)&x->prev_choicepoint);

             /*
             ** Update x->prev_choicepoint to indicate that
             ** x->data's previous value has been trailed
             ** at this choice point.
             */
             x->prev_choicepoint = MR_current_choicepoint_id();
         }
         x->data = NewValue;
         Ref = Ref0;
     ").


File: mercury_ref.info,  Node: Bibliography,  Prev: Implementation-dependent extensions,  Up: Top

20 Bibliography
***************

* Menu:

* [1]::         Spiers, Somogyi, and Sondergaard,
                `Termination Analysis for Mercury'.
* [2]::        	Groger and Plumer, `Handling of mutual recursion in
                automatic termination proofs for logic programs'.
* [3]::         Spiers, `Termination Analysis for logic programs'.
* [4]::         Sagonas, `The SLG-WAM: A Search-Efficient Engine
                for Well-Founded Evaluation of Normal Logic Programs'.
* [5]::         Demoen and Sagonas, `CAT: the copying approach to tabling'.


File: mercury_ref.info,  Node: [1],  Next: [2],  Up: Bibliography

[1]
===

Chris Speirs, Zoltan Somogyi and Harald Sondergaard, `Termination
Analysis for Mercury'.  In P. Van Hentenryck, editor, `Static Analysis:
Proceedings of the 4th International Symposium', Lecture Notes in
Computer Science. Springer, 1997.  A longer version is available for
download from
<http://www.cs.mu.oz.au/publications/tr_db/mu_97_09.ps.gz>.


File: mercury_ref.info,  Node: [2],  Next: [3],  Prev: [1],  Up: Bibliography

[2]
===

Gerhard Groger and Lutz Plumer, `Handling of mutual recursion in
automatic termination proofs for logic programs.'  In K. Apt, editor,
`The Proceedings of the Joint International Conference and Symposium on
Logic Programming', pages 336-350.  MIT Press, 1992.


File: mercury_ref.info,  Node: [3],  Next: [4],  Prev: [2],  Up: Bibliography

[3]
===

Chris Speirs, `Termination Analysis for Logic Programs', Technical
Report 97/23, Department of Computer Science, The University of
Melbourne, Melbourne, Australia, 1997.  Available from
<http://www.cs.mu.oz.au/mercury/papers/mu_97_23.ps.gz>.


File: mercury_ref.info,  Node: [4],  Next: [5],  Prev: [3],  Up: Bibliography

[4]
===

K. Sagonas, `The SLG-WAM: A Search-Efficient Engine for Well-Founded
Evaluation of Normal Logic Programs', PhD thesis, SUNY at Stony Brook,
1996.  Available from
<http://www.cs.kuleuven.ac.be/~kostis/Thesis/thesis.ps.gz>.


File: mercury_ref.info,  Node: [5],  Prev: [4],  Up: Bibliography

[5]
===

B. Demoen and K. Sagonas, `CAT: the copying approach to tabling',
submitted for publication, Katholieke Universiteit Leuven, 1998.


