Уточнение термина равенство / неравенство
Программы на чистом прологе, которые четко различают равенство и неравенство терминов, страдают от неэффективности исполнения; даже когда все условия релевантны.
Недавний пример SO - это ответ. Все ответы и все ошибки верны в этом определении. Рассматривать:
?- Es = [E1,E2], occurrences(E, Es, Fs).
Es = Fs, Fs = [E, E],
E1 = E2, E2 = E ;
Es = [E, E2],
E1 = E,
Fs = [E],
dif(E, E2) ;
Es = [E1, E],
E2 = E,
Fs = [E],
dif(E, E1) ;
Es = [E1, E2],
Fs = [],
dif(E, E1),
dif(E, E2).
Хотя программа безупречна с декларативной точки зрения, ее прямое выполнение в современных системах, таких как B, SICStus, SWI, YAP, излишне неэффективно. Для достижения следующей цели точка выбора остается открытой для каждого элемента списка.
? - вхождения (a,[a,a,a,a,a],M). М = [а, а, а, а, а] ; ложь
Это можно наблюдать, используя достаточно большой список a S следующим образом. Возможно, вам придется адаптировать I такой, что список все еще может быть представлен; в SWI это будет означать, что
1 месяц I должно быть достаточно маленьким, чтобы предотвратить ошибку ресурса для глобального стека, как показано ниже:
? - 24 = I, N равно 2^I, длина (L,N), список карт (=(a),L). ОШИБКА: вне глобального стека
2до I должен быть достаточно большим, чтобы вызвать ошибку ресурса для локального стека:
? - 22 = I, N равно 2^I, длина (L,N), список карт (=(a),L), (длина = нормально; вхождения (a,L,M)). Я = 22, N = 4194304, L = [a, a, a, a, a, a, a, a, a|...], Длина = хорошо; ОШИБКА: вне локального стека
Чтобы преодолеть эту проблему и сохранить хорошие декларативные свойства, необходим некоторый предикат сравнения.
Как определить предикат сравнения?
Вот такое возможное определение:
равенство равное (X, X, правда). равенство (X, Y, ложь):- диф (X, Y).
Редактировать: Возможно, порядок аргументов должен быть обратным, аналогично встроенному в ISO compare/3(ссылки только на черновик).
Эффективная реализация этого будет обрабатывать быстрые детерминированные случаи в первую очередь:
равенство равных (X, Y, R):- X == Y,!, R = true. равенство равное (X, Y, R):-?=(X, Y),!, R = ложь. % синтаксически отличается равенство равных (X, Y, R):- X \= Y,!, R = ложь. % семантически отличается равенство равное (X, X, правда). равенство (X, Y, ложь):- диф (X, Y).
Изменить: мне не ясно, или нет X \= Y является подходящим охранником при наличии ограничений. Без ограничений, ?=(X, Y) или же X \= Y подобные.
пример
Как подсказывает @user1638891, вот пример того, как можно использовать такой примитив. Оригинальный код по матам был:
occurrences_mats(_, [], []).
occurrences_mats(X, [X|Ls], [X|Rest]) :-
occurrences_mats(X, Ls, Rest).
occurrences_mats(X, [L|Ls], Rest) :-
dif(X, L),
occurrences_mats(X, Ls, Rest).
Который может быть переписан что-то вроде:
occurrences(_, [], []).
occurrences(E, [X|Xs], Ys0) :-
reified_equality(Bool, E, X),
( Bool == true -> Ys0 = [X|Ys] ; Ys0 = Ys ),
% ( Bool = true, Ys0 = [X|Ys] ; Bool = true, Ys0 = Ys ),
occurrences(E, Xs, Ys).
reified_equality(R, X, Y) :- X == Y, !, R = true.
reified_equality(R, X, Y) :- ?=(X, Y), !, R = false.
reified_equality(true, X, X).
reified_equality(false, X, Y) :-
dif(X, Y).
Обратите внимание, что индексирование второго аргумента SWI активируется только после ввода запроса, например occurrences(_,[],_), Кроме того, SWI необходим по своей сути немонотонный if-then-else, поскольку он не индексируется на (;)/2 Дизъюнкция. SICStus делает это, но имеет индексирование только первого аргумента. Таким образом, он оставляет одну (1) точку выбора открытой (в конце []).
6 ответов
Ну, с одной стороны, имя должно быть более декларативным, как equality_truth/2,
Следующий код основан на if_/3 а также (=)/3 (ака equal_truth/3), как реализовано @false в объединении Пролог для AUBUC:
=(X, Y, R) :- X == Y, !, R = true.
=(X, Y, R) :- ?=(X, Y), !, R = false. % syntactically different
=(X, Y, R) :- X \= Y, !, R = false. % semantically different
=(X, Y, R) :- R == true, !, X = Y.
=(X, X, true).
=(X, Y, false) :-
dif(X, Y).
if_(C_1, Then_0, Else_0) :-
call(C_1, Truth),
functor(Truth,_,0), % safety check
( Truth == true -> Then_0 ; Truth == false, Else_0 ).
По сравнению с occurrences/3вспомогательный occurrences_aux/3 использует другой порядок аргументов, который передает список Es в качестве первого аргумента, который может включить индексацию первого аргумента:
occurrences_aux([], _, []).
occurrences_aux([X|Xs], E, Ys0) :-
if_(E = X, Ys0 = [X|Ys], Ys0 = Ys),
occurrences_aux(Xs, E, Ys).
Как указывает @migfilg, цель Fs=[1,2], occurrences_aux(Es,E,Fs) должен потерпеть неудачу, поскольку это логически неверно:occurrences_aux(_,E,Fs) утверждает, что все элементы в Fs равны E, Однако сам по себе, occurrences_aux/3 не заканчивается в подобных случаях.
Мы можем использовать вспомогательный предикат allEqual_to__lazy/2 улучшить поведение завершения:
allEqual_to__lazy(Xs,E) :-
freeze(Xs, allEqual_to__lazy_aux(Xs,E)).
allEqual_to__lazy_aux([],_).
allEqual_to__lazy_aux([E|Es],E) :-
allEqual_to__lazy(Es,E).
Со всеми вспомогательными предикатами на месте, давайте определимся occurrences/3:
occurrences(E,Es,Fs) :-
allEqual_to__lazy(Fs,E), % enforce redundant equality constraint lazily
occurrences_aux(Es,E,Fs). % flip args to enable first argument indexing
Давайте сделаем несколько запросов:
?- occurrences(E,Es,Fs). % first, the most general query
Es = Fs, Fs = [] ;
Es = Fs, Fs = [E] ;
Es = Fs, Fs = [E,E] ;
Es = Fs, Fs = [E,E,E] ;
Es = Fs, Fs = [E,E,E,E] ... % will never terminate universally, but ...
% that's ok: solution set size is infinite
?- Fs = [1,2], occurrences(E,Es,Fs).
false. % terminates thanks to allEqual_to__lazy/2
?- occurrences(E,[1,2,3,1,2,3,1],Fs).
Fs = [1,1,1], E=1 ;
Fs = [2,2], E=2 ;
Fs = [3,3], E=3 ;
Fs = [], dif(E,1), dif(E,2), dif(E,3).
?- occurrences(1,[1,2,3,1,2,3,1],Fs).
Fs = [1,1,1]. % succeeds deterministically
?- Es = [E1,E2], occurrences(E,Es,Fs).
Es = [E, E], Fs = [E,E], E1=E , E2=E ;
Es = [E, E2], Fs = [E], E1=E , dif(E2,E) ;
Es = [E1, E], Fs = [E], dif(E1,E), E2=E ;
Es = [E1,E2], Fs = [], dif(E1,E), dif(E2,E).
?- occurrences(1,[E1,1,2,1,E2],Fs).
E1=1 , E2=1 , Fs = [1,1,1,1] ;
E1=1 , dif(E2,1), Fs = [1,1,1] ;
dif(E1,1), E2=1 , Fs = [1,1,1] ;
dif(E1,1), dif(E2,1), Fs = [1,1].
Редактировать 2015-04-27
Еще несколько запросов для тестирования, если occurrences/3 универсальный заканчивается в определенных случаях:
?- occurrences(1,L,[1,2]).
false.
?- L = [_|_],occurrences(1,L,[1,2]).
false.
?- L = [X|X],occurrences(1,L,[1,2]).
false.
?- L = [L|L],occurrences(1,L,[1,2]).
false.
Кажется, лучше всего вызывать этот предикат с теми же аргументами (=)/3, Таким образом, условия, такие как if_/3 теперь гораздо более читабельны. И использовать скорее суффикс _t на месте _truth:
memberd_t(_X, [], false).
memberd_t(X, [Y|Ys], Truth) :-
if_( X = Y, Truth=true, memberd_t(X, Ys, Truth) ).
Который раньше был:
memberd_truth(_X, [], false).
memberd_truth(X, [Y|Ys], Truth) :-
if_( equal_truth(X, Y), Truth=true, memberd_truth(X, Ys, Truth) ).
ОБНОВЛЕНИЕ: Этот ответ был заменен моим 18 апреля. Я не предлагаю, чтобы это было удалено из-за комментариев ниже.
Мой предыдущий ответ был неверным. Следующий пример работает с контрольным примером, о котором идет речь, и у реализации есть желаемая возможность избежать лишних точек выбора. Я предполагаю, что верхний режим предиката будет?,+,? хотя другие режимы могут быть легко реализованы.
У программы всего 4 предложения: список во втором аргументе посещается, и для каждого члена есть две возможности: он либо объединяется с первым аргументом верхнего предиката, либо отличается от него, в этом случае dif применяется ограничение:
occurrences(X, L, Os) :- occs(L, X, Os).
occs([],_,[]).
occs([X|R], X, [X|ROs]) :- occs(R, X, ROs).
occs([X|R], Y, ROs) :- dif(Y, X), occs(R, Y, ROs).
Примеры прогонов с использованием YAP:
?- occurrences(1,[E1,1,2,1,E2],Fs).
E1 = E2 = 1,
Fs = [1,1,1,1] ? ;
E1 = 1,
Fs = [1,1,1],
dif(1,E2) ? ;
E2 = 1,
Fs = [1,1,1],
dif(1,E1) ? ;
Fs = [1,1],
dif(1,E1),
dif(1,E2) ? ;
no
?- occurrences(E,[E1,E2],Fs).
E = E1 = E2,
Fs = [E,E] ? ;
E = E1,
Fs = [E],
dif(E,E2) ? ;
E = E2,
Fs = [E],
dif(E,E1) ? ;
Fs = [],
dif(E,E1),
dif(E,E2) ? ;
no
Вот еще более короткая логически-чистая реализация occurrences/3,
Мы строим это на мета-предикате tfilter/3Утвержденный термин равенства предиката (=)/3 и сопрограмма allEqual_to__lazy/2 (определено в моем предыдущем ответе на этот вопрос):
occurrences(E,Xs,Es) :-
allEqual_to__lazy(Es,E),
tfilter(=(E),Xs,Es).
Готово! Чтобы упростить сравнение, мы повторяем те же самые запросы, которые я использовал в моем предыдущем ответе:
?- Fs = [1,2], occurrences(E,Es,Fs).
false.
?- occurrences(E,[1,2,3,1,2,3,1],Fs).
Fs = [1,1,1], E=1 ;
Fs = [2,2], E=2 ;
Fs = [3,3], E=3 ;
Fs = [], dif(E,1), dif(E,2), dif(E,3).
?- occurrences(1,[1,2,3,1,2,3,1],Fs).
Fs = [1,1,1].
?- Es = [E1,E2], occurrences(E,Es,Fs).
Es = [E, E ], Fs = [E,E], E1=E , E2=E ;
Es = [E, E2], Fs = [E], E1=E , dif(E2,E) ;
Es = [E1,E ], Fs = [E], dif(E1,E), E2=E ;
Es = [E1,E2], Fs = [], dif(E1,E), dif(E2,E).
?- occurrences(1,[E1,1,2,1,E2],Fs).
E1=1 , E2=1 , Fs = [1,1,1,1] ;
E1=1 , dif(E2,1), Fs = [1,1,1] ;
dif(E1,1), E2=1 , Fs = [1,1,1] ;
dif(E1,1), dif(E2,1), Fs = [1,1].
?- occurrences(1,L,[1,2]).
false.
?- L = [_|_],occurrences(1,L,[1,2]).
false.
?- L = [X|X],occurrences(1,L,[1,2]).
false.
?- L = [L|L],occurrences(1,L,[1,2]).
false.
Наконец, самый общий запрос:
?- occurrences(E,Es,Fs).
Es = Fs, Fs = [] ;
Es = Fs, Fs = [E] ;
Es = Fs, Fs = [E,E] ;
Es = Fs, Fs = [E,E,E] % ... and so on ad infinitum ...
Мы получаем одинаковые ответы.
Реализация occurrences/3 ниже основано на моих предыдущих ответах, а именно на извлечении выгоды из механизма индексации предложений по 1-му аргументу, чтобы избежать некоторых точек выбора, и затрагивает все вопросы, которые были подняты.
Более того, он до сих пор справляется с проблемой во всех подчиненных реализациях, включая ту, о которой говорится в вопросе, а именно, что все они входят в бесконечный цикл, когда в запросе 2 первых аргумента свободны, а 3 - список с различными базовыми элементами. Конечно, правильное поведение должно провалиться.
Использование предиката сравнения
Я думаю, что для того, чтобы избежать неиспользованных точек выбора и сохранить хорошую степень декларативности реализации, нет необходимости в предикате сравнения, как предложенный в вопросе, но я согласен, что это может быть вопросом вкуса или склонности.
Реализация
В этом порядке рассматриваются три исключительных случая: если 2-й аргумент является наземным, то его посещают рекурсивно; в противном случае, если третий аргумент является наземным, он проверяется, а затем посещается рекурсивно; в противном случае подходящие списки создаются для 2-го и 3-го аргументов.
occurrences(X, L, Os) :-
( nonvar(L) -> occs(L, X, Os) ;
( nonvar(Os) -> check(Os, X), glist(Os, X, L) ; v_occs(L, X, Os) ) ).
Второй аргумент "визит на землю" имеет три случая, когда список не пуст: если его голова и X выше как наземный и разборный X находится в заголовке результирующего списка случаев, и другой альтернативы нет; в противном случае есть две альтернативы с X отличаться от головы или объединяться с ней:
occs([],_,[]).
occs([X|R], Y, ROs) :-
( X==Y -> ROs=[X|Rr] ; foccs(X, Y, ROs, Rr) ), occs(R, Y, Rr).
foccs(X, Y, ROs, ROs) :- dif(X, Y).
foccs(X, X, [X|ROs], ROs).
Проверка основания 3-й аргумент состоит в том, чтобы убедиться, что все его члены объединены с X, В принципе, эта проверка может быть выполнена glist/3 но таким образом неиспользуемые точки выбора избегаются.
check([], _).
check([X|R], X) :- check(R, X).
Визит к основному 3-му аргументу со свободным 2-м аргументом должен завершиться добавлением переменных, отличных от X в сгенерированный список. На каждом шаге рекурсии есть две альтернативы: текущий заголовок сгенерированного списка является текущим заголовком посещенного списка, который должен быть совместим с X или свободная переменная отличается от X, Это только теоретическое описание, потому что на самом деле существует бесконечное количество решений, и 3-е предложение никогда не будет достигнуто, когда заголовок списка является переменной. Поэтому третий пункт ниже закомментирован, чтобы избежать неиспользуемых точек выбора.
glist([], X, L) :- gdlist(L,X).
glist([X|R], X, [X|Rr]) :- glist(R, X, Rr).
%% glist([X|R], Y, [Y|Rr]) :- dif(X, Y), glist([X|R], Y, Rr).
gdlist([], _).
gdlist([Y|R], X) :- dif(X, Y), gdlist(R, X).
Наконец, случай, когда все аргументы свободны, рассматривается аналогично предыдущему случаю и имеет аналогичную проблему с некоторыми шаблонами решений, которые на практике не генерируются:
v_occs([], _, []).
v_occs([X|R], X, [X|ROs]) :- v_occs(R, X, ROs).
%% v_occs([X|R], Y, ROs) :- dif(Y, X), v_occs(R, Y, ROs). % never used
Образцы тестов
?- occurrences(1,[E1,1,2,1,E2],Fs).
Fs = [1,1],
dif(E1,1),
dif(E2,1) ? ;
E2 = 1,
Fs = [1,1,1],
dif(E1,1) ? ;
E1 = 1,
Fs = [1,1,1],
dif(E2,1) ? ;
E1 = E2 = 1,
Fs = [1,1,1,1] ? ;
no
?- occurrences(1,L,[1,2]).
no
?- occurrences(1,L,[1,E,1]).
E = 1,
L = [1,1,1] ? ;
E = 1,
L = [1,1,1,_A],
dif(1,_A) ? ;
E = 1,
L = [1,1,1,_A,_B],
dif(1,_A),
dif(1,_B) ? ;
...