Deducing facts from a set via a predicate by metaprogramming

Question

Suppose I have a set of Literals (represented as a list for instance) and a predicate specified dynamically, what I want is to produce a set of literals that contains all the previous ones in addition to the ones that can be deducted by applying the predicate to the set.

An example, having defined the predicate

pred(A, B) :- base(A, B).
pred(A, C) :- base(A, B), pred(B, C).

and supposing such a signature for the predicate

deduce_set(+Set, +Pred, ?DeducedSet)

the following statement holds (is true):

deduce_set([base(a,b), base(a,c), base(b,d), base(d, e)],
           pred/2,
           [base(a,b), base(a,c), base(b,d), base(d,e), pred(a,d), pred(a,e), pred(b,e)]
          ).

What is the most efficient and general way to do so? I've been thinking about something like:

asserting all literals in Set
call Pred
if it succeeds assert its head
collect all the asserted facts in the resulting set and put into a list

isn't there a better way?

UPDATE This solution, better defined by CapelliC, by using metaprogramming can't cope with vars in the set under Object Identity. Any workaround for this?

Are you trying to populate DeducedSet with a completed list (closure) of Set under (dynamically defined) rules of inference for predicate Pred? In this case DeducedSet will always consist of the (initial) list Set (which perhaps consists of terms with various functors) followed by a tail consisting of new terms for functor Pred. Finding the closure under such rules of inference would probably be facilitated by introducing an accumulator argument. — hardmath
Yes I am, But why an accumulator shall be more efficient in this case? — rano
What I have in mind is that an accumulator makes it easy to construct the DeducedSet until no further inferences are possible, and then "return" the already assembled list. Primarily I was asking if you want "closure" or simply a single pass revision to your DeducedSet. — hardmath
I've understood the easyness of programming, I'd like to get also an efficient solution to find a closure and possibly one to cope with vars under OI — rano

CapelliC CapelliC · Accepted Answer · 2013-02-13T10:15:36

You can use findall/3 (or better, findall/4), avoiding some problem to discriminate (for instance) what instances of pred/2 you will need to remove before retrying the deductive step.

deduce_set(Base, Pred/Arity, Res) :-
    functor(P, Pred, Arity),

    % how to 'undo' this without a description?
    % retractall(base(_,_)),

    setof(F-A, M^(member(M, Base), functor(M, F, A)), Desc),
    maplist(retractdesc, Desc),

    maplist(assertz, Base),

    findall(P, P, All),
    append(Base, All, Res).

retractdesc(F-A) :-
    functor(P, F, A),
    retractall(P).

I'll would add also a description of Base elements, to know what to clear before running (of course could be obtained using setof(F-A,M^(member(M,Base),functor(M,F,A)),Desc) )

pred(A, B) :- base(A, B).
pred(A, C) :- base(A, B), pred(B, C).

test :-
    deduce_set([base(a,b), base(a,c), base(b,d), base(d, e)], pred/2, R),
    R = [base(a,b), base(a,c), base(b,d), base(d,e), pred(a,d), pred(a,e), pred(b,e)].

Note that test/0 will fail, because the return set doesn't match the expected list.

?- test.
base(a,b)
base(a,c)
base(b,d)
base(d,e)
pred(a,b)
pred(a,c)
pred(b,d)
pred(d,e)
pred(a,d)
pred(a,e)
pred(b,e)
false.

Generally, I would suggest to use Datalog for your task, as the informal description seems suspiciously similar. See DES for a 'free to use' and feature rich system.

Deducing facts from a set via a predicate by metaprogramming

1 Answers