Finding all goals that have to hold

General
1

Hi!

I am trying to write a predicate that just gets all goals that have to hold for something to hold. This should be simple but i am stuck. For example, i have:

a:- b, c.
b:- d, e.
e:- f.

What i am trying to achieve is explains(a, X).

X = b
X = c
X = d
X = e
X = f

What i have so far doesn’t work:

a:- b, c.
b:- d, e.
e:- f.

explains(C, A):- clause(C, A).
explains(C, A):- clause(C, A1), A1 \= (_, _), explains(A1, A).
explains(C, A):- clause(C, A), A = (A1, A2), explains(A1, A11), explains(A2, A22), A = (A11, A22).
explains(C, A):- clause(C, A1), A1 = (A11, A22), A = (A11, A22).

OUTPUT:

?- explains(a, X).
X =  (b, c) ;
X =  (b, c).
2

I don’t plan to answer this but just want to point out a question that has me scratching my head if I were to try to answer this.

What does the comma between b, c mean?

Many people look at code or syntax and do not consider , as an operator but they should. If one considers it as an operator then what does it mean in the context of what you created. Is it a logical and as used in Prolog? Is it a representation of an edge on a graph? Is it a rule of inference connecting two subgoals?

1 Like
3

This should get you closer.


explains(Head,Bodies):-clause(Head,(C1,C2)),explains(C1,Fact1),explains(C2,Fact2 ),Bodies=(Fact1,Fact2).

explains(Head,Fact):-clause(Head,(Fact)).

explains(Head,Head):- \+clause(Head,_).
2 Likes
4

Great, thanks for you help!

2 Likes
5

For your specific problem, I think it could be converted into a graph problem.

:- dynamic edge/2.

flatten(X,L) :-
  atom(X), L=[X].
flatten((A,B),L) :-
  flatten(A,L1), flatten(B,L2), append(L1,L2,L).

explains((A,B)) :- 
  explains(A),  
  explains(B).
explains(Goal) :-
  clause(Goal, Body),
  flatten(Body, BodyL),
  foreach(member(X, BodyL), assert(edge(Goal,X))), 
  explains(Body).
explains(Goal) :-
  \+ clause(Goal, _).

a:- b, c.
b:- d, e.
e:- f.

path(X,Y) :- edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).

?- explains(a), path(a,X).
X = b ;
X = c ;
X = d ;
X = e ;
X = f ;
false.

This program firstly explains the clauses to a graph via explains, then solves the single-source reachability problem of the graph via path.

However, this approach is not ideal in general, because what if some one could write:

a:- b, c.
a:- b, e. % <--- add a new clause with the same head `a`
b:- d, e.
e:- f.

Note that now there are two heads of a. From the graph perspective, it will fork two worlds, but unfortunately SWI-Prolog DB doesn’t seem to support backtrackable assert. So we no longer use this graph approach. (See below).

1 Like
6

Thats interesting! Thank you :slight_smile:

7

I don’t know if this would fit into this problem, but transactional assertions seem to be supported

8

Yip, as well as the following, which realizes a backtrackable assert.

 assert(Term, Ref), undo(erase(Ref)).
3 Likes
9

I tried this approach. It’s very powerful and I think it is not easy to be implemented in other languages.

Thanks!

The following is the updated version of the graph approach above:

:- dynamic edge/2.

b_assertz(Term) :-
  assert(Term, Ref), undo(erase(Ref)).

flatten(X,L) :-
  atom(X), L=[X].
flatten((A,B),L) :-
  flatten(A,L1), flatten(B,L2), append(L1,L2,L).

explains((A,B)) :- 
  explains(A),  
  explains(B).
explains(Goal) :-
  clause(Goal, Body),
  flatten(Body, BodyL),
  foreach(member(X, BodyL), b_assertz(edge(Goal,X))),
  explains(Body).
explains(Goal) :-
  \+ clause(Goal, _).

path(X,Y) :- edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).

Now I can deal with the “different worlds” problem:

a:- b, c.
a:- b, e.
b:- d, e.
e:- f.

?- explains(a), setof(X, path(a,X), Ls).
Ls = [b,c,d,e,f] ;
Ls = [b,d,e,f] ;
false.

There is only minor changes to the old code. Just change assertz to b_assertz.

BTW, I think this approach could even solve circular dependency problem if turn on tabling, but I haven’t tried it yet :slightly_smiling_face:.

10

Keeping track of a path during a derivation is much easier and faster using a backtrackable global variable as implemented by b_setval/2. For example:

push(Term) :-
     b_getval(path, P0),
     b_setval(path, [Term|P0]).

Before entering set the initial path to [] using b_setval(path, []).

P.s. your flatten/2 looks a lot like comma_list/2 from library(prolog_code).

1 Like
11

You are right.

For this problem, the graph approach seems overkill.