[mercury-users] tabling

[Fergus Henderson]

On 29-Nov-2000, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> 
> We could add an optional argument to the pragma memo declaration to tell the
> compiler that a given set of arguments should be tabled by address, not by
> value.

The main difficulty with this proposal is that for implementations
with garbage collectors that move objects and that don't preserve the
relative ordering of pointers, a table of addresses would have to be
searched using linear search.  So on some implementations you might
get radically worse performance if there are many different values
for those arguments in the table.

But for this particular program, since the program always passes the
same map to the tabled procedure, it wouldn't be a problem.

As for syntax, rather than adding a special annotation on the `pragma memo'
directive, I suggest using the type system.  In particular, for terms
that you want to table by address, use an `object(T)' type, as DJ suggested.

The advantage of this approach is that you can table on structured
data with some fields of the structured data being tabled by address
and other fields tabled by value.  Also it doesn't require any new syntax;
only the object(T) type and the tabling routines in the runtime library
need to know about it, not the compiler front-end.

I've attached an implementation of the `object(T)' type that works
with our current (conservative) collector.

Instead of

	:- pred is_some_condition(int::in, string::in,
			map(int, string)::in) is semidet.

you would write

	:- pred is_some_condition(int::in, string::in,
			object(map(int, string))::in) is semidet.

and then the top-level of your program could call either
canonical_object/1 or the reverse mode of object_value/2,
passing it the map(int, string), to create the initial
object(map(int, string)).

I've attached an implementation of the `object(T)' type.
This version only works with conservative collectors
or with implementations that only recover memory on backtracking,
but that covers all of our current implementations.

It would not be too hard to make the object(T) type also work with
non-moving accurate collectors, and it could also be adapted to work
with moving collectors, but for moving collectors that don't preserve
the relative order of pointers, tables on `object(T)' would have to
use linear search.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
-------------- next part --------------
%-----------------------------------------------------------------------------%
% Copyright (C) 1997 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: object.m
% author: fjh
% stability: medium
%
%	Provides (immutable) objects with identity.
%	Useful for hash consing, amoung other things.
%
%	The main disadvantage is that the current implementation
%	won't work with non-conservative garbage collectors.
%
%-----------------------------------------------------------------------------%
:- module object.
:- interface.

	% An object(T) is an abstract thing that
	% has an identity, and a value of type T.
	% Objects with the same identity have the same value,
	% but objects with the same value can have different
	% identities.  However, for each value there is
	% a canonical object with that value.
	% Objects are unifiable and comparable;
	% those operations are both constant time, since they need
	% only compare the object identities, not the values.
:- type object(T).

	% `object_value(Object) = Value' is true iff
	% `Object' is an object with value `Value'.
:- func object_value(object(T)) = T.
:- mode object_value(in) = out is det.		% this is O(1)
:- mode object_value(out) = in is cc_multi.	% this is also O(1)

	% `canonical_object(Value)' returns the canonical object for the
	% specified value.
	% Warning: such objects will NOT be garbage collected.
:- func canonical_object(T) = object(T).

%-----------------------------------------------------------------------------%
:- implementation.
:- import_module map, std_util.

	% XXX Defining object(T) like this won't work for accurate
	% garbage collectors!
	% It would be nicer to use c_pointer rather than int for the
	% addresses, but unfortunately tabling doesn't work for c_pointers.
:- type object(T) ---> object(address)
	where equality is object_equal.
:- type address == int.

	% The equality for object(T) is just address comparison.
	% The reason that we give a user-defined equality for object(T)
	% is just to prevent the use of compare/3 for that type.
:- pred object_equal(object(T)::in, object(T)::in) is semidet.
:- pragma c_code(object_equal(X::in, Y::in),
	[will_not_call_mercury, thread_safe],
"
	SUCCESS_INDICATOR = (X == Y);
").

:- pragma c_code(object_value(Obj::in) = (Val::out), will_not_call_mercury, "
	MR_save_transient_hp();
	Val = MR_make_permanent(Obj, (MR_TypeInfo) TypeInfo_for_T);
	MR_restore_transient_hp();
").
:- pragma c_code(object_value(Obj::out) = (Val::in), will_not_call_mercury, "
	Obj = Val;
").

	% This implementation uses tabling.
canonical_object(Value) = promise_only_solution(canonical_object_2(Value)).

:- pred canonical_object_2(T::in, object(T)::out) is cc_multi.
:- pragma memo(canonical_object_2/2).
canonical_object_2(object_value(Object), Object).

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