Нетривиальный Пролог найти и заменить

Question

Таким образом, мы можем легко найти и заменить атом другим атомом в Прологе, выполнив что-то вроде:

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

Я уверен, что есть и другие способы сделать это.

Однако я хочу сделать что-то более сложное в логике вычислений.Как бы вы сделали что-то вроде замены конъюнкций типа conj(x,y) в логическом выражении просто (x, y)?Так что это как финал и заменить, но не с атомами.Таким образом, у нас может быть что-то вроде reduce(conj(conj(x,y),z))., которое я бы хотел уменьшить до ((x,y),z).

Это простой пример только с конъюнкциями, но я хочу, чтобы это произошло в случае союзов.Если кому-то интересно, это все о дескриптивной логике и методе таблиц.

Что меня смущает в том, как вы делаете поиск и замену, когда входные данные на самом деле не являются списком;это структура.Я не понимаю, как вы можете решить эту проблему, не используя стандартный трюк [H|T] с рекурсией и списками.У кого-нибудь есть идеи?

Большое спасибо.

Answer 1

Это делается простым путём написания мета-интерпретатора, например:

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].

Обратите внимание на второе последнее предложение, которое служит для замены вашего конкретного случая замены conj/2 с соединением, ,/2.Вы можете добавить столько же других предложений тем же способом, что и здесь, чтобы выполнить замену термина в целом, потому что остальная часть определения (все остальные пункты replace/2) здесь будет рекурсивно деконструировать любой термин PROLOG, какмы охватили все типы;переменные, атомы и составные термины (включая списки явно).

Выполнение этого в вашем случае дает нам:

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

Обратите внимание, что это определение выполнит правильную замену любых терминов, вложенных впроизвольная глубина в пределах другого термина.

Answer 2

Напомним, что список - это просто определенный вид структуры, поэтому вы можете легко перевести свой код, чтобы он соответствовал любой другой структуре. Это может помочь вам использовать более чистое представление для ваших данных: так же, как вы используете Con / 2 для обозначения конъюнкций, вы можете ввести функтор var / 1 для обозначения переменных:

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

Пример:

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

Answer 3

Вы можете превратить общий термин в список, используя =.., например,

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

Делая это рекурсивно, вы можете сгладить полный термин.

Общий предикат, который изменяетсянекоторые узлы во входном члене будут выглядеть примерно так:

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

Если вы сейчас определите:

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

, тогда вы можете определить предикат Reduce следующим образом:

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

Использование:

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

Вы должны быть осторожны, хотя, как вы определяете NodeChanger, некоторые определения могут сделать цикл change_term/3.Может быть, кто-то может улучшить это.