[m-users.] Tabling a semidet predicate

[Volker Wysk]

Am Mittwoch, den 09.06.2021, 05:54 +1000 schrieb Zoltan Somogyi:
> 2021-06-08 22:47 GMT+10:00 "Volker Wysk" <post at volker-wysk.de>:
> > Hi!
> > 
> > I have a semidet predicate, and want to achieve termination with tabling.
> > Like this:
> > 
> > 
> > :- pred test(int::in) is semidet.
> > :- pragma minimal_model(test/1).
> > 
> > test(X) :- test(X).
> > test(1).
> > test(2).
> 
> The way to achieve termination in this case is not to enable tabling,
> but to simply delete the first clause.
> 
> > I'm not sure if I understand this fully. Is this the way to go?
> 
> No. You have not told us anything about the *actual* program
> you are working on, but probably what you want is pragma memo,
> not pragma minimal_model.

What I'm trying to build is a miniature expert system. The following is a
simplified description.

It's about items (files on disk) and categories (directories). A file can be
member of several directories.

I have a type for terms:

:- type tterm
   ---> dir(string)	    % meaning "the file in question is member 
                            % of this directory"
   ;    and(tterm, tterm)
   ;    or(tterm, tterm)
   ;    not(tterm).

The rules are read from a text file and are stored like this:

:- type rules == multi_map(string,    % rule head (directory name)
		           tterm).    % rule body

The memberships of files in directories is stored like this:

:- type files == multi_map(string,     % directory name
                           string).    % file name

The central predicate checks if a file name satisfies a term:

:- pred check(rules::in, files::in, tterm::in, string::in) is semidet.
:- pragma memo(check/4).

I've used "pragma memo" now, instead of "pragma minimal_model", as you
suggested.

The inference goes like this:

check(Rules, Files, dir(Dir), File) :-
    (
        multi_map.search(Files, Dir, FilesL),
        member(File, FilesL)
    ;
        multi_map.search(Rules, Dir, Terme),
        member(Term, Terme),
        check(Rules, Files, Term, File)
    ).

check(Rules, Files, and(T1, T2), File) :-
    check(Rules, Files, T1, File),
    check(Rules, Files, T2, File).

check(Rules, Files, or(T1, T2), File) :-
    (
        check(Rules, Files, T1, File)
    ;
        check(Rules, Files, T2, File)
    ).

check(Rules, Files, not(T), File) :-
    not(check(Rules, Files, T, File)).


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

Can you tell what's going on, and how to do it right?


Best wishes,
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/ec24f80c/attachment.sig>