CODEWITHSUNDEEP
prolog
joelawe
joelawe

Reputation: 43

Prolog program to return atoms in a proposition formula

I am a newbie to prolog and am trying to write a program which returns the atoms in a well formed propositional formula. For instance the query ats(and(q, imp(or(p, q), neg(p))), As). should return [p,q] for As. Below is my code which returns the formula as As. I dont know what to do to split the single F in ats in the F1 and F2 in wff so wff/2 never gets called. Please I need help to proceed from here. Thanks.

CODE

logical_atom( A ) :-
       atom( A ),     
       atom_codes( A, [AH|_] ),
       AH >= 97,
       AH =< 122.

wff(A):- ground(A),
         logical_atom(A).

wff(neg(A)) :- ground(A),wff(A).

wff(or(F1,F2)) :-
    wff(F1),
    wff(F2).
wff(and(F1,F2)) :-
    wff(F1),
    wff(F2).

wff(imp(F1,F2)) :-
    wff(F1),
    wff(F2).
ats(F, As):- wff(F), setof(F, logical_atom(F), As).

Upvotes: 4

Views: 1056

Answers (3)

Nicholas Carey
Nicholas Carey

Reputation: 74227

This should do what you want. It extracts the unique set of atoms found in any arbitrary prolog term.

I'll leave it up to you, though, to determine what constitutes a "well formed propositional formula", as you put it in your problem statement (You might want to take a look at DCG's for parsing and validation).

The bulk of the work is done by this "worker predicate". It simply extracts, one at a time via backtracking, any atoms found in the parse tree and discards anything else:

expression_atom( [T|_] , T ) :-  % Case #1: head of list is an ordinary atom
  atom(T) ,                      % - verify that the head of the list is an atom.
  T \= []                        % - and not an empty list
  .                              % 
expression_atom( [T|_] , A ) :-  % Case #2: head of listl is a compound term
  compound(T) ,                  % - verify that the head of the list is a compound term
  T =.. [_|Ts] ,                 % - decompose it, discarding the functor and keeping the arguments
  expression_atom(Ts,A)          % - recurse down on the term's arguments
  .                              %
expression_atom( [_|Ts] , A ) :- % Finally, on backtracking,
  expression_atom(Ts,A)          % - we simply discard the head and recurse down on the tail
  .                              %

Then, at the top level, we have this simple predicate that accepts any [compound] prolog term and extracts the unique set of atoms found within by the worker predicate via setof/3:

expression_atoms( T , As ) :-       % To get the set of unique atoms in an arbitrary term,
  compound(T) ,                     % - ensure that's its a compound term,
  T =.. [_|Ts] ,                    % - decompose it, discarding the functor and keeping the arguments
  setof(A,expression_atom(Ts,A),As) % - invoke the worker predicate via setof/3
  .                                 % Easy!

Upvotes: 1

Daniel Lyons
Daniel Lyons

Reputation: 22803

I'd approach this problem using the "univ" operator =../2 and explicit recursion. Note that this solution will not generate and is not "logically correct" in that it will not process a structure with holes generously, so it will produce different results if conditions are reordered. Please see @mat's comments below.

I'm using cuts instead of if statements for personal aesthetics; you would certainly find better performance with a large explicit conditional tree. I'm not sure you'd want a predicate such as this to generate in the first place.

Univ is handy because it lets you treat Prolog terms similarly to how you would treat a complex s-expression in Lisp: it converts terms to lists of atoms. This lets you traverse Prolog terms as lists, which is handy if you aren't sure exactly what you'll be processing. It saves me from having to look for your boolean operators explicitly.

atoms_of_prop(Prop, Atoms) :-
    % discard the head of the term ('and', 'imp', etc.)
    Prop =.. [_|PropItems],

    collect_atoms(PropItems, AtomsUnsorted),

    % sorting makes the list unique in Prolog
    sort(AtomsUnsorted, Atoms).

The helper predicate collect_atoms/2 processes lists of terms (univ only dismantles the outermost layer) and is mutually recursive with atoms_of_prop/2 when it finds terms. If it finds atoms, it just adds them to the result.

% base case
collect_atoms([], []).

% handle atoms
collect_atoms([A|Ps], [A|Rest]) :-
    % you could replace the next test with logical_atom/1
    atom(A), !,
    collect_atoms(Ps, Rest).

% handle terms
collect_atoms([P|Ps], Rest) :-
    compound(P), !,                % compound/1 tests for terms
    atoms_of_prop(P, PAtoms),
    collect_atoms(Ps, PsAtoms),
    append(PAtoms, PsAtoms, Rest).

% ignore everything else
collect_atoms([_|Ps], Rest) :- atoms_of_prop(Ps, Rest).

This works for your example as-is:

?- atoms_of_prop(ats(and(q, imp(or(p, q), neg(p))), As), Atoms).
Atoms = [p, q].

Upvotes: 1

mat
mat

Reputation: 40768

First, consider using a cleaner representation: Currently, you cannot distinguish atoms by a common functor. So, wrap them for example in a(Atom).

Second, use a DCG to describe the relation between a well-formed formula and the list of its atoms, like in:

wff_atoms(a(A))       --> [A].
wff_atoms(neg(F))     --> wff_atoms(F).
wff_atoms(or(F1,F2))  --> wff_atoms(F1), wff_atoms(F2).
wff_atoms(and(F1,F2)) --> wff_atoms(F1), wff_atoms(F2).
wff_atoms(imp(F1,F2)) --> wff_atoms(F1), wff_atoms(F2).

Example query and its result:

?- phrase(wff_atoms(and(a(q), imp(or(a(p), a(q)), neg(a(p))))), As).
As = [q, p, q, p].

Upvotes: 4

Related Questions