Пролог: избегайте лишних точек выбора (недетерминизм) с оператором вырезания и без него

Во-первых, я прочитал все другие посты на SO, касающиеся использования разрезов в Прологе, и определенно вижу проблемы, связанные с их использованием. Однако для меня все еще есть некоторая неясность, и я хотел бы решить это раз и навсегда.

В приведенном ниже тривиальном примере мы рекурсивно перебираем список и проверяем, равен ли каждый 2-й элемент единице. При этом рекурсивный процесс может завершиться в одном из следующих базовых случаев: останется либо пустой список, либо список с одним элементом.

base([]).
base([_]).
base([_,H|T]) :- H =:= 1, base(T).

Когда выполнено:

?- time(base([1])).
   % 0 inferences, 0.000 CPU in 0.000 seconds (74% CPU, 0 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 99502 Lips)
   false.

?- time(base([3,1,3])).
   % 2 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 304044 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 122632 Lips)
   false.

В таких ситуациях я всегда использовал явный оператор обрезки во 2-м базовом случае (т. Е. Тот, который представляет один элемент, оставленный в списке), как показано ниже, чтобы покончить с избыточной точкой выбора.

base([]).
base([_]) :- !.
base([_,H|T]) :- H =:= 1, base(T).

Теперь мы получаем:

?- time(base([1])).
   % 1 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 49419 Lips)
   true.

?- time(base([3,1,3])).
   % 3 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 388500 Lips)
   true.

Я понимаю, что поведение этого сокращения зависит от положения правила и может рассматриваться как плохая практика.

Двигаясь дальше, можно изменить положение дел следующим образом:

base([_,H|T]) :- H =:= 1, base(T).
base([_]).
base([]).

что также избавит от избыточной точки выбора без использования вырезки, но, конечно, мы просто сместим точку выбора на запросы со списками с четным количеством цифр, как показано ниже:

?- time(base([3,1])).
% 2 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 99157 Lips)
true ;
% 2 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 96632 Lips)
false.

Так что это, очевидно, тоже не решение. Однако мы могли бы адаптировать этот порядок правил с помощью разреза, как показано ниже:

base([_,H|T]) :- H =:= 1, base(T), !.
base([_]).
base([]).

поскольку это фактически не оставило бы точек выбора. Глядя на некоторые запросы:

?- time(base([3])).
% 1 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 157679 Lips)
true.

?- time(base([3,1])).
% 3 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 138447 Lips)
true.

?- time(base([3,1,3])).
% 3 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 393649 Lips)
true.

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

base([]).
base([_]).
base([_,H|T]) :- H =:= 1, base(T), !.

мы все равно получили бы нежелательное поведение:

?- time(base([1])).
   % 0 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 0 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 119546 Lips)
   false.

В подобных сценариях я всегда использовал один разрез во втором базовом случае, так как я единственный, кто когда-либо просматривал свой код, и я к нему немного привык. Однако в одном из моих ответов на другой пост SO мне было сказано, что не рекомендуется использовать оператор cut и что я должен стараться избегать его как можно больше.

Это подводит меня к моему двустороннему вопросу:

  • Если разрез, независимо от положения правила, в котором он присутствует, меняет поведение, но не решение (как в приведенных выше примерах), все еще считается ли это плохой практикой?

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

Заранее спасибо!

Источник

2 ответа

Решение

Всегда старайся избегать !/0, Почти всегда, !/0 полностью разрушает декларативную семантику вашей программы.

Все, что может быть выражено сопоставлением с образцом, должно быть выражено сопоставлением с образцом. В вашем примере:

каждую секунду([]).
каждые_секунды ([_|Ls]):-
        every_second_(Ls).

каждую секунду_([]).
every_second_([1|Rest]):- every_second(Rest).

Как и в вашей нечистой версии, для оставленных вами примеров вообще не остается точек выбора:

? - каждые_ секунды ([1]).
правда.?- каждую секунду ([3,1]).
правда.?- каждую секунду ([3,1,3]).
правда.

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

? - каждую секунду (Ls).
Ls = [];
Ls = [_G774];
Ls = [_G774, 1];
Ls = [_G774, 1, _G780];
Ls = [_G774, 1, _G780, 1] .

Ни одна из опубликованных вами версий не может этого сделать из-за нечистых или не декларативных предикатов (!/0, (=:=)/2) ты используешь!

Рассуждая о списках, вы почти всегда можете использовать только сопоставление с образцом, чтобы различать случаи. Если это невозможно, используйте, например, if_/3 за логическую чистоту при сохранении приемлемой производительности.

Источник

Хитрость заключается в том, чтобы "прокрутить" количество правил в правиле:

base([]). 
base([_|Q]) :- base2(Q).

base2([]). 
base2([H|Q]) :- H =:= 1, base(Q).

Тем не менее, это плохое правило, чтобы сказать, что сокращения являются плохими. На самом деле, моим любимым будет:

base([]) :- !. 
base([_]) :- !. 
base([_,H|Q]) :- !, H =:= 1, base(Q).

Вещь об этом примере primes(++):

primes([5]).
primes([7]).
primes([11]).

против

primes([5]) :- !.
primes([7]) :- !.
primes([11]) :- !.
Источник
Другие вопросы по тегам