Copyright (C) 1995 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.
%--------------------------------------------------% % Copyright (C) 1995 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. %--------------------------------------------------% % array.m % Main author: bromage. % this file contains a set of predicates for generating an manipulating % an array data structure. It is based on the original module by conway, % which used 2-3 trees to store the array. This uses the map module % instead, because it's less likely to contain bugs. :-) % % Arrays will be internal soon anyway, so it doesn't really matter how % efficient this code is, as long as it works. %--------------------------------------------------% %--------------------------------------------------% :- module array. :- interface. :- import_module int, list. :- type array(T). % array__init creates an array with bounds from Low to High, with each % element initialized to Init. :- pred array__init(int, int, T, array(T)). :- mode array__init(in, in, in, out) is det. % want an array_skeleton? % array__bounds returns the upper and lower bounds of an array. :- pred array__bounds(array(_T), int, int). :- mode array__bounds(in, out, out) is det. % array__lookup returns the Nth element of an array % or aborts if the index is out of bounds. :- pred array__lookup(array(T), int, T). :- mode array__lookup(in, in, out) is det. % array__semidet_lookup is like array__lookup except that % it fails if the index is out of bounds. :- pred array__semidet_lookup(array(T), int, T). :- mode array__semidet_lookup(in, in, out) is semidet. % array__set sets the nth element of an array, and returns the resulting % array (good oppertunity for destructive update ;-). It aborts if the % index is out of bounds. :- pred array__set(array(T), int, T, array(T)). :- mode array__set(in, in, in, out) is det. % array__resize takes an array and new lower and upper bounds. % the array is expanded or shrunk at each end to make it fit % the new bounds. :- pred array__resize(array(T), int, int, array(T)). :- mode array__resize(in, in, in, out) is det. % array__from_list takes a list (of nonzero length), % 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, out) is det. % array__to_list takes an array and returns a list containing the % elements of the array in the same order that they % occured in the array. :- pred array__to_list(array(T), list(T)). :- mode array__to_list(in, out) is det. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % %--------------------------------------------------% %--------------------------------------------------% :- module bag. :- interface. :- type bag(T). :- pred bag__init(bag(T)). :- mode bag__init(out) is det. :- pred bag__insert(bag(T), T, bag(T)). :- mode bag__insert(in, in, out) is det. :- pred bag__remove(bag(T), T, bag(T)). :- mode bag__remove(in, in, out) is det. :- pred bag__remove_all(bag(T), T, bag(T)). :- mode bag__remove_all(in, in, out) is det. :- pred bag__contains(T, bag(T)). :- mode bag__contains(in, in) is semidet. :- pred bag__to_list_without_duplicates(bag(T), list(T)). :- mode bag__to_list_without_duplicates(in, out) is det. %--------------------------------------------------% %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % % This file provides the 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. % % The implementation is a pair of maps. % %--------------------------------------------------% %--------------------------------------------------% :- module bimap. :- interface. :- import_module list, int, std_util. %--------------------------------------------------% :- 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)). %--------------------------------------------------% %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % % 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, std_util. :- type bintree(K, V). :- pred bintree__init(bintree(K,V)). :- mode bintree__init(out) 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(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. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % 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'. % 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(out) 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(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(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. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % 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. :- import_module list. %--------------------------------------------------% :- 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__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). %--------------------------------------------------% %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. %--------------------------------------------------% :- module dir. :- interface. :- import_module string. % 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. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % % Floating point support. % % The interface provided here is rather low-level and not % syntactically elegant. It's a building block, not a finished tool. % % XXX - What should we do about unification of two Nan's? % %--------------------------------------------------% :- module float. :- interface. :- pred builtin_float_plus(float, float, float). :- mode builtin_float_plus(in, in, out) is det. :- pred builtin_float_minus(float, float, float). :- mode builtin_float_minus(in, in, out) is det. :- pred builtin_float_times(float, float, float). :- mode builtin_float_times(in, in, out) is det. :- pred builtin_float_divide(float, float, float). :- mode builtin_float_divide(in, in, out) is det. :- pred builtin_float_gt(float, float). :- mode builtin_float_gt(in, in) is semidet. :- pred builtin_float_lt(float, float). :- mode builtin_float_lt(in, in) is semidet. :- pred builtin_float_ge(float, float). :- mode builtin_float_ge(in, in) is semidet. :- pred builtin_float_le(float, float). :- mode builtin_float_le(in, in) is semidet. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % % This module defines a directed graph data type. % % graph__insert_node is O(log N) for N nodes. % graph__insert_edge is O(log N+log A) for N nodes and A arcs. % graph__path(in, in, in) is O(log N) + O(set__member) for N nodes. % The cost of the set__member operation is in the number of % edges leaving the node. % %--------------------------------------------------% %--------------------------------------------------% :- module graph. :- interface. :- import_module set. :- type graph(N, A). :- type node(N). :- type arc(A). :- pred graph__init(graph(N, A)). :- mode graph__init(out) is det. :- pred graph__insert_node(graph(N, A), N, node(N), graph(N, A)). :- mode graph__insert_node(in, in, out, out) is det. :- pred graph__find_node(graph(N, A), N, node(N)). :- mode graph__find_node(in, in, out) is det. :- pred graph__lookup_node(graph(N, A), node(N), N). :- mode graph__lookup_node(in, in, out) is det. :- pred graph__successors(graph(N, A), node(N), set(node(N))). :- mode graph__successors(in, in, out) is det. :- pred graph__nodes(graph(N, A), set(node(N))). :- mode graph__nodes(in, out) is det. :- 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 det. :- pred graph__path(graph(N, A), node(N), node(N)). :- mode graph__path(in, in, in) is semidet. :- mode graph__path(in, in, out) is nondet. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % % 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, std_util. :- 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.
%--------------------------------------------------% % Copyright (C) 1995 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. % %--------------------------------------------------% :- module int. :- interface. :- import_module float. % '<' and '>' are currently defined in mercury_builtin.m, since they need to % be because they are used in the implementation of compare/3. % % :- pred <(int, int). % :- mode <(in, in) is semidet. % % :- pred >(int, int). % :- mode >(in, in) is semidet. :- pred =<(int, int). :- mode =<(in, in) is semidet. :- pred >=(int, int). :- mode >=(in, in) is semidet. :- pred int__abs(int, int). :- mode int__abs(in, out) is det. :- pred int__max(int, int, int). :- mode int__max(in, in, out) is det. :- pred int__min(int, int, int). :- mode int__min(in, in, out) is det. :- pred int__to_float(int, float) is det. :- mode int__to_float(in ,out) is det. :- pred int__pow(int, int, int). :- mode int__pow(in, in, out) is det. % int__pow(X, Y, Z): Z is X raised to the Yth power % Y must not be negative. :- pred int__log2(int, int). :- mode int__log2(in, out) is det. % 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. /* % If Mercury had undiscriminated unions (like the NU-Prolog type checker) % we could handle is/2 better: :- type int__expr = int__expr_2 + int. :- type int__expr_2 ---> (int__expr + int__expr) ; (int__expr * int__expr) ; (int__expr - int__expr) ; (int__expr mod int__expr) ; (int__expr // int__expr). :- pred is(int :: out, int__expr :: (in)) is det. */ % Instead, we use some hacks in the parser. :- type int__simple_expr ---> (int + int) ; (int * int) ; (int - int) ; (int mod int) % modulus ; (int // int) % integer division ; (int << int) % left shift ; (int >> int) % right shift ; (int /\ int) % bitwise and ; (int \/ int) % bitwise or ; (int ^ int) % bitwise exclusive or ; (\ int). % bitwise complement :- pred is(int :: out, int__simple_expr :: in) is det. /* NB: calls to `is' get automagically converted into calls to builtin_whatever by the parser. That is a quick hack to allow us to generate efficient code for it. */ :- pred builtin_plus(int, int, int). :- mode builtin_plus(in, in, out) is det. :- pred builtin_minus(int, int, int). :- mode builtin_minus(in, in, out) is det. :- pred builtin_times(int, int, int). :- mode builtin_times(in, in, out) is det. :- pred builtin_div(int, int, int). :- mode builtin_div(in, in, out) is det. :- pred builtin_mod(int, int, int). :- mode builtin_mod(in, in, out) is det. :- pred builtin_left_shift(int, int, int). :- mode builtin_left_shift(in, in, out) is det. :- pred builtin_right_shift(int, int, int). :- mode builtin_right_shift(in, in, out) is det. :- pred builtin_bit_or(int, int, int). :- mode builtin_bit_or(in, in, out) is det. :- pred builtin_bit_and(int, int, int). :- mode builtin_bit_and(in, in, out) is det. :- pred builtin_bit_xor(int, int, int). :- mode builtin_bit_xor(in, in, out) is det. :- pred builtin_bit_neg(int, int). :- mode builtin_bit_neg(in, out) is det.
%--------------------------------------------------% % Copyright (C) 1995 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. % % 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 enforced at compile time by using unique modes. % (Except that we haven't implemented that yet. So instead it's checked at % runtime. Except that those checks prevent doing a `redo' in the debugger. % So we don't check at all. Oh well. Just don't write any programs that % depend on it, because they *WILL* break!) % %--------------------------------------------------% %--------------------------------------------------% :- module io. :- interface. :- import_module char, int, float, 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 I/O streams. :- type io__input_stream. :- type io__output_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(T) ---> ok(T) ; eof ; error(io__error). :- type io__error. % Use io__error_message to decode it. % Poly-type :- type io__poly_type ---> c(char) ; s(string) ; i(int) ; f(float). %--------------------------------------------------% % 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__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__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_anything(io__res(_T), io__state, io__state). :- mode io__read_anything(in, di, uo) is det. % Reads its argument to the current output stream. % The argument may be of any type. % The term read had better be of the right type! % This is a hack! :- pred io__read_anything(io__input_stream, io__res(_T), io__state, io__state). :- mode io__read_anything(in, out, di, uo) is det. % Reads its argument to the specified stream. % The argument may be of any type. % The term read had better be of the right type! % This is a hack! :- pred io__ignore_whitespace(io__res, 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__res, io__state, io__state). :- mode io__ignore_whitespace(in, out, di, uo) is det. % Discards all the whitespace from the specified stream. %--------------------------------------------------% % Output predicates. :- 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 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 string to the specified 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 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 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 stream. :- pred io__write_many(list(io__poly_type), io__state, io__state). :- mode io__write_many(in, di, uo) is det. % writes a polyglot to output. :- 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. % writes a polyglot to a specified stream. :- pred io__write_anything(_T, io__state, io__state). :- mode io__write_anything(in, di, uo) is det. % Writes it's argument to the current output stream. % The argument may be of any type. This is a hack! :- pred io__write_anything(io__output_stream, _T, io__state, io__state). :- mode io__write_anything(in, in, di, uo) is det. % Writes it's argument to the specified stream. % The argument may be of any type. This is a hack! :- 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 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. :- 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 current input stream % (as per NU-Prolog lineCount/1). %--------------------------------------------------% % Output 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 input>". % 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 input>". % For stderr this is the string "<standard error>". %--------------------------------------------------% % 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(out, di, uo) is det. % Doesn't modify the io__state. :- pred io__set_globals(univ, io__state, io__state). :- mode io__set_globals(in, di, uo) is det. %--------------------------------------------------% % 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. :- pred io__gc_call(pred(io__state, io__state), io__state, io__state). :- mode io__gc_call( det_pred(ground_unique, dead, free_unique, ground_unique), 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. :- 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. %--------------------------------------------------% % For use by term_io.m: :- import_module ops. :- pred io__get_op_table(ops__table, io__state, io__state). :- mode io__get_op_table(out, di, uo) is det. :- pred io__set_op_table(ops__table, io__state, io__state). :- mode io__set_op_table(in, di, uo) is det. % For use by the Mercury runtime (io.mod): :- type io__external_state. :- pred io__init_state(io__external_state, io__state). :- mode io__init_state(di, uo) is det. %--------------------------------------------------% %--------------------------------------------------%
%--------------------------------------------------%
% Copyright (C) 1995 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.
%
% 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 char, string, int, float, list, std_util, 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(character) % 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
:- type token_context == int.
:- type token_list == list(pair(token, token_context)).
:- 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.
%--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. :- import_module array, bag, bimap, bintree, bintree_set, char, dir. :- import_module float, graph, group, int, io. :- import_module list, map, pqueue, queue, random, relation, require. :- import_module set, stack, std_util, string, term, term_io. :- import_module tree234, varset, store, rbtree. :- import_module parser, lexer, ops.
%--------------------------------------------------% % Copyright (C) 1995 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. % % Main author: fjh. % %--------------------------------------------------% :- module list. :- import_module int. :- interface. :- type list(T) ---> [] ; [T | list(T)]. :- inst list_skel(I) = bound(([] ; [I | list_skel(I)])). :- inst list_skel = list_skel(free). :- inst non_empty_list = bound([ground | ground]). :- mode input_list_skel :: list_skel -> list_skel. :- mode output_list_skel :: free -> list_skel. :- mode list_skel_output :: list_skel -> ground. %--------------------------------------------------% % standard append predicate :- pred list__append(list(T), list(T), list(T)). :- 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 multidet. % 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_prefix instead. % :- mode list__append(out, in, in) is semidet. :- pred list__remove_suffix(list(T), list(T), list(T)). :- mode list__remove_suffix(in, in, out) 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. % merge - see NU-Prolog documentation :- pred list__merge(list(T), list(T), list(T)). :- mode list__merge(in, in, out) is det. % list__merge(L1, L2, L): % L is the result of merging L1 and L2. % L1 and L2 must be sorted. :- pred list__merge_and_remove_dups(list(T), list(T), list(T)). :- mode list__merge_and_remove_dups(in, in, out) is det. % list__merge_and_remove_dups(L1, L2, L): % L is the result of merging L1 and L2 and eliminating % any duplicates. % L1 and L2 must be sorted. :- pred list__remove_adjacent_dups(list(T), list(T)). :- mode list__remove_adjacent_dups(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_dups(list(T), list(T)). :- mode list__remove_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__member(T, list(T)). :- mode list__member(in, in) is semidet. :- mode list__member(out, in) is nondet. :- pred list__member(T, list(T), list(T)). :- mode list__member(out, in, out) is nondet. :- pred list__length(list(_T), int). /**** % XXX The current mode checker can't handle this :- mode list__length(input_list_skel, out) is det. *****/ :- mode list__length(in, out) is det. :- mode list__length(in, in) is semidet. % implied :- pred list__condense(list(list(T)), list(T)). :- mode list__condense(in, out) is det. :- pred list__same_length(list(T1), list(T2)). /**** % XXX The current mode checker can't handle this :- mode list__same_length(input_list_skel, output_list_skel) is det. :- mode list__same_length(output_list_skel, input_list_skel) is det. ****/ :- 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. % list__split_list(Len, List, Start, End): % splits `List' into a prefix `Start' of length `Len', % and a remainder `End'. :- pred list__split_list(int, list(T), list(T), list(T)). :- mode list__split_list(in, in, out, out) is semidet. :- pred list__reverse(list(T), list(T)). :- mode list__reverse(in, out) is det. :- 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. % 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(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__sort(List0, List): % List is List0 sorted with duplicates removed. :- pred list__sort(list(T), list(T)). :- mode list__sort(in, out) is det. :- pred list__nth_member_search(list(T), T, int). :- mode list__nth_member_search(in, in, out) is semidet. :- 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. % 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. % Take two lists and alternate elements starting with % the first list. 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. :- pred list__split3(list(T), list(T), list(T), list(T)). :- mode list__split3(in, out, in, in) is semidet. % 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. :- pred list__chunk(list(T), int, list(list(T))). :- mode list__chunk(in, in, out) is det. % Non deterministic insert. Keeps insertling T into different places % in the list. :- pred list__insert(T, list(T), list(T)). :- mode list__insert(in, in, out) is multidet. % list__perm(List0, List) is true iff if List0 is a permutation of List :- pred list__perm(list(T), list(T)). :- mode list__perm(in, out) is nondet. %--------------------------------------------------% %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % % 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, std_util, require. %--------------------------------------------------% :- type map(_K, _V). %--------------------------------------------------% % Initialize an empty map. :- pred map__init(map(_,_)). :- mode map__init(out) 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. % 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(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(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). %--------------------------------------------------% %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % 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)', ... % are builtin and are implemented using special code in the % type-checker. (XXX TODO: report an error for attempts to redefine % these types.) %--------------------------------------------------% % INSTS. % The standard insts `free', `ground', and `bound(...)' are builtin % and are implemented using special code in the parser and mode-checker. % Unique insts. Currently aliased to standard insts, since unique insts % aren't implemented yet. Note that `bound_unique' is aliased to `bound' % in the parser (prog_io.m), because it couldn't be done here. :- inst free_unique = free. :- inst ground_unique = ground. :- inst dead = ground. %--------------------------------------------------% % 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). % Unique modes. Currently aliased to standard modes, since unique modes % aren't implemented yet. :- mode di :: input. :- mode uo :: output. :- mode ui :: input. % Higher-order predicate modes. % This needs to be builtin - the following is just a temporary hack. :- mode det_pred :: output. :- mode det_pred(_, _) :: output. :- mode det_pred(_, _, _, _) :: output. :- mode det_pred(_, _, _, _, _, _) :: output. :- mode semidet_pred :: output. :- mode semidet_pred(_, _) :: output. :- mode semidet_pred(_, _, _, _) :: output. :- mode semidet_pred(_, _, _, _, _, _) :: output. :- mode nondet_pred :: output. :- mode nondet_pred(_, _) :: output. :- mode nondet_pred(_, _, _, _) :: output. :- mode nondet_pred(_, _, _, _, _, _) :: output. %--------------------------------------------------% % PREDICATES. % 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 !(in, out) is det. % The call/N family. Note that the compiler (make_hlds.m) will transform % goals which are not atoms (e.g. goals which are free variables) into % calls to call/1. :- pred call(pred). :- mode call(in) is semidet. :- pred call(pred(T), T). :- mode call(in, in) is semidet. :- pred call(pred(T1, T2), T1, T2). :- mode call(in, in, in) is semidet. % 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 %--------------------------------------------------% :- type comparison_result ---> (=) ; (<) ; (>). :- pred unify(T::in, T::in) is semidet. :- pred compare(comparison_result::out, T::in, T::in) is det. % The following are used by the compiler, to implement polymorphism. % They should not be used in programs. :- pred index(T::in, int::out) is det. :- pred builtin_unify_int(int::in, int::in) is semidet. :- pred builtin_index_int(int::in, int::out) is det. :- pred builtin_compare_int(comparison_result::out, int::in, int::in) is det. :- pred builtin_unify_string(string::in, string::in) is semidet. :- pred builtin_index_string(string::in, int::out) is det. :- pred builtin_compare_string(comparison_result::out, string::in, string::in) is det. :- pred builtin_unify_float(float::in, float::in) is semidet. :- pred builtin_index_float(float::in, int::out) is det. :- pred builtin_compare_float(comparison_result::out, float::in, float::in) is det. :- pred builtin_unify_pred((pred)::in, (pred)::in) is semidet. :- pred builtin_index_pred((pred)::in, int::out) is det. :- pred builtin_compare_pred(comparison_result::out, (pred)::in, (pred)::in) is det. :- pred compare_error is erroneous. :- type type_info(T) ---> type_info(int /*, ... */). % These should be defined in int.m, but we define them here since % they're need for the implementation of compare/3. :- pred <(int, int). :- mode <(in, in) is semidet. :- pred >(int, int). :- mode >(in, in) is semidet. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % % 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. :- pred ops__init_op_table(ops__table). :- mode ops__init_op_table(out) is det. :- 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. :- pred ops__lookup_prefix_op(ops__table, string, int, ops__assoc). :- mode ops__lookup_prefix_op(in, in, out, out) is semidet. :- 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. :- pred ops__lookup_postfix_op(ops__table, string, int, ops__assoc). :- mode ops__lookup_postfix_op(in, in, out, out) is semidet. :- pred ops__lookup_op(ops__table, string). :- mode ops__lookup_op(in, in) is semidet. :- 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.
%--------------------------------------------------% % Copyright (C) 1995 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. % % 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. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % main author: conway. % % A qpueue is a priority queue DDT with the smallest element at the root. % It takes keys and values to provide a dictionary type function, and % is not guarenteed to be stable. (XXX stability should be fixed.) % %--------------------------------------------------% %--------------------------------------------------% :- module pqueue. :- interface. :- import_module list, std_util. :- 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 associative % 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. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % This file contains a `queue' ADT. % This implementation is in terms of a pair of lists. %--------------------------------------------------% :- module queue. :- interface. :- import_module int. :- 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. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. %--------------------------------------------------% % % rand.m % % main author: conway % % 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 unique modes. % %--------------------------------------------------% :- module random. :- interface. :- import_module int, list. :- type random__supply. :- pred random__init(int, random__supply). :- mode random__init(in, uo) is det. :- pred random__random(int, random__supply, random__supply). :- mode random__random(out, di, uo) is det. :- pred random__randmax(int, random__supply, random__supply). :- mode random__randmax(out, di, uo) is det. :- pred random__test(int, int, list(int), int). :- mode random__test(in, in, out, out) is det. :- pred random__bit_reverse(int::in, int::out) is det. %--------------------------------------------------%
%--------------------------------------------------% %--------------------------------------------------% % % Red-black tree module. % Main author: petdr % % 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. % % 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, std_util. :- type rbtree(K,V) ---> empty ; red(K, V, rbtree(K,V), rbtree(K,V)) ; black(K, V, rbtree(K, V), rbtree(K, V)). :- pred rbtree__init(rbtree(K, V)). :- mode rbtree__init(out) is det. :- pred rbtree__insert(rbtree(K, V), K, V, rbtree(K, V)). :- mode rbtree__insert(in, in, in, out) is semidet. :- pred rbtree__update(rbtree(K, V), K, V, rbtree(K, V)). :- mode rbtree__update(in, in, in, out) is semidet. :- pred rbtree__set(rbtree(K, V), K, V, rbtree(K, V)). :- mode rbtree__set(in, in, in, out) is det. :- pred rbtree__lookup(rbtree(K, V), K, V). :- mode rbtree__lookup(in, in, out) is det. :- pred rbtree__search(rbtree(K, V), K, V). :- mode rbtree__search(in, in, out) is semidet. :- pred rbtree__delete(rbtree(K, V), K, rbtree(K, V)). :- mode rbtree__delete(in, in, out) is det. :- pred rbtree__remove(rbtree(K, V), K, rbtree(K, V)). :- mode rbtree__remove(in, in, out) is semidet. :- pred rbtree__keys(rbtree(K, V), list(K)). :- mode rbtree__keys(in, out) is det. :- pred rbtree__values(rbtree(K, V), list(V)). :- mode rbtree__values(in, out) is det. :- 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. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % % 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, std_util. :- type relation(T). % relation__init creates a new relation. :- pred relation__init(relation(T)). :- mode relation__init(out) is det. % relation__add adds an element to the relation. :- pred relation__add(relation(T), T, T, 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(T, T), 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), T, T, 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(T, T), 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), T, T). :- 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), T, T). :- 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), T, set(T)). :- 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), T, set(T)). :- 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(T, T)). :- 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__effective domain finds the set of all % elements actually used in a relation. :- pred relation__effective_domain(relation(T), set(T)). :- mode relation__effective_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), T, list(T)). :- mode relation__dfs(in, in, out) is det. % relation__components(R, Comp) is true if Comp % is the set of the connected components of R. :- pred relation__components(relation(T), set(set(T))). :- 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(T))). :- 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. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % This module provides features similar to <assert.h> in C. %--------------------------------------------------% :- interface. /*** :- pred require(pred, string). :- mode require(in, in). % require(Goal, Message). % Call goal, and abort with error message if Goal fails. ****/ :- pred error(string). :- mode error(in) is erroneous. % error(Message). % Abort with error message.
%--------------------------------------------------% % Copyright (C) 1995 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. % This file contains a `set' ADT. % Sets are implemented here as unsorted lists, which may contain duplicates. %--------------------------------------------------% :- module set. :- interface. :- import_module list, std_util. :- 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. :- 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. :- 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(out) 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_member(X, Set, Res)' returns 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(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(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. :- 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'. :- pred set__intersect(set(T), set(T), set(T)). :- mode set__intersect(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_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__join(Sets, Set)' is true iff `Set' is the union of % all of the elements of `Sets'. :- pred set__join(set(set(T)), set(T)). :- mode set__join(in, out) is det. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % This file contains a `stack' ADT. % Stacks are implemented here using lists. %--------------------------------------------------% :- module stack. :- interface. :- import_module int, std_util, 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 %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % 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. %--------------------------------------------------% % The universal type. % Note that the current NU-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 definely match. :- type univ. :- pred type_to_univ(_T, univ). :- mode type_to_univ(in, out) is det. :- mode type_to_univ(out, in) is semidet. :- pred univ_to_type(univ, _T). :- mode univ_to_type(in, out) is semidet. :- mode univ_to_type(out, in) is det. %--------------------------------------------------% % 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 ---> yes ; no. :- 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. %--------------------------------------------------% % The "maybe" type. :- type maybe(T) ---> yes(T) ; no. %--------------------------------------------------% :- type unit ---> unit. :- type pair(T1, T2) ---> (T1 - T2). :- type pair(T) == pair(T,T). :- type assoc_list(K,V) == list(pair(K,V)). :- pred assoc_list__reverse_members(assoc_list(K, V), assoc_list(V, K)). :- mode assoc_list__reverse_members(in, out) is det. :- 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. %--------------------------------------------------% :- pred gc_call(pred). :- mode gc_call(in) is nondet. :- pred solutions(pred(T), list(T)). :- mode solutions(complicated_mode, out) is det. % Note! solutions/2 is implemented, but the compiler currently % DOES NOT CHECK that the higher-order pred term you pass has the correct % mode for it's argument (out) and the correct determinism (nondet). % If you pass the wrong sort of pred, your program will most likely dump % core. % The following is a temporary hack until we implement higher-order % modes. :- mode complicated_mode :: input. %--------------------------------------------------% % 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 invokation which disables this side-effect.) :- pred report_stats 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. :- pred semidet_succeed is semidet. :- pred semidet_fail is semidet. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % % This file provides facilities for manipulating stores. % A store is a set of nodes, each of which may contain a value of % any type, and which are identified by node_ids. % % Currently stores are implemented as maps from node_ids to values, % where node_ids are just integers, but we should re-implement this % for unique stores using addresses as ids. % % Graphs may be used to implement cyclic data structures such as % circular linked lists, etc. % % Theoretical problem: we would like to allow heterogenous stores, % with types store and node_id(T) instead of store(T) and node_id(T). % This would be completely type-safe as far as the user of the stores % is concerned, but it isn't possible to implement it except as a builtin. % Stores are a pretty fundamental type, so it might make sense to do so, % but I'm still not sure whether this would cause any theoretical problems. % %--------------------------------------------------% %--------------------------------------------------% :- module store. :- interface. :- type store(T). :- type node_id(T). % initialize a store :- pred store__init(store(_T)). :- mode store__init(out) is det. % create a new node with the specified value :- pred store__new_node(store(T), T, node_id(T), store(T)). :- mode store__new_node(in, in, out, out) is det. % replace the value stored in a given node :- pred store__set_node(store(T), node_id(T), T, store(T)). :- mode store__set_node(in, in, in, out) is det. % lookup the value stored in a given node :- pred store__lookup_node(store(T), node_id(T), T). :- mode store__lookup_node(in, in, out) is det. % Axioms: % % (also determinism of store__init, store__new_node, store__set_node) % % all [G,V,N] % ( % store__new_node(G, V, N) => % ( % store__lookup(G, N, V), % all [V2] store_lookup(G, N, V2) => V2 = V % ) % ). % all [G,V,N] % ( % store__new_node(G, V, N) => % ( % store__lookup(G, N, V), % all [V2] store_lookup(G, N, V2) => V2 = V % ) % ). % etc. % %--------------------------------------------------% %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % Beware that char_to_string/2 won't work with NU-Prolog 1.5.33 because % of a NU-Prolog bug (fixed in 1.5.35). % Main author: fjh. % This modules provides basic string handling facilities. %--------------------------------------------------% :- interface. :- import_module char, int, float. :- pred string__length(string, int). :- mode string__length(in, out) is det. :- pred string__append(string, string, string). :- mode string__append(in, in, out) is det. :- mode string__append(in, in, in) is semidet. % implied :- mode string__append(in, out, in) is semidet. :- 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(character, 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, character, 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__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(character)). :- mode string__to_char_list(in, out) is det. :- pred string__from_char_list(list(character), string). :- mode string__from_char_list(in, out) is det. :- pred string__to_int(string, int). :- mode string__to_int(in, out) is semidet. % Convert a string (of digits) to an int. If the string contains % non-digit characters, 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 of digits in the specified base (2-36) to an int. % If the string contains invalid characters, 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, character, 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, character, 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(character, 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__index(string, int, character). :- 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, character). :- 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__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 what would remain of `String' if the % left-most `Count' characters were removed. % (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 nondet. % 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. %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % This file provides a type `term' used to represent Prolog terms, % and various predicates to manipulate terms and substitutions. %--------------------------------------------------% :- module term. :- interface. :- import_module int, string, float, 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 comparison ---> (>) ; (<) ; (=). :- type var. :- type var_supply. :- type term__context. %--------------------------------------------------% :- 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__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, Bindings) is true iff Term contains no % variables. :- pred term__compare(comparison, 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. %--------------------------------------------------% %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % % 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, int, float, string, list, varset, term, char. % 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(character, 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__quote_single_char(character, io__state, io__state). :- mode term_io__quote_single_char(in, di, uo) is det. % Given a character C, write C, escaped if necessary, to stdout. % The character is not enclosed in quotes. %--------------------------------------------------% %--------------------------------------------------% %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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 (blame him for the lack of documentation! - fjh ;-). %--------------------------------------------------% :- module tree234. :- interface. :- import_module list, std_util. :- type tree234(K, V). :- pred tree234__init(tree234(K, V)). :- mode tree234__init(out) 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. :- pred tree234__set(tree234(K, V), K, V, tree234(K, V)). :- mode tree234__set(in, in, in, out) is det. :- pred tree234__delete(tree234(K, V), K, tree234(K, V)). :- mode tree234__delete(in, in, out) is det. :- pred tree234__remove(tree234(K, V), K, V, tree234(K, V)). :- 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(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. % 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. %--------------------------------------------------% %--------------------------------------------------%
%--------------------------------------------------% % Copyright (C) 1995 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. % % 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). % [But at the moment, the rest of the code is only using varsets to store % names, not values.] % % 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 string, 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. % 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, or the variable with a given name. :- pred varset__lookup_name(varset, var, string). :- mode varset__lookup_name(in, in, out) is semidet. :- mode varset__lookup_name(in, out, in) 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 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__lookup_var(varset, var, term). :- mode varset__lookup_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. %--------------------------------------------------%