Non-trivial Prolog find and replace

Question

So we can easily find and replace an atom with another atom in Prolog by doing something like:

replace([],A,B,[]).
replace([H|T],A,B,[B|Result]) :- 
    H=A, 
    replace(T,A,B,Result),!.
replace([H|T],A,B,[H|Result]) :- 
    replace(T,A,B,Result).

I'm sure there are other ways to do this too.

However, I want to do something more complicated in logic in computing. How would you do something like replacing conjunctions like conj(x,y) in a logical statement with just (x,y)? So it's like final and replace but not with atoms. So we could have something like reduce(conj(conj(x,y),z)). that I would want reducing to ((x,y),z).

This is a simple example with only conjunctions but this is what I want to happen in the case of conjunctions. If anyone's interested, this is all about descriptive logic and the tableau method.

What I'm confused about it how you go about doing a find and replace when the input isn't actually a list; it's a structure. I don't see how you can solve this without using the standard [H|T] trick with recursion and lists. Has anyone got any ideas?

Many thanks.

Answer 1

You can turn a general term into a list using =.., e.g.

?- conj(conj(x,y),z) =.. List.
List = [conj, conj(x, y), z].

Doing this recursively, you can flatten out the complete term.

A general predicate that changes certain nodes in the input term would look something like this:

change_term(NodeChanger, Term1, Term3) :-
    call(NodeChanger, Term1, Term2),
    change_term(NodeChanger, Term2, Term3),
    !.

change_term(NodeChanger, Term1, Term2) :-
    Term1 =.. [Functor | SubTerms1],
    change_termlist(NodeChanger, SubTerms1, SubTerms2),
    Term2 =.. [Functor | SubTerms2].


change_termlist(_, [], []).

change_termlist(NodeChanger, [Term1 | Terms1], [Term2 | Terms2]) :-
    change_term(NodeChanger, Term1, Term2),
    change_termlist(NodeChanger, Terms1, Terms2).

If you now define:

conj_changer(conj(X, Y), (X, Y)).

then you can define your reduce-predicate by:

reduce(Term1, Term2) :-
    change_term(conj_changer, Term1, Term2).

Usage:

?- reduce(conj(conj(x,y),z), ReducedTerm).
ReducedTerm = ((x, y), z).

You have to be careful though how you define the NodeChanger, certain definitions can make change_term/3 loop. Maybe somebody can improve on that.

Answer 2

Recall that a list is just a certain kind of structure, so you can easily translate your code to match any other structure as well. It may help you to use a cleaner representation for your data: Just as you use conj/2 to denote conjunctions, you could introduce a functor var/1 to denote variables:

reduce(conj(X0,Y0), (X,Y)) :-
        reduce(X0, X),
        reduce(Y0, Y).
reduce(var(X), X).

Example:

?- reduce(conj(conj(var(x),var(y)), var(z)), R).
R = ((x, y), z).

Answer 3

This is done in a straightforward way by writing a meta-interpreter, such as the following:

replace(V, V) :-
    % pass vars through 
    var(V), !.     
replace(A, A) :- 
    % pass atoms through 
    atomic(A), !.
replace([], []) :- 
    % pass empty lists through
    !.
replace([X|Xs], [Y|Ys]) :-
    % recursively enter non-empty lists
    !, 
    replace(X, Y),
    replace(Xs, Ys).
replace(conj(X,Y), (NX,NY)) :-
    % CUSTOM replacement clause for conj/2
    !, 
    replace(X, NX),
    replace(Y, NY).
replace(T, NT) :-
    % finally, recursively enter any as yet unmatched compound term
    T =.. [F|AL],
    replace(AL, NAL),
    NT =.. [F|NAL].

Note the second last clause, which serves to perform a replacement of your specific case of replacing conj/2 with conjunction, ,/2. You can add as many other clauses in the same manner as this to perform term replacement in general, because the rest of the definition (all other clauses of replace/2) here will recursively deconstruct any PROLOG term, as we've covered all the types; vars, atoms, and compound terms (including lists explicitly).

Executing this in your case gives us:

?- replace(conj(conj(x,y),z), NewTerm).
NewTerm = ((x, y), z).

Note that this definition will perform the correct replacement of any terms nested to arbitrary depth within another term.