The Mercury Library Reference Manual

Copyright (C) 1995-1997 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.

The Mercury standard library contains a variety of modules which we hope may be of general usefulness. If you write a module that would be useful to others, and you would like us to include it as part of the Mercury standard library, please let us know.

The following documentation is simply the interface parts to those modules, automatically extracted from the source code. Some of the library modules are not very well documented; we apologize.

For many of the modules in the standard library, we have not yet had enough experience using them to be confident that the current interface is satisfactory; it is likely that the interfaces to many of the modules in the standard library will change somewhat in future releases of the Mercury system. Some modules are rather experimental modules that may even be removed in future releases. Of course, we wouldn't make changes gratuitously, but at the current time, preserving 100% backwards compatibility would be disadvantageous in the long run.

To help you protect yourself from depending on modules that are likely to change, each module has a comment "stability: low/medium/high" at the top which gives an indication of the likely stability of the interface to that module. For modules whose stability is "high", new functionality may be added to the interface, but we envisage very few if any changes to the interface of the sort that might break existing code. For modules whose stability is "medium", we expect that changes are more likely. For modules whose stability is "low", such changes are highly likely. If you want to minimize the possibility of your programs requiring modification to work with new releases of the Mercury system, we recommend that if possible you use only those modules whose stability is described as either "medium to high" or "high".

Sometime in the near future, we will implement module qualifiers, and then all of the double-underscores will be replaced with module qualifiers, so that e.g. `list__append' will become `list:append' (and in fact the `list:' prefix will become optional). At that time, some reorganization of the library may occur. When this change happens, we will provide users with a tool to automate conversion of existing programs.

array

%--------------------------------------------------%
% Copyright (C) 1993-1995, 1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: array.m
% Main authors: fjh, bromage
% Stability: medium-low

% This module provides dynamically-sized one-dimensional arrays.
% Array indices start at zero.

%--------------------------------------------------%
%--------------------------------------------------%

:- module array.
:- interface.
:- import_module list, std_util.

:- type array(T).

:- inst array(I) = bound(array(I)).
:- inst array == array(ground).
:- inst array_skel == array(free).

	% XXX the current Mercury compiler doesn't support `ui' modes,
	% so to work-around that problem, we currently don't use
	% unique modes in this module.

% :- inst uniq_array(I) = unique(array(I)).
% :- inst uniq_array == uniq_array(unique).
:- inst uniq_array(I) = bound(array(I)). % XXX work-around
:- inst uniq_array == uniq_array(ground). % XXX work-around
:- inst uniq_array_skel == uniq_array(free).

:- mode array_di == di(uniq_array).
:- mode array_uo == out(uniq_array).
:- mode array_ui == in(uniq_array).

% :- inst mostly_uniq_array(I) = mostly_unique(array(I)).
% :- inst mostly_uniq_array == mostly_uniq_array(mostly_unique).
:- inst mostly_uniq_array(I) = bound(array(I)).	% XXX work-around
:- inst mostly_uniq_array == mostly_uniq_array(ground).	% XXX work-around
:- inst mostly_uniq_array_skel == mostly_uniq_array(free).

:- mode array_mdi == mdi(mostly_uniq_array).
:- mode array_muo == out(mostly_uniq_array).
:- mode array_mui == in(mostly_uniq_array).

%--------------------------------------------------%

	% array__make_empty_array(Array) creates an array of size zero
	% starting at lower bound 0.
:- pred array__make_empty_array(array(T)).
:- mode array__make_empty_array(array_uo) is det.

	% array__init(Size, Init, Array) creates an array
	% with bounds from 0 to Size-1, with each element initialized to Init.
:- pred array__init(int, T, array(T)).
:- mode array__init(in, in, array_uo) is det.

	% array/1 is a function that constructs an array from a list.
	% (It does the same thing as the predicate array__from_list/2.)
	% The syntax `array([...])' is used to represent arrays
	% for io__read, io__write, term_to_type, and type_to_term.
:- func array(list(T)) = array(T).
:- mode array(in) = array_uo is det.

%--------------------------------------------------%

	% array__min returns the lower bound of the array.
	% Note: in this implementation, the lower bound is always zero.
:- pred array__min(array(_T), int).
:- mode array__min(array_ui, out) is det.
:- mode array__min(in, out) is det.

	% array__max returns the upper bound of the array.
:- pred array__max(array(_T), int).
:- mode array__max(array_ui, out) is det.
:- mode array__max(in, out) is det.

	% array__size returns the length of the array,
	% i.e. upper bound - lower bound + 1.
:- pred array__size(array(_T), int).
:- mode array__size(array_ui, out) is det.
:- mode array__size(in, out) is det.

	% array__bounds returns the upper and lower bounds of an array.
	% Note: in this implementation, the lower bound is always zero.
:- pred array__bounds(array(_T), int, int).
:- mode array__bounds(array_ui, out, out) is det.
:- mode array__bounds(in, out, out) is det.

	% array__in_bounds checks whether an index is in the bounds
	% of an array.
:- pred array__in_bounds(array(_T), int).
:- mode array__in_bounds(array_ui, in) is semidet.
:- mode array__in_bounds(in, in) is semidet.

%--------------------------------------------------%

	% array__lookup returns the Nth element of an array.
	% It is an error if the index is out of bounds.
:- pred array__lookup(array(T), int, T).
:- mode array__lookup(array_ui, in, out) is det.
:- mode array__lookup(in, in, out) is det.

	% array__semidet_lookup returns the Nth element of an array.
	% It fails if the index is out of bounds.
:- pred array__semidet_lookup(array(T), int, T).
:- mode array__semidet_lookup(array_ui, in, out) is semidet.
:- mode array__semidet_lookup(in, in, out) is semidet.

	% array__set sets the nth element of an array, and returns the
	% resulting array (good opportunity for destructive update ;-).  
	% It is an error if the index is out of bounds.
:- pred array__set(array(T), int, T, array(T)).
:- mode array__set(array_di, in, in, array_uo) is det.

	% array__semidet_set sets the nth element of an array,
	% and returns the resulting array.
	% It fails if the index is out of bounds.
:- pred array__semidet_set(array(T), int, T, array(T)).
:- mode array__semidet_set(array_di, in, in, array_uo) is semidet.

	% array__slow_set sets the nth element of an array,
	% and returns the resulting array.  The initial array is not
	% required to be unique, so the implementation may not be able to use
	% destructive update.
	% It is an error if the index is out of bounds.
:- pred array__slow_set(array(T), int, T, array(T)).
:- mode array__slow_set(array_ui, in, in, array_uo) is det.
:- mode array__slow_set(in, in, in, array_uo) is det.

	% array__semidet_slow_set sets the nth element of an array,
	% and returns the resulting array.  The initial array is not
	% required to be unique, so the implementation may not be able to use
	% destructive update.
	% It fails if the index is out of bounds.
:- pred array__semidet_slow_set(array(T), int, T, array(T)).
:- mode array__semidet_slow_set(array_ui, in, in, array_uo) is semidet.
:- mode array__semidet_slow_set(in, in, in, array_uo) is semidet.

	% array__copy(Array0, Array):
	% Makes a new unique copy of an array.
:- pred array__copy(array(T), array(T)).
:- mode array__copy(array_ui, array_uo) is det.
:- mode array__copy(in, array_uo) is det.

	% array__resize(Array0, Size, Init, Array):
	% The array is expanded or shrunk to make it fit
	% the new size `Size'.  Any new entries are filled
	% with `Init'.
:- pred array__resize(array(T), int, T, array(T)).
:- mode array__resize(array_di, in, in, array_uo) is det.

	% array__shrink(Array0, Size, Array):
	% The array is shrunk to make it fit the new size `Size'.
	% It is an error if `Size' is larger than the size of `Array0'.
:- pred array__shrink(array(T), int, array(T)).
:- mode array__shrink(array_di, in, array_uo) is det.

	% array__from_list takes a list,
	% and returns an array containing those elements in
	% the same order that they occured in the list.
:- pred array__from_list(list(T), array(T)).
:- mode array__from_list(in, array_uo) is det.

	% array__to_list takes an array and returns a list containing
	% the elements of the array in the same order that they
	% occurred in the array.
:- pred array__to_list(array(T), list(T)).
:- mode array__to_list(array_ui, out) is det.
:- mode array__to_list(in, out) is det.

	% array__fetch_items takes an array and a lower and upper
	% index, and places those items in the array between these
	% indices into a list.  It is an error if either index is
	% out of bounds.
:- pred array__fetch_items(array(T), int, int, list(T)).
:- mode array__fetch_items(in, in, in, out) is det.

	% array__bsearch takes an array, an element to be found
	% and a comparison predicate and returns the position of
	% the element in the array.  Assumes the array is in sorted
	% order.  Fails if the element is not present.  If the
	% element to be found appears multiple times, the index of
	% the first occurrence is returned.
:- pred array__bsearch(array(T), T, pred(T, T, comparison_result),
			maybe(int)).
:- mode array__bsearch(array_ui, in, pred(in, in, out) is det, out) is det.
:- mode array__bsearch(in, in, pred(in, in, out) is det, out) is det.

%--------------------------------------------------%

assoc_list

%--------------------------------------------------%
% Copyright (C) 1995-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: assoc_list.m.
% Main authors: fjh, zs.
% Stability: medium to high.

% This file contains the definition of the type assoc_list(K, V)
% and some predicates which operate on those types.

%--------------------------------------------------%
%--------------------------------------------------%

:- module assoc_list.

:- interface.

:- import_module list, std_util.

%--------------------------------------------------%

:- type assoc_list(K,V)	==	list(pair(K,V)).

:- type assoc_list(T)	==	list(pair(T,T)).

	% Swap the two sides of the pairs in each member of the list.

:- pred assoc_list__reverse_members(assoc_list(K, V), assoc_list(V, K)).
:- mode assoc_list__reverse_members(in, out) is det.

	% Zip together two lists; abort if they are of different lengths.

:- pred assoc_list__from_corresponding_lists(list(K), list(V),
						assoc_list(K,V)).
:- mode assoc_list__from_corresponding_lists(in, in, out) is det.

	% Return the first member of each pair.

:- pred assoc_list__keys(assoc_list(K, V), list(K)).
:- mode assoc_list__keys(in, out) is det.

	% Return the second member of each pair.

:- pred assoc_list__values(assoc_list(K, V), list(V)).
:- mode assoc_list__values(in, out) is det.

	% Find the first element of the association list that matches
	% the given key, and return the associated value.

:- pred assoc_list__search(assoc_list(K, V), K, V).
:- mode assoc_list__search(in, in, out) is semidet.

	% Find the first element of the association list that matches
	% the given key. Return the associated value, and the original
	% list with the selected element removed.

:- pred assoc_list__remove(assoc_list(K, V), K, V,
	assoc_list(K, V)).
:- mode assoc_list__remove(in, in, out, out) is semidet.

%--------------------------------------------------%

bag

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% file: bag.m
%	An implementation of multisets.
% main author: conway, crs.
% stability: medium
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module bag.

:- interface.

:- import_module list.

:- type bag(T).

	% Create an empty bag.
:- pred bag__init(bag(T)).
:- mode bag__init(out) is det.

	% Insert a particular value in a bag.
:- pred bag__insert(bag(T), T, bag(T)).
:- mode bag__insert(in, in, out) is det.

	% Insert a list of values into a bag.
:- pred bag__insert_list(bag(T), list(T), bag(T)).
:- mode bag__insert_list(in, in, out) is det.

	% Make a bag from a list.
:- pred bag__from_list(list(T), bag(T)).
:- mode bag__from_list(in, out) is det.

	 % Given a bag, produce a sorted list containing all the values in
	 % the bag.  Each value will appear in the list the same number of
	 % times that it appears in the bag.
:- pred bag__to_list(bag(T), list(T)).
:- mode bag__to_list(in, out) is det.

	% Given a bag, produce a sorted list with no duplicates 
	% containing all the values in the bag.
:- pred bag__to_list_without_duplicates(bag(T), list(T)).
:- mode bag__to_list_without_duplicates(in, out) is det.

	% Remove one occurrence of a particular value from a bag.
	% Fail if the item does not exist in the bag.
:- pred bag__remove(bag(T), T, bag(T)).
:- mode bag__remove(in, in, out) is semidet.

	% Remove one occurrence of a particular value from a bag.
	% Abort if the item does not exist in the bag.
:- pred bag__det_remove(bag(T), T, bag(T)).
:- mode bag__det_remove(in, in, out) is det.

	% Delete one occurrence of a particular value from a bag.
	% If the key is not present, leave the bag unchanged.
:- pred bag__delete(bag(T), T, bag(T)).
:- mode bag__delete(in, in, out) is det.

	% Remove all occurrences of a particular value from a bag.
	% Fail if the item does not exist in the bag.
:- pred bag__remove_all(bag(T), T, bag(T)).
:- mode bag__remove_all(in, in, out) is semidet.

	% Delete all occurrences of a particular value from a bag.
:- pred bag__delete_all(bag(T), T, bag(T)).
:- mode bag__delete_all(in, in, out) is det.

	% Check whether a bag contains a particular value.
:- pred bag__contains(bag(T), T).
:- mode bag__contains(in, in) is semidet.

	% bag__subtract(Bag0, SubBag, Bag)
	% subtracts SubBag from Bag0 to produce Bag
	% each element in SubBag is removed from Bag0 to produce Bag.
	% If an element exists in SubBag, but not in Bag, then that
	% element is not removed.
	% e.g. bag__subtract({1, 1, 2, 2, 3 }, {1, 1, 2, 3, 3, 3}, {2}). 
:- pred bag__subtract(bag(T), bag(T), bag(T)).
:- mode bag__subtract(in, in, out) is det.

	% The third bag is the union of the first 2 bags.
	% e.g. {1, 1, 2, 2} U {2, 2, 3, 3} = {1, 1, 2, 2, 2, 2, 3, 3}
	% If the two input bags are known to be unequal in size, then
	% making the first bag the larger bag will usually be more
	% efficient.
:- pred bag__union(bag(T), bag(T), bag(T)).
:- mode bag__union(in, in, out) is det.

	% The third bag is the intersection of the first 2 bags.  Every
	% element in the third bag exists in both of the first 2 bags.
	% e.g. bag__intersect({1, 2, 2, 3, 3}, {2, 2, 3, 4}, {2, 2, 3}).
:- pred bag__intersect(bag(T), bag(T), bag(T)).
:- mode bag__intersect(in, in, out) is det.

	% Fails if there is no intersection between the 2 bags.
	% bag__intersect(A, B) :- bag__intersect(A, B, C), not bag__is_empty(C).
:- pred bag__intersect(bag(T), bag(T)).
:- mode bag__intersect(in, in) is semidet.

	% Fails if the first bag is not a subbag of the second.
	% bag__is_subbag(A, B). implies that every element in the bag A
	% is also in the bag B.  If an element is in bag A multiple times, it
	% must be in bag B at least as many times.
	% e.g. bag__is_subbag({1, 1, 2}, {1, 1, 2, 2, 3}).
	% e.g. bag__is_subbag({1, 1, 2}, {1, 2, 3}) :- fail.
:- pred bag__is_subbag(bag(T), bag(T)).
:- mode bag__is_subbag(in, in) is semidet.

	% Check whether a bag is empty.
:- pred bag__is_empty(bag(T)).
:- mode bag__is_empty(in) is semidet.

	% Fails if the bag is empty.
:- pred bag__remove_smallest(bag(T), T, bag(T)).
:- mode bag__remove_smallest(in, out, out) is semidet.

	% Compares the two bags, and returns whether the first bag is a 
	% subset (<), is equal (=), or is a superset (>) of the second.
	% bag__subset_compare(<, {apple, orange}, {apple, apple, orange}).
	% bag__subset_compare(=, {apple, orange}, {apple, orange}).
	% bag__subset_compare(>, {apple, apple, orange}, {apple, orange}).
	% bag__subset_compare(_, {apple, apple}, {orange, orange}) :- fail.
:- pred bag__subset_compare(comparison_result, bag(T), bag(T)).
:- mode bag__subset_compare(out, in, in) is semidet.

%--------------------------------------------------%
%--------------------------------------------------%

benchmarking

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: benchmarking.m.
% Main author: zs.
% Stability: medium to high.

% This module contains predicates that deal with the CPU time requirements
% of (various parts of) the program.

%--------------------------------------------------%
%--------------------------------------------------%

:- module benchmarking.

:- interface.

% Declaratively, `report_stats' is the same as `true'.
% It has the side-effect of reporting some memory and time usage statistics
% to stdout. (Technically, every Mercury implementation must offer
% a mode of invocation which disables this side-effect.)

:- pred report_stats is det.

% benchmark_det(Pred, In, Out, Repeats, Time) is for benchmarking the
% det predicate Pred. We call Pred with the input In and the output Out,
% and return Out so that the caller can check the correctness of the
% benchmarked predicate. Since most systems do not have good facilities
% for measuring small times, the Repeats parameter allows the caller to
% specify how many times Pred should be called inside the timed interval.
% The number of milliseconds required to execute Pred with input In this
% many times is returned as Time.

:- pred benchmark_det(pred(T1, T2), T1, T2, int, int).
:- mode benchmark_det(pred(in, out) is det, in, out, in, out) is cc_multi.

% benchmark_nondet(Pred, In, Count, Repeats, Time) is for benchmarking
% the nondet predicate Pred. benchmark_nondet is similar to benchmark_det,
% but it returns only a count of the solutions, rather than solutions
% themselves.  The number of milliseconds required to generate
% all solutions of Pred with input In Repeats times is returned as Time.

:- pred benchmark_nondet(pred(T1, T2), T1, int, int, int).
:- mode benchmark_nondet(pred(in, out) is nondet, in, out, in, out)
	is cc_multi.

bimap

%--------------------------------------------------%
% Copyright (C) 1994-1995, 1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: bimap.m.
% Main author: conway.
% Stability: medium.
%
% This file provides a bijective map ADT.
% A map (also known as a dictionary or an associative array) is a collection
% of (Key,Data) pairs which allows you to look up any Data item given the
% Key.  A bimap also allows you to look up the Key given the Data.
%
% The implementation is a pair of maps.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module bimap.
:- interface.
:- import_module list, assoc_list.

%--------------------------------------------------%

:- type bimap(_K, _V).

%--------------------------------------------------%

	% Initialize an empty bimap.
:- pred bimap__init(bimap(_,_)).
:- mode bimap__init(out) is det.

	% Check whether a bimap is empty.
:- pred bimap__is_empty(bimap(_,_)).
:- mode bimap__is_empty(in) is semidet.

:- pred bimap__search(bimap(K,V), K, V).
:- mode bimap__search(in, in, out) is semidet.
:- mode bimap__search(in, out, in) is semidet.

:- pred bimap__lookup(bimap(K,V), K, V).
:- mode bimap__lookup(in, in, out) is det.

:- pred bimap__reverse_lookup(bimap(K,V), K, V).
:- mode bimap__reverse_lookup(in, out, in) is det.

:- pred bimap__insert(bimap(K,V), K, V, bimap(K,V)).
:- mode bimap__insert(in, in, in, out) is semidet.

:- pred bimap__set(bimap(K,V), K, V, bimap(K,V)).
:- mode bimap__set(in, in, in, out) is det.

	% Given a bimap, return a list of all the keys in the bimap
:- pred bimap__ordinates(bimap(K, _V), list(K)).
:- mode bimap__ordinates(in, out) is det.

	% Given a bimap, return a list of all the data values in the bimap
:- pred bimap__coordinates(bimap(_K, V), list(V)).
:- mode bimap__coordinates(in, out) is det.

	% convert a bimap to an association list
:- pred bimap__to_assoc_list(bimap(K,V), assoc_list(K,V)).
:- mode bimap__to_assoc_list(in, out) is det.

	% convert an association list to a bimap
:- pred bimap__from_assoc_list(assoc_list(K,V), bimap(K,V)).
:- mode bimap__from_assoc_list(in, out) is det.

/****
	% delete a key-value pair from a bimap
:- pred bimap__delete(bimap(K,V), K, V, bimap(K,V)).
:- mode bimap__delete(in, in, out, out) is det.
:- mode bimap__delete(in, out, in, out) is det.

:- pred bimap__from_corresponding_lists(list(K), list(V), bimap(K, V)).
:- mode bimap__from_corresponding_lists(in, in, out) is det.
****/

%--------------------------------------------------%

:- import_module map.

:- type bimap(K,V)	--->	bimap(map(K,V), map(V, K)).

%--------------------------------------------------%
%--------------------------------------------------%

bintree

%--------------------------------------------------%
% Copyright (C) 1993-1995, 1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: bintree.m.
% Main author: conway.
% Stability: medium (obsolete).
%
% This module exists primarily for historical reasons.  It is unlikely
% to be useful, and may not be supported in future releases.
% You should use `map' instead.
%
% This file provides a straight-forward binary search tree implementation of
% a map (dictionary).
%
% bintree__insert, bintree__update, and
% bintree__set differ only in how they handle the case where the value
% being inserted already exists in the tree.  `insert' will only insert
% new keys, and will fail if you attempt to insert an existing key into
% the tree. `update' will only allow you to modify the data for existing
% keys, and will fail if the key isn't already in the tree.  `set' will
% always succeed; it will replace the old value for that key if the key
% was already in the tree, or insert a new node into the tree if the key
% wasn't already present.
% 
%--------------------------------------------------%

:- module bintree.
:- interface.
:- import_module list, assoc_list.

:- type bintree(K, V).

:- pred bintree__init(bintree(K,V)).
:- mode bintree__init(uo) is det.

:- pred bintree__insert(bintree(K,V), K, V, bintree(K,V)).
:- mode bintree__insert(in, in, in, out) is semidet.

:- pred bintree__update(bintree(K,V), K, V, bintree(K,V)).
:- mode bintree__update(in, in, in, out) is semidet.

:- pred bintree__set(bintree(K,V), K, V, bintree(K,V)).
:- mode bintree__set(di, di, di, uo) is det.
:- mode bintree__set(in, in, in, out) is det.

:- pred bintree__search(bintree(K,V), K, V).
:- mode bintree__search(in, in, in) is semidet.	% implied
:- mode bintree__search(in, in, out) is semidet.

:- pred bintree__delete(bintree(K,V), K, bintree(K,V)).
:- mode bintree__delete(in, in, out) is det.

:- pred bintree__remove(bintree(K,V), K, V, bintree(K,V)).
:- mode bintree__remove(in, in, out, out) is semidet.

:- pred bintree__keys(bintree(K,_V), list(K)).
:- mode bintree__keys(in, out) is det.

:- pred bintree__values(bintree(_K,V), list(V)).
:- mode bintree__values(in, out) is det.

:- pred bintree__from_list(assoc_list(K,V), bintree(K,V)).
:- mode bintree__from_list(in, out) is det.

:- pred bintree__from_sorted_list(assoc_list(K,V), bintree(K,V)).
:- mode bintree__from_sorted_list(in, out) is det.

:- pred bintree__from_corresponding_lists(list(K), list(V), bintree(K,V)).
:- mode bintree__from_corresponding_lists(in, in, out) is det.

:- pred bintree__to_list(bintree(K,V), assoc_list(K,V)).
:- mode bintree__to_list(in, out) is det.

	% count the number of elements in a tree
:- pred bintree__count(bintree(_K,_V), int).
:- mode bintree__count(in, out) is det.

	% count the depth of a tree
:- pred bintree__depth(bintree(_K,_V), int).
:- mode bintree__depth(in, out) is det.

:- pred bintree__branching_factor(bintree(_K,_V), int, int).
:- mode bintree__branching_factor(in, out, out) is det.

:- pred bintree__balance(bintree(K, V), bintree(K, V)).
:- mode bintree__balance(in, out) is det.

%--------------------------------------------------%

bintree_set

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

:- module bintree_set.

% Main authors: fjh.
% Stability: medium.

% This file provides an alternate implementation of the `set' ADT
% defined in module `set'.  See that file for comments about the semantics
% of the predicates.  This file implements sets as binary sorted trees,
% using module `bintree', and so provides different performance
% characteristics.

% bintree_set__is_member is a version of bintree_set__member
% with a more restricted mode, which is implemented much
% more efficiently using bintree__search.

%--------------------------------------------------%

:- interface.
:- import_module list.

:- type bintree_set(_T).

	% `bintree_set__list_to_set(List, Set)' is true iff `Set' is the set 
	% containing only the members of `List'.

:- pred bintree_set__list_to_set(list(T), bintree_set(T)).
:- mode bintree_set__list_to_set(in, out) is det.

	% `bintree_set__sorted_list_to_set(List, Set)' is true iff
	% `Set' is the set containing only the members of `List'.
	% `List' must be sorted.

:- pred bintree_set__sorted_list_to_set(list(T), bintree_set(T)).
:- mode bintree_set__sorted_list_to_set(in, out) is det.

	% `bintree_set__list_to_bintree_set(Set, List)' is true iff
	% `List' is the list of all the members of `Set', in sorted
	% order.

:- pred bintree_set__to_sorted_list(bintree_set(T), list(T)).
:- mode bintree_set__to_sorted_list(in, out) is det.

	% `bintree_set__init(Set)' is true iff `Set' is an empty set.

:- pred bintree_set__init(bintree_set(_T)).
:- mode bintree_set__init(uo) is det.

:- pred bintree_set__singleton_set(bintree_set(T), T).
:- mode bintree_set__singleton_set(out, in) is det.

	% `bintree_set__equal(SetA, SetB)' is true iff
	% `SetA' and `SetB' contain the same elements.

:- pred bintree_set__equal(bintree_set(T), bintree_set(T)).
:- mode bintree_set__equal(in, in) is semidet.

	% `bintree_set__subset(SetA, SetB)' is true iff `SetA' is a
	% subset of `SetB'.

:- pred bintree_set__subset(bintree_set(T), bintree_set(T)).
:- mode bintree_set__subset(in, in) is semidet.

	% `bintree_set__superset(SetA, SetB)' is true iff `SetA' is a
	% superset of `SetB'.

:- pred bintree_set__superset(bintree_set(T), bintree_set(T)).
:- mode bintree_set__superset(in, in) is semidet.

	% `bintree_set_member(X, Set)' is true iff `X' is a member of `Set'.

:- pred bintree_set__member(T, bintree_set(T)).
:- mode bintree_set__member(in, in) is semidet.
:- mode bintree_set__member(out, in) is nondet.

	% `bintree_set_member(X, Set)' is true iff `X' is a member of `Set'.

:- pred bintree_set__is_member(T, bintree_set(T)).
:- mode bintree_set__is_member(in, in) is semidet.

	% `bintree_set__insert(Set0, X, Set)' is true iff `Set' is the union of
	% `Set0' and the set containing only `X'.

:- pred bintree_set__insert(bintree_set(T), T, bintree_set(T)).
:- mode bintree_set__insert(di, di, uo) is det.
:- mode bintree_set__insert(in, in, out) is det.

	% `bintree_set__insert_list(Set0, Xs, Set)' is true iff `Set'
	% is the union of `Set0' and the set containing only the
	% members of `Xs'.

:- pred bintree_set__insert_list(bintree_set(T), list(T), bintree_set(T)).
:- mode bintree_set__insert_list(di, di, uo) is det.
:- mode bintree_set__insert_list(in, in, out) is det.

	% `bintree_set__remove(Set0, X, Set)' is true iff `Set0' contains `X',
	% and `Set' is the relative complement of `Set0' and the set
	% containing only `X', i.e.  if `Set' is the set which contains
	% all the elements of `Set0' except `X'.

:- pred bintree_set__remove(bintree_set(T), T, bintree_set(T)).
:- mode bintree_set__remove(in, in, out) is semidet.
% The following mode could be implemented, but hasn't been:
% :- mode bintree_set__remove(in, out, out) is nondet. 

	% `bintree_set__remove_list(Set0, Xs, Set)' is true iff Xs does
	% not contain any duplicates, `Set0' contains every member of
	% `Xs', and `Set' is the relative complement of `Set0' and the
	% set containing only the members of `Xs'.

:- pred bintree_set__remove_list(bintree_set(T), list(T), bintree_set(T)).
:- mode bintree_set__remove_list(in, in, out) is semidet.

	% `bintree_set__delete(Set0, X, Set)' is true iff `Set' is the relative
	% complement of `Set0' and the set containing only `X', i.e.
	% if `Set' is the set which contains all the elements of `Set0'
	% except `X'.

:- pred bintree_set__delete(bintree_set(T), T, bintree_set(T)).
:- mode bintree_set__delete(in, in, out) is det.

	% `bintree_set__delete_list(Set0, Xs, Set)' is true iff `Set'
	% is the relative complement of `Set0' and the set containing
	% only the members of `Xs'.

:- pred bintree_set__delete_list(bintree_set(T), list(T), bintree_set(T)).
:- mode bintree_set__delete_list(in, in, out) is det.

	% `set_union(SetA, SetB, Set)' is true iff `Set' is the union of
	% `SetA' and `SetB'.  If the sets are known to be of different
	% sizes, then for efficiency make `SetA' the larger of the two.

:- pred bintree_set__union(bintree_set(T), bintree_set(T), bintree_set(T)).
:- mode bintree_set__union(in, in, out) is det.

	% `set_intersect(SetA, SetB, Set)' is true iff `Set' is the
	% intersection of `SetA' and `SetB'.

:- pred bintree_set__intersect(bintree_set(T), bintree_set(T),
				bintree_set(T)).
:- mode bintree_set__intersect(in, in, out) is det.

%--------------------------------------------------%

bool

%--------------------------------------------------%
% Copyright (C) 1996-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: bool.m.
% Main authors: fjh, zs.
% Stability: medium to high.

% This module exports the boolean type `bool' and some operations on bools.

%--------------------------------------------------%
%--------------------------------------------------%

:- module bool.

:- interface.

:- import_module list.

%--------------------------------------------------%

% The boolean type.
% Unlike most languages, we use `yes' and `no' as boolean constants
% rather than `true' and `false'.  This is to avoid confusion
% with the predicates `true' and `fail'.

:- type bool ---> no ; yes.

:- pred bool__or(bool, bool, bool).
:- mode bool__or(in, in, out) is det.

:- pred bool__or_list(list(bool), bool).
:- mode bool__or_list(in, out) is det.

:- pred bool__and(bool, bool, bool).
:- mode bool__and(in, in, out) is det.

:- pred bool__and_list(list(bool), bool).
:- mode bool__and_list(in, out) is det.

:- pred bool__not(bool, bool).
:- mode bool__not(in, out) is det.

%--------------------------------------------------%

bt_array

%--------------------------------------------------%
% Copyright (C) 1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: bt_array.m
% Main author: bromage.
% Stability: medium-low

% This file contains a set of predicates for generating an manipulating
% a bt_array data structure.  This implementation allows O(log n) access
% and update time, and does not require the bt_array to be unique.  If you
% need O(1) access/update time, use the array datatype instead.
% (`bt_array' is supposed to stand for either "binary tree array"
% or "backtrackable array".)

% Implementation obscurity: This implementation is biassed towards larger
% indices.  The access/update time for a bt_array of size N with index I
% is actually O(log(N-I)).  The reason for this is so that the resize
% operations can be optimised for a (possibly very) common case, and to
% exploit accumulator recursion in some operations.  See the documentation
% of bt_array__resize and bt_array__shrink for more details.

%--------------------------------------------------%
%--------------------------------------------------%

:- module bt_array.
:- interface.
:- import_module int, list.

:- type bt_array(T).

%--------------------------------------------------%

	% bt_array__init(Low, Array) creates a bt_array of size zero
	% starting at index Low.
:- pred bt_array__make_empty_array(int, bt_array(T)).
:- mode bt_array__make_empty_array(in, out) is det.

	% bt_array__init creates a bt_array with bounds from Low to High,
	% with each element initialized to Init.
:- pred bt_array__init(int, int, T, bt_array(T)).
:- mode bt_array__init(in, in, in, out) is det. % want a bt_array_skeleton?

%--------------------------------------------------%

	% array__min returns the lower bound of the array
:- pred bt_array__min(bt_array(_T), int).
:- mode bt_array__min(in, out) is det.

	% array__max returns the upper bound of the array
:- pred bt_array__max(bt_array(_T), int).
:- mode bt_array__max(in, out) is det.

	% array__size returns the length of the array,
	% i.e. upper bound - lower bound + 1.
:- pred bt_array__size(bt_array(_T), int).
:- mode bt_array__size(in, out) is det.

	% bt_array__bounds returns the upper and lower bounds of a bt_array.
:- pred bt_array__bounds(bt_array(_T), int, int).
:- mode bt_array__bounds(in, out, out) is det.

	% bt_array__in_bounds checks whether an index is in the bounds
	% of a bt_array
:- pred bt_array__in_bounds(bt_array(_T), int).
:- mode bt_array__in_bounds(in, in) is semidet.

%--------------------------------------------------%

	% bt_array__lookup returns the Nth element of a bt_array.
	% It is an error if the index is out of bounds.
:- pred bt_array__lookup(bt_array(T), int, T).
:- mode bt_array__lookup(in, in, out) is det.

	% bt_array__semidet_lookup is like bt_array__lookup except that
	% it fails if the index is out of bounds.
:- pred bt_array__semidet_lookup(bt_array(T), int, T).
:- mode bt_array__semidet_lookup(in, in, out) is semidet.

	% bt_array__set sets the nth element of a bt_array, and returns the
	% resulting bt_array.
	% It is an error if the index is out of bounds.
:- pred bt_array__set(bt_array(T), int, T, bt_array(T)).
:- mode bt_array__set(in, in, in, out) is det.

	% bt_array__set sets the nth element of a bt_array, and returns the
	% resulting bt_array (good opportunity for destructive update ;-).  
	% It fails if the index is out of bounds.
:- pred bt_array__semidet_set(bt_array(T), int, T, bt_array(T)).
:- mode bt_array__semidet_set(in, in, in, out) is semidet.

	% `bt_array__resize(BtArray0, Lo, Hi, Item, BtArray)' is true
	% if BtArray is a bt_array created by expanding or shrinking
	% BtArray0 to fit the bounds (Lo,Hi).  If the new bounds are
	% not wholly contained within the bounds of BtArray0, Item is
	% used to fill out the other places.
	%
	% Note: This operation is optimised for the case where the
	% lower bound of the new bt_array is the same as that of
	% the old bt_array.  In that case, the operation takes time
	% proportional to the absolute difference in size between
	% the two bt_arrays.  If this is not the case, it may take
	% time proportional to the larger of the two bt_arrays.
:- pred bt_array__resize(bt_array(T), int, int, T, bt_array(T)).
:- mode bt_array__resize(in, in, in, in, out) is det.

	% `bt_array__shrink(BtArray0, Lo, Hi, Item, BtArray)' is true
	% if BtArray is a bt_array created by shrinking BtArray0 to
	% fit the bounds (Lo,Hi).  It is an error if the new bounds
	% are not wholly within the bounds of BtArray0.
	%
	% Note: This operation is optimised for the case where the
	% lower bound of the new bt_array is the same as that of
	% the old bt_array.  In that case, the operation takes time
	% proportional to the absolute difference in size between
	% the two bt_arrays.  If this is not the case, it may take
	% time proportional to the larger of the two bt_arrays.
:- pred bt_array__shrink(bt_array(T), int, int, bt_array(T)).
:- mode bt_array__shrink(in, in, in, out) is det.

	% `bt_array__from_list(Low, List, BtArray)' takes a list (of
	% possibly zero length), and returns a bt_array containing
	% those elements in the same order that they occured in the
	% list.  The lower bound of the new array is `Low'.
:- pred bt_array__from_list(int, list(T), bt_array(T)).
:- mode bt_array__from_list(in, in, out) is det.

	% bt_array__to_list takes a bt_array and returns a list containing
	% the elements of the bt_array in the same order that they
	% occurred in the bt_array.
:- pred bt_array__to_list(bt_array(T), list(T)).
:- mode bt_array__to_list(in, out) is det.

	% bt_array__fetch_items takes a bt_array and a lower and upper
	% index, and places those items in the bt_array between these
	% indices into a list.  It is an error if either index is
	% out of bounds.
:- pred bt_array__fetch_items(bt_array(T), int, int, list(T)).
:- mode bt_array__fetch_items(in, in, in, out) is det.

	% bt_array__bsearch takes a bt_array, an element to be found
	% and a comparison predicate and returns the position of
	% the element in the bt_array.  Assumes the bt_array is in sorted
	% order.  Fails if the element is not present.  If the
	% element to be found appears multiple times, the index of
	% the first occurrence is returned.
:- pred bt_array__bsearch(bt_array(T), T, pred(T, T, comparison_result), int).
:- mode bt_array__bsearch(in, in, pred(in, in, out) is det, out) is semidet.

%--------------------------------------------------%

char

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%--------------------------------------------------%

% File: char.m.
% Main author: fjh.
% Stability: high.

% This module defines some predicates that manipulate characters.

% Originally we used `character' rather than `char' for the type name
% because `char' was used by NU-Prolog to mean something different.
% But now we use `char' and the use of `character' is discouraged.
%
% NU-Prolog atoms can only include 7-bit ASCII chars, so the current
% implementation does not support 8-bit characters.

%--------------------------------------------------%
%--------------------------------------------------%

:- module char.
:- interface.

%--------------------------------------------------%

:- type char == character.

:- pred char__to_int(char, int).
:- mode char__to_int(in, out) is det.
:- mode char__to_int(in, in) is semidet.	% implied
:- mode char__to_int(out, in) is semidet.
	% Convert a character to it's corresponding numerical code.

:- pred char__max_char_value(int).
:- mode char__max_char_value(out) is det.
	% Returns the maximum numerical character code.

:- pred char__min_char_value(int).
:- mode char__min_char_value(out) is det.
	% Returns the minimum numerical character code.

:- pred char__to_upper(char, char).
:- mode char__to_upper(in, out) is det.
	% Convert a character to uppercase.

:- pred char__to_lower(char, char).
:- mode char__to_lower(in, out) is det.
	% Convert a character to lowercase.

:- pred char__lower_upper(char, char).
:- mode char__lower_upper(in, out) is semidet.
:- mode char__lower_upper(out, in) is semidet.
	% char__lower_upper(Lower, Upper) is true iff
	% Lower is a lower-case letter and Upper is the corresponding
	% upper-case letter.

:- pred char__is_whitespace(char).
:- mode char__is_whitespace(in) is semidet.
	% True iff the character is whitespace, i.e. a space, tab,
	% newline, carriage return, form-feed, or vertical tab.

:- pred char__is_upper(char).
:- mode char__is_upper(in) is semidet.
	% True iff the character is an uppercase letter.

:- pred char__is_lower(char).
:- mode char__is_lower(in) is semidet.
	% True iff the character is a lowercase letter.

:- pred char__is_alpha(char).
:- mode char__is_alpha(in) is semidet.
	% True iff the character is a letter.

:- pred char__is_alnum(char).
:- mode char__is_alnum(in) is semidet.
	% True iff the character is a letter or digit.

:- pred char__is_alpha_or_underscore(char).
:- mode char__is_alpha_or_underscore(in) is semidet.
	% True iff the character is a letter or an underscore.

:- pred char__is_alnum_or_underscore(char).
:- mode char__is_alnum_or_underscore(in) is semidet.
	% True iff the character is a letter, a digit or an underscore.

:- pred char__is_digit(char).
:- mode char__is_digit(in) is semidet.
	% True iff the character is a decimal digit (0-9).

:- pred char__is_binary_digit(char).
:- mode char__is_binary_digit(in) is semidet.
	% True iff the character is a binary digit (0 or 1).

:- pred char__is_octal_digit(char).
:- mode char__is_octal_digit(in) is semidet.
	% True iff the character is a octal digit (0-7).

:- pred char__is_hex_digit(char).
:- mode char__is_hex_digit(in) is semidet.
	% True iff the character is a hexadecimal digit (0-9, a-f, A-F).

:- pred char__digit_to_int(char, int).
:- mode char__digit_to_int(in, out) is semidet.
	% Succeeds if char is a decimal digit (0-9) or letter (a-z or A-Z).
	% Returns the character's value as a digit (0-9 or 10-35).

:- pred char__int_to_digit(int, char).
:- mode char__int_to_digit(in, out) is semidet.
:- mode char__int_to_digit(out, in) is semidet.
	% char__int_to_uppercase_digit(Int, DigitChar):
	% True iff `Int' is an integer in the range 0-35 and
	% `DigitChar' is a decimal digit or uppercase letter
	% whose value as a digit is `Int'.

:- pred char__det_int_to_digit(int, char).
:- mode char__det_int_to_digit(in, out) is det.
	% Returns a decimal digit or uppercase letter corresponding to the
	% value.
	% Calls error/1 if the integer is not in the range 0-35.

%--------------------------------------------------%
%--------------------------------------------------%

dir

%--------------------------------------------------%
% Copyright (C) 1994-1995, 1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: dir.m.
% Main author: fjh.

% Filename and directory handling.
% Stability: high.

%--------------------------------------------------%

:- module dir.
:- interface.

	% predicates to isolate system dependencies 

:- pred dir__directory_separator(character).
:- mode dir__directory_separator(out) is det.
:- mode dir__directory_separator(in) is semidet.
	% Returns '/'.

:- pred dir__this_directory(string).
:- mode dir__this_directory(out) is det.	
:- mode dir__this_directory(in) is semidet.	 % Implied
	% Returns ".".

	% predicates for splitting filenames into a directory part and
	% a filename part.

:- pred dir__split_name(string::in, string::out, string::out) is det.
:- pred dir__basename(string::in, string::out) is det.
:- pred dir__dirname(string::in, string::out) is det.

%--------------------------------------------------%

eqvclass

%--------------------------------------------------%
% Copyright (C) 1995-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: eqvclass.m.
% Author: zs.
% Stability: low.
%
% A module for handling equivalence classes.
%
%--------------------------------------------------%

:- module eqvclass.

:- interface.

:- import_module set, list.

:- type eqvclass(T).

	% Create an empty equivalance class.

:- pred eqvclass__init(eqvclass(T)).
:- mode eqvclass__init(out) is det.

	% Is this item known to the equivalence class?

:- pred eqvclass__is_member(eqvclass(T), T).
:- mode eqvclass__is_member(in, in) is semidet.

	% Make an element known to the equivalence class.
	% The element may already be known to the class;
	% if it isn't, it is created without any equivalence relationships.

:- pred eqvclass__ensure_element(eqvclass(T), T, eqvclass(T)).
:- mode eqvclass__ensure_element(in, in, out) is det.

	% Make an element known to the equivalence class.
	% The element must not already be known to the class;
	% it is created without any equivalence relationships.

:- pred eqvclass__new_element(eqvclass(T), T, eqvclass(T)).
:- mode eqvclass__new_element(in, in, out) is det.

	% Make two elements of the equivalence class equivalent.
	% It is ok if they already are.

:- pred eqvclass__ensure_equivalence(eqvclass(T), T, T, eqvclass(T)).
:- mode eqvclass__ensure_equivalence(in, in, in, out) is det.

	% Make two elements of the equivalence class equivalent.
	% It is an error if they are already equivalent.

:- pred eqvclass__new_equivalence(eqvclass(T), T, T, eqvclass(T)).
:- mode eqvclass__new_equivalence(in, in, in, out) is det.

	% Test if two elements are equivalent.

:- pred eqvclass__same_eqvclass(eqvclass(T), T, T).
:- mode eqvclass__same_eqvclass(in, in, in) is semidet.

	% Return the set of the partitions of the equivalence class.

:- pred eqvclass__partition_set(eqvclass(T), set(set(T))).
:- mode eqvclass__partition_set(in, out) is det.

	% Return a list of the partitions of the equivalence class.

:- pred eqvclass__partition_list(eqvclass(T), list(set(T))).
:- mode eqvclass__partition_list(in, out) is det.

	% Create an equivalence class from a partition set.
	% It is an error if the sets are not disjoint.

:- pred eqvclass__partition_set_to_eqvclass(set(set(T)), eqvclass(T)).
:- mode eqvclass__partition_set_to_eqvclass(in, out) is det.

	% Create an equivalence class from a list of partitions.
	% It is an error if the sets are not disjoint.

:- pred eqvclass__partition_list_to_eqvclass(list(set(T)), eqvclass(T)).
:- mode eqvclass__partition_list_to_eqvclass(in, out) is det.

%--------------------------------------------------%

float

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: float.m.
% Main author: fjh.
% Stability: medium.
%
% Floating point support.
%
% XXX - What should we do about unification of two Nan's?
%
%--------------------------------------------------%

:- module float.
:- interface.

%
% Arithmetic functions
%

	% addition
:- func float + float = float.
:- mode in    + in    = uo  is det.
:- mode uo    + in    = in  is det.
:- mode in    + uo    = in  is det.

	% subtraction
:- func float - float = float.
:- mode in    - in    = uo  is det.
:- mode uo    - in    = in  is det.
:- mode in    - uo    = in  is det.

	% multiplication
:- func float * float = float.
:- mode in    * in    = uo  is det.
:- mode uo    * in    = in  is det.
:- mode in    * uo    = in  is det.

	% division
:- func float / float = float.
:- mode in    / in    = uo  is det.
:- mode uo    / in    = in  is det.
:- mode in    / uo    = in  is det.

	% unary plus
:- func + float = float.
:- mode + in    = uo  is det.

	% unary minus
:- func - float = float.
:- mode - in    = uo  is det.

%
% Comparison predicates
%

	% less than
:- pred <(float, float).
:- mode <(in, in) is semidet.

	% greater than
:- pred >(float, float).
:- mode >(in, in) is semidet.

	% less than or equal
:- pred =<(float, float).
:- mode =<(in, in) is semidet.

	% greater than or equal
:- pred >=(float, float).
:- mode >=(in, in) is semidet.

%
% Conversion functions
%

	% Convert int to float
:- func float(int) = float.

	% ceiling_to_int(X) returns the
	% smallest integer not less than X.
:- func ceiling_to_int(float) = int.

	% floor_to_int(X) returns the
	% largest integer not greater than X.
:- func floor_to_int(float) = int.

	% round_to_int(X) returns the integer closest to X.
	% If X has a fractional value of 0.5, it is rounded up.
:- func round_to_int(float) = int.

	% truncate_to_int(X) returns 
	% the integer closest to X such that |truncate_to_int(X)| =< |X|.
:- func truncate_to_int(float) = int.

%
% Miscellaneous functions
%

	% absolute value
:- func abs(float) = float.

	% maximum
:- func max(float, float) = float.

	% minimum
:- func min(float, float) = float.

	% pow(Base, Exponent) returns Base raised to the power Exponent.
	% The exponent must be an integer greater or equal to 0.
	% Currently this function runs at O(n), where n is the value
	% of the exponent.
:- func pow(float, int) = float.

	% Compute a non-negative integer hash value for a float.
	% (Note: the hash values computed by the Mercury implementation of
	% this predicate are different to those computed by the Prolog
	% implementation.)
:- func hash(float) = int.

%
% System constants
%

	% Maximum floating-point number
:- func float__max = float.

	% Minimum normalised floating-point number
:- func float__min = float.

	% Smallest number x such that 1.0 + x \= 1.0
:- func float__epsilon = float.

%--------------------------------------------------%

% Predicate versions of the functions declared above.
% These are intended for use in programs that need to work
% in both Prolog and Mercury (e.g. for debugging).
% These predicate versions will eventually become obsolete.

%
% Conversion predicates
%

	% float__ceiling_to_int(X, Ceil) is true if Ceil is the
	% smallest integer not less than X.
:- pred float__ceiling_to_int(float, int).
:- mode float__ceiling_to_int(in, out) is det.

	% float__floor_to_int(X, Ceil) is true if Ceil is the
	% largest integer not greater than X.
:- pred float__floor_to_int(float, int).
:- mode float__floor_to_int(in, out) is det.

	% float__round_to_int(X, Round) is true if Round is the
	% integer closest to X.  If X has a fractional value of
	% 0.5, it is rounded up.
:- pred float__round_to_int(float, int).
:- mode float__round_to_int(in, out) is det.

	% float__truncate_to_int(X, Trunc) is true if Trunc is
	% the integer closest to X such that |Trunc| =< |X|.
:- pred float__truncate_to_int(float, int).
:- mode float__truncate_to_int(in, out) is det.

%
% Miscellaneous predicates
%

	% absolute value
:- pred float__abs(float, float).
:- mode float__abs(in, out) is det.

	% maximum
:- pred float__max(float, float, float).
:- mode float__max(in, in, out) is det.

	% minimum
:- pred float__min(float, float, float).
:- mode float__min(in, in, out) is det.

	% float__pow(Base, Exponent, Answer) is true iff Answer is
	% Base raised to the power Exponent.  The exponent must be an 
	% integer greater or equal to 0.  Currently this function runs
	% at O(n), where n is the value of the exponent.
:- pred float__pow(float, int, float).
:- mode float__pow(in, in, out) is det.

	% Compute a non-negative integer hash value for a float.
	% (Note: the hash values computed by the Mercury implementation of
	% this predicate are different to those computed by the Prolog
	% implementation.)
:- pred float__hash(float, int).
:- mode float__hash(in, out) is det.

%
% System constant predicates
%

	% Maximum floating-point number
:- pred float__max(float).
:- mode float__max(out) is det.

	% Minimum normalised floating-point number
:- pred float__min(float).
:- mode float__min(out) is det.

	% Smallest number x such that 1.0 + x \= 1.0
:- pred float__epsilon(float).
:- mode float__epsilon(out) is det.

%--------------------------------------------------%
%--------------------------------------------------%

getopt

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%--------------------------------------------------%

% File: getopt.m
% Authors: fjh, zs
% Stability: medium

% This module exports the predicate getopt__process_options/4,
% which can be used to parse command-line options.
%
% This version allows both short (single-character) options
% and GNU-style long options. It also has the GNU extension
% of recognizing options anywhere in the command-line, not
% just at the start.
%
% To use this module, you must provide an `option' type which
% is an enumeration of all your different options.
% You must provide predicates `short_option(Char, Option)'
% and `long_option(String, Option)' which convert the short
% and/or long names for the option to this enumeration type.
% (An option can have as many names as you like, long or short.)
% You must provide a predicate `option_default(Option, OptionData)'
% which specifies both the type and the default value for every option.
% We support five different option types: bool, int, string, maybe_string
% (which have either a value of `no' or `yes(string)'), and
% "accumulating" (which accumulates a list of strings).
% For the first four option types, if there are multiple occurrences
% of the same option on the command-line, then the last (right-most)
% occurrence will take precedence.  For "accumulating" options,
% multiple occurrences will be appended together into a list.
% Single-character boolean or maybe-string options can be negated by
% following them with another `-', e.g. `-x-' will negate the `-x' option.
% Long boolean or maybe-string options can be negated by preceding them with
% `--no-', e.g. `--no-foo' will negate the `--foo' option.

:- module getopt.
:- interface.
:- import_module bool, char, list, map, std_util.

% getopt__process_options(OptionOps, Args, NonOptionArgs, Result)
%
%	Scans through 'Args' looking for options, places all the
%	non-option arguments in 'NonOptionArgs', and records the
%	options in the OptionTable.  OptionTable is a map from 
%	a user-defined option type to option_data.
%	If an invalid option is encountered, we return error(Message)
%	otherwise we return ok(OptionTable) in 'Result'.
% 
%	The argument `OptionOps' is a structure holding three or four
%	predicates used to categorize a set of options. Their
%	interfaces should be like these:
%
% :- pred short_option(char::in, option::out) is semidet.
% 	True if the character names a valid single-character option.
%
% :- pred long_option(string::in, option::out) is semidet.
%	True if the character names a valid long option.
%
% :- pred option_default(option::out, option_data::out) is nondet.
%	Nondeterministically returns all the options with their
%	corresponding types and default values.
%
% :- pred special_handler(option::in, special_data::in,
%	option_table::in, maybe_option_table::out) is semidet.
%	This predicate is invoked whenever getopt finds an option
%	(long or short) designated as special, with special_data holding
%	the argument of the option (if any). The predicate can change the
%	option table in arbitrary ways in the course of handling the option,
%	or it can return an error message.
%	The canonical examples of special options are -O options in compilers,
%	which set many other options at once.

:- pred getopt__process_options(
		option_ops(OptionType)::in(option_ops),
		list(string)::in,
		list(string)::out,
		maybe_option_table(OptionType)::out
	) is det.

:- type option_ops(OptionType)
	--->	option_ops(
			pred(char, OptionType),		% short_option
			pred(string, OptionType),	% long_option
			pred(OptionType, option_data)	% option_default
		)
	;	option_ops(
			pred(char, OptionType),		% short_option
			pred(string, OptionType),	% long_option
			pred(OptionType, option_data),	% option_default
			pred(OptionType, special_data,	% special option handler
				option_table(OptionType),
				maybe_option_table(OptionType))
		).

:- inst option_ops =
	bound((
		option_ops(
			pred(in, out) is semidet,	% short_option
			pred(in, out) is semidet,	% long_option
			pred(out, out) is nondet	% option_default
		)
	;	option_ops(
			pred(in, out) is semidet,	% short_option
			pred(in, out) is semidet,	% long_option
			pred(out, out) is nondet,	% option_default
			pred(in, in, in, out) is semidet% special handler
		)
	)).

:- type option_data
	--->	bool(bool)
	;	int(int)
	;	string(string)
	;	maybe_string(maybe(string))
	;	accumulating(list(string))
	;	special
	;	bool_special
	;	int_special
	;	string_special.

:- type special_data
	--->	none
	;	bool(bool)
	;	int(int)
	;	string(string).

:- type option_table(OptionType)
	==	map(OptionType, option_data).

:- type maybe_option_table(OptionType)
	--->	ok(option_table(OptionType))
	;	error(string).

	% The following three predicates search the option table for
	% an option of the specified type; if it is not found, they
	% report an error by calling error/1.

:- pred getopt__lookup_bool_option(option_table(Option), Option, bool).
:- mode getopt__lookup_bool_option(in, in, out) is det.

:- pred getopt__lookup_int_option(option_table(Option), Option, int).
:- mode getopt__lookup_int_option(in, in, out) is det.

:- pred getopt__lookup_string_option(option_table(Option), Option, string).
:- mode getopt__lookup_string_option(in, in, out) is det.

:- pred getopt__lookup_maybe_string_option(option_table(Option), Option,
		maybe(string)).
:- mode getopt__lookup_maybe_string_option(in, in, out) is det.

:- pred getopt__lookup_accumulating_option(option_table(Option), Option,
		list(string)).
:- mode getopt__lookup_accumulating_option(in, in, out) is det.

%--------------------------------------------------%

graph

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: graph.m.
% Main author: conway.
% Stability: low.
%
% This module defines a directed graph data type. The type graph(N, A)
% stores information of type N in the nodes, and information of type A
% in the arcs.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module graph.

:- interface.
:- import_module set, std_util.

	% graph(Node, Arc) represents a directed graph with information of
	% type Node associated with each node, and information of type Arc
	% associated with each arc.
:- type graph(N, A).

:- type node(N).

:- type arc(A).

	% Lots of graphs don't need to store anything in the arcs so here's
	% a type equivalence that only has `real' information in the nodes.
:- type graph(N)	== graph(N, unit).

:- type arc		== arc(unit).

	% graph__init(Graph) binds Graph to an empty graph
	% containing no nodes and no arcs. (The graph contains
	% a counter of the number of nodes allocated in it, so
	% it is possible for a graph to contain no nodes or arcs
	% and still fail to unify with the binding of Graph from
	% graph__init.)
:- pred graph__init(graph(N, A)).
:- mode graph__init(out) is det.

	% graph__set_node(OldGraph, NodeInfo, Node, NewGraph) takes
	% OldGraph and NodeInfo which is the information to be stored
	% in a new node, and returns a key "Node" which refers to that
	% node, and the new graph NewGraph containing all of the nodes
	% and arcs in OldGraph as well as the new node.
	% It is possible to have two nodes in the graph with the
	% same information stored in them.
	%
	% This operation is O(lgN) for a graph containing N nodes.
:- pred graph__set_node(graph(N, A), N, node(N), graph(N, A)).
:- mode graph__set_node(in, in, out, out) is det.

	% graph__insert_node/4 is the same as graph__set_node/4 except
	% that if the information to be stored in the node is stored
	% in another node, then the graph__insert_node/4 fails.
	%
	% This operation is O(N) for a graph containing N nodes since
	% this predicate has to check that the node data isn't in an
	% existing node.
:- pred graph__insert_node(graph(N, A), N, node(N), graph(N, A)).
:- mode graph__insert_node(in, in, out, out) is semidet.

	% graph__det_insert_node/4 is like graph__insert_node, except
	% that if the insertion would fail, it calls error/1.
:- pred graph__det_insert_node(graph(N, A), N, node(N), graph(N, A)).
:- mode graph__det_insert_node(in, in, out, out) is det.

	% graph__search_node(Graph, NodeInfo, Node) nondeterministically
	% produces bindings of Node such that Node is a node in Graph
	% that has the information NodeInfo attatched to it.
	%
	% This operation is O(lgN) for the first solution for a graph
	% containing N nodes.
:- pred graph__search_node(graph(N, A), N, node(N)).
:- mode graph__search_node(in, in, out) is nondet.

	% graph__find_matching_nodes(Graph, NodeInfo, Nodes) takes a graph
	% Graph and the information NodeInfo and returns the set of nodes
	% Nodes which have the information NodeInfo stored in them. (The set
	% Nodes will of course be empty if there are no matching nodes.)
	%
	% This operation is O(NlgN) for a graph containing N nodes.
:- pred graph__find_matching_nodes(graph(N, A), N, set(node(N))).
:- mode graph__find_matching_nodes(in, in, out) is det.

	% graph__node_contents(Graph, Node, NodeInfo) takes Graph and
	% Node and returns the information NodeInfo stored in Node.
	%
	% This operation is O(lgN) for a graph containing N nodes.
:- pred graph__node_contents(graph(N, A), node(N), N).
:- mode graph__node_contents(in, in, out) is det.

	% graph__successors(Graph, Node, Nodes) takes a graph Graph and
	% a node Node and returns the set of nodes Nodes that are reachable
	% (directly - not transitively) from Node.
	%
	% This operation is O(NlgN) for a graph containing N nodes.
:- pred graph__successors(graph(N, A), node(N), set(node(N))).
:- mode graph__successors(in, in, out) is det.

	% graph__nodes(Graph, Nodes) binds Nodes to the set of nodes in Graph.
:- pred graph__nodes(graph(N, A), set(node(N))).
:- mode graph__nodes(in, out) is det.

	% graph__set_edge(OldGraph, Start, End, ArcInfo, Arc, NewGraph)
	% takes a graph OldGraph and adds an arc from Start to End with
	% the information ArcInfo stored in it, and returns a key for
	% that arc Arc, and the new graph NewGraph.
	% If an identical arc already exists then this operation has
	% no effect.
	%
	% This operation is O(lgN+lgM) for a graph with N nodes and M arcs.
:- pred graph__set_edge(graph(N, A), node(N), node(N), A,
						arc(A), graph(N, A)).
:- mode graph__set_edge(in, in, in, in, out, out) is det.

	% graph__insert_edge/6 is the same as graph__set_edge/6 except that
	% if an identical arc already exists in the graph the operation fails.
	% This is O(N) for a graph with N edges between the two nodes.
:- pred graph__insert_edge(graph(N, A), node(N), node(N), A,
						arc(A), graph(N, A)).
:- mode graph__insert_edge(in, in, in, in, out, out) is semidet.

	% graph__det_insert_edge/6 is like graph__insert_edge except
	% than instead of failing, it calls error/1.
:- pred graph__det_insert_edge(graph(N, A), node(N), node(N), A,
						arc(A), graph(N, A)).
:- mode graph__det_insert_edge(in, in, in, in, out, out) is det.

	% graph__arc_contents(Graph, Arc, Start, End, ArcInfo) takes a
	% graph Graph and an arc Arc and returns the start and end nodes
	% and the information stored in that arc.
:- pred graph__arc_contents(graph(N, A), arc(A), node(N), node(N), A).
:- mode graph__arc_contents(in, in, out, out, out) is det.

	% graph__path(Graph, Start, End, Path) is true iff there is a path
	% from the node Start to the node End in Graph that goes through
	% the sequence of arcs Arcs.
	% The algorithm will return paths containing at most one cycle.
:- pred graph__path(graph(N, A), node(N), node(N), list(arc(A))).
:- mode graph__path(in, in, in, out) is nondet.
:- mode graph__path(in, in, out, out) is nondet.

%--------------------------------------------------%

group

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% file: group.m.
% main author: conway.
% stability: low.
%
% This module is probably not terribly useful, and it may not be supported
% in future releases.
%
% The `group' module provides a facility for handling a partitioned set.
% A group is a set of sets of elements, where each element is unique within
% the scope of the group. The module provides moderately efficient ways for
% manipulating groups and elements.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module group.

:- interface.

:- import_module set, list, assoc_list.

:- type group(T).

:- type group__key.

	% Create an empty group

:- pred group__init(group(T)).
:- mode group__init(out) is det.

	% Insert a set of elements into the group.

:- pred group__insert(group(T), set(T), group(T)).
:- mode group__insert(in, in, out) is det.

	% Given an element, get the set containing that element.

:- pred group__group(group(T), T, set(T)).
:- mode group__group(in, in, out) is det.

	% Convert the group to a set of sets.

:- pred group__to_set(group(T), set(set(T))).
:- mode group__to_set(in, out) is det.

:- pred group__sets_and_keys(group(T), assoc_list(set(T), group__key)).
:- mode group__sets_and_keys(in, out) is det.

	% Given an element, get the key for the group containing
	% that element.

:- pred group__group_key(group(T), T, group__key).
:- mode group__group_key(in, in, out) is det.

	% Given a group key, get the corresponding set of elements.

:- pred group__key_group(group(T), group__key, set(T)).
:- mode group__key_group(in, in, out) is det.

	% Remove a set from the group, and return the set.

:- pred group__remove_group(group(T), group__key, set(T), group(T)).
:- mode group__remove_group(in, in, out, out) is det.

	% Test to see if two elements are in the same set.

:- pred group__same_group(group(T), T, T).
:- mode group__same_group(in, in, in) is semidet.

:- pred group__largest_group_key(group(T), group__key).
:- mode group__largest_group_key(in, out) is det.

:- pred group__group_keys(group(T), list(group__key)).
:- mode group__group_keys(in, out) is det.

%--------------------------------------------------%
%--------------------------------------------------%

int

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% int - some predicates for dealing with machine-size integer numbers.
%
% Main authors: conway, fjh.
% Stability: medium.
%
%--------------------------------------------------%

:- module int.

:- interface.

	% less than
:- pred int < int.
:- mode in  < in is semidet.

	% greater than
:- pred int > int.
:- mode in  > in is semidet.

	% less than or equal
:- pred int =< int.
:- mode in  =< in is semidet.

	% greater than or equal
:- pred int >= int.
:- mode in >= in is semidet.

	% absolute value
:- pred int__abs(int, int).
:- mode int__abs(in, out) is det.

	% maximum
:- pred int__max(int, int, int).
:- mode int__max(in, in, out) is det.

	% minimum
:- pred int__min(int, int, int).
:- mode int__min(in, in, out) is det.

	% conversion of integer to floating point
:- pred int__to_float(int, float) is det.
:- mode int__to_float(in, out) is det.

	% expontiation
	% int__pow(X, Y, Z): Z is X raised to the Yth power
	% Y must not be negative.
:- pred int__pow(int, int, int).
:- mode int__pow(in, in, out) is det.

	% base 2 logarithm
	% int__log2(X, N): N is the least integer such that 2 to the power N
	% is greater than or equal to X.  X must be positive.
:- pred int__log2(int, int).
:- mode int__log2(in, out) is det.

	% addition
:- func int + int = int.
:- mode in  + in  = uo  is det.
:- mode uo  + in  = in  is det.
:- mode in  + uo  = in  is det.

	% multiplication
:- func int * int = int.
:- mode in  * in  = uo  is det.
/*
% XXX need to change code_util.m before adding these modes
:- mode in  * in  = in  is semidet.
:- mode in  * in  = uo  is det.
:- mode uo  * in  = in  is semidet.
:- mode in  * uo  = in  is semidet.
*/

	% subtraction
:- func int - int = int.
:- mode in  - in  = uo  is det.
:- mode uo  - in  = in  is det.
:- mode in  - uo  = in  is det.

	% flooring integer division
	% truncates towards minus infinity, e.g. (-10) // 3 = (-4).
:- func div(int, int) = int.
:- mode div(in, in) = uo is det.

	% truncating integer division
	% truncates towards zero, e.g. (-10) // 3 = (-3).
	% `div' has nicer mathematical properties for negative operands,
	% but `//' is typically more efficient.
:- func int // int = int.
:- mode in  // in  = uo  is det.

	% modulus
	% X mod Y = X - (X div Y) * Y
:- func int mod int = int.
:- mode in  mod in  = uo  is det.

	% remainder
	% X rem Y = X - (X // Y) * Y
	% `mod' has nicer mathematical properties for negative X,
	% but `rem' is typically more efficient.
:- func int rem int = int.
:- mode in rem in = uo is det.

	% left shift
:- func int << int = int.
:- mode in  << in  = uo  is det.

	% (arithmetic) right shift
:- func int >> int = int.
:- mode in  >> in  = uo  is det.

	% bitwise and
:- func int /\ int = int.
:- mode in  /\ in  = uo  is det.

	% bitwise or
:- func int \/ int = int.
:- mode in  \/ in  = uo  is det.

	% bitwise exclusive or (xor)
:- func int ^ int = int.
:- mode in  ^ in  = uo  is det.

	% bitwise complement
:- func \ int = int.
:- mode \ in  = uo  is det.

	% unary plus
:- func + int = int.
:- mode + in = uo is det.

	% unary minus
:- func - int = int.
:- mode - in = uo is det.

	% is/2, for backwards compatiblity with Prolog (and with
	% early implementations of Mercury)
:- pred is(T, T) is det.
:- mode is(uo, di) is det.
:- mode is(out, in) is det.

	% int__max_int(Max) binds Max to the maximum value of an int
	% on this machine.
:- pred int__max_int(int::out) is det.

	% int__min_int(Max) binds Min to the minimum value of an int
	% on this machine.
:- pred int__min_int(int::out) is det.

	% int__bits_per_int(Bits) binds Bits to the number of bits in an int
	% on this machine.
:- pred int__bits_per_int(int::out) is det.

/* The following routines are builtins that the compiler knows about.
   Don't use them; use the functions above.
   These will go away in some future release.
*/

:- pred builtin_plus(int, int, int).
:- mode builtin_plus(in, in, uo) is det.
:- mode builtin_plus(in, in, uo) is det.

:- pred builtin_unary_plus(int, int).
:- mode builtin_unary_plus(in, uo) is det.

:- pred builtin_minus(int, int, int).
:- mode builtin_minus(in, in, uo) is det.

:- pred builtin_unary_minus(int, int).
:- mode builtin_unary_minus(in, uo) is det.

:- pred builtin_times(int, int, int).
:- mode builtin_times(in, in, uo) is det.

:- pred builtin_div(int, int, int).
:- mode builtin_div(in, in, uo) is det.

:- pred builtin_mod(int, int, int).
:- mode builtin_mod(in, in, uo) is det.

:- pred builtin_left_shift(int, int, int).
:- mode builtin_left_shift(in, in, uo) is det.

:- pred builtin_right_shift(int, int, int).
:- mode builtin_right_shift(in, in, uo) is det.

:- pred builtin_bit_or(int, int, int).
:- mode builtin_bit_or(in, in, uo) is det.

:- pred builtin_bit_and(int, int, int).
:- mode builtin_bit_and(in, in, uo) is det.

:- pred builtin_bit_xor(int, int, int).
:- mode builtin_bit_xor(in, in, uo) is det.

:- pred builtin_bit_neg(int, int).
:- mode builtin_bit_neg(in, uo) is det.

io

%--------------------------------------------------%
% Copyright (C) 1993-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: io.m.
% Main author: fjh.
% Stability: medium to high.
%
% This file encapsulates all the file I/O.
% We implement a purely logical I/O system using non-logical I/O primitives
% of the underlying system (C or Prolog).
% The logicalness is ensured by passing around a "state-of-the-world"
% argument using unique modes.  The compiler will check that the state
% of the world argument is properly single-threaded, and will also check
% to ensure that you don't attempt to backtrack over any I/O.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module io.
:- interface.
:- import_module char, string, std_util, list.

%--------------------------------------------------%

% External interface: imported predicate

% :- pred main(io__state, io__state).
% :- mode main(di, uo) is det.
%	main(IOState0, IOState1).
%		This module provides startup code which calls main/2.

%--------------------------------------------------%

% Exported types

	% The state of the universe.

:- type io__state.

	% Opaque handles for text I/O streams.

:- type io__input_stream.

:- type io__output_stream.

	% Opaque handles for binary I/O streams.

:- type io__binary_input_stream		==	io__binary_stream.

:- type io__binary_output_stream	==	io__binary_stream.

:- type io__binary_stream.

	% Various types used for the result from the access predicates

:- type io__res		--->	ok
			;	error(io__error).

:- type io__res(T)	--->	ok(T)
			;	error(io__error).

:- type io__result	--->	ok
			;	eof
			;	error(io__error).

:- type io__result(T)	--->	ok(T)
			;	eof
			;	error(io__error).

:- type io__read_result(T)	--->	ok(T)
				;	eof
				;	error(string, int).
					% error message, line number

:- type io__error.	% Use io__error_message to decode it.

	% Poly-type is used for io__write_many and io__format,
	% which do printf-like formatting.

:- type io__poly_type == string__poly_type.
%			--->
%		c(char)
%	;	s(string)
%	;	i(int)
%	;	f(float).
%

	% io__whence denotes the base for a seek operation.
	% 	set	- seek relative to the start of the file
	%	cur	- seek relative to the current position in the file
	%	end	- seek relative to the end of the file.

:- type io__whence
	--->	set
	;	cur
	;	end
	.

%--------------------------------------------------%

% Text input predicates.

:- pred io__read_char(io__result(char), io__state, io__state).
:- mode io__read_char(out, di, uo) is det.
%		Reads a character from the current input stream.

:- pred io__read_word(io__result(list(char)), io__state, io__state).
:- mode io__read_word(out, di, uo) is det.
%		Reads a whitespace delimited word from the current input stream.

:- pred io__read_line(io__result(list(char)), io__state, io__state).
:- mode io__read_line(out, di, uo) is det.
%		Reads a line from the current input stream.

:- pred io__read_file(io__result(list(char)), io__state, io__state).
:- mode io__read_file(out, di, uo) is det.
%		Reads all the characters from the current input stream until
%		eof or error.

:- pred io__putback_char(char, io__state, io__state).
:- mode io__putback_char(in, di, uo) is det.
%		Un-reads a character from the current input stream.
%		You can put back as many characters as you like.
%		You can even put back something that you didn't actually read.

:- pred io__read_char(io__input_stream, io__result(char),
				io__state, io__state).
:- mode io__read_char(in, out, di, uo) is det.
%		Reads a character from specified stream.

:- pred io__read_word(io__input_stream, io__result(list(char)),
							io__state, io__state).
:- mode io__read_word(in, out, di, uo) is det.
%		Reads a whitespace delimited word from specified stream.

:- pred io__read_line(io__input_stream, io__result(list(char)),
							io__state, io__state).
:- mode io__read_line(in, out, di, uo) is det.
%		Reads a line from specified stream.

:- pred io__read_file(io__input_stream, io__result(list(char)),
							io__state, io__state).
:- mode io__read_file(in, out, di, uo) is det.
%		Reads all the characters from the given input stream until
%		eof or error.

:- pred io__putback_char(io__input_stream, char, io__state, io__state).
:- mode io__putback_char(in, in, di, uo) is det.
%		Un-reads a character from specified stream.
%		You can put back as many characters as you like.
%		You can even put back something that you didn't actually read.

:- pred io__read(io__read_result(T), io__state, io__state).
:- mode io__read(out, di, uo) is det.
:- pred io__read(io__input_stream, io__read_result(T), io__state, io__state).
:- mode io__read(in, out, di, uo) is det.
%		Reads a ground term of any type, written using standard
%		Mercury syntax, from the current or specified input stream.
%		The type of the term read is determined by the context
%		in which `io__read' is used.
%		If there are no more non-whitespace characters before the
%		end of file, then `io__read' returns `eof'.
%		If it can read in a syntactically correct ground term
%		of the correct type, then it returns `ok(Term)'.
%		If characters on the input stream (up to the next `.' that
%		is followed by whitespace) do not form a syntactically
%		correct term, or if the term read is not a ground term,
%		if the term is not a valid term of the appropriate type,
%		or if encounters an I/O error, then it returns
%		`error(Message, LineNumber)'.

:- pred io__ignore_whitespace(io__result, io__state, io__state).
:- mode io__ignore_whitespace(out, di, uo) is det.
%		Discards all the whitespace from the current stream.

:- pred io__ignore_whitespace(io__input_stream, io__result,
				io__state, io__state).
:- mode io__ignore_whitespace(in, out, di, uo) is det.
%		Discards all the whitespace from the specified stream.



%--------------------------------------------------%

% Text output predicates.

:- pred io__print(T, io__state, io__state).
:- mode io__print(in, di, uo) is det.
:- pred io__print(io__output_stream, T, io__state, io__state).
:- mode io__print(in, in, di, uo) is det.
%		io__print/3 writes its argument to the current output stream.
%		io__print/4 writes its argument to the specified output
%		stream.  In either case, the argument may be of any type.
%		The argument is written in a format that is intended to
%		be human-readable. 
%
%		If the argument is just a single string or character, it
%		will be printed out exactly as is (unquoted).
%		If the argument is of type univ, then it will print out
%		the value stored in the univ, but not the type.
%		For higher-order types, or for types defined using the
%		foreign language interface (pragma c_code), the text output
%		will only describe the type that is being printed, not the
%		value.

:- pred io__write(T, io__state, io__state).
:- mode io__write(in, di, uo) is det.
:- pred io__write(io__output_stream, T, io__state, io__state).
:- mode io__write(in, in, di, uo) is det.
%		io__write/3 writes its argument to the current output stream.
%		io__write/4 writes its argument to the specified output stream.
%		The argument may be of any type.
%		The argument is written in a format that is intended to
%		be valid Mercury syntax whenever possible.
%
%		Strings and characters are always printed out in quotes,
%		using backslash escapes if necessary.
%		For higher-order types, or for types defined using the
%		foreign language interface (pragma c_code), the text output
%		will only describe the type that is being printed, not the
%		value, and the result may not be parsable by io__read.
%		But in all other cases the format used is standard Mercury
%		syntax, and if you do append a period and newline (".\n"),
%		then the results can be read in again using `io__read'.

:- pred io__nl(io__state, io__state).
:- mode io__nl(di, uo) is det.
%		Writes a newline character to the current output stream.

:- pred io__nl(io__output_stream, io__state, io__state).
:- mode io__nl(in, di, uo) is det.
%		Writes a newline character to the specified output stream.

:- pred io__write_string(string, io__state, io__state).
:- mode io__write_string(in, di, uo) is det.
%		Writes a string to the current output stream.

:- pred io__write_string(io__output_stream, string, io__state, io__state).
:- mode io__write_string(in, in, di, uo) is det.
%		Writes a string to the specified output stream.

:- pred io__write_strings(list(string), io__state, io__state).
:- mode io__write_strings(in, di, uo) is det.
%		Writes a list of strings to the current output stream.

:- pred io__write_strings(io__output_stream, list(string),
				io__state, io__state).
:- mode io__write_strings(in, in, di, uo) is det.
%		Writes a list of strings to the specified output stream.

:- pred io__write_char(char, io__state, io__state).
:- mode io__write_char(in, di, uo) is det.
%		Writes a character to the current output stream.

:- pred io__write_char(io__output_stream, char, io__state, io__state).
:- mode io__write_char(in, in, di, uo) is det.
%		Writes a character to the specified output stream.

:- pred io__write_int(int, io__state, io__state).
:- mode io__write_int(in, di, uo) is det.
%		Writes an integer to the current output stream.

:- pred io__write_int(io__output_stream, int, io__state, io__state).
:- mode io__write_int(in, in, di, uo) is det.
%		Writes an integer to the specified output stream.

:- pred io__write_float(float, io__state, io__state).
:- mode io__write_float(in, di, uo) is det.
%	io__write_float(Float, IO0, IO1).
%		Writes a floating point number to the current output stream.

:- pred io__write_float(io__output_stream, float, io__state, io__state).
:- mode io__write_float(in, in, di, uo) is det.
%	io__write_float(Float, IO0, IO1).
%		Writes a floating point number to the specified output stream.

:- pred io__format(string, list(io__poly_type), io__state, io__state).
:- mode io__format(in, in, di, uo) is det.
%	io__format(FormatString, Arguments, IO0, IO).
%		Formats the specified arguments according to
%		the format string, using string__format, and
%		then writes the result to the current output stream.
%		(See the documentation of string__format for details.)

:- pred io__format(io__output_stream, string, list(io__poly_type),
		io__state, io__state).
:- mode io__format(in, in, in, di, uo) is det.
%	io__format(Stream, FormatString, Arguments, IO0, IO).
%		Formats the specified argument list according to
%		the format string, using string__format, and
%		then writes the result to the specified output stream.
%		(See the documentation of string__format for details.)

:- pred io__write_many(list(io__poly_type), io__state, io__state).
:- mode io__write_many(in, di, uo) is det.
%	io__write_many(Arguments, IO0, IO).
%		Writes the specified arguments to the current output stream.

:- pred io__write_many(io__output_stream, list(io__poly_type),
			io__state, io__state).
:- mode io__write_many(in, in, di, uo) is det.
%	io__write_many(Stream, Arguments, IO0, IO).
%		Writes the specified arguments to the specified output stream.

:- pred io__write_list(list(T), string, pred(T, io__state, io__state),
	io__state, io__state).
:- mode io__write_list(in, in, pred(in, di, uo) is det, di, uo) is det.
	% io__write_list(List, Separator, OutputPred, IO0, IO)
	% applies OutputPred to each element of List, printing Separator
	% between each element. Outputs to the current output stream.

:- pred io__write_list(io__output_stream, list(T), string, 
	pred(T, io__state, io__state), io__state, io__state).
:- mode io__write_list(in, in, in, pred(in, di, uo) is det, di, uo) is det.
	% io__write_list(Stream, List, Separator, OutputPred, IO0, IO)
	% applies OutputPred to each element of List, printing Separator
	% between each element. Outputs to Stream.

:- pred io__flush_output(io__state, io__state).
:- mode io__flush_output(di, uo) is det.
%	Flush the output buffer of the current output stream.

:- pred io__flush_output(io__output_stream, io__state, io__state).
:- mode io__flush_output(in, di, uo) is det.
%	Flush the output buffer of the specified output stream.

%--------------------------------------------------%

% Input text stream predicates.

:- pred io__see(string, io__res, io__state, io__state).
:- mode io__see(in, out, di, uo) is det.
%	io__see(File, Result, IO0, IO1).
%		Attempts to open a file for input, and if successful
%		sets the current input stream to the newly opened stream.
%		Result is either 'ok' or 'error'.

:- pred io__seen(io__state, io__state).
:- mode io__seen(di, uo) is det.
%		Closes the current input stream.
%		The current input stream reverts to standard input.

:- pred io__open_input(string, io__res(io__input_stream),
			io__state, io__state).
:- mode io__open_input(in, out, di, uo) is det.
%	io__open_input(File, Result, IO0, IO1).
%		Attempts to open a file for input.
%		Result is either 'ok(Stream)' or 'error(ErrorCode)'.

:- pred io__close_input(io__input_stream, io__state, io__state).
:- mode io__close_input(in, di, uo) is det.
%	io__close_input(File, IO0, IO1).
%		Closes an open input stream.

:- pred io__input_stream(io__input_stream, io__state, io__state).
:- mode io__input_stream(out, di, uo) is det.
%		Retrieves the current input stream.
%		Does not modify the IO state.

:- pred io__set_input_stream(io__input_stream, io__input_stream,
				io__state, io__state).
:- mode io__set_input_stream(in, out, di, uo) is det.
%       io__set_input_stream(NewStream, OldStream, IO0, IO1)
%		Changes the current input stream to the stream specified.
%		Returns the previous stream.

:- pred io__stdin_stream(io__input_stream, io__state, io__state).
:- mode io__stdin_stream(out, di, uo) is det.
%		Retrieves the standard input stream.
%		Does not modify the IO state.

:- pred io__input_stream_name(string, io__state, io__state).
:- mode io__input_stream_name(out, di, uo) is det.
%	Retrieves the human-readable name associated with the current input
%	stream.
%	For file streams, this is the filename.
%	For stdin this is the string "<standard input>".

:- pred io__input_stream_name(io__input_stream, string, io__state, io__state).
:- mode io__input_stream_name(in, out, di, uo) is det.
%	Retrieves the human-readable name associated with the specified input
%	stream.
%	For file streams, this is the filename.
%	For stdin this is the string "<standard input>".

:- pred io__get_line_number(int, io__state, io__state).
:- mode io__get_line_number(out, di, uo) is det.
%	Return the line number of the current input stream.
%	Lines are normally numbered starting at 1
%	(but this can be overridden by calling io__set_line_number).

:- pred io__get_line_number(io__input_stream, int, io__state, io__state).
:- mode io__get_line_number(in, out, di, uo) is det.
%	Return the line number of the specified input stream.
%	Lines are normally numbered starting at 1
%	(but this can be overridden by calling io__set_line_number).

:- pred io__set_line_number(int, io__state, io__state).
:- mode io__set_line_number(in, di, uo) is det.
%	Set the line number of the current input stream.

:- pred io__set_line_number(io__input_stream, int, io__state, io__state).
:- mode io__set_line_number(in, in, di, uo) is det.
%	Set the line number of the specified input stream.

%--------------------------------------------------%

% Output text stream predicates.

:- pred io__tell(string, io__res, io__state, io__state).
:- mode io__tell(in, out, di, uo) is det.
%	io__tell(File, Result, IO0, IO1).
%		Attempts to open a file for output, and if successful
%		sets the current output stream to the newly opened stream.
%		As per Prolog tell/1. Result is either 'ok' or 'error(ErrCode)'.

:- pred io__told(io__state, io__state).
:- mode io__told(di, uo) is det.
%	io__told(IO0, IO1).
%		Closes the current output stream.
%		The default output stream reverts to standard output.
%		As per Prolog told/0.

:- pred io__open_output(string, io__res(io__output_stream),
				io__state, io__state).
:- mode io__open_output(in, out, di, uo) is det.
%	io__open_output(File, Result, IO0, IO1).
%		Attempts to open a file for output.
%		Result is either 'ok(Stream)' or 'error(ErrorCode)'.

:- pred io__open_append(string, io__res(io__output_stream),
				io__state, io__state).
:- mode io__open_append(in, out, di, uo) is det.
%	io__open_append(File, Result, IO0, IO1).
%		Attempts to open a file for appending.
%		Result is either 'ok(Stream)' or 'error(ErrorCode)'.

:- pred io__close_output(io__output_stream, io__state, io__state).
:- mode io__close_output(in, di, uo) is det.
%	io__close_output(File, IO0, IO1).
%		Closes an open output stream.

:- pred io__output_stream(io__output_stream, io__state, io__state).
:- mode io__output_stream(out, di, uo) is det.
%		Retrieves the current output stream.
%		Does not modify the IO state.

:- pred io__set_output_stream(io__output_stream, io__output_stream,
				io__state, io__state).
:- mode io__set_output_stream(in, out, di, uo) is det.
%	io__set_output_stream(NewStream, OldStream, IO0, IO)
%		Changes the current output stream to the stream specified.
%		Returns the previous stream.

:- pred io__stdout_stream(io__output_stream, io__state, io__state).
:- mode io__stdout_stream(out, di, uo) is det.
%		Retrieves the standard output stream.
%		Does not modify the IO state.

:- pred io__stderr_stream(io__output_stream, io__state, io__state).
:- mode io__stderr_stream(out, di, uo) is det.
%		Retrieves the standard error stream.
%		Does not modify the IO state.

:- pred io__output_stream_name(string, io__state, io__state).
:- mode io__output_stream_name(out, di, uo) is det.
%	Retrieves the human-readable name associated with the current
%	output stream.
%	For file streams, this is the filename.
%	For stdout this is the string "<standard output>".
%	For stderr this is the string "<standard error>".

:- pred io__output_stream_name(io__output_stream, string,
				io__state, io__state).
:- mode io__output_stream_name(in, out, di, uo) is det.
%	Retrieves the human-readable name associated with the specified stream.
%	For file streams, this is the filename.
%	For stdout this is the string "<standard output>".
%	For stderr this is the string "<standard error>".

:- pred io__get_output_line_number(int, io__state, io__state).
:- mode io__get_output_line_number(out, di, uo) is det.
%	Return the line number of the current output stream.
%	Lines are normally numbered starting at 1
%	(but this can be overridden by calling io__set_output_line_number).

:- pred io__get_output_line_number(io__output_stream, int,
				io__state, io__state).
:- mode io__get_output_line_number(in, out, di, uo) is det.
%	Return the line number of the specified output stream.
%	Lines are normally numbered starting at 1
%	(but this can be overridden by calling io__set_output_line_number).

:- pred io__set_output_line_number(int, io__state, io__state).
:- mode io__set_output_line_number(in, di, uo) is det.
%	Set the line number of the current output stream.

:- pred io__set_output_line_number(io__output_stream, int,
				io__state, io__state).
:- mode io__set_output_line_number(in, in, di, uo) is det.
%	Set the line number of the specified output stream.


%--------------------------------------------------%

% Binary input predicates.

:- pred io__read_binary(io__result(T), io__state, io__state).
:- mode io__read_binary(out, di, uo) is det.
%		Reads a binary representation of a term of type T
%		from the current binary input stream.

:- pred io__read_binary(io__binary_input_stream, io__result(T),
		io__state, io__state).
:- mode io__read_binary(in, out, di, uo) is det.
%		Reads a binary representation of a term of type T
%		from the specified binary input stream.

%		Note: if you attempt to read a binary representation written
%		by a different program, or a different version of the same
%		program, then the results are not guaranteed to be meaningful.
%		Another caveat is that higher-order types cannot be read. 
%		(If you try, you will get a runtime error.)

:- pred io__read_byte(io__result(int), io__state, io__state).
:- mode io__read_byte(out, di, uo) is det.
%		Reads a single 8-bit byte from the current binary input
%		stream.

:- pred io__read_byte(io__binary_input_stream, io__result(int),
				io__state, io__state).
:- mode io__read_byte(in, out, di, uo) is det.
%		Reads a single 8-bit byte from the specified binary input
%		stream.

:- pred io__read_binary_file(io__result(list(int)), io__state, io__state).
:- mode io__read_binary_file(out, di, uo) is det.
%		Reads all the bytes from the current binary input stream
%		until eof or error.

:- pred io__read_binary_file(io__input_stream, io__result(list(int)),
						io__state, io__state).
:- mode io__read_binary_file(in, out, di, uo) is det.
%		Reads all the bytes from the given binary input stream until
%		eof or error.

:- pred io__putback_byte(int, io__state, io__state).
:- mode io__putback_byte(in, di, uo) is det.
%		Un-reads a byte from the current binary input stream.
%		You can put back as many bytes as you like.
%		You can even put back something that you didn't actually read.
%		The byte is taken from the bottom 8 bits of an integer.

:- pred io__putback_byte(io__binary_input_stream, int, io__state, io__state).
:- mode io__putback_byte(in, in, di, uo) is det.
%		Un-reads a byte from specified binary input stream.
%		You can put back as many bytes as you like.
%		You can even put back something that you didn't actually read.
%		The byte is returned in the bottom 8 bits of an integer.

%--------------------------------------------------%

% Binary output predicates.

% XXX what about wide characters?

:- pred io__write_binary(T, io__state, io__state).
:- mode io__write_binary(in, di, uo) is det.
%		Writes a binary representation of a term to the current
%		binary output stream, in a format suitable for reading
%		in again with io__read_binary.

:- pred io__write_binary(io__binary_output_stream, T, io__state, io__state).
:- mode io__write_binary(in, in, di, uo) is det.
%		Writes a binary representation of a term to the specified
%		binary output stream, in a format suitable for reading
%		in again with io__read_binary.

:- pred io__write_byte(int, io__state, io__state).
:- mode io__write_byte(in, di, uo) is det.
%		Writes a single byte to the current binary output stream.
%		The byte is taken from the bottom 8 bits of an int.

:- pred io__write_byte(io__binary_output_stream, int, io__state, io__state).
:- mode io__write_byte(in, in, di, uo) is det.
%		Writes a single byte to the specified binary output stream.
%		The byte is taken from the bottom 8 bits of an int.

:- pred io__write_bytes(string, io__state, io__state).
:- mode io__write_bytes(in, di, uo) is det.
%		Writes several bytes to the current binary output stream.
%		The bytes are taken from a string.

:- pred io__write_bytes(io__binary_output_stream, string,
				io__state, io__state).
:- mode io__write_bytes(in, in, di, uo) is det.
%		Writes several bytes to the specified binary output stream.
%		The bytes are taken from a string.

:- pred io__flush_binary_output(io__state, io__state).
:- mode io__flush_binary_output(di, uo) is det.
%	Flush the output buffer of the current binary output stream.

:- pred io__flush_binary_output(io__binary_output_stream,
				io__state, io__state).
:- mode io__flush_binary_output(in, di, uo) is det.
%	Flush the output buffer of the specified binary output stream.

:- pred io__seek_binary(io__binary_stream, io__whence, int,
				io__state, io__state).
:- mode io__seek_binary(in, in, in, di, uo) is det.
%	Seek to an offset relative to Whence (documented above)
%	on a specified binary stream. Attempting to seek on a
%	pipe or tty results in implementation dependent behaviour.

:- pred io__binary_stream_offset(io__binary_stream, int,
				io__state, io__state).
:- mode io__binary_stream_offset(in, out, di, uo) is det.
%	Returns the offset (in bytes) into the specified binary stream.

%--------------------------------------------------%

% Binary input stream predicates.

:- pred io__see_binary(string, io__res, io__state, io__state).
:- mode io__see_binary(in, out, di, uo) is det.
%	io__see_binary(File, Result, IO0, IO1).
%		Attempts to open a file for binary input, and if successful
%		sets the current binary input stream to the newly opened stream.
%		Result is either 'ok' or 'error'.

:- pred io__seen_binary(io__state, io__state).
:- mode io__seen_binary(di, uo) is det.
%		Closes the current input stream.
%		The current input stream reverts to standard input.

:- pred io__open_binary_input(string, io__res(io__binary_input_stream),
			io__state, io__state).
:- mode io__open_binary_input(in, out, di, uo) is det.
%	io__open_binary_input(File, Result, IO0, IO1).
%		Attempts to open a binary file for input.
%		Result is either 'ok(Stream)' or 'error(ErrorCode)'.

:- pred io__close_binary_input(io__binary_input_stream, io__state, io__state).
:- mode io__close_binary_input(in, di, uo) is det.
%	io__close_binary_input(File, IO0, IO1).
%		Closes an open binary input stream.

:- pred io__binary_input_stream(io__binary_input_stream,
			io__state, io__state).
:- mode io__binary_input_stream(out, di, uo) is det.
%		Retrieves the current binary input stream.
%		Does not modify the IO state.

:- pred io__set_binary_input_stream(io__binary_input_stream,
			io__binary_input_stream, io__state, io__state).
:- mode io__set_binary_input_stream(in, out, di, uo) is det.
%       io__set_binary_input_stream(NewStream, OldStream, IO0, IO1)
%		Changes the current input stream to the stream specified.
%		Returns the previous stream.

:- pred io__stdin_binary_stream(io__binary_input_stream,
			io__state, io__state).
:- mode io__stdin_binary_stream(out, di, uo) is det.
%		Retrieves the standard binary input stream.
%		Does not modify the IO state.

:- pred io__binary_input_stream_name(string, io__state, io__state).
:- mode io__binary_input_stream_name(out, di, uo) is det.
%	Retrieves the human-readable name associated with the current binary
%	input stream.
%	For file streams, this is the filename.

:- pred io__binary_input_stream_name(io__binary_input_stream, string,
		io__state, io__state).
:- mode io__binary_input_stream_name(in, out, di, uo) is det.
%	Retrieves the human-readable name associated with the specified binary
%	input stream.
%	For file streams, this is the filename.

%--------------------------------------------------%

% Binary output stream predicates.

:- pred io__tell_binary(string, io__res, io__state, io__state).
:- mode io__tell_binary(in, out, di, uo) is det.
%	io__tell_binary(File, Result, IO0, IO1).
%		Attempts to open a file for binary output, and if successful
%		sets the current binary output stream to the newly opened
%		stream. As per Prolog tell/1. Result is either 'ok' or
%		'error(ErrCode)'.

:- pred io__told_binary(io__state, io__state).
:- mode io__told_binary(di, uo) is det.
%	io__told_binary(IO0, IO1).
%		Closes the current binary output stream.
%		The default binary output stream reverts to standard output.
%		As per Prolog told/0.

:- pred io__open_binary_output(string, io__res(io__binary_output_stream),
				io__state, io__state).
:- mode io__open_binary_output(in, out, di, uo) is det.
%	io__open_binary_output(File, Result, IO0, IO1).
%		Attempts to open a file for binary output.
%		Result is either 'ok(Stream)' or 'error(ErrorCode)'.

:- pred io__open_binary_append(string, io__res(io__binary_output_stream),
				io__state, io__state).
:- mode io__open_binary_append(in, out, di, uo) is det.
%	io__open_binary_append(File, Result, IO0, IO1).
%		Attempts to open a file for binary appending.
%		Result is either 'ok(Stream)' or 'error(ErrorCode)'.

:- pred io__close_binary_output(io__binary_output_stream,
				io__state, io__state).
:- mode io__close_binary_output(in, di, uo) is det.
%	io__close_binary_output(File, IO0, IO1).
%		Closes an open binary output stream.

:- pred io__binary_output_stream(io__binary_output_stream,
				io__state, io__state).
:- mode io__binary_output_stream(out, di, uo) is det.
%		Retrieves the current binary output stream.
%		Does not modify the IO state.

:- pred io__stdout_binary_stream(io__binary_output_stream,
				io__state, io__state).
:- mode io__stdout_binary_stream(out, di, uo) is det.
%		Retrieves the standard binary output stream.
%		Does not modify the IO state.

:- pred io__set_binary_output_stream(io__binary_output_stream,
			io__binary_output_stream, io__state, io__state).
:- mode io__set_binary_output_stream(in, out, di, uo) is det.
%	io__set_binary_output_stream(NewStream, OldStream, IO0, IO)
%		Changes the current binary output stream to the stream
%		specified. Returns the previous stream.

:- pred io__binary_output_stream_name(string, io__state, io__state).
:- mode io__binary_output_stream_name(out, di, uo) is det.
%	Retrieves the human-readable name associated with the current
%	binary output stream.
%	For file streams, this is the filename.

:- pred io__binary_output_stream_name(io__binary_output_stream, string,
			io__state, io__state).
:- mode io__binary_output_stream_name(in, out, di, uo) is det.
%	Retrieves the human-readable name associated with the specified 
%	output stream.
%	For file streams, this is the filename.

%--------------------------------------------------%

% Global state predicates.

:- pred io__progname(string, string, io__state, io__state).
:- mode io__progname(in, out, di, uo) is det.
% 	io__progname(DefaultProgname, Progname)
%		Returns the name that the program was invoked with,
%		if available, or DefaultProgname if the name is not
%		available.
%		
%		Does not modify the IO state.

:- pred io__progname_base(string, string, io__state, io__state).
:- mode io__progname_base(in, out, di, uo) is det.
% 	io__progname_base(DefaultProgname, Progname)
%		Like `io__progname', except that it strips off any path name
%		preceding the program name.  Useful for error messages.

:- pred io__command_line_arguments(list(string), io__state, io__state).
:- mode io__command_line_arguments(out, di, uo) is det.
% 	io__command_line_arguments(Args)
%		Returns the arguments that the program was invoked with,
%		if available, otherwise an empty list.
%		
%		Does not modify the IO state.

% The io__state contains an integer used to record the program's exit
% status.  When the program finishes, it will return this exit status to
% the operating system.  The following predicates can be used to get and
% set the exit status.

:- pred io__get_exit_status(int, io__state, io__state).
:- mode io__get_exit_status(out, di, uo) is det.

:- pred io__set_exit_status(int, io__state, io__state).
:- mode io__set_exit_status(in, di, uo) is det.

% The io__state includes a `globals' field which is not used by the I/O
% library, but can be used by the application.  The globals field is
% of type `univ' so that the application can store any data it wants there.
% The following predicates can be used to access this global state.

:- pred io__get_globals(univ, io__state, io__state).
:- mode io__get_globals(uo, di, uo) is det.
	% Doesn't modify the io__state.

:- pred io__set_globals(univ, io__state, io__state).
:- mode io__set_globals(di, di, uo) is det.

% The following predicates provide an interface to the environment list.
% Do not attempt to put spaces or '=' signs in the names of environment
% variables, or bad things may result!

:- pred io__get_environment_var(string, maybe(string), io__state, io__state).
:- mode io__get_environment_var(in, out, di, uo) is det.
	% First argument is the name of the environment variable.
	% Returns yes(Value) if the variable was set (Value will
	% be set to the value of the variable) and no if the
	% variable was not set.

:- pred io__set_environment_var(string, string, io__state, io__state).
:- mode io__set_environment_var(in, in, di, uo) is det.
	% First argument is the name of the environment variable,
	% second argument is the value to be assigned to that
	% variable.  Will abort if the system runs out of environment
	% space.

%--------------------------------------------------%

:- pred io__tmpnam(string, io__state, io__state).
:- mode io__tmpnam(out, di, uo) is det.
	% io__tmpnam(Name, IO0, IO) binds `Name' to a temporary
	% file name which is different to the name of any existing file.
	% It will reside in /tmp if the TMPDIR environment variable
	% is not set, or in the directory specified by TMPDIR if it
	% is set.

:- pred io__tmpnam(string, string, string, io__state, io__state).
:- mode io__tmpnam(in, in, out, di, uo) is det.
	% io__tmpnam(Dir, Prefix, Name, IO0, IO) binds `Name' to a
	% temporary file name which is different to the name of any
	% existing file. It will reside in the directory specified by
	% `Dir' and have a prefix using up to the first 5 characters
	% of `Prefix'.

:- pred io__remove_file(string, io__res, io__state, io__state).
:- mode io__remove_file(in, out, di, uo) is det.
	% io__remove_file(FileName, Result, IO0, IO) attempts to remove the
	% file `FileName', binding Result to ok/0 if it succeeds, or
	% error/1 if it fails.

%--------------------------------------------------%

% Memory management predicates.

	% Write some memory/time usage statistics to stdout.

:- pred io__report_stats(io__state, io__state).
:- mode io__report_stats(di, uo) is det.

	% Preallocate heap space (to avoid NU-Prolog panic).

:- pred io__preallocate_heap_space(int, io__state, io__state).
:- mode io__preallocate_heap_space(in, di, uo) is det.

/*** no longer supported, sorry
:- pred io__gc_call(pred(io__state, io__state), io__state, io__state).
:- mode io__gc_call(pred(di, uo) is det, di, uo) is det.
%	io__gc_call(Goal, IO0, IO1).
%		Execute Goal, passing IO0, and IO1, and
%		collect any garbage created during it's execution.
***/

%--------------------------------------------------%

% Miscellaneous predicates

:- pred io__call_system(string, io__res(int), io__state, io__state).
:- mode io__call_system(in, out, di, uo) is det.
%	io__call_system(Command, Result, IO0, IO1).
%		Invokes the operating system shell with the specified
%		Command.  Result is either `ok(ExitStatus)', if it was
%		possible to invoke the command, or `error(ErrorCode)' if not.
%		The ExitStatus will be 0 if the command completed
%		successfully or the return value of the system call.  If a
%		signal kills the system call, then Result will be an error
%		indicating which signal occured.

:- pred io__error_message(io__error, string).
:- mode io__error_message(in, out) is det.
%	io__error_message(ErrorCode, ErrorMessage).
%		Look up the error message corresponding to a particular error
%		code.

%--------------------------------------------------%

lexer

%--------------------------------------------------%
% Copyright (C) 1993-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% file: lexer.m.
% main author: fjh.
% stability: high.
%
% Lexical analysis.  This module defines the representation of tokens
% and exports predicates for reading in tokens from an input stream.
%
% See ISO Prolog 6.4.  Also see the comments at the top of parser.m.
%
%--------------------------------------------------%

:- module lexer.
:- interface.
:- import_module io.

:- type	token
	--->	name(string)
	;	variable(string)
	;	integer(int)
	;	float(float)
	;	string(string)		% "...."
	;	open			% '('
	;	open_ct			% '(' without any preceding whitespace
	;	close			% ')'
	;	open_list		% '['
	;	close_list		% ']'
	;	open_curly		% '}'
	;	close_curly		% '{'
	;	ht_sep			% '|'
	;	comma			% ','
	;	end			% '.'
	;	junk(char)		% junk character in the input stream
	;	error(string)		% some other invalid token
	;	io_error(io__error)	% error reading from the input stream
	;	eof.			% end-of-file

% For every token, we record the line number of the line on
% which the token occurred.

:- type token_context == int.	% line number

% This "fat list" representation is more efficient than a list of pairs.
:- type token_list	--->	token_cons(token, token_context, token_list)
			;	token_nil.

:- pred lexer__get_token_list(token_list, io__state, io__state).
:- mode lexer__get_token_list(out, di, uo) is det.
%	Read a list of tokens from the current input stream.
%	Keep reading until either we encounter either an `end' token
%	(i.e. a full stop followed by whitespace) or the end-of-file.

:- pred lexer__token_to_string(token, string).
:- mode lexer__token_to_string(in, out) is det.
%	Convert a token to a human-readable string describing the token.

%--------------------------------------------------%

library

%--------------------------------------------------%
% Copyright (C) 1993-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% This module imports all the modules in the Mercury library.
%
% It is used as a way for the Makefiles to know which library interface
% files, objects, etc., need to be installed, and it is also linked to
% create the executable invoked by the `mnp' script.
% 
% ---------------------------------------------------------------------------%
% ---------------------------------------------------------------------------%

:- module library.

:- interface.

:- pred library__version(string::out) is det.

%--------------------------------------------------%

list

%--------------------------------------------------%
% Copyright (C) 1993-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% Module `list' - defines the list type, and various utility predicates
% that operate on lists.
%
% Authors: fjh, conway, trd, zs, philip, warwick, ...
% Stability: medium to high.
%
%--------------------------------------------------%

:- module list.
:- interface.
:- import_module int.

%--------------------------------------------------%

	% The definition of the type `list(T)':
	%	A list is either an empty list, denoted `[]',
	%	or an element `Head' of type `T' followed by a tail `Tail'
	%	of type `list(T)', denoted `[Head | Tail]'.
	%	

:- type list(T) ---> [] ; [T | list(T)].

%--------------------------------------------------%

	% Some declarations for complicated modes using lists.
	% Partially instantiated mode aren't fully implemented yet,
	% so don't try to use these.

:- inst list_skel(I) = bound(([] ; [I | list_skel(I)])).
:- inst list_skel = list_skel(free).

:- inst non_empty_list = bound([ground | ground]).

:- mode in_list_skel :: list_skel -> list_skel.
:- mode out_list_skel :: free -> list_skel.
:- mode list_skel_out :: list_skel -> ground.

	% These more verbose versions are deprecated.
	% They exist only for backwards compatibility,
	% and will be removed in a future release.
:- mode input_list_skel :: in_list_skel.
:- mode output_list_skel :: out_list_skel.
:- mode list_skel_output :: list_skel_out.

	% These modes are particularly useful for passing around lists
	% of higher order terms, since they have complicated insts
	% which are not correctly approximated by "ground".
:- mode list_skel_in(I) :: list_skel(I) -> list_skel(I).
:- mode list_skel_out(I) :: free -> list_skel(I).

%--------------------------------------------------%

	% Standard append predicate:
	% list__append(Start, End, List) is true iff
	% `List' is the result of concatenating `Start' and `End'.
	%
:- pred list__append(list(T), list(T), list(T)).
:- mode list__append(di, di, uo) is det.
:- mode list__append(in, in, out) is det.
:- mode list__append(in, in, in) is semidet.	% implied
:- mode list__append(in, out, in) is semidet.
:- mode list__append(out, out, in) is multi.
%	The following mode is semidet in the sense that it doesn't
%	succeed more than once - but it does create a choice-point,
%	which means it's inefficient and that the compiler can't deduce
%	that it is semidet.  Use list__remove_suffix instead.
% :- mode list__append(out, in, in) is semidet.

	% list__remove_suffix(List, Suffix, Prefix):
	%	The same as list__append(Prefix, Suffix, List) except that
	%	this is semidet whereas list__append(out, in, in) is nondet.
:- pred list__remove_suffix(list(T), list(T), list(T)).
:- mode list__remove_suffix(in, in, out) is semidet.

	% list__merge(L1, L2, L):
	%	L is the result of merging the elements of L1 and L2,
	%	in ascending order.  L1 and L2 must be sorted.
:- pred list__merge(list(T), list(T), list(T)).
:- mode list__merge(in, in, out) is det.

	% list__merge_and_remove_dups(L1, L2, L):
	%	L is the result of merging the elements of L1 and L2,
	%	in ascending order, and eliminating any duplicates.
	%	L1 and L2 must be sorted and must each not contain any
	%	duplicates.
:- pred list__merge_and_remove_dups(list(T), list(T), list(T)).
:- mode list__merge_and_remove_dups(in, in, out) is det.

	% list__remove_adjacent_dups(L0, L) :
	%	L is the result of replacing every sequence of duplicate
	%	elements in L0 with a single such element.
:- pred list__remove_adjacent_dups(list(T), list(T)).
:- mode list__remove_adjacent_dups(in, out) is det.

	% list__remove_dups(L0, L) :
	%	L is the result of deleting the second and subsequent
	%	occurrences of every element that occurs twice in L.
:- pred list__remove_dups(list(T), list(T)).
:- mode list__remove_dups(in, out) is det.

	% list__member(Elem, List) :
	%	True iff `List' contains `Elem'.
:- pred list__member(T, list(T)).
:- mode list__member(in, in) is semidet.
:- mode list__member(out, in) is nondet.

	% list__member(Elem, List, SubList) :
	%	True iff `List' contains `Elem', and `SubList' is
	%	a suffix of `List' beginning with `Elem'.
	%	Same as `SubList = [Elem | _], list__append(_, SubList, List)'.
	%
:- pred list__member(T, list(T), list(T)).
:- mode list__member(out, in, out) is nondet.

	% list__length(List, Length) :
	%	True iff `Length' is the length of `List', i.e. if
	%	`List' contains `Length' elements.
	%
:- pred list__length(list(_T), int).
:- mode list__length(in, out) is det.
	% XXX The current mode checker can't handle this mode
% :- mode list__length(input_list_skel, out) is det.

	% list__same_length(ListA, ListB) :
	%	True iff `ListA' and `ListB' have the same length,
	%	i.e. iff they both contain the same number of elements.
	%
:- pred list__same_length(list(T1), list(T2)).
:- mode list__same_length(in, output_list_skel) is det.
:- mode list__same_length(output_list_skel, in) is det.
:- mode list__same_length(in, in) is semidet.
	% XXX The current mode checker can't handle these modes
% :- mode list__same_length(input_list_skel, output_list_skel) is det.
% :- mode list__same_length(output_list_skel, input_list_skel) is det.

	% list__split_list(Len, List, Start, End):
	%	splits `List' into a prefix `Start' of length `Len',
	%	and a remainder `End'.
	%	See also: list__take, list__drop.
	%
:- pred list__split_list(int, list(T), list(T), list(T)).
:- mode list__split_list(in, in, out, out) is semidet.

	% list__take(Len, List, Start):
	%	`Start' is the first `Len' elements of `List'.
	%	See also: list__split_list.
	%
:- pred list__take(int, list(T), list(T)).
:- mode list__take(in, in, out) is semidet.

	% list__drop(Len, List, End):
	%	`End' is the remainder of `List' after removing the
	%	first `Len' elements.
	%	See also: list__split_list.
	%
:- pred list__drop(int, list(T), list(T)).
:- mode list__drop(in, in, out) is semidet.

	% list__insert(Elem, List0, List):
	%	`List' is the result of inserting `Elem' somewhere in `List0'.
	%	Same as `list__delete(List, Elem, List0)'.
	%	
:- pred list__insert(T, list(T), list(T)).
:- mode list__insert(in, in, in) is semidet.
:- mode list__insert(in, out, in) is nondet.
:- mode list__insert(out, out, in) is nondet.
:- mode list__insert(in, in, out) is multi.

	% list__delete(List, Elem, Remainder):
	%	True iff `Elem' occurs in `List', and
	%	`Remainder' is the result of deleting one occurrence of
	%	`Elem' from `List'.
	%
:- pred list__delete(list(T), T, list(T)).
:- mode list__delete(in, in, in) is semidet.
:- mode list__delete(in, in, out) is nondet.
:- mode list__delete(in, out, out) is nondet.
:- mode list__delete(out, in, in) is multi.

	% list__delete_first(List0, Elem, List) is true iff Elem occurs in List0
	% and List is List0 with the first occurence of Elem removed
	%
:- pred list__delete_first(list(T), T, list(T)).
:- mode list__delete_first(in, in, out) is semidet.

	% list__delete_all(List0, Elem, List) is true iff List is List0 with
	% all occurences of Elem removed
	%
:- pred list__delete_all(list(T), T, list(T)).
:- mode list__delete_all(di, in, uo) is det.
:- mode list__delete_all(in, in, out) is det.

	% list__delete_elems(List0, Elems, List) is true iff List is List0 with
	% all occurences of all elements of Elems removed
	%
:- pred list__delete_elems(list(T), list(T), list(T)).
:- mode list__delete_elems(in, in, out) is det.

	% list__replace(List0, D, R, List) is true iff List is List0 
	% with an occurence of D replaced with R.
	%
:- pred list__replace(list(T), T, T, list(T)).
:- mode list__replace(in, in, in, in) is semidet.
:- mode list__replace(in, in, in, out) is nondet.

	% list__replace_first(List0, D, R, List) is true iff List is List0 
	% with the first occurence of D replaced with R.
	%
:- pred list__replace_first(list(T), T, T, list(T)).
:- mode list__replace_first(in, in, in, out) is semidet.

	% list__replace_all(List0, D, R, List) is true iff List is List0 
	% with all occurences of D replaced with R.
	%
:- pred list__replace_all(list(T), T, T, list(T)).
:- mode list__replace_all(in, in, in, out) is det.

	% list__sort_and_remove_dups(List0, List):
	%	List is List0 sorted with duplicates removed.
	%
:- pred list__sort_and_remove_dups(list(T), list(T)).
:- mode list__sort_and_remove_dups(in, out) is det.

	% list__sort(List0, List):
	%	List is List0 sorted.
	%
:- pred list__sort(list(T), list(T)).
:- mode list__sort(in, out) is det.

	% list__reverse(List, Reverse):
	%	`Reverse' is a list containing the same elements as `List'
	%	but in reverse order.
	%
:- pred list__reverse(list(T), list(T)).
:- mode list__reverse(in, out) is det.

	% list__perm(List0, List):
	%	True iff `List' is a permutation of `List0'.
	%
:- pred	list__perm(list(T), list(T)).
:- mode list__perm(in, out) is nondet.

	% list__nth_member_search(List, Elem, Position):
	%	Elem is the Position'th member of List.
	%
:- pred list__nth_member_search(list(T), T, int).
:- mode list__nth_member_search(in, in, out) is semidet.

	% list__index*(List, Position, Elem):
	%	These predicates select an element in a list from it's
	%	position.  The `index0' preds consider the first element
	%	element to be element number zero, whereas the `index1' preds
	%	consider the first element to be element number one.
	%	The `_det' preds call error/1 if the index is out of
	%	range, whereas the semidet preds fail if the index is out of
	%	range.
	%
:- pred list__index0(list(T)::in, int::in, T::out) is semidet.
:- pred list__index1(list(T)::in, int::in, T::out) is semidet.
:- pred list__index0_det(list(T)::in, int::in, T::out) is det.
:- pred list__index1_det(list(T)::in, int::in, T::out) is det.

	% list__zip(ListA, ListB, List):
	%	List is the result of alternating the elements
	%	of ListA and ListB.  When one of the lists goes to empty,
	% 	the remainder of the nonempty list is appended.
	%
:- pred list__zip(list(T), list(T), list(T)).
:- mode list__zip(in, in, out) is det.

	% list__duplicate(Count, Elem, List) is true iff List is a list
	% containing Count duplicate copies of Elem.
	%
:- pred list__duplicate(int, T, list(T)).
:- mode list__duplicate(in, in, out) is det.

	% list__condense(ListOfLists, List):
	%	`List' is the result of concatenating all the
	%	elements of `ListOfLists'.
	%
:- pred list__condense(list(list(T)), list(T)).
:- mode list__condense(in, out) is det.

	% list__chunk(List, ChunkSize, Chunks):
	%	Takes a list `List' and breaks it into a list of lists `Chunks',
	%	such that the length of each list in `Chunks' is at most
	%	`ChunkSize.  (More precisely, the length of each list in
	%	`Chunks' other than the last one is exactly `ChunkSize',
	%	and the length of the last list in `Chunks' is between one
	%	and `ChunkSize'.)
	%
:- pred list__chunk(list(T), int, list(list(T))).
:- mode list__chunk(in, in, out) is det.

	% list__sublist(SubList, FullList) is true
	%	if one can obtain SubList by starting with FullList
	%	and deleting some of its elements.
:- pred list__sublist(list(T), list(T)).
:- mode list__sublist(in, in) is semidet.

	% list__all_same(List) is true
	% 	if all elements of the list are the same
:- pred list__all_same(list(T)).
:- mode list__all_same(in) is semidet.

	% list__last(List, Last) is true
	%	if Last is the last element of List.
:- pred list__last(list(T), T).
:- mode list__last(in, out) is semidet.

%--------------------------------------------------%
%
% The following group of predicates use higher-order terms to simplify
% various list processing tasks. They implement pretty much standard
% sorts of operations provided by standard libraries for functional languages.
%
%--------------------------------------------------%

	% list__map(T, L, M) uses the closure T
	% to transform the elements of L into the elements of M.
:- pred list__map(pred(X, Y), list(X), list(Y)).
:- mode list__map(pred(in, out) is det, in, out) is det.
:- mode list__map(pred(in, out) is semidet, in, out) is semidet.
:- mode list__map(pred(in, out) is multi, in, out) is multi.
:- mode list__map(pred(in, out) is nondet, in, out) is nondet.

	% list__foldl(Pred, List, Start, End) calls Pred with each
	% element of List (working left-to-right) and an accumulator
	% (with the initial value of Start), and returns the final
	% value in End.
:- pred list__foldl(pred(X, Y, Y), list(X), Y, Y).
:- mode list__foldl(pred(in, di, uo) is det, in, di, uo) is det.
:- mode list__foldl(pred(in, in, out) is det, in, in, out) is det.
:- mode list__foldl(pred(in, in, out) is semidet, in, in, out) is semidet.

	% list__foldr(Pred, List, Start, End) calls Pred with each
	% element of List (working right-to-left) and an accumulator
	% (with the initial value of Start), and returns the final
	% value in End.
:- pred list__foldr(pred(X, Y, Y), list(X), Y, Y).
:- mode list__foldr(pred(in, in, out) is det, in, in, out) is det.
:- mode list__foldr(pred(in, in, out) is semidet, in, in, out) is semidet.

	% list__foldl2(Pred, List, Start, End, Start2, End2) 
	% calls Pred with each element of List (working left-to-right),
	% 2 accumulators (with the initial values of Start and Start2),
	% and returns the final values in End and End2.
	% (Although no more expressive than list__foldl, this is often
	% a more convenient format, and a little more efficient).
:- pred list__foldl2(pred(X, Y, Y, Z, Z), list(X), Y, Y, Z, Z).
:- mode list__foldl2(pred(in, in, out, in, out) is det,
		in, in, out, in, out) is det.
:- mode list__foldl2(pred(in, in, out, mdi, muo) is det,
		in, in, out, mdi, muo) is det.
:- mode list__foldl2(pred(in, in, out, di, uo) is det,
		in, in, out, di, uo) is det.
:- mode list__foldl2(pred(in, di, uo, di, uo) is det,
		in, di, uo, di, uo) is det.

	% list__map_foldl(Pred, InList, OutList, Start, End) calls Pred
	% with an accumulator (with the initial value of Start) on
	% each element of InList (working left-to-right) to transform
	% InList into OutList.  The final value of the acumulator is
	% returned in End.
:- pred list__map_foldl(pred(X, Y, Z, Z), list(X), list(Y), Z, Z).
:- mode list__map_foldl(pred(in, out, di, uo) is det, in, out, di, uo)
								is det.
:- mode list__map_foldl(pred(in, out, in, out) is det, in, out, in, out)
								is det.
:- mode list__map_foldl(pred(in, out, in, out) is semidet, in, out, in, out)
                                                                is semidet.

	% list__filter(Pred, List, TrueList) takes a closure with one
	% input argument and for each member of List `X', calls the closure.
	% Iff call(Pred, X) is true, then X is included in TrueList.
:- pred list__filter(pred(X), list(X), list(X)).
:- mode list__filter(pred(in) is semidet, in, out) is det.

	% list__filter(Pred, List, TrueList, FalseList) takes a closure with one
	% input argument and for each member of List `X', calls the closure.
	% Iff call(Pred, X) is true, then X is included in TrueList.
	% Iff call(Pred, X) is false, then X is included in FalseList.
:- pred list__filter(pred(X), list(X), list(X), list(X)).
:- mode list__filter(pred(in) is semidet, in, out, out) is det.

	% list__filter_map(Transformer, List, TrueList) takes a predicate
	% with one input argument and one output argument. It is called
	% with each element of List. If a call succeeds, then the output is
	% included in TrueList.
:- pred list__filter_map(pred(X, Y), list(X), list(Y)).
:- mode list__filter_map(pred(in, out) is semidet, in, out) is det.

	% list__filter_map(Transformer, List, TrueList, FalseList) takes
	% a predicate with one input argument and one output argument.
	% It is called with each element of List. If a call succeeds,
	% then the output is included in TrueList; otherwise, the failing
	% input is included in FalseList.
:- pred list__filter_map(pred(X, Y), list(X), list(Y), list(X)).
:- mode list__filter_map(pred(in, out) is semidet, in, out, out) is det.

	% list__takewhile(Predicate, List, UptoList, AfterList) takes a
	% closure with one input argument, and calls it on successive members
	% of List as long as the calls succeed. The elements for which
	% the call succeeds are placed in UptoList and the first element for
	% which the call fails, and all the remaining elements of List are
	% placed in AfterList.
:- pred list__takewhile(pred(T), list(T), list(T), list(T)).
:- mode list__takewhile(pred(in) is semidet, in, out, out) is det.

%--------------------------------------------------%

	% list__sort(Compare, Unsorted, Sorted) is true iff Sorted is a
	% list containing the same elements as Unsorted, where Sorted is
	% a sorted list, with respect to the ordering defined by the predicate
	% term Compare.
:- pred list__sort(pred(X, X, comparison_result), list(X), list(X)).
:- mode list__sort(pred(in, in, out) is det, in, out) is det.

	% list__sort_and_remove_dups(Compare, Unsorted, Sorted) is true iff 
	% Sorted is a list containing the same elements as Unsorted, but with
	% any duplicates removed. Where Sorted is a sorted list, with respect  
	% to the ordering defined by the predicate term Compare.
:- pred list__sort_and_remove_dups(pred(X, X, comparison_result), list(X), 
	list(X)).
:- mode list__sort_and_remove_dups(pred(in, in, out) is det, in, out) is det.

	% list__merge(Compare, As, Bs, Sorted) is true iff Sorted is a
	% list containing the elements of As and Bs in the order implied
	% by their sorted merge. The ordering of elements is defined by
	% the higher order comparison predicate Compare.
:- pred list__merge(pred(X, X, comparison_result), list(X), list(X), list(X)).
:- mode list__merge(pred(in, in, out) is det, in, in, out) is det.

	% list__merge_and_remove_dups(P, As, Bs, Sorted) is true if and only if
	% Sorted is a list containing the elements of As and Bs in the order 
	% implied by their sorted merge. The ordering of elements is defined by
	% the higher order comparison predicate P.
	% As and Bs must be sorted.
:- pred list__merge_and_remove_dups(pred(X, X, comparison_result),
	list(X), list(X), list(X)).
:- mode list__merge_and_remove_dups(pred(in, in, out) is det,
	in, in, out) is det.


%--------------------------------------------------%
%--------------------------------------------------%

map

%--------------------------------------------------%
% Copyright (C) 1993-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: map.m.
% Main author: fjh, conway.
% Stability: high.
%
% This file provides the 'map' ADT.
% A map (also known as a dictionary or an associative array) is a collection
% of (Key,Data) pairs which allows you to look up any Data item given the
% Key.
%
% The implementation is using balanced binary trees, as provided by
% tree234.m.  Virtually all the predicates in this file just
% forward the work to the corresponding predicate in tree234.m.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module map.
:- interface.
:- import_module set, list, assoc_list.

%--------------------------------------------------%

:- type map(_K, _V).

%--------------------------------------------------%

	% Initialize an empty map.
:- pred map__init(map(_,_)).
:- mode map__init(uo) is det.

	% Check whether a map is empty.
:- pred map__is_empty(map(_,_)).
:- mode map__is_empty(in) is semidet.

	% Check whether map contains key
:- pred map__contains(map(K,_V), K).
:- mode map__contains(in, in) is semidet.

:- pred map__member(map(K,V), K, V).
:- mode map__member(in, out, out) is nondet.

	% Search map for key.
:- pred map__search(map(K,V), K, V).
:- mode map__search(in, in, in) is semidet.	% implied
:- mode map__search(in, in, out) is semidet.

	% Search map for key, but abort if search fails.
:- pred map__lookup(map(K,V), K, V).
:- mode map__lookup(in, in, in) is semidet.	% implied
:- mode map__lookup(in, in, out) is det.

	% Search map for data.
:- pred map__inverse_search(map(K,V), V, K).
:- mode map__inverse_search(in, in, out) is nondet.

	% Insert a new key and corresponding value into a map.
	% Fail if the key already exists.
:- pred map__insert(map(K,V), K, V, map(K,V)).
:- mode map__insert(in, in, in, out) is semidet.

	% Insert a new key and corresponding value into a map.
	% Abort if the key already exists.
:- pred map__det_insert(map(K,V), K, V, map(K,V)).
:- mode map__det_insert(in, in, in, out) is det.

	% Apply map__det_insert to key - value pairs from corresponding lists.
:- pred map__det_insert_from_corresponding_lists(map(K,V), list(K),
						list(V), map(K,V)).
:- mode map__det_insert_from_corresponding_lists(in, in, in, out) is det.

	% Update the value corresponding to a given key
	% Fail if the key doesn't already exist.
:- pred map__update(map(K,V), K, V, map(K,V)).
:- mode map__update(in, in, in, out) is semidet.

	% Update the value corresponding to a given key
	% Abort if the key doesn't already exist.
:- pred map__det_update(map(K,V), K, V, map(K,V)).
:- mode map__det_update(in, in, in, out) is det.

	% Update value if the key is already present, otherwise
	% insert new key and value.
:- pred map__set(map(K,V), K, V, map(K,V)).
:- mode map__set(di, di, di, uo) is det.
:- mode map__set(in, in, in, out) is det.

	% Given a map, return a list of all the keys in the map
:- pred map__keys(map(K, _V), list(K)).
:- mode map__keys(in, out) is det.

	% Given a map, return a list of all the data values in the map
:- pred map__values(map(_K, V), list(V)).
:- mode map__values(in, out) is det.

	% convert a map to an association list
:- pred map__to_assoc_list(map(K,V), assoc_list(K,V)).
:- mode map__to_assoc_list(in, out) is det.

	% convert an association list to a map
:- pred map__from_assoc_list(assoc_list(K,V), map(K,V)).
:- mode map__from_assoc_list(in, out) is det.

	% convert a sorted association list to a map
:- pred map__from_sorted_assoc_list(assoc_list(K,V), map(K,V)).
:- mode map__from_sorted_assoc_list(in, out) is det.

	% delete a key-value pair from a map
	% if the key is not present, leave the map unchanged
:- pred map__delete(map(K,V), K, map(K,V)).
:- mode map__delete(di, in, uo) is det.
:- mode map__delete(in, in, out) is det.

	% apply map__delete/3 to a list of keys
:- pred map__delete_list(map(K,V), list(K), map(K,V)).
:- mode map__delete_list(di, in, uo) is det.
:- mode map__delete_list(in, in, out) is det.

	% delete a key-value pair from a map and return the value.
	% fail if the key is not present
:- pred map__remove(map(K,V), K, V, map(K,V)).
:- mode map__remove(in, in, out, out) is semidet.

	% delete a key-value pair from a map and return the value.
	% abort if the key is not present
:- pred map__det_remove(map(K,V), K, V, map(K,V)).
:- mode map__det_remove(in, in, out, out) is det.

	% Count the number of elements in the map.
:- pred map__count(map(K, V), int).
:- mode map__count(in, out) is det.

	% Convert a pair of lists (which must be of the same length)
	% to a map.
:- pred map__from_corresponding_lists(list(K), list(V), map(K, V)).
:- mode map__from_corresponding_lists(in, in, out) is det.

	% For map__merge(MapA, MapB, Map), MapA and MapB must
	% not both contain the same key.
:- pred map__merge(map(K, V), map(K, V), map(K, V)).
:- mode map__merge(in, in, out) is det.

	% For map__overlay(MapA, MapB, Map), if MapA and MapB both
	% contain the same key, then Map will map that key to
	% the value from MapB.  In otherwords, MapB takes precedence
	% over MapA.
:- pred map__overlay(map(K,V), map(K,V), map(K,V)).
:- mode map__overlay(in, in, out) is det.

	% map__select takes a map and a set of keys and returns
	% a map containing the keys in the set and their corresponding
	% values.
:- pred map__select(map(K,V), set(K), map(K,V)).
:- mode map__select(in, in, out) is det.

	% Given a list of keys, produce a list of their corresponding
	% values in a specified map.
:- pred map__apply_to_list(list(K), map(K, V), list(V)).
:- mode map__apply_to_list(in, in, out) is det.

	% Declaratively, a NOP.
	% Operationally, a suggestion that the implemention
	% optimize the representation of the map in the expectation
	% of a number of lookups but few or no modifications.
:- pred map__optimize(map(K, V), map(K, V)).
:- mode map__optimize(in, out) is det.

	% Remove the smallest item from the map, fail if
	% the map is empty.
:- pred map__remove_smallest(map(K, V), K, V, map(K, V)).
:- mode map__remove_smallest(in, out, out, out) is semidet.

%--------------------------------------------------%

:- import_module tree234.

:- type map(K,V)	==	tree234(K,V).

%--------------------------------------------------%
%--------------------------------------------------%

math

%--------------------------------------------------%
% Copyright (C) 1995-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: math.m
% Main author: bromage
% Stability: high (but as yet no Prolog implementation)
%
% Higher mathematical operations.  (The basics are in float.m.)
% The predicates in this module are not yet implemented in Prolog.
%
% Domain errors are currently handled by a program abort.  This is
% because Mercury currently does not have exceptions built in.
% Exception-handling would be nice, but it's kind of low on the
% priority scale.
%
%--------------------------------------------------%

:- module math.
:- interface.

%--------------------------------------------------%
% Mathematical constants

	% Pythagoras' number
:- func math__pi = float.
:- mode math__pi = out is det.

	% Base of natural logarithms
:- func math__e = float.
:- mode math__e = out is det.

%--------------------------------------------------%
% "Next integer" operations

	% math__ceiling(X) = Ceil is true if Ceil is the smallest integer
	% not less than X.
:- func math__ceiling(float) = float.
:- mode math__ceiling(in) = out is det.

	% math__floor(X) = Floor is true if Floor is the largest integer
	% not greater than X.
:- func math__floor(float) = float.
:- mode math__floor(in) = out is det.

	% math__round(X) = Round is true if Round is the integer
	% closest to X.  If X has a fractional value of 0.5, it
	% is rounded up.
:- func math__round(float) = float.
:- mode math__round(in) = out is det.

	% math__truncate(X) = Trunc is true if Trunc is the integer
	% closest to X such that |Trunc| =< |X|.
:- func math__truncate(float) = float.
:- mode math__truncate(in) = out is det.

%--------------------------------------------------%
% Power/logarithm operations

	% math__sqrt(X) = Sqrt is true if Sqrt is the positive square
	% root of X.
	%
	% Domain restriction: X >= 0
:- func math__sqrt(float) = float.
:- mode math__sqrt(in) = out is det.

	% math__pow(X, Y) = Res is true if Res is X raised to the
	% power of Y.
	%
	% Domain restriction: X >= 0 and (X = 0 implies Y > 0)
:- func math__pow(float, float) = float.
:- mode math__pow(in, in) = out is det.

	% math__exp(X) = Exp is true if Exp is X raised to the
	% power of e.
:- func math__exp(float) = float.
:- mode math__exp(in) = out is det.

	% math__ln(X) = Log is true if Log is the natural logarithm
	% of X.
	%
	% Domain restriction: X > 0
:- func math__ln(float) = float.
:- mode math__ln(in) = out is det.

	% math__log10(X) = Log is true if Log is the logarithm to
	% base 10 of X.
	%
	% Domain restriction: X > 0
:- func math__log10(float) = float.
:- mode math__log10(in) = out is det.

	% math__log2(X) = Log is true if Log is the logarithm to
	% base 2 of X.
	%
	% Domain restriction: X > 0
:- func math__log2(float) = float.
:- mode math__log2(in) = out is det.

	% math__log(B, X) = Log is true if Log is the logarithm to
	% base B of X.
	%
	% Domain restriction: X > 0 and B > 0 and B \= 1
:- func math__log(float, float) = float.
:- mode math__log(in, in) = out is det.

%--------------------------------------------------%
% Trigonometric operations

	% math__sin(X) = Sin is true if Sin is the sine of X.
:- func math__sin(float) = float.
:- mode math__sin(in) = out is det.

	% math__cos(X) = Cos is true if Cos is the cosine of X.
:- func math__cos(float) = float.
:- mode math__cos(in) = out is det.

	% math__tan(X) = Tan is true if Tan is the tangent of X.
:- func math__tan(float) = float.
:- mode math__tan(in) = out is det.

	% math__asin(X) = ASin is true if ASin is the inverse
	% sine of X, where ASin is in the range [-pi/2,pi/2].
	%
	% Domain restriction: X must be in the range [-1,1]
:- func math__asin(float) = float.
:- mode math__asin(in) = out is det.

	% math__acos(X) = ACos is true if ACos is the inverse
	% cosine of X, where ACos is in the range [0, pi].
	%
	% Domain restriction: X must be in the range [-1,1]
:- func math__acos(float) = float.
:- mode math__acos(in) = out is det.

	% math__atan(X) = ATan is true if ATan is the inverse
	% tangent of X, where ATan is in the range [-pi/2,pi/2].
:- func math__atan(float) = float.
:- mode math__atan(in) = out is det.

	% math__atan2(Y, X) = ATan is true if ATan is the inverse
	% tangent of Y/X, where ATan is in the range [-pi,pi].
:- func math__atan2(float, float) = float.
:- mode math__atan2(in, in) = out is det.

%--------------------------------------------------%
% Hyperbolic functions

	% math__sinh(X) = Sinh is true if Sinh is the hyperbolic
	% sine of X.
:- func math__sinh(float) = float.
:- mode math__sinh(in) = out is det.

	% math__cosh(X) = Cosh is true if Cosh is the hyperbolic
	% cosine of X.
:- func math__cosh(float) = float.
:- mode math__cosh(in) = out is det.

	% math__tanh(X) = Tanh is true if Tanh is the hyperbolic
	% tangent of X.
:- func math__tanh(float) = float.
:- mode math__tanh(in) = out is det.

%--------------------------------------------------%
%--------------------------------------------------%

mercury_builtin

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: mercury_builtin.m.
% Main author: fjh.
% Stability: low.

% This file is automatically imported into every module.
% It is intended for things that are part of the language,
% but which are implemented just as normal user-level code
% rather than with special coding in the compiler.

%--------------------------------------------------%
%--------------------------------------------------%

:- module mercury_builtin.
:- interface.

%--------------------------------------------------%

% TYPES.

% The types `character', `int', `float', and `string',
% and the types `pred', `pred(T)', `pred(T1, T2)', `pred(T1, T2, T3)', ...
% and `func(T1) = T2', `func(T1, T2) = T3', `func(T1, T2, T3) = T4', ...
% are builtin and are implemented using special code in the
% type-checker.  (XXX TODO: report an error for attempts to redefine
% these types.)

% The type c_pointer can be used by predicates which use the C interface.
:- type c_pointer.

%--------------------------------------------------%

% INSTS.

% The standard insts `free', `ground', and `bound(...)' are builtin
% and are implemented using special code in the parser and mode-checker.

% So are the standard unique insts `unique', `unique(...)',
% `mostly_unique', `mostly_unique(...)', and `clobbered'.
% The name `dead' is allowed as a synonym for `clobbered'.
% Similarly `mostly_dead' is a synonym for `mostly_clobbered'.

:- inst dead = clobbered.
:- inst mostly_dead = mostly_clobbered.

% The not yet properly supported `any' inst used for the
% constraint solver interface is also builtin.

% Higher-order predicate insts `pred(<modes>) is <detism>'
% and higher-order functions insts `func(<modes>) = <mode> is det'
% are also builtin.

%--------------------------------------------------%

% MODES.

% The standard modes.

:- mode unused :: (free -> free).
:- mode output :: (free -> ground).
:- mode input :: (ground -> ground).

:- mode in :: (ground -> ground).
:- mode out :: (free -> ground).

:- mode in(Inst) :: (Inst -> Inst).
:- mode out(Inst) :: (free -> Inst).
:- mode di(Inst) :: (Inst -> clobbered).
:- mode mdi(Inst) :: (Inst -> mostly_clobbered).

% Unique modes.  These are still not fully implemented.

% unique output
:- mode uo :: free -> unique.

% unique input
:- mode ui :: unique -> unique.

% destructive input
:- mode di :: unique -> clobbered.

% "Mostly" unique modes (unique except that that may be referenced
% again on backtracking).

% mostly unique output
:- mode muo :: free -> mostly_unique.

% mostly unique input
:- mode mui :: mostly_unique -> mostly_unique.

% mostly destructive input
:- mode mdi :: mostly_unique -> mostly_clobbered.

% Higher-order predicate modes are builtin.

%--------------------------------------------------%

% PREDICATES.

% copy/2 makes a deep copy of a data structure.  The resulting copy is a
% `unique' value, so you can use destructive update on it.

:- pred copy(T, T).
:- mode copy(ui, uo) is det.
:- mode copy(in, uo) is det.

% unsafe_promise_unique/2 is used to promise the compiler that you have a
% `unique' copy of a data structure, so that you can use destructive update.
% It is used to work around limitations in the current support for unique
% modes.  `unsafe_promise_unique(X, Y)' is the same as `Y = X' except that
% the compiler will assume that `Y' is unique.

:- pred unsafe_promise_unique(T, T).
:- mode unsafe_promise_unique(in, uo) is det.

% We define !/0 (and !/2 for dcgs) to be equivalent to `true'.  This is for
% backwards compatibility with Prolog systems.  But of course it only works
% if all your cuts are green cuts.

:- pred ! is det.

:- pred !(T, T).
:- mode !(di, uo) is det.
:- mode !(in, out) is det.

% In addition, the following predicate-like constructs are builtin:
%
%	:- pred (T = T).
%	:- pred (T \= T).
%	:- pred (pred , pred).
%	:- pred (pred ; pred).
%	:- pred (\+ pred).
%	:- pred (not pred).
%	:- pred (pred -> pred).
%	:- pred (if pred then pred).
%	:- pred (if pred then pred else pred).
%	:- pred (pred => pred).
%	:- pred (pred <= pred).
%	:- pred (pred <=> pred).
%
%	(pred -> pred ; pred).
%	some Vars pred
%	all Vars pred
%	call/N

%--------------------------------------------------%

	% unify(X, Y) is true iff X = Y.
:- pred unify(T::in, T::in) is semidet.

:- type comparison_result ---> (=) ; (<) ; (>).

	% compare(Res, X, Y) binds Res to =, <, or >
	% depending on whether X is =, <, or > Y in the
	% standard ordering.
:- pred compare(comparison_result, T, T).
:- mode compare(uo, ui, ui) is det.
:- mode compare(uo, ui, in) is det.
:- mode compare(uo, in, ui) is det.
:- mode compare(uo, in, in) is det.

%--------------------------------------------------%

multi_map

%--------------------------------------------------%
% Copyright (C) 1995, 1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: multi_map.m.
% Main author: dylan.  Based on map.m, by fjh, conway.
% Stability: low.
%
% This file provides the 'multi_map' ADT.
% A map (also known as a dictionary or an associative array) is a collection
% of (Key,Data) pairs which allows you to look up any Data item given the
% Key.  A multi_map is similar, though allows a one to many relationship
% between keys and data.
%
% This is implemented almost as a special case of map.m.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module multi_map.
:- interface.
:- import_module map, list, assoc_list, set.

%--------------------------------------------------%

:- type multi_map(Key, Data)	==	map(Key, list(Data)).

%--------------------------------------------------%

	% Initialize an empty multi_map.
:- pred multi_map__init(multi_map(_,_)).
:- mode multi_map__init(uo) is det.

	% Check whether a multi_map is empty.
:- pred multi_map__is_empty(multi_map(_,_)).
:- mode multi_map__is_empty(in) is semidet.

	% Check whether multi_map contains key
:- pred multi_map__contains(multi_map(K,_V), K).
:- mode multi_map__contains(in, in) is semidet.

:- pred multi_map__member(multi_map(K,V), K, V).
:- mode multi_map__member(in, out, out) is nondet.

	% Search multi_map for given key.
:- pred multi_map__search(multi_map(K,V), K, list(V)).
:- mode multi_map__search(in, in, out) is semidet.

	% Search multi_map for given key.
:- pred multi_map__nondet_search(multi_map(K,V), K, V).
:- mode multi_map__nondet_search(in, in, out) is nondet.

	% Search multi_map for key, but abort if search fails.
:- pred multi_map__lookup(multi_map(K,V), K, list(V)).
:- mode multi_map__lookup(in, in, out) is det.

	% Search multi_map for key.
:- pred multi_map__nondet_lookup(multi_map(K,V), K, V).
:- mode multi_map__nondet_lookup(in, in, out) is nondet.

	% Search multi_map for data.
:- pred multi_map__inverse_search(multi_map(K,V), V, K).
:- mode multi_map__inverse_search(in, in, out) is nondet.

	% Insert a new key and corresponding value into a multi_map.
	% Fail if the key already exists.
:- pred multi_map__insert(multi_map(K,V), K, V, multi_map(K,V)).
:- mode multi_map__insert(in, in, in, out) is semidet.

	% Insert a new key and corresponding value into a multi_map.
	% Abort if the key already exists.
:- pred multi_map__det_insert(multi_map(K,V), K, V, multi_map(K,V)).
:- mode multi_map__det_insert(in, in, in, out) is det.

	% Update (add) the value corresponding to a given key
	% Fail if the key doesn't already exist.
:- pred multi_map__update(multi_map(K,V), K, V, multi_map(K,V)).
:- mode multi_map__update(in, in, in, out) is semidet.

	% Update (add) the value corresponding to a given key
	% Abort if the key doesn't already exist.
:- pred multi_map__det_update(multi_map(K,V), K, V, multi_map(K,V)).
:- mode multi_map__det_update(in, in, in, out) is det.

	% Update (replace) the value corresponding to a given key
	% Abort if the key doesn't already exist.
:- pred multi_map__det_replace(multi_map(K,V), K, list(V), multi_map(K,V)).
:- mode multi_map__det_replace(in, in, in, out) is det.

	% Update (add) value if the key is already present, otherwise
	% insert new key and value.
:- pred multi_map__set(multi_map(K,V), K, V, multi_map(K,V)).
:- mode multi_map__set(in, in, in, out) is det.

	% Given a multi_map, return a list of all the keys in the multi_map
:- pred multi_map__keys(multi_map(K, _V), list(K)).
:- mode multi_map__keys(in, out) is det.

	% Given a multi_map, return a list of all the data values in the
	% multi_map
:- pred multi_map__values(multi_map(_K, V), list(V)).
:- mode multi_map__values(in, out) is det.

	% convert a multi_map to an association list
:- pred multi_map__to_assoc_list(multi_map(K,V), assoc_list(K,list(V))).
:- mode multi_map__to_assoc_list(in, out) is det.

	% convert an association list to a multi_map
:- pred multi_map__from_assoc_list(assoc_list(K,list(V)), multi_map(K,V)).
:- mode multi_map__from_assoc_list(in, out) is det.

	% convert a sorted association list to a multi_map
:- pred multi_map__from_sorted_assoc_list(assoc_list(K, list(V)), 
			multi_map(K, V)).
:- mode multi_map__from_sorted_assoc_list(in, out) is det.

	% delete a key and data from a multi_map
	% if the key is not present, leave the multi_map unchanged
:- pred multi_map__delete(multi_map(K,V), K, multi_map(K,V)).
:- mode multi_map__delete(in, in, out) is det.

	% delete a data value from a key in a multi_map
	% if the key is not present, leave the multi_map unchanged
:- pred multi_map__delete(multi_map(K,V), K, V, multi_map(K,V)).
:- mode multi_map__delete(in, in, in, out) is det.

	% delete a key-value pair from a multi_map and return the value.
	% fail if the key is not present
:- pred multi_map__remove(multi_map(K,V), K, list(V), multi_map(K,V)).
:- mode multi_map__remove(in, in, out, out) is semidet.

	% delete a key-value pair from a multi_map and return the value.
	% abort if the key is not present
:- pred multi_map__det_remove(multi_map(K,V), K, list(V), multi_map(K,V)).
:- mode multi_map__det_remove(in, in, out, out) is det.

	% Count the number of elements (keys) in the multi_map.
:- pred multi_map__count(multi_map(K, V), int).
:- mode multi_map__count(in, out) is det.

	% Count the number of data elements in the multi_map.
:- pred multi_map__all_count(multi_map(K, V), int).
:- mode multi_map__all_count(in, out) is det.

	% Convert a pair of lists (which must be of the same length)
	% to a multi_map.
:- pred multi_map__from_corresponding_lists(list(K), list(V),
				multi_map(K, V)).
:- mode multi_map__from_corresponding_lists(in, in, out) is det.

	% Convert a pair of lists (which must be of the same length)
	% to a multi_map.
:- pred multi_map__from_corresponding_list_lists(list(K), list(list(V)),
				multi_map(K, V)).
:- mode multi_map__from_corresponding_list_lists(in, in, out) is det.

	% For multi_map__merge(MultiMapA, MultiMapB, MultiMap).
:- pred multi_map__merge(multi_map(K, V), multi_map(K, V), multi_map(K, V)).
:- mode multi_map__merge(in, in, out) is det.

	% multi_map__select takes a multi_map and a set of keys and returns
	% a multi_map containing the keys in the set and their corresponding
	% values.
:- pred multi_map__select(multi_map(K,V), set(K), multi_map(K,V)).
:- mode multi_map__select(in, in, out) is det.

	% Given a list of keys, produce a list of their values in a
	% specified multi_map.
:- pred multi_map__apply_to_list(list(K), multi_map(K, V), list(V)).
:- mode multi_map__apply_to_list(in, in, out) is det.

	% Declaratively, a NOP.
	% Operationally, a suggestion that the implemention
	% optimize the representation of the multi_map in the expectation
	% of a number of lookups but few or no modifications.
:- pred multi_map__optimize(multi_map(K, V), multi_map(K, V)).
:- mode multi_map__optimize(in, out) is det.

	% Remove the smallest item from the multi_map, fail if 
	% the multi_map is empty.
:- pred multi_map__remove_smallest(multi_map(K, V), K, list(V),
			multi_map(K, V)).
:- mode multi_map__remove_smallest(in, out, out, out) is semidet.

%--------------------------------------------------%
%--------------------------------------------------%

ops

%--------------------------------------------------%
% Copyright (C) 1995-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% file: ops.m.
% main author: fjh.
% stability: low.
%
% Here's where we maintain the table of current operators.
%
% XXX In the current implementation the table is fixed and cannot be
% modified at run-time.
%
%--------------------------------------------------%

:- module ops.
:- interface.

:- type ops__specifier
	--->	fx ; fy ; xf ; yf ; xfx ; yfx ; xfy ; fxx ; fxy ; fyx.

:- type ops__assoc
	--->	x ; y.

:- type ops__class
	--->	infix(ops__assoc, ops__assoc)
	;	prefix(ops__assoc)
	;	binary_prefix(ops__assoc, ops__assoc)
	;	postfix(ops__assoc).

:- type ops__table.

:- type ops__priority == int.

	% create an ops_table with the standard Mercury operators.
:- pred ops__init_op_table(ops__table).
:- mode ops__init_op_table(uo) is det.

	% check whether a string is the name of an infix operator,
	% and if it is, return its precedence and associativity.
:- pred ops__lookup_infix_op(ops__table, string, int, ops__assoc, ops__assoc).
:- mode ops__lookup_infix_op(in, in, out, out, out) is semidet.

	% check whether a string is the name of a prefix operator,
	% and if it is, return its precedence and associativity.
:- pred ops__lookup_prefix_op(ops__table, string, int, ops__assoc).
:- mode ops__lookup_prefix_op(in, in, out, out) is semidet.

	% check whether a string is the name of a binary prefix operator,
	% and if it is, return its precedence and associativity.
:- pred ops__lookup_binary_prefix_op(ops__table, string,
					int, ops__assoc, ops__assoc).
:- mode ops__lookup_binary_prefix_op(in, in, out, out, out) is semidet.
		
	% check whether a string is the name of a postfix operator,
	% and if it is, return its precedence and associativity.
:- pred ops__lookup_postfix_op(ops__table, string, int, ops__assoc).
:- mode ops__lookup_postfix_op(in, in, out, out) is semidet.

	% check whether a string is the name of an operator
:- pred ops__lookup_op(ops__table, string).
:- mode ops__lookup_op(in, in) is semidet.

	% convert an ops__specifer (e.g. `xfy') to an ops__class
	% (e.g. `infix(x, y)').
:- pred ops__op_specifier_to_class(ops__specifier, ops__class).
:- mode ops__op_specifier_to_class(in, out) is det.
% :- mode ops__op_specifier_to_class(out, in) is semidet.

	% Returns the highest priority number (the lowest is zero).
	% Note that due to Prolog tradition, the priority numbers
	% are backwards: higher numbers mean lower priority
	% and lower numbers mean higher priority.  Sorry...
:- pred ops__max_priority(ops__priority).
:- mode ops__max_priority(out) is det.

%--------------------------------------------------%

parser

%--------------------------------------------------%
% Copyright (C) 1995-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% file: parser.m.
% main author: fjh.
% stability: high.
%
% This file exports the predicate parser__read_term, which reads
% a term from the current input stream.  The parser and lexer are
% intended to exactly follow ISO Prolog syntax, but there are some
% departures from that for three reasons:
%
%	(1) I wrote some of the code at home when the ISO Prolog draft
%	    was at uni - so in some places I just guessed.
%	(2) In some places the lexer reports an error when it shouldn't.
%	(3) There are a couple of hacks to make it compatible with NU-Prolog
%	    syntax.
%
% The parser is a relatively straight-forward top-down recursive descent
% parser, made somewhat complicated by the need to handle operator
% precedences.  It uses `lexer__get_token_list' to read a list of tokens.
% It uses the routines in module `ops' to look up operator precedences.
%
%--------------------------------------------------%

:- module parser.
:- interface.
:- import_module io, term_io.

:- pred parser__read_term(read_term, io__state, io__state).
:- mode parser__read_term(out, di, uo) is det.

	% The string is the filename to use for the current input stream;
	% this is used in constructing the term__contexts in the read term.
	% This interface is used to support the `:- pragma source_file'
	% directive.
:- pred parser__read_term(string, read_term, io__state, io__state).
:- mode parser__read_term(in, out, di, uo) is det.

%--------------------------------------------------%

pqueue

%--------------------------------------------------%
% Copyright (C) 1994-1995, 1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% file pqueue.m - implements a priority queue ADT.
% main author: conway.
% stability: high.
%
% A pqueue is a priority queue.  A priority queue holds a collection
% of key-value pairs; the interface provides operations to create
% an empty priority queue, to insert a key-value pair into a priority
% queue, and to remove the element with the lowest key.
%
% Insertion/removal is not guaranteed to be "stable"; that is,
% if you insert two values with the same key, the order in which
% they will be removed is unspecified.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module pqueue.

:- interface.

:- import_module assoc_list.

:- type pqueue(_K, _V).

	% Create an empty priority queue
:- pred pqueue__init(pqueue(_K, _V)).
:- mode pqueue__init(out) is det.

	% Insert a value V with key K into a priority queue
	% and return the new priority queue.
:- pred pqueue__insert(pqueue(K, V), K, V, pqueue(K, V)).
:- mode pqueue__insert(in, in, in, out) is det.

	% Remove the smallest item from the priority queue.
:- pred pqueue__remove(pqueue(K, V), K, V, pqueue(K, V)).
:- mode pqueue__remove(in, out, out, out) is semidet.

	% Extract all the items from a priority queue by
	% repeated removal, and place them in an association
	% list.
:- pred pqueue__to_assoc_list(pqueue(K, V), assoc_list(K, V)).
:- mode pqueue__to_assoc_list(in, out) is det.

	% Insert all the key-value pairs in an association list
	% into a priority queue.
:- pred pqueue__assoc_list_to_pqueue(assoc_list(K, V), pqueue(K, V)).
:- mode pqueue__assoc_list_to_pqueue(in, out) is det.

%--------------------------------------------------%

prolog

%--------------------------------------------------%
% Copyright (C) 1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: prolog.m.
% Main author: fjh.

% This file contains predicates that are intended to help people
% porting Prolog programs, or writing programs in the intersection
% of Mercury and Prolog.

%--------------------------------------------------%
:- module prolog.
:- interface.
:- import_module std_util, list.

% We define !/0 (and !/2 for dcgs) to be equivalent to `true'.  This is for
% backwards compatibility with Prolog systems.  But of course it only works
% if all your cuts are green cuts.

/********
cut is currently defined in mercury_builtin.m, for historical reasons.

:- pred ! is det.

:- pred !(T, T).
:- mode !(di, uo) is det.
:- mode !(in, out) is det.
********/

% Prolog arithmetic operators.

:- pred T =:= T.			% In Mercury, just use =
:- mode in =:= in is semidet.

:- pred T =\= T.			% In Mercury, just use \=
:- mode in =\= in is semidet.

/*******
is/2 is currently defined in int.m, for historical reasons.

:- pred is(T, T) is det.		% In Mercury, just use =
:- mode is(uo, di) is det.
:- mode is(out, in) is det.
******/

% Prolog term comparison operators.

:- pred T == T.				% In Mercury, just use =
:- mode in == in is semidet.

:- pred T \== T.			% In Mercury, just use \=
:- mode in \== in is semidet.

:- pred T @< T.
:- mode in @< in is semidet.

:- pred T @=< T.
:- mode in @=< in is semidet.

:- pred T @> T.
:- mode in @> in is semidet.

:- pred T @>= T.
:- mode in @>= in is semidet.

% Prolog's so-called "univ" operator, `=..'.
% Note: this is not related to Mercury's "univ" type!
% In Mercury, use `expand' (defined in module `std_util') instead.

:- pred T =.. univ_result.
:- mode in =.. out is det.
	%
	% Note that the Mercury =.. is a bit different to the Prolog
	% one.  We could make it slightly more similar by overloading '.'/2,
	% but that would cause ambiguities that might prevent type
	% inference in a lot of cases.
	% 
% :- type univ_result ---> '.'(string, list(univ)).
:- type univ_result == pair(string, list(univ)).

	% arg/3.  In Mercury, use argument/3 (defined in module std_util)
	% instead:
	%      arg(ArgNum, Term, Data) :- argument(Term, ArgNum - 1, Data).
	%
:- pred arg(int::in, T::in, univ::out) is semidet.

	% det_arg/3: like arg/3, but calls error/1 rather than failing
	% if the index is out of range.
	%
:- pred det_arg(int::in, T::in, univ::out) is det.
%--------------------------------------------------%

queue

%--------------------------------------------------%
% Copyright (C) 1994-1995, 1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: queue.m.
% Main author: fjh.
% Stability: high.

% This file contains a `queue' ADT.
% A queue holds a sequence of values, and provides operations
% to insert values at the end of the queue (queue__put) and remove them from
% the front of the queue (queue__get).
%
% This implementation is in terms of a pair of lists.
% The put and get operations are amortized constant-time.

%--------------------------------------------------%

:- module queue.
:- interface.
:- import_module list.

:- type queue(T).

	% `queue__init(Queue)' is true iff `Queue' is an empty queue.

:- pred queue__init(queue(T)).
:- mode queue__init(out) is det.

	% 'queue_equal(Q1, Q2)' is true iff Q1 and Q2 contain the same
	% elements in the same order.

:- pred queue__equal(queue(T), queue(T)).
:- mode queue__equal(in, in) is semidet.

	% `queue__is_empty(Queue)' is true iff `Queue' is an empty queue.

:- pred queue__is_empty(queue(T)).
:- mode queue__is_empty(in) is semidet.

	% `queue__is_full(Queue)' is intended to be true iff `Queue'
	% is a queue whose capacity is exhausted.  This
	% implementation allows arbitrary-sized queues, so queue__is_full
	% always fails.

:- pred queue__is_full(queue(T)).
:- mode queue__is_full(in) is semidet.

	% `queue__put(Queue0, Elem, Queue)' is true iff `Queue' is
	% the queue which results from appending `Elem' onto the end
	% of `Queue0'.

:- pred queue__put(queue(T), T, queue(T)).
:- mode queue__put(in, in, out) is det.

	% `queue__put_list(Queue0, Elems, Queue)' is true iff `Queue'
	% is the queue which results from inserting the items in the
	% list `Elems' into `Queue0'.

:- pred queue__put_list(queue(T), list(T), queue(T)).
:- mode queue__put_list(in, in, out) is det.

	% `queue__first(Queue, Elem)' is true iff `Queue' is a non-empty
	% queue whose first element is `Elem'.

:- pred queue__first(queue(T), T).
:- mode queue__first(in, out) is semidet.

	% `queue__get(Queue0, Elem, Queue)' is true iff `Queue0' is
	% a non-empty queue whose first element is `Elem', and `Queue'
	% the queue which results from removing that element from 
	% the front of `Queue0'.

:- pred queue__get(queue(T), T, queue(T)).
:- mode queue__get(in, out, out) is semidet.

	% `queue__length(Queue, Length)' is true iff `Queue' is a queue
	% containing `Length' elements.

:- pred queue__length(queue(T), int).
:- mode queue__length(in, out) is det.

	% `queue__list_to_queue(List, Queue)' is true iff `Queue' is a queue
	% containing the elements of List, with the first element of List at
	% the head of the queue.

:- pred queue__list_to_queue(list(T), queue(T)).
:- mode queue__list_to_queue(in, out) is det.

%--------------------------------------------------%

random

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% file: rand.m
% main author: conway
% stability: low
%
% Define a set of random number generator predicates. This implementation
% uses a threaded random-number supply. It could be made non-unique, but
% since each thread returns the same list of random numbers, in the interests
% of safety, it is declared with (backtrackable) unique modes.
%
%--------------------------------------------------%

:- module random.

:- interface.

:- import_module list.

	% The type `random__supply' represents a supply of random numbers.
:- type random__supply.

	% random__init(Seed, RS): creates a supply of random numbers RS
	% using the specified Seed.
:- pred random__init(int, random__supply).
:- mode random__init(in, uo) is det.

	% random__random(Num, RS0, RS): extracts a number Num in the
	% range 0 .. RandMax from the random number supply RS0, and
	% binds RS to the new state of the random number supply.
:- pred random__random(int, random__supply, random__supply).
:- mode random__random(out, mdi, muo) is det.

	% random__randmax(RandMax, RS0, RS): binds Randax to the maximum
	% random number that can be returned from the random number
	% supply RS0, and returns RS = RS0.
:- pred random__randmax(int, random__supply, random__supply).
:- mode random__randmax(out, mdi, muo) is det.

%--------------------------------------------------%

rbtree

%--------------------------------------------------%
% Copyright (C) 1995, 1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
%  Red-black tree module.
%  Main author: petdr.
%  Stability: medium.
%
%  Contains an implementation of red black trees.
%
% *** Exit conditions of main predicates ***
% insert:
%	fails if key already in tree.
% update:
%	changes value of key already in tree.  fails if key doesn't exist.
% set:
%	insert's or update's. Never fails.
%
% insert_duplicate:
%	insert's duplicate keys into the tree, never fails.  Search doesn't
%	yet support looking for duplicates.
%
% delete:
%	delete's a node from the tree if it exists.
% remove:
%	fails if node to remove doesn't exist in the tree.
%
% lookup:
%	Aborts program if key looked up doesn't exist.
% search:
%	Fails if key looked up doesn't exist.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module rbtree.
:- interface.

:- import_module list, assoc_list.

:- type rbtree(Key, Value).

	% Initialise the data structure.
:- pred rbtree__init(rbtree(K, V)).
:- mode rbtree__init(out) is det.

	% Insert's a new key-value pair into the tree.  Fails if key 
	% already in the tree.
:- pred rbtree__insert(rbtree(K, V), K, V, rbtree(K, V)).
:- mode rbtree__insert(in, in, in, out) is semidet.

	% Update's the value associated with a key.  Fails if the key 
	% doesn't exist.
:- pred rbtree__update(rbtree(K, V), K, V, rbtree(K, V)).
:- mode rbtree__update(in, in, in, out) is semidet.

	% Set's a value irregardless of whether key exists or not.  Never
	% fails.
:- pred rbtree__set(rbtree(K, V), K, V, rbtree(K, V)).
:- mode rbtree__set(in, in, in, out) is det.

	% Insert a duplicate key into the tree.  Never fails.
:- pred rbtree__insert_duplicate(rbtree(K, V), K, V, rbtree(K, V)).
:- mode rbtree__insert_duplicate(in, in, in, out) is det.

	% Lookup a value associated with a key.  Program abort's if key
	% doesn't exist.
:- pred rbtree__lookup(rbtree(K, V), K, V).
:- mode rbtree__lookup(in, in, out) is det.

	% Search for a key-value pair using the key.  Fails if key doesn't
	% exist.
:- pred rbtree__search(rbtree(K, V), K, V).
:- mode rbtree__search(in, in, out) is semidet.

	% Delete the key value pair associated with a key.  Does nothing
	% if the key doesn't exist.
:- pred rbtree__delete(rbtree(K, V), K, rbtree(K, V)).
:- mode rbtree__delete(in, in, out) is det.

	% Remove the key value pair associated with a key.  Fails
	% if the key doesn't exist.
:- pred rbtree__remove(rbtree(K, V), K, rbtree(K, V)).
:- mode rbtree__remove(in, in, out) is semidet.

	% Return's an in-order list of all the key's in the rbtree.
:- pred rbtree__keys(rbtree(K, V), list(K)).
:- mode rbtree__keys(in, out) is det.

	% Return's a list of values such that the key's associated with the
	% values are in-order.
:- pred rbtree__values(rbtree(K, V), list(V)).
:- mode rbtree__values(in, out) is det.

	% Count the number of elements in the tree
:- pred rbtree__count(rbtree(K, V), int).
:- mode rbtree__count(in, out) is det.

:- pred rbtree__assoc_list_to_rbtree(assoc_list(K, V), rbtree(K, V)).
:- mode rbtree__assoc_list_to_rbtree(in, out) is det.

:- pred rbtree__rbtree_to_assoc_list(rbtree(K, V), assoc_list(K, V)).
:- mode rbtree__rbtree_to_assoc_list(in, out) is det.

%--------------------------------------------------%

relation

%--------------------------------------------------%
% Copyright (C) 1995-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% file: relation.m.
% main author: bromage, petdr.
% stability: low.
%
% This module defines a data type for binary relations over reflexive
% domains.
%
% In fact, this is exactly equivalent to a graph/1 type.
%--------------------------------------------------%
%--------------------------------------------------%

:- module relation.

:- interface.
:- import_module list, set, set_bbbtree, assoc_list.

:- type relation(T).

:- type relation_key.

	% relation__init creates a new relation.
:- pred relation__init(relation(T)).
:- mode relation__init(out) is det.

	% relation__add_element adds an element to the domain of a
	% relation.  Return the old relation_key if one already
	% exists.
:- pred relation__add_element(relation(T), T, relation_key, relation(T)).
:- mode relation__add_element(in, in, out, out) is det.

	% relation__search_element returns the relation_key associated
        % with a domain element.  Fail if the relation_key is not valid.
:- pred relation__search_element(relation(T), T, relation_key).
:- mode relation__search_element(in, in, out) is semidet.

	% relation__lookup_element returns the relation_key associated
        % with a domain element.  Abort if the relation_key is not valid.
:- pred relation__lookup_element(relation(T), T, relation_key).
:- mode relation__lookup_element(in, in, out) is det.

	% relation__search_key returns the domain element associated
	% with a relation_key.  Fail if the relation_key is not valid.
:- pred relation__search_key(relation(T), relation_key, T).
:- mode relation__search_key(in, in, out) is semidet.

	% relation__lookup_key returns the domain element associated
	% with a relation_key.  Abort if the relation_key is not valid.
:- pred relation__lookup_key(relation(T), relation_key, T).
:- mode relation__lookup_key(in, in, out) is det.

	% relation__add adds an element to the relation.
:- pred relation__add(relation(T), relation_key, relation_key, relation(T)).
:- mode relation__add(in, in, in, out) is det.

	% relation__add_assoc_list adds a list of elements to a
	% relation.
:- pred relation__add_assoc_list(relation(T),
		assoc_list(relation_key, relation_key), relation(T)).
:- mode relation__add_assoc_list(in, in, out) is det.

	% relation__remove removes an element from the relation.
:- pred relation__remove(relation(T), relation_key, relation_key,
		relation(T)).
:- mode relation__remove(in, in, in, out) is det.

	% relation__remove_assoc_list removes a list of elements
	% from a relation.
:- pred relation__remove_assoc_list(relation(T),
		assoc_list(relation_key, relation_key), relation(T)).
:- mode relation__remove_assoc_list(in, in, out) is det.

	% relation__lookup checks to see if an element is
	% in the relation.
:- pred relation__lookup(relation(T), relation_key, relation_key).
:- mode relation__lookup(in, in, out) is nondet.
:- mode relation__lookup(in, in, in) is semidet.

	% relation__reverse_lookup checks to see if an element is
	% in the relation.
:- pred relation__reverse_lookup(relation(T), relation_key, relation_key).
:- mode relation__reverse_lookup(in, out, in) is nondet.
:- mode relation__reverse_lookup(in, in, in) is semidet.

	% relation__lookup_from returns the set of elements
	% y such that xRy, given an x.
:- pred relation__lookup_from(relation(T), relation_key, set(relation_key)).
:- mode relation__lookup_from(in, in, out) is det.

	% relation__lookup_to returns the set of elements
	% x such that xRy, given some y.
:- pred relation__lookup_to(relation(T), relation_key, set(relation_key)).
:- mode relation__lookup_to(in, in, out) is det.

	% relation__to_assoc_list turns a relation into a list of
	% pairs of elements.
:- pred relation__to_assoc_list(relation(T),
	assoc_list(relation_key, relation_key)).
:- mode relation__to_assoc_list(in, out) is det.

	% relation__from_assoc_list turns a list of pairs of
	% elements into a relation.
% :- pred relation__from_assoc_list(assoc_list(T, T), relation(T)).
% :- mode relation__from_assoc_list(in, out) is det.

	% relation__domain finds the set of all elements in the
	% domain of a relation.
:- pred relation__domain(relation(T), set(T)).
:- mode relation__domain(in, out) is det.

	% relation__inverse(R, R') is true iff for all x, y
	% in the domain of R, xRy if yR'x.
:- pred relation__inverse(relation(T), relation(T)).
:- mode relation__inverse(in, out) is det.

	% relation__compose(R1, R2, R) is true if R is the
	% composition of the relations R1 and R2.
% :- pred relation__compose(relation(T), relation(T), relation(T)).
% :- mode relation__compose(in, in, out) is det.

	% relation__dfs(Rel, X, Dfs) is true if Dfs is a
	% depth-first sorting of Rel starting at X.  The
	% set of elements in the list Dfs is exactly equal
	% to the set of elements y such that xR*y, where
	% R* is the reflexive transitive closure of R.
:- pred relation__dfs(relation(T), relation_key, list(relation_key)).
:- mode relation__dfs(in, in, out) is det.

	% relation__dfsrev(Rel, X, DfsRev) is true if DfsRev is a
	% reverse depth-first sorting of Rel starting at X.  The
	% set of elements in the list Dfs is exactly equal
	% to the set of elements y such that xR*y, where
	% R* is the reflexive transitive closure of R.
:- pred relation__dfsrev(relation(T), relation_key, list(relation_key)).
:- mode relation__dfsrev(in, in, out) is det.

	% relation__dfs(Rel, Dfs) is true if Dfs is a depth-
	% first sorting of Rel, i.e. a list of the nodes in Rel
	% such that it contains all elements in the relation and all 
	% the children of a node are placed in the list before 
	% the parent.
:- pred relation__dfs(relation(T), list(relation_key)).
:- mode relation__dfs(in, out) is det.

	% relation__dfsrev(Rel, DfsRev) is true if DfsRev is a reverse 
	% depth-first sorting of Rel.  ie DfsRev is the reverse of Dfs
	% from relation__dfs/2.
:- pred relation__dfsrev(relation(T), list(relation_key)).
:- mode relation__dfsrev(in, out) is det.

	% relation__dfs(Rel, X, Visit0, Visit, Dfs) is true 
	% if Dfs is a depth-first sorting of Rel starting at 
	% X providing we have already visited Visit0 nodes, 
	% i.e.  a list of nodes such that all the unvisited 
	% children of a node are placed in the list before the 
	% parent.  Visit0 allows us to initialise a set of
	% previously visited nodes.  Visit is Dfs + Visit0.
:- pred relation__dfs(relation(T), relation_key, set_bbbtree(relation_key),
		set_bbbtree(relation_key), list(relation_key)).
:- mode relation__dfs(in, in, in, out, out) is det.

	% relation__dfsrev(Rel, X, Visit0, Visit, DfsRev) is true if 
	% DfsRev is a reverse depth-first sorting of Rel starting at X 
	% providing we have already visited Visit0 nodes, 
	% ie the reverse of Dfs from relation__dfs/5.
	% Visit is Visit0 + DfsRev.
:- pred relation__dfsrev(relation(T), relation_key,
		set_bbbtree(relation_key), set_bbbtree(relation_key),
		list(relation_key)).
:- mode relation__dfsrev(in, in, in, out, out) is det.

	% relation__is_dag(R) is true iff R is a directed acyclic graph.
:- pred relation__is_dag(relation(T)).
:- mode relation__is_dag(in) is semidet.

	% relation__components(R, Comp) is true if Comp
	% is the set of the connected components of R.
:- pred relation__components(relation(T), set(set(relation_key))).
:- mode relation__components(in, out) is det.

	% relation__cliques(R, Cliques) is true if
	% Cliques is the set of the strongly connected
	% components (cliques) of R.
:- pred relation__cliques(relation(T), set(set(relation_key))).
:- mode relation__cliques(in, out) is det.

	% relation__reduced(R, Red) is true if Red is
	% the reduced relation (relation of cliques)
	% obtained from R.
:- pred relation__reduced(relation(T), relation(set(T))).
:- mode relation__reduced(in, out) is det.

	% relation__tsort(R, TS) is true if TS is a
	% topological sorting of R.  It fails if R
	% is cyclic.
:- pred relation__tsort(relation(T), list(T)).
:- mode relation__tsort(in, out) is semidet.

	% relation__atsort(R, ATS) is true if ATS is
	% a topological sorting of the cliques in R.
:- pred relation__atsort(relation(T), list(set(T))).
:- mode relation__atsort(in, out) is det.

	% relation__sc(R, SC) is true if SC is the
	% symmetric closure of R.  In graph terms,
	% symmetric closure % is the same as turning
	% a directed graph into an undirected graph.
:- pred relation__sc(relation(T), relation(T)).
:- mode relation__sc(in, out) is det.

	% relation__tc(R, TC) is true if TC is the
	% transitive closure of R.
:- pred relation__tc(relation(T), relation(T)).
:- mode relation__tc(in, out) is det.

	% relation__rtc(R, RTC) is true if RTC is the
	% reflexive transitive closure of R.
:- pred relation__rtc(relation(T), relation(T)).
:- mode relation__rtc(in, out) is det.

%--------------------------------------------------%

require

%--------------------------------------------------%
% Copyright (C) 1993-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

:- module require.

% Main author: fjh.
% Stability: medium to high.

% This module provides features similar to <assert.h> in C.

%--------------------------------------------------%
:- interface.

:- pred error(string).
:- mode error(in) is erroneous.

%	error(Message).
%		Abort with error message.


:- pred	require(pred, string).
:- mode	require((pred) is semidet, in) is det.

%	require(Goal, Message).
%		Call goal, and abort with error message if Goal fails.
%		This is not as useful as you might imagine, since it requires
%		that the goal not produce any output variables.  In
%		most circumstances you should use an explicit if-then-else
%		with a call to error/1 in the "else".

%--------------------------------------------------%

set

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: set.m.
% Main authors: conway, fjh, benyi.
% Stability: high.

% This module provides a set ADT. 
% The implementation represents sets using ordered lists.
% This file just calls the equivalent predicates in set_ordlist.

%--------------------------------------------------%

:- module set.
:- interface.
:- import_module bool, list.

:- type set(T).

	% `set__list_to_set(List, Set)' is true iff `Set' is the set 
	% containing only the members of `List'.

:- pred set__list_to_set(list(T), set(T)).
:- mode set__list_to_set(in, out) is det.

	% `set__sorted_list_to_set(List, Set)' is true iff `Set' is the set 
	% containing only the members of `List'.  `List' must be sorted
	% and must not contain any duplicates.

:- pred set__sorted_list_to_set(list(T), set(T)).
:- mode set__sorted_list_to_set(in, out) is det.

	% `set__to_sorted_list(Set, List)' is true iff `List' is the list
	% of all the members of `Set', in sorted order without any
	% duplicates.

:- pred set__to_sorted_list(set(T), list(T)).
:- mode set__to_sorted_list(in, out) is det.

	% `set__init(Set)' is true iff `Set' is an empty set.

:- pred set__init(set(T)).
:- mode set__init(uo) is det.

	% `set__singleton_set(Set, Elem)' is true iff `Set' is the set
	% containing just the single element `Elem'.

:- pred set__singleton_set(set(T), T).
:- mode set__singleton_set(in, out) is semidet.
:- mode set__singleton_set(out, in) is det.

	% `set__equal(SetA, SetB)' is true iff
	% `SetA' and `SetB' contain the same elements.

:- pred set__equal(set(T), set(T)).
:- mode set__equal(in, in) is semidet.

:- pred set__empty(set(T)).
:- mode set__empty(in) is semidet.

	% `set__subset(SetA, SetB)' is true iff `SetA' is a subset of `SetB'.

:- pred set__subset(set(T), set(T)).
:- mode set__subset(in, in) is semidet.

	% `set__superset(SetA, SetB)' is true iff `SetA' is a
	% superset of `SetB'.

:- pred set__superset(set(T), set(T)).
:- mode set__superset(in, in) is semidet.

	% `set__member(X, Set)' is true iff `X' is a member of `Set'.

:- pred set__member(T, set(T)).
:- mode set__member(in, in) is semidet.
:- mode set__member(out, in) is nondet.

	% `set_is_member(X, Set, Result)' returns
	% `Result = yes' iff `X' is a member of `Set'.

:- pred set__is_member(T, set(T), bool).
:- mode set__is_member(in, in, out) is det.

	% `set__insert(Set0, X, Set)' is true iff `Set' is the union of
	% `Set0' and the set containing only `X'.

:- pred set__insert(set(T), T, set(T)).
:- mode set__insert(di, di, uo) is det.
:- mode set__insert(in, in, out) is det.

	% `set__insert_list(Set0, Xs, Set)' is true iff `Set' is the union of
	% `Set0' and the set containing only the members of `Xs'.

:- pred set__insert_list(set(T), list(T), set(T)).
:- mode set__insert_list(in, in, out) is det.

	% `set__delete(Set0, X, Set)' is true iff `Set' is the relative
	% complement of `Set0' and the set containing only `X', i.e.
	% if `Set' is the set which contains all the elements of `Set0'
	% except `X'.

:- pred set__delete(set(T), T, set(T)).
% :- mode set__delete(di, in, uo) is det.
:- mode set__delete(in, in, out) is det.

	% `set__delete_list(Set0, Xs, Set)' is true iff `Set' is the relative
	% complement of `Set0' and the set containing only the members of
	% `Xs'.

:- pred set__delete_list(set(T), list(T), set(T)).
:- mode set__delete_list(in, in, out) is det.

	% `set__remove(Set0, X, Set)' is true iff `Set0' contains `X',
	% and `Set' is the relative complement of `Set0' and the set
	% containing only `X', i.e.  if `Set' is the set which contains
	% all the elements of `Set0' except `X'.

:- pred set__remove(set(T), T, set(T)).
:- mode set__remove(in, in, out) is semidet.

	% `set__remove_list(Set0, Xs, Set)' is true iff Xs does not
	% contain any duplicates, `Set0' contains every member of `Xs',
	% and `Set' is the relative complement of `Set0' and the set
	% containing only the members of `Xs'.

:- pred set__remove_list(set(T), list(T), set(T)).
:- mode set__remove_list(in, in, out) is semidet.

:- pred set__remove_least(set(T), T, set(T)).
:- mode set__remove_least(in, out, out) is semidet.

	% `set_union(SetA, SetB, Set)' is true iff `Set' is the union of
	% `SetA' and `SetB'.  If the sets are known to be of different
	% sizes, then for efficiency make `SetA' the larger of the two.
	% (The current implementation, using sorted lists with duplicates
	% removed is not sensitive to the ordering of the input arguments
	% but other set implementations may be, so observing this convention
	% will make it less likely that you will encounter problems if
	% the implementation is changed.)

:- pred set__union(set(T), set(T), set(T)).
:- mode set__union(in, in, out) is det.

	% `set__power_union(A, B)' is true iff `B' is the union of
	% all the sets in `A'

:- pred set__power_union(set(set(T)), set(T)).
:- mode set__power_union(in, out) is det.

	% `set__intersect(SetA, SetB, Set)' is true iff `Set' is the
	% intersection of `SetA' and `SetB'. If the two sets are
	% known to be unequal in size, then making SetA be the larger
	% set will usually be more efficient.
	% (The current implementation, using sorted lists with duplicates
	% removed is not sensitive to the ordering of the input arguments
	% but other set implementations may be, so observing this convention
	% will make it less likely that you will encounter problems if
	% the implementation is changed.)

:- pred set__intersect(set(T), set(T), set(T)).
:- mode set__intersect(in, in, out) is det.

	% `set__power_intersect(A, B)' is true iff `B' is the intersection of
	% all the sets in `A'

:- pred set__power_intersect(set(set(T)), set(T)).
:- mode set__power_intersect(in, out) is det.

	% `set__difference(SetA, SetB, Set)' is true iff `Set' is the
	% set containing all the elements of `SetA' except those that
	% occur in `SetB'

:- pred set__difference(set(T), set(T), set(T)).
:- mode set__difference(in, in, out) is det.

%--------------------------------------------------%

set_bbbtree

%--------------------------------------------------%
% Copyright (C) 1995-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: set_bbbtree.m.
% Main authors: benyi.
% Stability: low.

% set_bbbtree - implements sets using bounded balanced binary trees.

%--------------------------------------------------%

:- module set_bbbtree.

:- interface.

:- import_module bool, list.

:- type set_bbbtree(T).


	% `set_bbbtree__init(Set)' returns an initialized empty set.

:- pred set_bbbtree__init(set_bbbtree(T)).
:- mode set_bbbtree__init(uo) is det.


        % `set_bbbtree__empty(Set) is true iff `Set' is contains no elements.

:- pred set_bbbtree__empty(set_bbbtree(T)).
:- mode set_bbbtree__empty(in) is semidet.


	% `set_bbbtree__size(Set, Size)' is true iff `Size' is the cardinality
	% of `Set'.

:- pred set_bbbtree__size(set_bbbtree(T), int).
:- mode set_bbbtree__size(in, out) is det.


	% `set_bbbtree__member(X, Set)' is true iff `X' is a member of `Set'.
	% O(lg n) for (in, in) and O(1) for (out, in).

:- pred set_bbbtree__member(T, set_bbbtree(T)).
:- mode set_bbbtree__member(in, in) is semidet.
:- mode set_bbbtree__member(out, in) is nondet.


	% `set_bbbtree__is_member(X, Set, Result)' is true iff `X' is a member
	% of `Set'.

:- pred set_bbbtree__is_member(T, set_bbbtree(T), bool).
:- mode set_bbbtree__is_member(in, in, out) is det.


	% `set_bbbtree__least(Set, X)' is true iff `X' is smaller than all
	% the other members of `Set'.

:- pred set_bbbtree__least(set_bbbtree(T), T).
:- mode set_bbbtree__least(in, out) is semidet.
:- mode set_bbbtree__least(in, in) is semidet.


	% `set_bbbtree__largest(Set, X)' is true iff `X' is larger than all
	% the other members of `Set'.

:- pred set_bbbtree__largest(set_bbbtree(T), T).
:- mode set_bbbtree__largest(in, out) is semidet.
:- mode set_bbbtree__largest(in, in) is semidet.


	% `set_bbbtree__singleton_set(Set, X)' is true iff `Set' is the set
	% containing just the single element `X'.

:- pred set_bbbtree__singleton_set(set_bbbtree(T), T).
:- mode set_bbbtree__singleton_set(uo, di) is det.
:- mode set_bbbtree__singleton_set(in, out) is semidet.
:- mode set_bbbtree__singleton_set(in, in) is semidet.
:- mode set_bbbtree__singleton_set(out, in) is det.


	% `set_bbbtree__equal(SetA, SetB)' is true iff `SetA' and `SetB'
	% contain the same elements.

:- pred set_bbbtree__equal(set_bbbtree(T), set_bbbtree(T)).
:- mode set_bbbtree__equal(in, in) is semidet.


	% `set_bbbtree__insert(Set0, X, Set)' is true iff `Set' is the union of
	% `Set0' and the set containing only `X'.

:- pred set_bbbtree__insert(set_bbbtree(T), T, set_bbbtree(T)).
:- mode set_bbbtree__insert(di, di, uo) is det.
:- mode set_bbbtree__insert(in, in, out) is det.


	% `set_bbbtree__insert_list(Set0, Xs, Set)' is true iff `Set' is
	% the union of `Set0' and the set containing only the members of `Xs'.

:- pred set_bbbtree__insert_list(set_bbbtree(T), list(T), set_bbbtree(T)).
% :- mode set_bbbtree__insert_list(di, di, uo) is det.
:- mode set_bbbtree__insert_list(in, in, out) is det.


	% `set_bbbtree__delete(Set0, X, Set)' is true iff `Set' is the relative
	% complement of `Set0' and the set containing only `X', i.e.
	% if `Set' is the set which contains all the elements of `Set0'
	% except `X'.

:- pred set_bbbtree__delete(set_bbbtree(T), T, set_bbbtree(T)).
:- mode set_bbbtree__delete(di, in, uo) is det.
:- mode set_bbbtree__delete(in, in, out) is det.


	% `set_bbbtree__delete_list(Set0, Xs, Set)' is true iff `Set' is the
	% relative complement of `Set0' and the set containing only the members
	% of `Xs'.

:- pred set_bbbtree__delete_list(set_bbbtree(T), list(T), set_bbbtree(T)).
% :- mode set_bbbtree__delete_list(di, in, uo) is det.
:- mode set_bbbtree__delete_list(in, in, out) is det.


	% `set_bbbtree__remove(Set0, X, Set)' is true iff `Set0' contains `X',
	% and `Set' is the relative complement of `Set0' and the set
	% containing only `X', i.e.  if `Set' is the set which contains
	% all the elements of `Set0' except `X'.

:- pred set_bbbtree__remove(set_bbbtree(T), T, set_bbbtree(T)).
:- mode set_bbbtree__remove(in, in, out) is semidet.


	% `set_bbbtree__remove_list(Set0, Xs, Set)' is true iff Xs does not
	% contain any duplicates, `Set0' contains every member of `Xs',
	% and `Set' is the relative complement of `Set0' and the set
	% containing only the members of `Xs'.

:- pred set_bbbtree__remove_list(set_bbbtree(T), list(T), set_bbbtree(T)).
:- mode set_bbbtree__remove_list(in, in, out) is semidet.


	% `set_bbbtree__remove_least(Set0, X, Set)' is true iff the union if
	% `X' and `Set' is `Set0' and `X' is smaller than all the elements of
	% `Set'.

:- pred set_bbbtree__remove_least(set_bbbtree(T), T, set_bbbtree(T)).
:- mode set_bbbtree__remove_least(in, out, out) is semidet.


	% `set_bbbtree__remove_largest(Set0, X, Set)' is true iff the union if
	% `X' and `Set' is `Set0' and `X' is larger than all the elements of
	% `Set'.

:- pred set_bbbtree__remove_largest(set_bbbtree(T), T, set_bbbtree(T)).
:- mode set_bbbtree__remove_largest(in, out, out) is semidet.


	% `set_bbbtree__list_to_set(List, Set)' is true iff `Set' is the set
	% containing only the members of `List'. O(n lg n)

:- pred set_bbbtree__list_to_set(list(T), set_bbbtree(T)).
% :- mode set_bbbtree__list_to_set(di, uo) is det.
:- mode set_bbbtree__list_to_set(in, out) is det.


	% `set_bbbtree__sorted_list_to_set(List, Set)' is true iff `Set' is the
	% set containing only the members of `List'.
	% `List' must be sorted. O(n).

:- pred set_bbbtree__sorted_list_to_set(list(T), set_bbbtree(T)).
% :- mode set_bbbtree__sorted_list_to_set(di, uo) is det.
:- mode set_bbbtree__sorted_list_to_set(in, out) is det.


	% `set_bbbtree__sorted_list_to_set_len(List, Set, N)' is true iff
	% `Set' is the set set containing only the members of `List' and `N'
	% is the length of the list. If the length of the list is already known
	% then a noticable speed improvement can be expected over
	% `set_bbbtree__sorted_list_to_set' as a significant cost involved
	% with `set_bbbtree__sorted_list_to_set' is the call to list__length.
	% `List' must be sorted. O(n).

:- pred set_bbbtree__sorted_list_to_set_len(list(T), set_bbbtree(T), int).
% :- mode set_bbbtree__sorted_list_to_set_len(di, uo, in) is det.
:- mode set_bbbtree__sorted_list_to_set_len(in, out, in) is det.


	% `set_bbbtree__to_sorted_list(Set, List)' is true iff `List' is the
	% list of all the members of `Set', in sorted order. O(n).

:- pred set_bbbtree__to_sorted_list(set_bbbtree(T), list(T)).
:- mode set_bbbtree__to_sorted_list(di, uo) is det.
:- mode set_bbbtree__to_sorted_list(in, out) is det.


	% `set_bbbtree__union(SetA, SetB, Set)' is true iff `Set' is the union
	% of `SetA' and `SetB'.

:- pred set_bbbtree__union(set_bbbtree(T), set_bbbtree(T), set_bbbtree(T)).
:- mode set_bbbtree__union(in, in, out) is det.


	% `set_bbbtree__power_union(Sets, Set)' is true iff `Set' is the union
	% of all the sets in `Sets'

:- pred set_bbbtree__power_union(set_bbbtree(set_bbbtree(T)), set_bbbtree(T)).
:- mode set_bbbtree__power_union(in, out) is det.


	% `set_bbbtree__intersect(SetA, SetB, Set)' is true iff `Set' is the
	% intersection of `SetA' and `SetB'.

:- pred set_bbbtree__intersect(set_bbbtree(T), set_bbbtree(T),
					set_bbbtree(T)).
:- mode set_bbbtree__intersect(in, in, out) is det.


	% `set_bbbtree__power_intersect(Sets, Set) is true iff `Set' is the
	% interscetion of the sets in `Sets'.

:- pred set_bbbtree__power_intersect(set_bbbtree(set_bbbtree(T)),
					set_bbbtree(T)).
:- mode set_bbbtree__power_intersect(in, out) is det.


	% `set_bbtree__difference(SetA, SetB, Set)' is true iff `Set' is the
	%  set containing all the elements of `SetA' except those that
	% occur in `SetB'.

:- pred set_bbbtree__difference(set_bbbtree(T), set_bbbtree(T),
					set_bbbtree(T)).
:- mode set_bbbtree__difference(in, in, out) is det.


	% `set_bbbtree__subset(SetA, SetB)' is true iff all the elements of
	% `SetA' are also elements of `SetB'.

:- pred set_bbbtree__subset(set_bbbtree(T), set_bbbtree(T)).
:- mode set_bbbtree__subset(in, in) is semidet.


	% `set_bbbtree__superset(SetA, SetB)' is true iff all the elements of
	% `SetB' are also elements of `SetA'.

:- pred set_bbbtree__superset(set_bbbtree(T), set_bbbtree(T)).
:- mode set_bbbtree__superset(in, in) is semidet.

%--------------------------------------------------%
%--------------------------------------------------%

set_ordlist

%--------------------------------------------------%
% Copyright (C) 1996-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: set_ordlist.m.
% Main authors: conway, fjh.
% Stability: medium.

% This file contains a `set' ADT.
% Sets are implemented here as sorted lists without duplicates.

%--------------------------------------------------%

:- module set_ordlist.
:- interface.
:- import_module bool, list.

:- type set_ordlist(_T).

	% `set_ordlist__list_to_set(List, Set)' is true iff `Set' is the set 
	% containing only the members of `List'.

:- pred set_ordlist__list_to_set(list(T), set_ordlist(T)).
:- mode set_ordlist__list_to_set(in, out) is det.

	% `set_ordlist__sorted_list_to_set(List, Set)' is true iff `Set' is
	% the set containing only the members of `List'.  `List' must be sorted.

:- pred set_ordlist__sorted_list_to_set(list(T), set_ordlist(T)).
:- mode set_ordlist__sorted_list_to_set(in, out) is det.

	% `set_ordlist__to_sorted_list(Set, List)' is true iff `List' is the
	% list of all the members of `Set', in sorted order.

:- pred set_ordlist__to_sorted_list(set_ordlist(T), list(T)).
:- mode set_ordlist__to_sorted_list(in, out) is det.

	% `set_ordlist__init(Set)' is true iff `Set' is an empty set.

:- pred set_ordlist__init(set_ordlist(_T)).
:- mode set_ordlist__init(uo) is det.

	% `set_ordlist__singleton_set(Set, Elem)' is true iff `Set' is the set
	% containing just the single element `Elem'.

:- pred set_ordlist__singleton_set(set_ordlist(T), T).
:- mode set_ordlist__singleton_set(in, out) is semidet.
:- mode set_ordlist__singleton_set(out, in) is det.

	% `set_ordlist__equal(SetA, SetB)' is true iff
	% `SetA' and `SetB' contain the same elements.

:- pred set_ordlist__equal(set_ordlist(T), set_ordlist(T)).
:- mode set_ordlist__equal(in, in) is semidet.

	% `set_ordlist__empty(Set)' is true iff `Set' is an empty set.

:- pred set_ordlist__empty(set_ordlist(_T)).
:- mode set_ordlist__empty(in) is semidet.

	% `set_ordlist__subset(SetA, SetB)' is true iff `SetA' is a subset of
	% `SetB'.

:- pred set_ordlist__subset(set_ordlist(T), set_ordlist(T)).
:- mode set_ordlist__subset(in, in) is semidet.

	% `set_ordlist__superset(SetA, SetB)' is true iff `SetA' is a
	% superset of `SetB'.

:- pred set_ordlist__superset(set_ordlist(T), set_ordlist(T)).
:- mode set_ordlist__superset(in, in) is semidet.

	% `set_ordlist__member(X, Set)' is true iff `X' is a member of `Set'.

:- pred set_ordlist__member(T, set_ordlist(T)).
:- mode set_ordlist__member(in, in) is semidet.
:- mode set_ordlist__member(out, in) is nondet.

	% `set_ordlist__is_member(X, Set, Result)' returns
	% `Result = yes' iff `X' is a member of `Set'.

:- pred set_ordlist__is_member(T, set_ordlist(T), bool).
:- mode set_ordlist__is_member(in, in, out) is det.

	% `set_ordlist__insert(Set0, X, Set)' is true iff `Set' is the union
	% of `Set0' and the set containing only `X'.

:- pred set_ordlist__insert(set_ordlist(T), T, set_ordlist(T)).
:- mode set_ordlist__insert(di, di, uo) is det.
:- mode set_ordlist__insert(in, in, out) is det.

	% `set_ordlist__insert_list(Set0, Xs, Set)' is true iff `Set' is the
	% union of `Set0' and the set containing only the members of `Xs'.

:- pred set_ordlist__insert_list(set_ordlist(T), list(T), set_ordlist(T)).
:- mode set_ordlist__insert_list(in, in, out) is det.

	% `set_ordlist__delete(Set0, X, Set)' is true iff `Set' is the
	% relative complement of `Set0' and the set containing only `X', i.e.
	% if `Set' is the set which contains all the elements of `Set0'
	% except `X'.

:- pred set_ordlist__delete(set_ordlist(T), T, set_ordlist(T)).
% :- mode set_ordlist__delete(di, in, uo) is det.
:- mode set_ordlist__delete(in, in, out) is det.

	% `set_ordlist__delete_list(Set0, Xs, Set)' is true iff `Set' is the
	% relative complement of `Set0' and the set containing only the members
	% of `Xs'.

:- pred set_ordlist__delete_list(set_ordlist(T), list(T), set_ordlist(T)).
:- mode set_ordlist__delete_list(in, in, out) is det.

	% `set_ordlist__remove(Set0, X, Set)' is true iff `Set0' contains `X',
	% and `Set' is the relative complement of `Set0' and the set
	% containing only `X', i.e.  if `Set' is the set which contains
	% all the elements of `Set0' except `X'.

:- pred set_ordlist__remove(set_ordlist(T), T, set_ordlist(T)).
:- mode set_ordlist__remove(in, in, out) is semidet.

	% `set_ordlist__remove_list(Set0, Xs, Set)' is true iff Xs does not
	% contain any duplicates, `Set0' contains every member of `Xs',
	% and `Set' is the relative complement of `Set0' and the set
	% containing only the members of `Xs'.

:- pred set_ordlist__remove_list(set_ordlist(T), list(T), set_ordlist(T)).
:- mode set_ordlist__remove_list(in, in, out) is semidet.

	% `set_ordlist__remove_least(Set0, X, Set)' is true iff `X' is the
	% least element in `Set0', and `Set' is the set which contains all the
	% elements of `Set0' except `X'.

:- pred set_ordlist__remove_least(set_ordlist(T), T, set_ordlist(T)).
:- mode set_ordlist__remove_least(in, out, out) is semidet.

	% `set_ordlist_union(SetA, SetB, Set)' is true iff `Set' is the union
	% of `SetA' and `SetB'. The efficiency of the union operation is
	% O(card(SetA)+card(SetB)) and is not sensitive to the argument
	% ordering.

:- pred set_ordlist__union(set_ordlist(T), set_ordlist(T),
							set_ordlist(T)).
:- mode set_ordlist__union(in, in, out) is det.

	% `set_ordlist__power_union(A, B)' is true iff `B' is the union of
	% all the sets in `A'

:- pred set_ordlist__power_union(set_ordlist(set_ordlist(T)),
							set_ordlist(T)).
:- mode set_ordlist__power_union(in, out) is det.

	% `set_ordlist__intersect(SetA, SetB, Set)' is true iff `Set' is the
	% intersection of `SetA' and `SetB'. The efficiency of the intersection
	% operation is not influenced by the argument order.

:- pred set_ordlist__intersect(set_ordlist(T), set_ordlist(T),
							set_ordlist(T)).
:- mode set_ordlist__intersect(in, in, out) is det.
:- mode set_ordlist__intersect(in, in, in) is semidet.

	% `set_ordlist__power_intersect(A, B)' is true iff `B' is the
	% intersection of all the sets in `A'

:- pred set_ordlist__power_intersect(set_ordlist(set_ordlist(T)),
							set_ordlist(T)).
:- mode set_ordlist__power_intersect(in, out) is det.

	% `set_ordlist__difference(SetA, SetB, Set)' is true iff `Set' is the
	% set containing all the elements of `SetA' except those that
	% occur in `SetB'

:- pred set_ordlist__difference(set_ordlist(T), set_ordlist(T),
							set_ordlist(T)).
:- mode set_ordlist__difference(in, in, out) is det.

%--------------------------------------------------%

set_unordlist

%--------------------------------------------------%
% Copyright (C) 1995-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: set_unordlist.m.
% Main authors: conway, fjh.
% Stability: medium.

% This file contains a `set' ADT.
% Sets are implemented here as unsorted lists, which may contain duplicates.

%--------------------------------------------------%

:- module set_unordlist.
:- interface.
:- import_module bool, list.

:- type set_unordlist(_T).

	% `set_unordlist__list_to_set(List, Set)' is true iff `Set' is the set 
	% containing only the members of `List'.

:- pred set_unordlist__list_to_set(list(T), set_unordlist(T)).
:- mode set_unordlist__list_to_set(in, out) is det.

	% `set_unordlist__sorted_list_to_set(List, Set)' is true iff `Set' is
	% the set containing only the members of `List'.  `List' must be sorted.

:- pred set_unordlist__sorted_list_to_set(list(T), set_unordlist(T)).
:- mode set_unordlist__sorted_list_to_set(in, out) is det.

	% `set_unordlist__to_sorted_list(Set, List)' is true iff `List' is the
	% list of all the members of `Set', in sorted order.

:- pred set_unordlist__to_sorted_list(set_unordlist(T), list(T)).
:- mode set_unordlist__to_sorted_list(in, out) is det.

	% `set_unordlist__init(Set)' is true iff `Set' is an empty set.

:- pred set_unordlist__init(set_unordlist(_T)).
:- mode set_unordlist__init(uo) is det.

	% `set_unordlist__singleton_set(Set, Elem)' is true iff `Set' is the set
	% containing just the single element `Elem'.

:- pred set_unordlist__singleton_set(set_unordlist(T), T).
:- mode set_unordlist__singleton_set(in, out) is semidet.
:- mode set_unordlist__singleton_set(out, in) is det.

	% `set_unordlist__equal(SetA, SetB)' is true iff
	% `SetA' and `SetB' contain the same elements.

:- pred set_unordlist__equal(set_unordlist(T), set_unordlist(T)).
:- mode set_unordlist__equal(in, in) is semidet.

	% `set_unordlist__empty(Set)' is true iff `Set' is an empty set.

:- pred set_unordlist__empty(set_unordlist(_T)).
:- mode set_unordlist__empty(in) is semidet.

	% `set_unordlist__subset(SetA, SetB)' is true iff `SetA' is a subset of
	% `SetB'.

:- pred set_unordlist__subset(set_unordlist(T), set_unordlist(T)).
:- mode set_unordlist__subset(in, in) is semidet.

	% `set_unordlist__superset(SetA, SetB)' is true iff `SetA' is a
	% superset of `SetB'.

:- pred set_unordlist__superset(set_unordlist(T), set_unordlist(T)).
:- mode set_unordlist__superset(in, in) is semidet.

	% `set_unordlist__member(X, Set)' is true iff `X' is a member of `Set'.

:- pred set_unordlist__member(T, set_unordlist(T)).
:- mode set_unordlist__member(in, in) is semidet.
:- mode set_unordlist__member(out, in) is nondet.

	% `set_unordlist__is_member(X, Set, Result)' returns
	% `Result = yes' iff `X' is a member of `Set'.

:- pred set_unordlist__is_member(T, set_unordlist(T), bool).
:- mode set_unordlist__is_member(in, in, out) is det.

	% `set_unordlist__insert(Set0, X, Set)' is true iff `Set' is the union
	% of `Set0' and the set containing only `X'.

:- pred set_unordlist__insert(set_unordlist(T), T, set_unordlist(T)).
:- mode set_unordlist__insert(di, di, uo) is det.
:- mode set_unordlist__insert(in, in, out) is det.

	% `set_unordlist__insert_list(Set0, Xs, Set)' is true iff `Set' is the
	% union of `Set0' and the set containing only the members of `Xs'.

:- pred set_unordlist__insert_list(set_unordlist(T), list(T),
					set_unordlist(T)).
:- mode set_unordlist__insert_list(in, in, out) is det.

	% `set_unordlist__delete(Set0, X, Set)' is true iff `Set' is the
	% relative complement of `Set0' and the set containing only `X', i.e.
	% if `Set' is the set which contains all the elements of `Set0'
	% except `X'.

:- pred set_unordlist__delete(set_unordlist(T), T, set_unordlist(T)).
:- mode set_unordlist__delete(di, in, uo) is det.
:- mode set_unordlist__delete(in, in, out) is det.

	% `set_unordlist__delete_list(Set0, Xs, Set)' is true iff `Set' is the
	% relative complement of `Set0' and the set containing only the members
	% of `Xs'.

:- pred set_unordlist__delete_list(set_unordlist(T), list(T),
					set_unordlist(T)).
:- mode set_unordlist__delete_list(in, in, out) is det.

	% `set_unordlist__remove(Set0, X, Set)' is true iff `Set0' contains `X',
	% and `Set' is the relative complement of `Set0' and the set
	% containing only `X', i.e.  if `Set' is the set which contains
	% all the elements of `Set0' except `X'.

:- pred set_unordlist__remove(set_unordlist(T), T, set_unordlist(T)).
:- mode set_unordlist__remove(in, in, out) is semidet.

	% `set_unordlist__remove_list(Set0, Xs, Set)' is true iff Xs does not
	% contain any duplicates, `Set0' contains every member of `Xs',
	% and `Set' is the relative complement of `Set0' and the set
	% containing only the members of `Xs'.

:- pred set_unordlist__remove_list(set_unordlist(T), list(T),
					set_unordlist(T)).
:- mode set_unordlist__remove_list(in, in, out) is semidet.

	% `set_unordlist__remove_least(Set0, X, Set)' is true iff `X' is the
	% least element in `Set0', and `Set' is the set which contains all the
	% elements of `Set0' except `X'.

:- pred set_unordlist__remove_least(set_unordlist(T), T, set_unordlist(T)).
:- mode set_unordlist__remove_least(in, out, out) is semidet.

	% `set_unordlist_union(SetA, SetB, Set)' is true iff `Set' is the union
	% of `SetA' and `SetB'.  If the sets are known to be of different
	% sizes, then for efficiency make `SetA' the larger of the two.

:- pred set_unordlist__union(set_unordlist(T), set_unordlist(T),
							set_unordlist(T)).
:- mode set_unordlist__union(in, in, out) is det.

	% `set_unordlist__power_union(A, B)' is true iff `B' is the union of
	% all the sets in `A'

:- pred set_unordlist__power_union(set_unordlist(set_unordlist(T)),
							set_unordlist(T)).
:- mode set_unordlist__power_union(in, out) is det.

	% `set_unordlist__intersect(SetA, SetB, Set)' is true iff `Set' is the
	% intersection of `SetA' and `SetB'.

:- pred set_unordlist__intersect(set_unordlist(T), set_unordlist(T),
							set_unordlist(T)).
:- mode set_unordlist__intersect(in, in, out) is det.

	% `set_unordlist__power_intersect(A, B)' is true iff `B' is the
	% intersection of all the sets in `A'

:- pred set_unordlist__power_intersect(set_unordlist(set_unordlist(T)),
							set_unordlist(T)).
:- mode set_unordlist__power_intersect(in, out) is det.

	% `set_unordlist__difference(SetA, SetB, Set)' is true iff `Set' is the
	% set containing all the elements of `SetA' except those that
	% occur in `SetB'

:- pred set_unordlist__difference(set_unordlist(T), set_unordlist(T),
							set_unordlist(T)).
:- mode set_unordlist__difference(in, in, out) is det.

%--------------------------------------------------%

stack

%--------------------------------------------------%
% Copyright (C) 1994-1995, 1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: stack.m.
% Main author: fjh.
% Stability: high.

% This file contains a `stack' ADT.
% Stacks are implemented here using lists.

%--------------------------------------------------%

:- module stack.
:- interface.
:- import_module list.

:- type stack(_T).

	% `stack__init(Stack)' is true iff `Stack' is an empty stack.

:- pred stack__init(stack(_T)).
:- mode stack__init(out) is det.

	% `stack__is_empty(Stack)' is true iff `Stack' is an empty stack.

:- pred stack__is_empty(stack(_T)).
:- mode stack__is_empty(in) is semidet.

	% `stack__is_full(Stack)' is intended to be true iff `Stack'
	% is a stack whose capacity is exhausted.  This
	% implement allows arbitrary-sized stacks, so stack__is_full
	% always fails.

:- pred stack__is_full(stack(_T)).
:- mode stack__is_full(in) is semidet.

	% `stack__push(Stack0, Elem, Stack)' is true iff `Stack' is
	% the stack which results from pushing `Elem' onto the top
	% of `Stack0'.

:- pred stack__push(stack(T), T, stack(T)).
:- mode stack__push(in, in, out) is det.

	% `stack__push_list(Stack0, Elems, Stack)' is true iff `Stack' 
	% is the stack which results from pushing the elements of the
	% list `Elems' onto the top of `Stack0'.

:- pred stack__push_list(stack(T), list(T), stack(T)).
:- mode stack__push_list(in, in, out) is det.

	% `stack__top(Stack, Elem)' is true iff `Stack' is a non-empty
	% stack whose top element is `Elem'.

:- pred stack__top(stack(T), T).
:- mode stack__top(in, out) is semidet.

	% `stack__pop(Stack0, Elem, Stack)' is true iff `Stack0' is
	% a non-empty stack whose top element is `Elem', and `Stack'
	% the stack which results from popping `Elem' off `Stack0'.

:- pred stack__pop(stack(T), T, stack(T)).
:- mode stack__pop(in, out, out) is semidet.

	% `stack__pop_det' is like `stack__pop' except that it will
	% call error/1 rather than failing if given an empty stack.

:- pred stack__pop_det(stack(T), T, stack(T)).
:- mode stack__pop_det(in, out, out) is det.

	% `stack__depth(Stack, Depth)' is true iff `Stack' is a stack
	% containing `Depth' elements.

:- pred stack__depth(stack(_T), int).
:- mode stack__depth(in, out) is det.
:- mode stack__depth(in, in) is semidet. % implied

%--------------------------------------------------%

std_util

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: std_util.m.
% Main author: fjh.
% Stability: medium to high.

% This file is intended for all the useful standard utilities
% that don't belong elsewhere, like <stdlib.h> in C.

%--------------------------------------------------%
%--------------------------------------------------%

:- module std_util.

:- interface.

:- import_module list, set.

%--------------------------------------------------%

% The universal type `univ'.
% An object of type `univ' can hold the type and value of an object of any
% other type.
%
% Note that the current NU-Prolog/SICStus Prolog implementation of
% univ_to_type is buggy in that it always succeeds, even if the types didn't
% match, so until this gets implemented correctly, don't use
% univ_to_type unless you are sure that the types will definitely match,
% or you don't care about debugging with Prolog.

:- type univ.

	% type_to_univ(Object, Univ):
	% 	true iff the type stored in `Univ' is the same as the type
	%	of `Object', and the value stored in `Univ' is equal to the
	%	value of `Object'.
	%
	% Operational, the forwards mode converts an object to type `univ',
	% while the reverse mode converts the value stored in `Univ'
	% to the type of `Object', but fails if the type stored in `Univ'
	% does not match the type of `Object'.
	% 
:- pred type_to_univ(T, univ).
:- mode type_to_univ(di, uo) is det.
:- mode type_to_univ(in, out) is det.
:- mode type_to_univ(out, in) is semidet.

	% univ_to_type(Univ, Object) :- type_to_univ(Object, Univ).
	%
:- pred univ_to_type(univ, T).
:- mode univ_to_type(in, out) is semidet.
:- mode univ_to_type(out, in) is det.
:- mode univ_to_type(uo, di) is det.

	% The function univ/1 provides the same
	% functionality as type_to_univ/2.

	% univ(Object) = Univ :- type_to_univ(Object, Univ).
	%
:- func univ(T) = univ.
:- mode univ(in) = out is det.
:- mode univ(di) = uo is det.
:- mode univ(out) = in is semidet.

	% univ_type(Univ):
	%	returns the type_info for the type stored in `Univ'.
	%
:- func univ_type(univ) = type_info.

%--------------------------------------------------%

% The "maybe" type.

:- type maybe(T) ---> no ; yes(T).

%--------------------------------------------------%

% The "unit" type - stores no information at all.

:- type unit		--->	unit.

%--------------------------------------------------%

% The "pair" type.  Useful for many purposes.

:- type pair(T1, T2)	--->	(T1 - T2).
:- type pair(T)		==	pair(T,T).

%--------------------------------------------------%

% solutions/2 collects all the solutions to a predicate and
% returns them as a list in sorted order, with duplicates removed.
% solutions_set/2 returns them as a set.
% unsorted_solutions/2 returns them as an unsorted list with possible
% duplicates; since there are an infinite number of such lists,
% this must be called from a context in which only a single solution
% is required.

:- pred solutions(pred(T), list(T)).
:- mode solutions(pred(out) is multi, out) is det.
:- mode solutions(pred(out) is nondet, out) is det.

:- pred solutions_set(pred(T), set(T)).
:- mode solutions_set(pred(out) is multi, out) is det.
:- mode solutions_set(pred(out) is nondet, out) is det.

:- pred unsorted_solutions(pred(T), list(T)).
:- mode unsorted_solutions(pred(out) is multi, out) is cc_multi.
:- mode unsorted_solutions(pred(out) is nondet, out) is cc_multi.

%--------------------------------------------------%

	% aggregate/4 generates all the solutions to a predicate,
	% sorts them and removes duplicates, then applies an accumulator
	% predicate to each solution in turn:
	%
	% aggregate(Generator, Accumulator, Acc0, Acc) <=>
	%	solutions(Generator, Solutions),
	%	list__foldl(Accumulator, Solutions, Acc0, Acc).
	%

:- pred aggregate(pred(T), pred(T, U, U), U, U).
:- mode aggregate(pred(out) is multi, pred(in, in, out) is det,
		in, out) is det.
:- mode aggregate(pred(out) is multi, pred(in, di, uo) is det,
		di, uo) is det.
:- mode aggregate(pred(out) is nondet, pred(in, di, uo) is det,
		di, uo) is det.
:- mode aggregate(pred(out) is nondet, pred(in, in, out) is det,
		in, out) is det.

	% unsorted_aggregate/4 generates all the solutions to a predicate
	% and applies an accumulator predicate to each solution in turn.
	% Declaratively, the specification is as follows:
	%
	% unsorted_aggregate(Generator, Accumulator, Acc0, Acc) <=>
	%	unsorted_solutions(Generator, Solutions),
	%	list__foldl(Accumulator, Solutions, Acc0, Acc).
	%
	% Operationally, however, unsorted_aggregate/4 will call the
	% Accumulator for each solution as it is obtained, rather than
	% first building a list of all the solutions.

:- pred unsorted_aggregate(pred(T), pred(T, U, U), U, U).
:- mode unsorted_aggregate(pred(out) is multi, pred(in, in, out) is det,
		in, out) is cc_multi.
:- mode unsorted_aggregate(pred(out) is multi, pred(in, di, uo) is det,
		di, uo) is cc_multi.
:- mode unsorted_aggregate(pred(muo) is multi, pred(mdi, di, uo) is det,
		di, uo) is cc_multi.
:- mode unsorted_aggregate(pred(out) is nondet, pred(in, di, uo) is det,
		di, uo) is cc_multi.
:- mode unsorted_aggregate(pred(out) is nondet, pred(in, in, out) is det,
		in, out) is cc_multi.
:- mode unsorted_aggregate(pred(muo) is nondet, pred(mdi, di, uo) is det,
		di, uo) is cc_multi.

%--------------------------------------------------%

	% maybe_pred(Pred, X, Y) takes a closure Pred which transforms an
	% input semideterministically. If calling the closure with the input
	% X succeeds, Y is bound to `yes(Z)' where Z is the output of the
	% call, or to `no' if the call fails.
	%
:- pred maybe_pred(pred(T1, T2), T1, maybe(T2)).
:- mode maybe_pred(pred(in, out) is semidet, in, out) is det.

%--------------------------------------------------%

	% `semidet_succeed' is exactly the same as `true', except that
	% the compiler thinks that it is semi-deterministic.  You can
	% use calls to `semidet_succeed' to suppress warnings about
	% determinism declarations which could be stricter.
	% Similarly, `semidet_fail' is like `fail' except that its
	% determinism is semidet rather than failure, and
	% `cc_multi_equal(X,Y)' is the same as `X=Y' except that it
	% is cc_multi rather than det.

:- pred semidet_succeed is semidet.

:- pred semidet_fail is semidet.

:- pred cc_multi_equal(T, T).
:- mode cc_multi_equal(di, uo) is cc_multi.
:- mode cc_multi_equal(in, out) is cc_multi.

%--------------------------------------------------%

	% The `type_info' and `type_ctor_info' types: these
	% provide access to type information.
	% A type_info represents a type, e.g. `list(int)'.
	% A type_ctor_info represents a type constructor, e.g. `list/1'.

:- type type_info.
:- type type_ctor_info.

	% (Note: it is not possible for the type of a variable to be an
	% unbound type variable; if there are no constraints on a type
	% variable, then the typechecker will use the type `void'.
	% `void' is a special (builtin) type that has no constructors.
	% There is no way of creating an object of type `void'.
	% `void' is not considered to be a discriminated union, so
	% get_functor/5 and construct/3 will fail if used upon a value
	% of this type.)

	% type_of(Data) returns a representation of the type of Data.
	%
:- func type_of(T) = type_info.
:- mode type_of(unused) = out is det.

	% type_name(Type) returns the name of the specified type
	% (e.g. type_name(type_of([2,3])) = "list:list(int)").
	% Any equivalence types will be fully expanded.
	% Builtin types (those defined in mercury_builtin.m) will
	% not have a module qualifier.
	%
:- func type_name(type_info) = string.

	% type_ctor_and_args(Type, TypeCtor, TypeArgs):
	%	True iff `TypeCtor' is a representation of the top-level
	%	type constructor for `Type', and `TypeArgs' is a list
	%	of the corresponding type arguments to `TypeCtor',
	%	and `TypeCtor' is not an equivalence type.
	%
	% For example, type_ctor_and_args(type_of([2,3]), TypeCtor,
	% TypeArgs) will bind `TypeCtor' to a representation of the
	% type constructor list/1, and will bind `TypeArgs' to the list
	% `[Int]', where `Int' is a representation of the type `int'.
	%
	% Note that the requirement that `TypeCtor' not be an
	% equivalence type is fulfilled by fully expanding any
	% equivalence types.  For example, if you have a declaration
	% `:- type foo == bar.', then type_ctor_and_args/3 will always
	% return a representation of type constructor `bar/0', not `foo/0'. 
	% (If you don't want them expanded, you can use the reverse mode
	% of make_type/2 instead.)
	%
:- pred type_ctor_and_args(type_info, type_ctor_info, list(type_info)).
:- mode type_ctor_and_args(in, out, out) is det.

	% type_ctor(Type) = TypeCtor :-
	%	type_ctor_and_args(Type, TypeCtor, _).
	%
:- func type_ctor(type_info) = type_ctor_info.

	% type_args(Type) = TypeArgs :-
	%	type_ctor_and_args(Type, _, TypeArgs).
	%
:- func type_args(type_info) = list(type_info).

	% type_ctor_name(TypeCtor) returns the name of specified
	% type constructor.
	% (e.g. type_ctor_name(type_ctor(type_of([2,3]))) = "list").
	%
:- func type_ctor_name(type_ctor_info) = string.

	% type_ctor_module_name(TypeCtor) returns the module name of specified
	% type constructor.
	% (e.g. type_ctor_module_name(type_ctor(type_of(2))) =
	% 		"mercury_builtin").
	%
:- func type_ctor_module_name(type_ctor_info) = string.

	% type_ctor_arity(TypeCtor) returns the arity of specified
	% type constructor.
	% (e.g. type_ctor_arity(type_ctor(type_of([2,3]))) = 1).
	%
:- func type_ctor_arity(type_ctor_info) = int.

	% type_ctor_name_and_arity(TypeCtor, ModuleName, TypeName, Arity) :-
	%	Name = type_ctor_name(TypeCtor),
	%	ModuleName = type_ctor_module_name(TypeCtor),
	%	Arity = type_ctor_arity(TypeCtor).
	%
:- pred type_ctor_name_and_arity(type_ctor_info, string, string, int).
:- mode type_ctor_name_and_arity(in, out, out, out) is det.

	% make_type(TypeCtor, TypeArgs) = Type:
	%	True iff `Type' is a type constructed by applying
	%	the type constructor `TypeCtor' to the type arguments
	%	`TypeArgs'.
	%
	% Operationally, the forwards mode returns the type formed by
	% applying the specified type constructor to the specified
	% argument types, or fails if the length of TypeArgs is not the
	% same as the arity of TypeCtor.  The reverse mode returns a
	% type constructor and its argument types, given a type_info;
	% the type constructor returned may be an equivalence type
	% (and hence this reverse mode of make_type/2 may be more useful
	% for some purposes than the type_ctor/1 function).
	% 
:- func make_type(type_ctor_info, list(type_info)) = type_info.
:- mode make_type(in, in) = out is semidet.
:- mode make_type(out, out) = in is cc_multi.

	% det_make_type(TypeCtor, TypeArgs):
	%
	% Returns the type formed by applying the specified type
	% constructor to the specified argument types.  Aborts if the
	% length of `TypeArgs' is not the same as the arity of `TypeCtor'.
	%
:- func det_make_type(type_ctor_info, list(type_info)) = type_info.
:- mode det_make_type(in, in) = out is det.

%--------------------------------------------------%

	% num_functors(TypeInfo) 
	% 
	% Returns the number of different functors for the top-level
	% type constructor of the type specified by TypeInfo, or -1
	% if the type is not a discriminated union type.
	%
:- func num_functors(type_info) = int.

	% get_functor(Type, N, Functor, Arity, ArgTypes)
	%
	% Binds Functor and Arity to the name and arity of the Nth
	% functor for the specified type (starting at zero), and binds
	% ArgTypes to the type_infos for the types of the arguments of
	% that functor.  Fails if the type is not a discriminated union
	% type, or if N is out of range.
	%
:- pred get_functor(type_info::in, int::in, string::out, int::out,
		list(type_info)::out) is semidet.

	% construct(TypeInfo, N, Args) = Term
	%
	% Returns a term of the type specified by TypeInfo whose functor
	% is the Nth functor of TypeInfo (starting at zero), and whose
	% arguments are given by Args.  Fails if the type is not a
	% discriminated union type, or if N is out of range, or if the
	% number of arguments doesn't match the arity of the Nth functor
	% of the type, or if the types of the arguments doesn't match
	% the expected argument types for that functor.
	%
:- func construct(type_info, int, list(univ)) = univ.
:- mode construct(in, in, in) = out is semidet.

%--------------------------------------------------%

	% functor, argument and deconstruct take any type (including univ),
	% and return representation information for that type.
	%
	% The string representation of the functor that `functor' and 
	% `deconstruct' return is:
	% 	- for user defined types, the functor that is given
	% 	  in the type defintion. For lists, this
	% 	  means the functors ./2 and []/0 are used, even if
	% 	  the list uses the [....] shorthand.
	%	- for integers, the string is a base 10 number,
	%	  positive integers have no sign.
	%	- for floats, the string is a floating point,
	%	  base 10 number, positive floating point numbers have
	%	  no sign. 
	%	- for strings, the string, inside double quotation marks
	%	- for characters, the character inside single 
	%	  quotation marks
	%	- for predicates and functions, the string
	%	  <<predicate>>

	% functor(Data, Functor, Arity)
	% 
	% Given a data item (Data), binds Functor to a string
	% representation of the functor and Arity to the arity of this
	% data item.  (Aborts if the type of Data is a type with a
	% non-canonical representation, i.e. one for which there is a
	% user-defined equality predicate.)
	%
:- pred functor(T::in, string::out, int::out) is det.

	% arg(Data, ArgumentIndex) = Argument
	% argument(Data, ArgumentIndex) = ArgumentUniv
	% 
	% Given a data item (Data) and an argument index
	% (ArgumentIndex), starting at 0 for the first argument, binds
	% Argument to that argument of the functor of the data item. If
	% the argument index is out of range -- that is, greater than or
	% equal to the arity of the functor or lower than 0 -- then
	% the call fails.  For argument/1 the argument returned has the
	% type univ, which can store any type.  For arg/1, if the
	% argument has the wrong type, then the call fails.
	% (Both abort if the type of Data is a type with a non-canonical
	% representation, i.e. one for which there is a user-defined
	% equality predicate.)
	%
:- func arg(T::in, int::in) = (ArgT::out) is semidet.
:- func argument(T::in, int::in) = (univ::out) is semidet.

	% det_arg(Data, ArgumentIndex) = Argument
	% det_argument(Data, ArgumentIndex) = ArgumentUniv
	% 
	% Same as arg/2 and argument/2 respectively, except that
	% for cases where arg/2 or argument/2 would fail,
	% det_arg/2 or det_argument/2 will abort.
	%
:- func det_arg(T::in, int::in) = (ArgT::out) is det.
:- func det_argument(T::in, int::in) = (univ::out) is det.

	% deconstruct(Data, Functor, Arity, Arguments) 
	% 
	% Given a data item (Data), binds Functor to a string
	% representation of the functor, Arity to the arity of this data
	% item, and Arguments to a list of arguments of the functor.
	% The arguments in the list are each of type univ.
	% (Aborts if the type of Data is a type with a non-canonical
	% representation, i.e. one for which there is a user-defined
	% equality predicate.)
	%
:- pred deconstruct(T::in, string::out, int::out, list(univ)::out) is det.

%--------------------------------------------------%
%--------------------------------------------------%

store

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: store.m. 
% Main author: fjh.
% Stability: low.
%
% This file provides facilities for manipulating mutable stores.
% A store can be consider a mapping from abstract keys to their values.
% A store holds a set of nodes, each of which may contain a value of any
% type.
%
% Stores may be used to implement cyclic data structures such as
% circular linked lists, etc.
%
% Stores can have two different sorts of keys:
% mutable variables (mutvars) and references (refs).
% The difference between mutvars and refs is that
% mutvars can only be updated atomically,
% whereas it is possible to update individual fields of a reference
% one at a time (presuming the reference refers to a structured term).
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module store.
:- interface.

% Stores and keys are indexed by a type S that is used to distinguish
% between different stores.  The idea is to use an existential type
% declaration for store__init:
%	:- some [S] pred store__init(store(S)).
% That way, we could use the type system to ensure at compile time
% that you never attempt to use a key from one store to access a
% different store.
% However, Mercury doesn't yet support existential types :-(
% For the moment we just use a type `some_store_type'
% instead of `some [S] ... S'. 
% So currently this check is not done --
% if you attempt to use a key from one store to access a
% different store, the behaviour is undefined.
% This will hopefully be rectified in some future version when
% Mercury does support existential types.

:- type store(S).

:- type some_store_type.

	% initialize a store
:- pred store__init(store(some_store_type)).
:- mode store__init(uo) is det.

%--------------------------------------------------%
%
% mutvars
%

	% mutvar(T, S):
	% a mutable variable holding a value of type T in store S
:- type mutvar(T, S).

	% create a new mutable variable,
	% initialized with the specified value
:- pred store__new_mutvar(T, mutvar(T, S), store(S), store(S)).
:- mode store__new_mutvar(in, out, di, uo) is det.

	% lookup the value stored in a given mutable variable
:- pred store__get_mutvar(mutvar(T, S), T, store(S), store(S)).
:- mode store__get_mutvar(in, out, di, uo) is det.

	% replace the value stored in a given mutable variable
:- pred store__set_mutvar(mutvar(T, S), T, store(S), store(S)).
:- mode store__set_mutvar(in, in, di, uo) is det.

/* 
The syntax might be nicer if we used some new operators

	:- op(.., xfx, ('<-')).
	:- op(.., fy, ('!')).
	:- op(.., xfx, (':=')).

Then we could do something like this:

	Ptr <- new(Val)	  -->	new_mutvar(Val, Ptr).
	Val <- !Ptr 	  -->	get_mutvar(Ptr, Val).
	!Ptr := Val	  -->	set_mutvar(Ptr, Val).

I wonder whether it is worth it?
*/

%--------------------------------------------------%
%
% references
%

	% mutvar(T, S):
	% a reference to value of type T in store S
:- type ref(T, S).

	% new_ref(Val, Ref):	
	%	/* In C: Ref = malloc(...); *Ref = Val; */
	% Given a value of any type `T', insert a copy of the term
	% into the store and return a new reference to that term.
	% (This does not actually perform a copy, it just returns a view
	% of the representation of that value.
	% It does however allocate one cell to hold the reference;
	% you can use new_arg_ref to avoid that.)
:- pred store__new_ref(T, ref(T, S), store(S), store(S)).
:- mode store__new_ref(di, out, di, uo) is det.

	% ref_functor(Ref, Functor, Arity):
	% Given a reference to a term, return the functor and arity
	% of that term.
:- pred store__ref_functor(ref(T, S), string, int, store(S), store(S)).
:- mode store__ref_functor(in, out, out, di, uo) is det.

	% arg_ref(Ref, ArgNum, ArgRef):	     
	%	/* Psuedo-C code: ArgRef = &Ref[ArgNum]; */
	% Given a reference to a term, return a reference to
	% the specified argument (field) of that term
	% (argument numbers start from zero).
	% It is an error if the argument number is out of range,
	% or if the argument reference has the wrong type.
:- pred store__arg_ref(ref(T, S), int, ref(ArgT, S), store(S), store(S)).
:- mode store__arg_ref(in, in, out, di, uo) is det.

	% new_arg_ref(Val, ArgNum, ArgRef):
	%	/* Psuedo-C code: ArgRef = &Val[ArgNum]; */
	% Equivalent to `new_ref(Val, Ref), arg_ref(Ref, ArgNum, ArgRef)',
	% except that it is more efficient.
	% It is an error if the argument number is out of range,
	% or if the argument reference has the wrong type.
:- pred store__new_arg_ref(T, int, ref(ArgT, S), store(S), store(S)).
:- mode store__new_arg_ref(di, in, out, di, uo) is det.

	% set_ref(Ref, ValueRef):
	%	/* Pseudo-C code: *Ref = *ValueRef; */
	% Given a reference to a term (Ref), 
	% a reference to another term (ValueRef),
	% update the store so that the term referred to by Ref
	% is replaced with the term referenced by ValueRef.
:- pred store__set_ref(ref(T, S), ref(T, S), store(S), store(S)).
:- mode store__set_ref(in, in, di, uo) is det.

	% set_ref_value(Ref, Value):
	%	/* Pseudo-C code: *Ref = Value; */
	% Given a reference to a term (Ref), and a value (Value),
	% update the store so that the term referred to by Ref
	% is replaced with Value.
	% (Argument numbers start from zero).
:- pred store__set_ref_value(ref(T, S), ArgT, store(S), store(S)).
:- mode store__set_ref_value(in, di, di, uo) is det.

	% Given a reference to a term, return that term.
	% Note that this requires making a copy, so this pred may
	% be inefficient if used to return large terms; it
	% is most efficient with atomic terms.
:- pred store__copy_ref_value(ref(T, S), T, store(S), store(S)).
:- mode store__copy_ref_value(in, uo, di, uo) is det.

	% Same as above, but without making a copy.
	% Destroys the store.
:- pred store__extract_ref_value(store(S), ref(T, S), T).
:- mode store__extract_ref_value(di, in, out) is det.

%--------------------------------------------------%
%
% Nasty performance hacks
%
% WARNING: use of these procedures is dangerous!
% Use them only only as a last resort, only if performance
% is critical, and only if profiling shows that using the
% safe versions is a bottleneck.
%
% These procedures may vanish in some future version of Mercury.

	% `unsafe_arg_ref' is the same as `arg_ref',
	% and `unsafe_new_arg_ref' is the same as `new_arg_ref'
	% except that they doesn't check for errors,
	% and they don't work for `no_tag' types (types with
	% exactly one functor which has exactly one argument),
	% and they don't work for types with >4 functors.
	% If the argument number is out of range,
	% or if the argument reference has the wrong type,
	% or if the argument is a `no_tag' type,
	% then the behaviour is undefined, and probably harmful.

:- pred store__unsafe_arg_ref(ref(T, S), int, ref(ArgT, S), store(S), store(S)).
:- mode store__unsafe_arg_ref(in, in, out, di, uo) is det.

:- pred store__unsafe_new_arg_ref(T, int, ref(ArgT, S), store(S), store(S)).
:- mode store__unsafe_new_arg_ref(di, in, out, di, uo) is det.

%--------------------------------------------------%
%--------------------------------------------------%

string

%--------------------------------------------------%
% Copyright (C) 1993-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

:- module string.

% Main authors: fjh, dylan.
% Stability: medium to high.

% This modules provides basic string handling facilities.

% Beware that char_to_string/2 won't work with NU-Prolog 1.5.33 because
% of a NU-Prolog bug (fixed in NU-Prolog 1.5.35).

%--------------------------------------------------%

:- interface.
:- import_module list, char.

:- pred string__length(string, int).
:- mode string__length(in, out) is det.
	% Determine the length of a string.
	% An empty string has length zero.

:- pred string__append(string, string, string).
:- mode string__append(in, in, in) is semidet.	% implied
:- mode string__append(in, out, in) is semidet.
:- mode string__append(in, in, out) is det.
:- mode string__append(out, out, in) is multidet.
%	Append two strings together.
%
%       The following mode is semidet in the sense that it doesn't
%       succeed more than once - but it does create a choice-point,
%       which means it's inefficient and that the compiler can't deduce
%       that it is semidet.  Use string__remove_suffix instead.
% :- mode string__append(out, in, in) is semidet.

:- pred string__remove_suffix(string, string, string).
:- mode string__remove_suffix(in, in, out) is semidet.
%	string__remove_suffix(String, Suffix, Prefix):
%       The same as string__append(Prefix, Suffix, List) except that
%       this is semidet whereas string__append(out, in, in) is nondet.

:- pred string__prefix(string, string).
:- mode string__prefix(in, in) is semidet.
:- mode string__prefix(in, out) is multidet.
	% string__prefix(String, Prefix) is true iff Prefix is a
	% prefix of String.  Same as string__append(Prefix, _, String).

:- pred string__char_to_string(char, string).
:- mode string__char_to_string(in, out) is det.
:- mode string__char_to_string(out, in) is semidet.
%	string__char_to_string(Char, String).
%		Converts a character (single-character atom) to a string
%		or vice versa.

:- pred string__int_to_string(int, string).
:- mode string__int_to_string(in, out) is det.
%	Convert an integer to a string.

:- pred string__int_to_base_string(int, int, string).
:- mode string__int_to_base_string(in, in, out) is det.
%	string__int_to_base_string(Int, Base, String):
%	Convert an integer to a string in a given Base (between 2 and 36).

:- pred string__float_to_string(float, string).
:- mode string__float_to_string(in, out) is det.
%	Convert an float to a string.

:- pred string__first_char(string, char, string).
:- mode string__first_char(in, in, in) is semidet.	% implied
:- mode string__first_char(in, out, in) is semidet.	% implied
:- mode string__first_char(in, in, out) is semidet.	% implied
:- mode string__first_char(in, out, out) is semidet.
:- mode string__first_char(out, in, in) is det.
%	string__first_char(String, Char, Rest) is true iff
%		Char is the first character of String, and Rest is the
%		remainder.

:- pred string__replace(string, string, string, string).
:- mode string__replace(in, in, in, out) is semidet.
% 	string__replace replaces the first occurence of the second string in 
% 	the first string with the third string to give the fourth string.
% 	It fails if the second string does not occur in the first.

:- pred string__replace_all(string, string, string, string).
:- mode string__replace_all(in, in, in, out) is det.
% 	string__replace_all replaces any occurences of the second string in 
% 	the first string with the third string to give the fourth string.

:- pred string__to_lower(string, string).
:- mode string__to_lower(in, out) is det.
:- mode string__to_lower(in, in) is semidet.		% implied
%	Converts a string to lowercase.

:- pred string__to_upper(string, string).
:- mode string__to_upper(in, out) is det.
:- mode string__to_upper(in, in) is semidet.		% implied
%	Converts a string to uppercase.

:- pred string__capitalize_first(string, string).
:- mode string__capitalize_first(in, out) is det.
%	Convert the first character (if any) of a string to uppercase.

:- pred string__uncapitalize_first(string, string).
:- mode string__uncapitalize_first(in, out) is det.
%	Convert the first character (if any) of a string to lowercase.

:- pred string__to_char_list(string, list(char)).
:- mode string__to_char_list(in, out) is det.

:- pred string__from_char_list(list(char), string).
:- mode string__from_char_list(in, out) is det.
:- mode string__from_char_list(out, in) is semidet.
	% XXX second mode should be det too
	% (but this turns out to be tricky to implement)

:- pred string__from_rev_char_list(list(char), string).
:- mode string__from_rev_char_list(in, out) is det.
%	Same as string__from_char_list, except that it reverses the order
%	of the characters.

:- pred string__to_int(string, int).
:- mode string__to_int(in, out) is semidet.
% 	Convert a string to an int.  The string must contain only digits,
% 	optionally preceded by a plus or minus sign.  If the string does
% 	not match this syntax, string__to_int fails.

:- pred string__base_string_to_int(int, string, int).
:- mode string__base_string_to_int(in, in, out) is semidet.
% 	Convert a string in the specified base (2-36) to an int.  The
% 	string must contain only digits in the specified base, optionally
% 	preceded by a plus or minus sign.  For bases > 10, digits 10 to 35
% 	are repesented by the letters A-Z or a-z.  If the string does not
% 	match this syntax, the predicate fails.

:- pred string__to_float(string, float).
:- mode string__to_float(in, out) is semidet.
%	Convert a string to an float. If the string is not
%	a syntactically correct float literal, string__to_float fails.

:- pred string__is_alpha(string).
:- mode string__is_alpha(in) is semidet.
	% True if string contains only alphabetic characters (letters).

:- pred string__is_alpha_or_underscore(string).
:- mode string__is_alpha_or_underscore(in) is semidet.
	% True if string contains only alphabetic characters and underscores.

:- pred string__is_alnum_or_underscore(string).
:- mode string__is_alnum_or_underscore(in) is semidet.
	% True if string contains only letters, digits, and underscores.

:- pred string__pad_left(string, char, int, string).
:- mode string__pad_left(in, in, in, out) is det.
%	string__pad_left(String0, PadChar, Width, String):
%	insert `PadChar's at the left of `String0' until it is at least
%	as long as `Width', giving `String'.

:- pred string__pad_right(string, char, int, string).
:- mode string__pad_right(in, in, in, out) is det.
%	string__pad_right(String0, PadChar, Width, String):
%	insert `PadChar's at the right of `String0' until it is at least
%	as long as `Width', giving `String'.

:- pred string__duplicate_char(char, int, string).
:- mode string__duplicate_char(in, in, out) is det.
%	string__duplicate_char(Char, Count, String):
%	construct a string consisting of `Count' occurrences of `Char'
%	in sequence.

:- pred string__contains_char(string, char).
:- mode string__contains_char(in, in) is semidet.
%	string__contains_char(String, Char):
%	succeed if `Char' occurs in `String'.

:- pred string__index(string, int, char).
:- mode string__index(in, in, out) is semidet.
%	string__index(String, Index, Char):
%	`Char' is the (`Index' + 1)-th character of `String'.
%	Fails if `Index' is out of range (negative, or greater than or
%	equal to the length of `String').

:- pred string__index_det(string, int, char).
:- mode string__index_det(in, in, out) is det.
%	string__index_det(String, Index, Char):
%	`Char' is the (`Index' + 1)-th character of `String'.
%	Calls error/1 if `Index' is out of range (negative, or greater than or
%	equal to the length of `String').

:- pred string__foldl(pred(char, T, T), string, T, T).
:- mode string__foldl(pred(in, in, out) is det, in, in, out) is det.
:- mode string__foldl(pred(in, di, uo) is det, in, di, uo) is det.
:- mode string__foldl(pred(in, in, out) is semidet, in, in, out) is semidet.
:- mode string__foldl(pred(in, in, out) is nondet, in, in, out) is nondet.
:- mode string__foldl(pred(in, in, out) is multi, in, in, out) is multi.
%	string__foldl(Closure, String, Acc0, Acc):
%	`Closure' is an accumulator predicate which is to be called for each
%	character of the string `String' in turn. The initial value of the
%	accumulator is `Acc0' and the final value is `Acc'.
%	(string__foldl is equivalent to
%		string__to_char_list(String, Chars),
%		list__foldl(Closure, Chars, Acc0, Acc)
%	but is implemented more efficiently.)

:- pred string__split(string, int, string, string).
:- mode string__split(in, in, out, out) is det.
%	string__split(String, Count, LeftSubstring, RightSubstring):
%	`LeftSubstring' is the left-most `Count' characters of `String',
%	and `RightSubstring' is the remainder of `String'.
%	(If `Count' is out of the range [0, length of `String'], it is
%	treated as if it were the nearest end-point of that range.)

:- pred string__left(string, int, string).
:- mode string__left(in, in, out) is det.
%	string__left(String, Count, LeftSubstring):
%	`LeftSubstring' is the left-most `Count' characters of `String'.
%	(If `Count' is out of the range [0, length of `String'], it is
%	treated as if it were the nearest end-point of that range.)

:- pred string__right(string, int, string).
:- mode string__right(in, in, out) is det.
%	string__right(String, Count, RightSubstring):
%	`RightSubstring' is the right-most `Count' characters of `String'.
%	(If `Count' is out of the range [0, length of `String'], it is
%	treated as if it were the nearest end-point of that range.)

:- pred string__substring(string, int, int, string).
:- mode string__substring(in, in, in, out) is det.
%	string__substring(String, Start, Count, Substring):
%	`Substring' is first the `Count' characters in what would
%	remain of `String' after the first `Start' characters were
%	removed.
%	(If `Start' is out of the range [0, length of `String'], it is
%	treated as if it were the nearest end-point of that range.
%	If `Count' is out of the range [0, length of `String' - `Start'], it is
%	treated as if it were the nearest end-point of that range.)

:- pred string__append_list(list(string), string).
:- mode string__append_list(in, out) is det.
:- mode string__append_list(out, in) is multidet.
%	Append a list of strings together.

:- pred string__hash(string, int).
:- mode string__hash(in, out) is det.
%	Compute a hash value for a string.

:- pred string__sub_string_search(string, string, int).
:- mode string__sub_string_search(in, in, out) is semidet.
%	string__sub_string_search(String, SubString, Index).
%	`Index' is the position in `String' where the first occurrence of
%	`SubString' begins.
%	Do a brute-force search in the first string for the second string.
%	XXX Note: not the most efficient algorithm.

:- pred string__format(string, list(string__poly_type), string).
:- mode string__format(in, in, out) is det.
%
%	A function similar to sprintf() in C.  
%
%	For example,
%		string__format("%s %i %c %f\n", 
%			[s("Square-root of"), i(2), c('='), f(1.41)], String)
%	will return
%		String = "Square-root of 2 = 1.41\n".
%
%	All the normal options available in C are supported, ie Flags [0+-# ],
%	a field width (or *), '.', precision (could be a '*'), and a length
%	modifier (currently ignored).
%
%	Valid conversion character types are {dioxXucsfeEgGp%}.  %n is not
%	supported.  string__format will not return the length of the string.
%
%	conv	var	output form.		effect of '#'.
%	char.	type.
%
%	d	int	signed integer
%	i	int	signed integer
%	o	int	signed octal		with '0' prefix
%	x,X	int	signed hex		with '0x', '0X' prefix
%	u	int	unsigned integer
%	c	char	character
%	s	string	string
%	f	float	rational number		with '.', if precision 0
%	e,E	float	[-]m.dddddE+-xx		with '.', if precision 0
%	g,G	float	either e or f		with trailing zeros.
%	p	int	integer
%
%	An option of zero will cause any padding to be zeros rather than spaces.
%	A '-' will cause the output to be left-justified in its 'space'. 
%	(With a `-', the default is for fields to be right-justified.)
%	A '+' forces a sign to be printed.  This is not sensible for string and
%	character output.  A ' ' causes a space to be printed before a thing
%	if there is no sign there.  The other option is the '#', which 
%	modifies the output string's format.  These options are normally put 
%	directly after the '%'.
%
%	Note:
%		%#.0e, %#.0E won't print a '.' before the 'e' ('#' ignored).
%
%		Asking for more precision than a float actually has will
%		result in potentially misleading output.
%
%		If a width or precision is specified, without a `.', a number
%		is assumed to be a width and a `*' is assumed to be a precision.
%		It is always better to include a `.' to remove ambiguity.  This
%		interpretation is non-standard and may change.
%
%		Numbers are truncated by a precision value, not rounded off.

%--------------------------------------------------%

:- type string__poly_type --->
			f(float)
		;	i(int)
		;	s(string)
		;	c(char).

%--------------------------------------------------%

swi_builtin

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%--------------------------------------------------%
%
% Main author: fjh.
%
% Note that SWI-Prolog support is not complete.
% SWI-Prolog is so slow anyway, why bother?
%
%--------------------------------------------------%

% Declare the appropriate operators.

:- op(1199, fx, (module)).
:- op(1199, fx, (end_module)).

:- op(1199, fx, (export_module)).
:- op(1199, fx, (export_sym)).
:- op(1199, fx, (export_pred)).
:- op(1199, fx, (export_cons)).
:- op(1199, fx, (export_type)).
:- op(1199, fx, (export_adt)).
:- op(1199, fx, (export_op)).

:- op(1199, fx, (import_module)).
:- op(1199, fx, (import_sym)).
:- op(1199, fx, (import_pred)).
:- op(1199, fx, (import_cons)).
:- op(1199, fx, (import_type)).
:- op(1199, fx, (import_adt)).
:- op(1199, fx, (import_op)).

:- op(1199, fx, (use_module)).
:- op(1199, fx, (use_sym)).
:- op(1199, fx, (use_pred)).
:- op(1199, fx, (use_cons)).
:- op(1199, fx, (use_type)).
:- op(1199, fx, (use_adt)).
:- op(1199, fx, (use_op)).

:- op(1199, fx, (rule)).

:- op(1199, fx, (type)).
:- op(1199, fx, (pred)).
:- op(1199, fx, (mode)).
:- op(1199, fx, (inst)).
:- op(1179, xfy, (--->)).
:- op(1175, xfx, (::)).

:- op(900, xfx, (when)).
:- op(740, xfy, (or)).
:- op(720, xfy, (and)).

% Prevent warnings about undefined predicates
% when the interpreter tries to execute the new declarations.

:- assert(rule(_)).

:- assert(type(_)).
:- assert(pred(_)).
:- assert(mode(_)).
:- assert(inst(_)).

:- assert(module(_)).
:- assert(end_module(_)).
:- assert(interface).
:- assert(implementation).

:- assert(import_module(_)).
:- assert(import_sym(_)).
:- assert(import_pred(_)).
:- assert(import_cons(_)).
:- assert(import_type(_)).
:- assert(import_adt(_)).
:- assert(import_op(_)).

:- assert(export_module(_)).
:- assert(export_sym(_)).
:- assert(export_pred(_)).
:- assert(export_cons(_)).
:- assert(export_type(_)).
:- assert(export_adt(_)).
:- assert(export_op(_)).

:- assert(use_module(_)).
:- assert(use_sym(_)).
:- assert(use_pred(_)).
:- assert(use_cons(_)).
:- assert(use_type(_)).
:- assert(use_adt(_)).
:- assert(use_op(_)).

:- assert(external(_)).

:- assert(when(_,_)).

%--------------------------------------------------%

swi_lib

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%--------------------------------------------------%

% Various predicates for SWI-Prolog compatibility.

%--------------------------------------------------%

nuprolog :-
	fail.

compound(X) :-
	functor(X, _, _).

putprop(Atom, Key, Property) :-
	retractall(property(Atom, Key, _)),
	assert(property(Atom, Key, Property)).
getprop(Atom, Key, Property) :-
	property(Atom, Key, Property).
remprop(Atom, Key) :-
	retractall(property(Atom, Key, _Property)).

currentInput(X) :-
	current_input(X).

currentOutput(X) :-
	current_output(X).

flushOutput(X) :-
	flush_output(X).

setInput(X) :-
	set_input(X).

setOutput(X) :-
	set_output(X).

lineCount(X,Y) :-
	line_count(X,Y).

eof(end_of_file).

member(Element, List, SubList) :-
	SubList = [Element | _],
	append(_, SubList, List).

	% define =/3 for DCGs
=(A, A, A).

system(Command, Status) :-
	name(Com, Command),
	shell(Com, Status).

%--------------------------------------------------%

% Various hacks to get things to work

random__random(R, X, X1) :-
	X1 is X + 1,
	bit_reverse(X1, R).

bit_reverse(A, B) :-
	A0 is A /\ 255,
	A1 is (A >> 8) /\ 255,
	A2 is (A >> 16) /\ 255,
	bit_rev(A0, B2),
	bit_rev(A1, B1),
	bit_rev(A2, B0),
	B is (B2 << 16) + (B1 << 8) + B0.

/*
bit_rev(A, B) :-
	A0 is A /\ 1,
	A1 is (A >> 1) /\ 1,
	A2 is (A >> 2) /\ 1,
	A3 is (A >> 3) /\ 1,
	A4 is (A >> 4) /\ 1,
	A5 is (A >> 5) /\ 1,
	A6 is (A >> 6) /\ 1,
	A7 is (A >> 7) /\ 1,
	B is (A0 << 7) + (A1 << 6) + (A2 << 5) + (A3 << 4) + (A4 << 3) +
		(A5 << 2) + (A6 << 1) + A7.
*/
bit_rev(0, 0).
bit_rev(1, 128).
bit_rev(2, 64).
bit_rev(3, 192).
bit_rev(4, 32).
bit_rev(5, 160).
bit_rev(6, 96).
bit_rev(7, 224).
bit_rev(8, 16).
bit_rev(9, 144).
bit_rev(10, 80).
bit_rev(11, 208).
bit_rev(12, 48).
bit_rev(13, 176).
bit_rev(14, 112).
bit_rev(15, 240).
bit_rev(16, 8).
bit_rev(17, 136).
bit_rev(18, 72).
bit_rev(19, 200).
bit_rev(20, 40).
bit_rev(21, 168).
bit_rev(22, 104).
bit_rev(23, 232).
bit_rev(24, 24).
bit_rev(25, 152).
bit_rev(26, 88).
bit_rev(27, 216).
bit_rev(28, 56).
bit_rev(29, 184).
bit_rev(30, 120).
bit_rev(31, 248).
bit_rev(32, 4).
bit_rev(33, 132).
bit_rev(34, 68).
bit_rev(35, 196).
bit_rev(36, 36).
bit_rev(37, 164).
bit_rev(38, 100).
bit_rev(39, 228).
bit_rev(40, 20).
bit_rev(41, 148).
bit_rev(42, 84).
bit_rev(43, 212).
bit_rev(44, 52).
bit_rev(45, 180).
bit_rev(46, 116).
bit_rev(47, 244).
bit_rev(48, 12).
bit_rev(49, 140).
bit_rev(50, 76).
bit_rev(51, 204).
bit_rev(52, 44).
bit_rev(53, 172).
bit_rev(54, 108).
bit_rev(55, 236).
bit_rev(56, 28).
bit_rev(57, 156).
bit_rev(58, 92).
bit_rev(59, 220).
bit_rev(60, 60).
bit_rev(61, 188).
bit_rev(62, 124).
bit_rev(63, 252).
bit_rev(64, 2).
bit_rev(65, 130).
bit_rev(66, 66).
bit_rev(67, 194).
bit_rev(68, 34).
bit_rev(69, 162).
bit_rev(70, 98).
bit_rev(71, 226).
bit_rev(72, 18).
bit_rev(73, 146).
bit_rev(74, 82).
bit_rev(75, 210).
bit_rev(76, 50).
bit_rev(77, 178).
bit_rev(78, 114).
bit_rev(79, 242).
bit_rev(80, 10).
bit_rev(81, 138).
bit_rev(82, 74).
bit_rev(83, 202).
bit_rev(84, 42).
bit_rev(85, 170).
bit_rev(86, 106).
bit_rev(87, 234).
bit_rev(88, 26).
bit_rev(89, 154).
bit_rev(90, 90).
bit_rev(91, 218).
bit_rev(92, 58).
bit_rev(93, 186).
bit_rev(94, 122).
bit_rev(95, 250).
bit_rev(96, 6).
bit_rev(97, 134).
bit_rev(98, 70).
bit_rev(99, 198).
bit_rev(100, 38).
bit_rev(101, 166).
bit_rev(102, 102).
bit_rev(103, 230).
bit_rev(104, 22).
bit_rev(105, 150).
bit_rev(106, 86).
bit_rev(107, 214).
bit_rev(108, 54).
bit_rev(109, 182).
bit_rev(110, 118).
bit_rev(111, 246).
bit_rev(112, 14).
bit_rev(113, 142).
bit_rev(114, 78).
bit_rev(115, 206).
bit_rev(116, 46).
bit_rev(117, 174).
bit_rev(118, 110).
bit_rev(119, 238).
bit_rev(120, 30).
bit_rev(121, 158).
bit_rev(122, 94).
bit_rev(123, 222).
bit_rev(124, 62).
bit_rev(125, 190).
bit_rev(126, 126).
bit_rev(127, 254).
bit_rev(128, 1).
bit_rev(129, 129).
bit_rev(130, 65).
bit_rev(131, 193).
bit_rev(132, 33).
bit_rev(133, 161).
bit_rev(134, 97).
bit_rev(135, 225).
bit_rev(136, 17).
bit_rev(137, 145).
bit_rev(138, 81).
bit_rev(139, 209).
bit_rev(140, 49).
bit_rev(141, 177).
bit_rev(142, 113).
bit_rev(143, 241).
bit_rev(144, 9).
bit_rev(145, 137).
bit_rev(146, 73).
bit_rev(147, 201).
bit_rev(148, 41).
bit_rev(149, 169).
bit_rev(150, 105).
bit_rev(151, 233).
bit_rev(152, 25).
bit_rev(153, 153).
bit_rev(154, 89).
bit_rev(155, 217).
bit_rev(156, 57).
bit_rev(157, 185).
bit_rev(158, 121).
bit_rev(159, 249).
bit_rev(160, 5).
bit_rev(161, 133).
bit_rev(162, 69).
bit_rev(163, 197).
bit_rev(164, 37).
bit_rev(165, 165).
bit_rev(166, 101).
bit_rev(167, 229).
bit_rev(168, 21).
bit_rev(169, 149).
bit_rev(170, 85).
bit_rev(171, 213).
bit_rev(172, 53).
bit_rev(173, 181).
bit_rev(174, 117).
bit_rev(175, 245).
bit_rev(176, 13).
bit_rev(177, 141).
bit_rev(178, 77).
bit_rev(179, 205).
bit_rev(180, 45).
bit_rev(181, 173).
bit_rev(182, 109).
bit_rev(183, 237).
bit_rev(184, 29).
bit_rev(185, 157).
bit_rev(186, 93).
bit_rev(187, 221).
bit_rev(188, 61).
bit_rev(189, 189).
bit_rev(190, 125).
bit_rev(191, 253).
bit_rev(192, 3).
bit_rev(193, 131).
bit_rev(194, 67).
bit_rev(195, 195).
bit_rev(196, 35).
bit_rev(197, 163).
bit_rev(198, 99).
bit_rev(199, 227).
bit_rev(200, 19).
bit_rev(201, 147).
bit_rev(202, 83).
bit_rev(203, 211).
bit_rev(204, 51).
bit_rev(205, 179).
bit_rev(206, 115).
bit_rev(207, 243).
bit_rev(208, 11).
bit_rev(209, 139).
bit_rev(210, 75).
bit_rev(211, 203).
bit_rev(212, 43).
bit_rev(213, 171).
bit_rev(214, 107).
bit_rev(215, 235).
bit_rev(216, 27).
bit_rev(217, 155).
bit_rev(218, 91).
bit_rev(219, 219).
bit_rev(220, 59).
bit_rev(221, 187).
bit_rev(222, 123).
bit_rev(223, 251).
bit_rev(224, 7).
bit_rev(225, 135).
bit_rev(226, 71).
bit_rev(227, 199).
bit_rev(228, 39).
bit_rev(229, 167).
bit_rev(230, 103).
bit_rev(231, 231).
bit_rev(232, 23).
bit_rev(233, 151).
bit_rev(234, 87).
bit_rev(235, 215).
bit_rev(236, 55).
bit_rev(237, 183).
bit_rev(238, 119).
bit_rev(239, 247).
bit_rev(240, 15).
bit_rev(241, 143).
bit_rev(242, 79).
bit_rev(243, 207).
bit_rev(244, 47).
bit_rev(245, 175).
bit_rev(246, 111).
bit_rev(247, 239).
bit_rev(248, 31).
bit_rev(249, 159).
bit_rev(250, 95).
bit_rev(251, 223).
bit_rev(252, 63).
bit_rev(253, 191).
bit_rev(254, 127).
bit_rev(255, 255).

bimap__search(bimap(O, C), K, V) :-
	( nonvar(K) ->
		map__search(O, K, V),
		map__search(C, V, K)
	; nonvar(V) ->
		map__search(C, V, K),
		map__search(O, K, V)
	;
		error("bimap__search")
	).

portray(Stream, Term) :-
	currentOutput(S),
	setOutput(Stream),
	( portray(Term) -> true ; print(Term) ),
	setOutput(S).

code_info__current_store_map(Map) -->
        code_info__get_store_map(Maps0),
        { stack__top(Maps0, Map0) },
        !,
        { Map = Map0 }.
code_info__current_store_map(_) -->
        { error("No store map on stack") }.

%--------------------------------------------------%

term

%--------------------------------------------------%
% Copyright (C) 1993-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% File: term.m.
% Main author: fjh.
% Stability: medium.

% This file provides a type `term' used to represent Prolog terms,
% and various predicates to manipulate terms and substitutions.

%--------------------------------------------------%

:- module term.
:- interface.
:- import_module list, map.

%--------------------------------------------------%

:- type term		--->	term__functor(const, list(term), term__context)
			;	term__variable(var).
:- type const		--->	term__atom(string)
			;	term__integer(int)
			;	term__string(string)
			;	term__float(float).

:- type term__context   --->    term__context(string, int).
				% file name, line number.

:- type var.
:- type var_supply.

%--------------------------------------------------%

	% The following predicates can convert values of (almost)
	% any type to the type `term' and back again.

:- type term_to_type_result(T)
	--->	ok(T)
	;	error(term_to_type_error).

:- pred term__try_term_to_type(term, term_to_type_result(T)).
:- mode term__try_term_to_type(in, out) is det.
	% term__try_term_to_type(Term, Result):
	% Try to convert the given term to a ground value of type T.
	% If successful, return `ok(X)' where X is the converted value.
	% If Term is not ground, return `mode_error(Var, Context)',
	% where Var is a variable occurring in Term.
	% If Term is not a valid term of the specified type, return
	% `type_error(SubTerm, ExpectedType, Context, ArgContexts)',
	% where SubTerm is a sub-term of Term and ExpectedType is
	% the type expected for that part of Term. 
	% Context specifies the file and line number where the
	% offending part of the term was read in from, if available.
	% ArgContexts specifies the path from the root of the term
	% to the offending subterm.

:- type term_to_type_error
	--->	type_error(term, type_info, term__context,
			term_to_type_context)
	;	mode_error(var, term_to_type_context).

:- type term_to_type_context == list(term_to_type_arg_context).

:- type term_to_type_arg_context
	--->	arg_context(
			const,		% functor
			int,		% argument number (starting from 1)
			term__context	% filename & line number
		).

:- pred term__term_to_type(term, T).
:- mode term__term_to_type(in, out) is semidet.
	% term_to_type(Term, Type) :- try_term_to_type(Term, ok(Type)).

:- pred term__det_term_to_type(term, T).
:- mode term__det_term_to_type(in, out) is det.
	% like term_to_type, but calls error/1 rather than failing.

:- pred term__type_to_term(T, term).
:- mode term__type_to_term(in, out) is det.
	% converts a value to a term representation of that value

:- pred term__univ_to_term(univ, term).
:- mode term__univ_to_term(in, out) is det.
	% calls term__type_to_term on the value stored in the univ
	% (as distinct from the univ itself).

%--------------------------------------------------%

:- pred term__vars(term, list(var)).
:- mode term__vars(in, out) is det.
%	term__vars(Term, Vars)
%		Vars is the list of variables contained in Term, in the order 
%		obtained by traversing the term depth first, left-to-right.

:- pred term__vars_2(term, list(var), list(var)).
:- mode term__vars_2(in, in, out) is det.
%		As above, but with an accumulator.

:- pred term__vars_list(list(term), list(var)).
:- mode term__vars_list(in, out) is det.
%	term__vars_list(TermList, Vars)
%		Vars is the list of variables contained in TermList, in the
%		order obtained by traversing the list of terms depth-first,
%		left-to-right.

:- pred term__contains_var(term, var).
:- mode term__contains_var(in, in) is semidet.
:- mode term__contains_var(in, out) is nondet.
%	term__contains_var(Term, Var)
%		True if Term contains Var. (On backtracking returns all the 
%		variables contained in Term.)

:- pred term__contains_var_list(list(term), var).
:- mode term__contains_var_list(in, in) is semidet.
:- mode term__contains_var_list(in, out) is nondet.
%	term__contains_var_list(TermList, Var)
%		True if TermList contains Var. (On backtracking returns all the 
%		variables contained in Term.)

:- type substitution == map(var, term).

:- pred term__unify(term, term, substitution, substitution).
:- mode term__unify(in, in, in, out) is semidet.
%	term__unify(Term1, Term2, Bindings0, Bindings)
%		unify (with occur check) two terms with respect to a set
%	 	of bindings and possibly update the set of bindings

:- pred term__substitute(term, var, term, term).
:- mode term__substitute(in, in, in, out) is det.
%	term__substitute(Term0, Var, Replacement, Term) :
%		replace all occurrences of Var in Term0 with Replacement,
%		and return the result in Term.

:- pred term__substitute_list(list(term), var, term, list(term)).
:- mode term__substitute_list(in, in, in, out) is det.
%		as above, except for a list of terms rather than a single term

:- pred term__substitute_corresponding(list(var), list(term), term, term).
:- mode term__substitute_corresponding(in, in, in, out) is det.
%       term__substitute_corresponding(Vars, Repls, Term0, Term).
%		replace all occurrences of variables in Vars with
%		the corresponding term in Repls, and return the result in Term.
%		If Vars contains duplicates, or if Vars is not the same
%	        length as Repls, the behaviour is undefined and probably
%		harmful.

:- pred term__substitute_corresponding_list(list(var), list(term), list(term),
						list(term)).
:- mode term__substitute_corresponding_list(in, in, in, out) is det.
%       term__substitute_corresponding_list(Vars, Repls, TermList0, TermList).
%		As above, except applies to a list of terms rather than a
%		single term.

:- pred term__apply_rec_substitution(term, substitution, term).
:- mode term__apply_rec_substitution(in, in, out) is det.
%	term__apply_rec_substitution(Term0, Substitution, Term) :
%		recursively apply substitution to Term0 until
%		no more substitions can be applied, and then
%		return the result in Term.

:- pred term__apply_rec_substitution_to_list(list(term), substitution,
						list(term)).
:- mode term__apply_rec_substitution_to_list(in, in, out) is det.

:- pred term__apply_substitution(term, substitution, term).
:- mode term__apply_substitution(in, in, out) is det.
%	term__apply_substitution(Term0, Substitution, Term) :
%		apply substitution to Term0 and return the result in Term.

:- pred term__apply_substitution_to_list(list(term), substitution,
						list(term)).
:- mode term__apply_substitution_to_list(in, in, out) is det.
%	term__apply_substitution_to_list(TermList0, Substitution, TermList) :
%		as above, except for a list of terms rather than a single term


:- pred term__occurs(term, var, substitution).
:- mode term__occurs(in, in, in) is semidet.
%	term__occurs(Term0, Var, Substitution) :
%		true iff Var occurs in the term resulting after
%		applying Substitution to Term0.

:- pred term__occurs_list(list(term), var, substitution).
:- mode term__occurs_list(in, in, in) is semidet.
%		as above, except for a list of terms rather than a single term

:- pred term__relabel_variable(term, var, var, term).
:- mode term__relabel_variable(in, in, in, out) is det.
%	term__relabel_variable(Term0, OldVar, NewVar, Term) :
%		replace all occurences of OldVar in Term0 with
%		NewVar and put the result in Term.

:- pred term__relabel_variables(list(term), var, var, list(term)).
:- mode term__relabel_variables(in, in, in, out) is det.
%	term__relabel_variables(Terms0, OldVar, NewVar, Terms) :
%		same as term__relabel_variable but for a list of terms.

:- pred term__apply_variable_renaming(term, map(var, var), term).
:- mode term__apply_variable_renaming(in, in, out) is det.
% 		same as term__relabel_variable, except relabels
% 		multiple variables. If a variable is not in the
% 		map, it is not replaced.

:- pred term__apply_variable_renaming_to_list(list(term), map(var, var),
							 list(term)).
:- mode term__apply_variable_renaming_to_list(in, in, out) is det.
%		applies term__apply_variable_renaming to a list of terms.
		

:- pred term__is_ground(term, substitution).
:- mode term__is_ground(in, in) is semidet.
%	term__is_ground(Term, Bindings) is true iff no variables contained
%		in Term are non-ground in Bindings.

:- pred term__is_ground(term).
:- mode term__is_ground(in) is semidet.
%	term__is_ground(Term) is true iff Term contains no variables.

:- pred term__compare(comparison_result, term, term, substitution).
:- mode term__compare(out, in, in, in) is semidet.
%	term__compare(Comparison, Term1, Term2, Bindings) is true iff
%		there is a binding of Comparison to <, =, or > such
%		that the binding holds for the two ground terms Term1
%		and Term2 with respect to the bindings in Bindings.
%		Fails if Term1 or Term2 is not ground (with respect to
%		the bindings in Bindings).

%--------------------------------------------------%

	% To manage a supply of variables, use the following 2 predicates.
	% (We might want to give these a unique mode later.)

:- pred term__init_var_supply(var_supply).
:- mode term__init_var_supply(out) is det.
:- mode term__init_var_supply(in) is semidet. % implied
%	term__init_var_supply(VarSupply) :
%		returns a fresh var_supply for producing fresh variables.

:- pred term__create_var(var_supply, var, var_supply).
:- mode term__create_var(in, out, out) is det.
%	term__create_var(VarSupply0, Variable, VarSupply) :
%		create a fresh variable (var) and return the
%		updated var_supply.

:- pred term__var_to_int(var, int).
:- mode term__var_to_int(in, out) is det.
%		Convert a variable to an int.
%		Different variables map to different ints.
%		Other than that, the mapping is unspecified.
	
%--------------------------------------------------%

	% Given a term context, return the source line number.

:- pred term__context_line(term__context, int).
:- mode term__context_line(in, out) is det.

	% Given a term context, return the source file.

:- pred term__context_file(term__context, string).
:- mode term__context_file(in, out) is det.

	% Used to initialize the term context when reading in
	% (or otherwise constructing) a term.

:- pred term__context_init(term__context).
:- mode term__context_init(out) is det.

:- pred term__context_init(string, int, term__context).
:- mode term__context_init(in, in, out) is det.

	% Convert a list of terms which are all vars into a list
	% of vars.  Abort (call error/1) if the list contains
	% any non-variables.

:- pred term__term_list_to_var_list(list(term), list(var)).
:- mode term__term_list_to_var_list(in, out) is det.

	% Convert a list of terms which are all vars into a list
	% of vars (or vice versa).

:- pred term__var_list_to_term_list(list(var), list(term)).
:- mode term__var_list_to_term_list(in, out) is det.
:- mode term__var_list_to_term_list(out, in) is semidet.

%--------------------------------------------------%
%--------------------------------------------------%

term_io

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: term_io.m.
% Main author: fjh.
% Stability: medium to high.
%
% This file encapsulates all the term I/O.
% This exports predicates to read and write terms in the
% nice ground representation provided in term.m.
%
%--------------------------------------------------%

:- module term_io.
:- interface.
:- import_module io, varset, term.

% External interface: exported predicates

/***** not yet implemented
:- type op_type ---> fx; fy; xf; yf; xfx; xfy; yfx; fxx; fxy; fyx; fyy.
:- pred term_io__op(int, op_type, string, io__state, io__state).
:- mode term_io__op(in, in, in, di, uo) is det.
%	term_io__op(Prec, Type, OpName, IOState0, IOState1).
%		Define an operator as per Prolog op/3 for future calls to
%		term_io__read_term.

:- type op_details ---> op(int, op_type, string).
:- pred term_io__current_ops(list(op_details), io__state, io__state).
:- mode term_io__current_ops(out, di, uo) is det.
%		Return a list containing all the current operator definitions.
%		Does not modify the io__state.
*****/

:- type read_term ---> eof ; error(string, int) ; term(varset, term).
:- pred term_io__read_term(read_term, io__state, io__state).
:- mode term_io__read_term(out, di, uo) is det.

%	term_io__read_term(Result, IO0, IO1).
%		Read a term from standard input. Similar to NU-Prolog
%		read_term/2, except that resulting term is in the ground
%		representation. Binds Result to either `eof',
%		`term(VarSet, Term)', or `error(Message, LineNumber)'.

:- pred term_io__write_term(varset, term, io__state, io__state).
:- mode term_io__write_term(in, in, di, uo) is det.
%		Writes a term to standard output.

:- pred term_io__write_term_nl(varset, term, io__state, io__state).
:- mode term_io__write_term_nl(in, in, di, uo) is det.
%		As above, except it appends a period and new-line.

:- pred term_io__write_constant(const, io__state, io__state).
:- mode term_io__write_constant(in, di, uo) is det.
%		Writes a constant (integer, float, or atom) to stdout.

:- pred term_io__write_variable(var, varset, io__state, io__state).
:- mode term_io__write_variable(in, in, di, uo) is det.
%		Writes a variable to stdout.

:- pred term_io__quote_string(string, io__state, io__state).
:- mode term_io__quote_string(in, di, uo) is det.
	% Given a string S, write S in double-quotes, with characters
	% escaped if necessary, to stdout.

:- pred term_io__quote_atom(string, io__state, io__state).
:- mode term_io__quote_atom(in, di, uo) is det.
	% Given an atom-name A, write A, enclosed in single-quotes if necessary,
	% with characters escaped if necessary, to stdout.

:- pred term_io__quote_char(char, io__state, io__state).
:- mode term_io__quote_char(in, di, uo) is det.
	% Given a character C, write C in single-quotes,
	% escaped if necessary, to stdout.

:- pred term_io__write_escaped_char(char, io__state, io__state).
:- mode term_io__write_escaped_char(in, di, uo) is det.
	% Given a character C, write C, escaped if necessary, to stdout.
	% The character is not enclosed in quotes.

:- pred term_io__write_escaped_string(string, io__state, io__state).
:- mode term_io__write_escaped_string(in, di, uo) is det.
	% Given a string S, write S, with characters
	% escaped if necessary, to stdout.
	% The string is not enclosed in quotes.

	% `term_io__quote_single_char' is the old (misleading) name for
	% `term_io__write_escaped_char'.  Use the latter instead.
:- pragma obsolete(term_io__quote_single_char/3).
:- pred term_io__quote_single_char(char, io__state, io__state).
:- mode term_io__quote_single_char(in, di, uo) is det.

%--------------------------------------------------%
%--------------------------------------------------%
%--------------------------------------------------%

tree234

%--------------------------------------------------%
% Copyright (C) 1994-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%

% tree234 - implements a map (dictionary) using 2-3-4 trees.
% main author: conway.
% stability: medium.

% See map.m for documentation.

%--------------------------------------------------%

:- module tree234.

:- interface.

:- import_module list, assoc_list.

:- type tree234(K, V).

:- pred tree234__init(tree234(K, V)).
:- mode tree234__init(uo) is det.

:- pred tree234__member(tree234(K, V), K, V).
:- mode tree234__member(in, out, out) is nondet.

:- pred tree234__search(tree234(K, V), K, V).
:- mode tree234__search(in, in, out) is semidet.

:- pred tree234__lookup(tree234(K, V), K, V).
:- mode tree234__lookup(in, in, out) is det.

:- pred tree234__insert(tree234(K, V), K, V, tree234(K, V)).
:- mode tree234__insert(in, in, in, out) is semidet.
% :- mode tree234__insert(di_tree234, in, in, uo_tree234) is semidet.
% :- mode tree234__insert(in, in, in, out) is semidet.

:- pred tree234__set(tree234(K, V), K, V, tree234(K, V)).
:- mode tree234__set(di, di, di, uo) is det.
% :- mode tree234__set(di_tree234, in, in, uo_tree234) is det.
:- mode tree234__set(in, in, in, out) is det.

:- pred tree234__delete(tree234(K, V), K, tree234(K, V)).
:- mode tree234__delete(di, in, uo) is det.
% :- mode tree234__delete(di_tree234, in, uo_tree234) is det.
:- mode tree234__delete(in, in, out) is det.

:- pred tree234__remove(tree234(K, V), K, V, tree234(K, V)).
:- mode tree234__remove(di, in, uo, uo) is semidet.
% :- mode tree234__remove(di_tree234, in, out, uo_tree234) is semidet.
:- mode tree234__remove(in, in, out, out) is semidet.

:- pred tree234__remove_smallest(tree234(K, V), K, V, tree234(K, V)).
:- mode tree234__remove_smallest(di, uo, uo, uo) is semidet.
% :- mode tree234__remove_smallest(di_tree234, out, out, uo_tree234)
%	is semidet.
:- mode tree234__remove_smallest(in, out, out, out) is semidet.

:- pred tree234__keys(tree234(K, V), list(K)).
:- mode tree234__keys(in, out) is det.

:- pred tree234__values(tree234(K, V), list(V)).
:- mode tree234__values(in, out) is det.

:- pred tree234__update(tree234(K, V), K, V, tree234(K, V)).
:- mode tree234__update(in, in, in, out) is semidet.
% :- mode tree234__update(di_tree234, in, in, uo_tree234) is det.
% :- mode tree234__update(di, di, di, uo) is semidet.

	% count the number of elements in a tree
:- pred tree234__count(tree234(K, V), int).
:- mode tree234__count(in, out) is det.

:- pred tree234__assoc_list_to_tree234(assoc_list(K, V), tree234(K, V)).
:- mode tree234__assoc_list_to_tree234(in, out) is det.

:- pred tree234__tree234_to_assoc_list(tree234(K, V), assoc_list(K, V)).
:- mode tree234__tree234_to_assoc_list(in, out) is det.

%--------------------------------------------------%
%--------------------------------------------------%

varset

%--------------------------------------------------%
% Copyright (C) 1993-1997 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: varset.m.
% Main author: fjh.
% Stability: low.
%
% This file provides facilities for manipulating collections of
% variables and terms.
% It provides the 'varset' ADT. A varset is a set of variables.
% (These variables are object-level variables, and are represented
% as ground terms, so it might help to think of them as "variable ids"
% rather than variables.)
% Associated with each variable there can be both a name and a value
% (binding).
%
% There may be some design flaws in the relationship between varset.m,
% term.m, and graph.m.  Once we have implemented unique modes and
% destructive assignment, we will need to rethink the design;  we may
% end up modifying these modules considerably, or we may end up
% making new single-threaded versions of these modules.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module varset.
:- interface.
:- import_module term.

:- type varset.

	% construct an empty varset.
:- pred varset__init(varset).
:- mode varset__init(out) is det.

	% check whether a varset is empty.
:- pred varset__is_empty(varset).
:- mode varset__is_empty(in) is semidet.

	% create a new variable
:- pred varset__new_var(varset, var, varset).
:- mode varset__new_var(in, out, out) is det.

	% create a new named variable
:- pred varset__new_named_var(varset, string, var, varset).
:- mode varset__new_named_var(in, in, out, out) is det.

	% create multiple new variables
:- pred varset__new_vars(varset, int, list(var), varset).
:- mode varset__new_vars(in, in, out, out) is det.

	% delete the name and value for a variable
:- pred varset__delete_var(varset, var, varset).
:- mode varset__delete_var(in, in, out) is det.

	% delete the names and values for a list of variables
:- pred varset__delete_vars(varset, list(var), varset).
:- mode varset__delete_vars(in, in, out) is det.

	% return a list of all the variables in a varset
:- pred varset__vars(varset, list(var)).
:- mode varset__vars(in, out) is det.

	% set the name of a variable
	% (if there is already a variable with the same name "Foo",
	% then try naming it "Foo'", or "Foo"", or "Foo"'", etc. until
	% an unused name is found.)
:- pred varset__name_var(varset, var, string, varset).
:- mode varset__name_var(in, in, in, out) is det.

	% lookup the name of a variable;
	% create one if it doesn't have one using V_ as a prefix
:- pred varset__lookup_name(varset, var, string).
:- mode varset__lookup_name(in, in, out) is det.

	% lookup the name of a variable;
	% create one if it doesn't have one using the specified prefix
:- pred varset__lookup_name(varset, var, string, string).
:- mode varset__lookup_name(in, in, in, out) is det.

	% lookup the name of a variable;
	% fail if it doesn't have one
:- pred varset__search_name(varset, var, string).
:- mode varset__search_name(in, in, out) is semidet.

	% bind a value to a variable
	% (will overwrite any existing binding).
:- pred varset__bind_var(varset, var, term, varset).
:- mode varset__bind_var(in, in, in, out) is det.

	% bind a set of terms to a set of variables.
:- pred varset__bind_vars(varset, substitution, varset).
:- mode varset__bind_vars(in, in, out) is det.

	% lookup the value of a variable
:- pred varset__search_var(varset, var, term).
:- mode varset__search_var(in, in, out) is semidet.

	% get the bindings for all the bound variables.
:- pred varset__lookup_vars(varset, substitution).
:- mode varset__lookup_vars(in, out) is det.

	% Combine two different varsets, renaming apart:
	% varset__merge(VarSet0, NewVarSet, Terms0, VarSet, Terms) is
	% true iff VarSet is the varset that results from joining
	% VarSet0 to a suitably renamed version of NewVarSet,
	% and Terms is Terms0 renamed accordingly.
	% (Any bindings in NewVarSet are ignored.)

:- pred varset__merge(varset, varset, list(term), varset, list(term)).
:- mode varset__merge(in, in, in, out, out) is det.

	% As above, except return the substitution directly
	% rather than applying it to a list of terms.

:- pred varset__merge_subst(varset, varset, varset, substitution).
:- mode varset__merge_subst(in, in, out, out) is det.

	% get the bindings for all the bound variables.
:- pred varset__get_bindings(varset, substitution).
:- mode varset__get_bindings(in, out) is det.

	% set the bindings for all the bound variables.
:- pred varset__set_bindings(varset, substitution, varset).
:- mode varset__set_bindings(in, in, out) is det.

	% Create a map from names to variables.
	% Each name is mapped to only one variable, even if a name is
	% shared by more than one variable. Therefore this predicate
	% is only really useful if it is already known that no two
	% variables share the same name.
:- pred varset__create_name_var_map(varset, map(string, var)).
:- mode varset__create_name_var_map(in, out) is det.

	% Return an association list giving the name of each variable.
	% Every variable has an entry in the returned association list,
	% even if it shares its name with another variable.
:- pred varset__var_name_list(varset, assoc_list(var, string)).
:- mode varset__var_name_list(in, out) is det.

	% Given a list of variable and varset in which some variables have
	% no name but some other variables may have the same name,
	% return another varset in which every variable has a unique name.
	% If necessary, names will have suffixes added on the end;
	% the second argument gives the suffix to use.
:- pred varset__ensure_unique_names(list(var), string, varset, varset).
:- mode varset__ensure_unique_names(in, in, in, out) is det.

%--------------------------------------------------%