[m-users.] Tabling a semidet predicate

[Zoltan Somogyi]

2021-06-10 19:45 GMT+10:00 "Volker Wysk" <post at volker-wysk.de>:
> After I've changed from minimal_model to memo, it *appears* to work. Except
> for it being *very* slow. I've done a trace and get only a few calls of
> check/4 per second. 
> 
> The "files" multimap has about 60000 entries. The "rules" multimap has some
> 100 entries. I suspect that Files has to be copied with every call of
> check/4...

It does not necessarily have to be copied, but it does have to be traversed.
As section 19.2 of the reference manual says:

"The default implementation looks up the value of each input argument, and thus
requires time proportional to the number of function symbols in the input arguments."

Given this fact, and the data structure sizes you gave, the very slow speed you mention
is not surprising to me at all.
 
> Can you tell what's going on

As above.

> and how to do it right?

That depends on things you haven't told us. If Rules and Files are the same for
every call, then you can specify that they should not be tabled (by telling
pragma memo that they are implied). Failing that, you could try tabling them
by address. But I don't see why you need tabling at all for this code.
If the task is to find the set of files for which a specified tterm is true,
given specific values of Rules and Files, then the only reason why you
may have an infinite loop is that a rule body may contain a tterm
that is the same as the tterm in an ancestor call. The standard way
to handle such situations is simply to pass an extra argument that contains
the set of tterms in what is now the third arg position in any ancestor call.
You execute the body of the check predicate only if the current tterm arg
is not in this set, and at each recursive call, you pass the set you were passed
plus your own tterm arg. This stops infinite loops in the same circumstances
in which tabling would stop it, i.e. when the set of tterm args encountered is finite.

This has the advantage that the set is temporary; it goes away when the top
level call returns. In all forms of tabling, the table itself is normally permanent,
though Mercury allows tables' contents to be reset by the program.

Zoltan.