[m-users.] Tabling a semidet predicate

[Volker Wysk]

Am Donnerstag, den 10.06.2021, 20:30 +1000 schrieb 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.

This make sense...

>  
> > 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). 

Yes, Rules and Files are the same for all calls to "check". I've tried using
promise_implied, and then it became really fast.

> 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. 

Yes, that's it.

> 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.

Sometimes you see the simple solution last... I've done as you described,
and it works now.

> 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.

Many thanks!


Volker
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: This is a digitally signed message part
URL: <http://lists.mercurylang.org/archives/users/attachments/20210610/113f68d3/attachment.sig>