# Finding all goals that have to hold

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

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

This should get you closer.

``````

``````
1 Like

Great, thanks for you help!

1 Like

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

Thats interesting! Thank you

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

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

`` assert(Term, Ref), undo(erase(Ref)).``
2 Likes

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 .

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

You are right.

For this problem, the graph approach seems overkill.