Пролог Использование порезов

Question

Я переписываю следующую функцию в Прологе:

V1:

f(X,Y):- X < 2, Y is X+1.
f(X,3):- 2 =< X, X < 5.
f(X,Y):- 5 =< X, Y is 8-X.

Как V2:

f(X,Y) :-
    X < 2,
    Y is X + 1. 
f(X,Y) :-
    X >= 2,
    X < 5,
    Y is 3.
f(X,Y) :-
    X >= 5,
    Y is 8-X.

Затем я хотел поэкспериментировать с порезами. Для зеленых нарезок (V3):

f(X,Y) :-
    X < 2, !,
    Y is X + 1.
f(X,Y) :-
    X >= 2,
    X < 5, !,
    Y is 3.
f(X,Y) :-
    X >= 5,
    Y is 8-X.

Для красных порезов (V4):

f(X,Y) :-
    X < 2, !,
    Y is X + 1.
f(X,Y) :-
    X < 5, !,
    Y is 3.
f(X,Y) :-
    Y is 8-X.

Тем не менее, я не понимаю их преимущества, так как удаление разрезов позволит такое же поведение кода... Любая помощь?

Answer 1

Все ваши версии V1..V4 обсервационно эквивалентны, так что вы правильно поняли. Тем не менее, есть различия.

Избегайте лишних точек выбора

Во многих реализациях V1 и V2 могут быть особенно менее эффективными, поскольку внутренне они "оставляют открытой точку выбора". Это так, потому что такие прологи не смотрят дальше других правил. Итак, каждая цель f(1,X) потребляет немного памяти, которая может быть освобождена только при возврате (или использовании!). Вот простой способ попробовать это самостоятельно:

loop(Goal) :-
   Goal,
   loop(Goal).

Вот что я получаю в SWI:

?- time(loop(f1(1,2))).
% 5,991,554 inferences, 81.282 CPU in 81.443 seconds (100% CPU, 73713 Lips)
ERROR: Out of local stack
?- time(loop(f2(1,2))).
% 5,991,553 inferences, 85.032 CPU in 85.212 seconds (100% CPU, 70462 Lips)
ERROR: Out of local stack

В то время как V3 и V4, кажется, работают бесконечно - по крайней мере, намного дольше, чем 85-е годы. Подобные эксперименты забавны для очень маленьких программ, но не очень практичны для больших. К счастью, во многих прологах есть простой способ определить, выполняется ли запрос определенным образом. Чтобы увидеть, если ваша система делает это, введите:

?- X = 1.
X = 1.

Для ваших вариаций:

?- f1(1,2).
true ;        % <== Prolog asked for another answer
false.        % <== only to conclude that there is none.

?- f2(1,2).
true ;        % same again
false.

?- f3(1,2).
true.         % <== Prolog knows there will be no further answer

?- f4(1,2).
true.

Избегать пересчетов - делать порезы красным

В то время как V3 избегает лишних точек выбора, V4 теперь даже избегает лишних вычислений. Так что это должно быть наиболее эффективным. Но это происходит за счет установления порядка пунктов.

---

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

1. Неперекрывающиеся условия. Это должно быть очевидно для вас.

2. Безопасное тестирование экземпляров. Это далеко не очевидно. Обратите внимание, что цель X < 2 имеет неявный тест для правильного создания экземпляра! Выдает ошибку инстанции X быть необоснованной переменной. Именно из-за этого самого теста разрез в V3 оказался зеленым. Без этого тестирования это был бы красный порез.

Также обратите внимание, что V1 и V2 не будут эквивалентны, если второе правило будет одним! Для цели f(X,5). потерпит неудачу в V1, но приведет к ошибке в V2.

Answer 2

Как вы заметили, первая версия показывает зеленые срезы, а вторая - красные. Не обязательно, чтобы вы почувствовали разницу между этими двумя версиями.

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

б) перетасовка правил не должна изменять поведение кода в случае зеленых сокращений, и это верно для первого кода. Но во втором коде, если вы поместите второе предложение перед первым, то поведение изменится: f(0,3) верно, но изначально оно было ложным. Поэтому вы почувствуете разницу, если будете перетасовывать правила.

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