Какая разница в исполнении, если вырез '!' настоящее?

Каков эффект "!"

Вырез сокращает пространство поиска. То есть в чистой и монотонной программе разрез удалит некоторые решения или ответы. Пока они избыточны, это нормально. Звучит так невинно и полезно, не правда ли? Давайте посмотрим!

^{_{И, если я забыл, использование [E,Nr] для обозначения пар довольно необычно, лучше используйте пару E-Nr.}}

Теперь мы сравним counter_cut/2 и counter_sans/2.

| ?- counter_cut([a,a],Xs).
     Xs = [[a,2]].

| ?- counter_sans([a,a],Xs).
     Xs = [[a, 2]]
  ;  Xs = [[a, 1], [a, 1]].     % <<< surprise !!!

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

| ?- counter_cut([a,B],Xs).
     B = a,
     Xs = [[a, 2]].

| ?- counter_sans([a,B],Xs).
     B = a,
     Xs = [[a, 2]]
  ;  Xs = [[a, 1], [B, 1]].

Опять же, _sans болтливее, и на этот раз даже немного правее; для последнего ответа включает B = b. Другими словами,

| ?- counter_cut([a,B], Xs), B = b.
     fails.              % incomplete !

| ?- counter_sans([a,B], Xs), B = b.
     B = b,
     Xs = [[a,1],[b,1]].

Так что иногда _cut версия лучше, а иногда _sans. Или, говоря более прямо: и то, и другое как-то не так, но _sans-версия, по крайней мере, включает все решения.

Вот «очищенная» версия, которая просто переписывает последнее правило в двух разных случаях: один для конца списка, а другой для другого, другого элемента.

counter_pure([],[]).
counter_pure([H|T],[[H,C1]|R]) :- counter_pure(T,[[H,C]|R]), C1 is C+1.
counter_pure([H],[[H,1]]).
counter_pure([H,D|T],[[H,1]|R]) :- dif(H,D), counter_pure([D|T],R).

С точки зрения эффективности это не слишком известно.

Вот тестовый пример эффективности для системы с рациональным объединением деревьев:

?- Es = [e|Es], counter(Es, Dict).
resource_error(stack).

Вместо этого реализация должна плавно зацикливаться, по крайней мере, до конца этой вселенной. Строго говоря, этот запрос должен выдавать ошибку ресурса, но только после того, как он подсчитал до числа, значительно превышающего 10^100000000.

Вот мое чистое и, надеюсь, эффективное решение:

counter([X|L], C):- counter(L, X, 1, C).

counter([],X, Cnt, [[X,Cnt]]).
counter([Y|L], X, Cnt, [[X,Cnt]|C]):-
  dif(X, Y),
  counter(L, Y, 1, C).
counter([X|L],X, Cnt, [[X,XCnt]|C]):-
  Cnt1 #= Cnt+1,
  Cnt1 #=< XCnt,
  counter(L, X, Cnt1, [[X,XCnt]|C]).

Использование if_3, предложенное @false:

counter([X|L], C):- counter(L, X, 1, C).

counter([],X, Cnt, [[X,Cnt]]).
counter([Y|L], X, Cnt, [[X,XCnt]|C]):-
  if_(X=Y,
    (
      Cnt1 #= Cnt+1,
      Cnt1 #=< XCnt,
      counter(L, X, Cnt1, [[X,XCnt]|C])
    ),
    (
      XCnt=Cnt,
      counter(L, Y, 1, C)
    )
  ).

Оператор вырезания ! фиксирует текущий путь деривации, отсекая все точки выбора. Учитывая некоторые факты

fact(a).
fact(b).

можно сравнить ответы с вырезом и без:

?- fact(X).
X = a ;
X = b.

?- fact(X), !.
X = a.

Как видите, общий запрос теперь сообщает только о первом успехе. Тем не менее, запрос

?- fact(b), !.
true.

удается. Это означает, что разрез нарушает интерпретацию , как логической конъюнкции:

?- X = b, fact(X), !.
X = b.

?- fact(X), !, X=b.
false.

но, исходя из нашего понимания конъюнкции, A ∧ B должно выполняться точно тогда, когда выполняется B ∧ A. Так зачем вообще это делать?

• Эффективность: сокращения можно использовать так, что они изменяют только свойства выполнения, но не ответы предиката. Эти так называемые «зеленые сокращения» описаны, например, в книге Ричарда О'Кифа Craft of Prolog. Как показано выше, поддерживать правильность предиката с отсечением намного сложнее, чем без него, но очевидно, что правильность должна превалировать над эффективностью.

  Похоже, ваша проблема была зеленой, но я не уверен на 100%, если ответы не изменились.

• Отрицание: логическое отрицание в соответствии с предположением о закрытом мире выражается с помощью cut. Вы можете определить neg(X) как:

  neg(X) :-
    call(X),
    !,
    false.
  neg(_) :-
    true.
  

  Итак, если call(X) успешно, мы отсекаем точку выбора для второго правила и получаем false. В противном случае ничего не вырезается и мы выводим истину. Имейте в виду, что это не является отрицанием в классической логике и что оно страдает от нелогического эффекта отсечения. Предположим, вы определили предикат land/1 как один из континентов:

  land(africa).
  land(america).
  land(antarctica).
  land(asia).
  land(australia).
  land(europe).
  

  а затем определить воду как все, что не находится на суше:

  water(X) :-
    neg(land(X)).
  

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

  ?- water(pacific).
  true.
  
  ?- water(africa).
  false.
  

  Но вы также можете получить:

  ?- water(space).
  true.
  

  что не должно держать. В частности, в классической логике:

  land(africa) ∧
  land(america) ∧
  land(antarctica) ∧
  land(asia) ∧
  land(australia) ∧
  land(europe) → ¬ land(space).
  

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

Вот моя попытка использовать if_/3:

counter([], []).
counter([H|T], [[H,C]|OutT] ):-
         if_( 
               T=[], 
               (C = 1,OutT=[]), 
               (
                 [H|T] = [H,H1|T2],
                 if_(
                       H=H1, 
                       (counter([H1|T2], [[H1,C1]|OutT]), C is C1+1),
                       (C = 1, counter([H1|T2], OutT))
                     )
               )  
            ).