[mercury-users] fact tables (was Re: &&/if-then-else semantics (was Re: Request for comments on this code

[Peter Moulder]

On Sat, Jul 15, 2006 at 07:07:34AM -0500, doug.auclair at logicaltypes.com wrote:

> I think I have a similar issue to the one described above:  I wish to generate
> facts that are more expressive than what fact_table allows, but the compiler
> churns when I try to compile these massive fact_table-like modules.
>
> So, would you please share your work?  I'd be very interested to see how you
> approached this issue.

First of all, try using a 0.13 beta, to see if it already does a good
enough job.  Using custom C code involves more source files, more
clutter, more complexity of building, more opportunity for bugs, and
more programmer work.


The data in my case has quite dense coverage of its input arguments,
and (as I've mentioned) each input argument is a smallish non-negative
integer (in most cases corresponding to a Mercury enum type).

The ideal case would would be complete coverage where every input
argument is an enum type, in which case we could use a multi-dimensional
array lookup.

The two tables I've done aren't too far from that.  I'll illustrate it
with the following predicate:

  :- pred lookup(int::in, int::in, char::out) is semidet.
  lookup(String_id, Char_ix, C):-
  	index0(my_strings, String_id, String),
	string.index(String, Char_ix, C).

The most natural way of writing this in C might be:

  char const *const my_strings[] = {"Blah", "Foo", "Frog", ...};
  int lookup(unsigned string_id, unsigned char_ix) {
  	if (string_id >= G_N_ELEMENTS(my_strings)) return -1;
	char const *const str = my_strings[string_id];
	if (char_ix >= strlen(str)) return -1;
	return (int) (unsigned char) str[char_ix];
  }

For automatically-generated code, we can slightly improve that, getting
rid of the linear strlen search for an out-of-bounds element ('\0' here)
and using slightly less memory:

  char const concatenated[] = "BlahFooFrog...";
  unsigned const string_id_to_start[] = {0, 4, 7, 11, ..., sentinel_n};
  int lookup(unsigned string_id, unsigned char_ix) {
  	if (string_id >= G_N_ELEMENTS(string_id_to_start) - 1) return -1;
	unsigned const start = string_id_to_start[string_id];
	unsigned const next = string_id_to_start[string_id + 1];
	if (start + char_ix >= next) return -1;
	return concatenated[start + char_ix];
  }

One of the fact tables that I've coded is like this, and the other one
has an extra level: continuing the string example, there's a number of
collections of strings, and lookup has a collection_id argument.

  char const concatenated_strings = "BlahFooFrog...SecondCollectionStrings...";
  unsigned const concatenated_string_id_to_start[] =
	  {0,4,7,...,100,106,116,123,...};
  unsigned const collection_id_to_start = {/* indexes into
	  concatenated_string_id_to_start */};


I can send you full code if this pattern is in fact useful to you.


Coming back to my question "I wonder whether this would be useful in
the Mercury compiler": the main problem with the existing compiler's
handling of such predicates isn't so much the generated code (nested
switch statements in hlc grade) as how long it takes to compile such
predicates, and (for one example of mine, in hlc grade and at -O0)
running out of stack space if --intermodule-optimization is requested.
In other words, I'd guess that the main problem is just recognizing
the special form and accordingly not bothering with whatever analysis
is taking up all the time & memory.  I don't have any code for that.
It does surprise me that pragma fact_table is necessary, though: isn't
it fairly cheap to detect when a clause meets the requirements?  I'd
have thought that the pragma's only use would be to warn the programmer
if the requirements aren't in fact met.

pjrm.
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at csse.unimelb.edu.au
administrative address: owner-mercury-users at csse.unimelb.edu.au
unsubscribe: Address: mercury-users-request at csse.unimelb.edu.au Message: unsubscribe
subscribe:   Address: mercury-users-request at csse.unimelb.edu.au Message: subscribe
--------------------------------------------------------------------------