Реализация "последней" в Prolog

Ответ 1

Вопрос 1:

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

?- X = 1 ; 1 = 2.
X = 1 ;
false.

Очень умный Prolog мог обнаружить, что 1 = 2 всегда терпит неудачу, и поэтому просто ответьте X = 1.. С другой стороны, такая "умность" является очень дорогостоящей для реализации, и время лучше потрачено на оптимизацию более частых случаев.

Итак, почему Prologs показывают это вообще? Основная причина заключается в том, чтобы избежать смиренного ответа на другой ответ, если Пролог уже знает, что ответа нет. Таким образом, до этого улучшения вам было предложено получить еще один ответ для всех запросов, содержащих переменные, и получило false или "no" для каждого запроса с одним ответом. Раньше это было настолько громоздким, что многие программисты никогда не просили о следующем ответе и поэтому не были предупреждены о непреднамеренных ответах.

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

В вашем примере с last1/2 вы сталкиваетесь с таким случаем. И вы уже сделали что-то очень умное, BTW: вы пытались свести к минимуму запрос, чтобы увидеть первое появление неожиданного поведения.

В вашем примере запроса last1([1,2],X) система Prolog не просматривает весь список [1,2], а только смотрит на главный функтор. Поэтому для системы Prolog запрос выглядит так же, как last1([_|_],X), когда он решает, какие условия применять. Эта цель теперь подходит для обоих предложений, и именно по этой причине Prolog запомнит второе предложение в качестве альтернативы, чтобы попробовать.

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

?- length(L,10000000), last1(L,E).
ERROR: Out of local stack

С другой стороны, предопределенный last/2 работает плавно:

?- length(L,10000000), last(L,E).
L = [_G343, _G346, _G349, _G352, _G355, _G358, _G361, _G364, _G367|...].

Фактически, он использует пространство константа!

Теперь есть два пути:

• Попробуйте оптимизировать свое определение. Да, вы можете это сделать, но вам нужно быть очень умным! Например, определение @back_dragon неверно. Часто бывает, что новички пытаются оптимизировать программу, когда на самом деле они разрушают ее семантику.

• Спросите себя, действительно ли вы определяете тот же предикат, что и last/2. На самом деле это не так.

Вопрос 2:

Рассмотрим:

?- last(Xs, X).
Xs = [X] ;
Xs = [_G299, X] ;
Xs = [_G299, _G302, X] ;
Xs = [_G299, _G302, _G305, X] ;
Xs = [_G299, _G302, _G305, _G308, X] 
...

и

?- last1(Xs, X).
** loops **

Таким образом, ваше определение отличается в этом случае определением SWI. Обмен порядком предложений.

?- length(L,10000000), last2(L,E).
L = [_G343, _G346, _G349, _G352, _G355, _G358, _G361, _G364, _G367|...] ;
false.

Опять же, это false! Но на этот раз большой список работает. И на этот раз минимальный запрос:

?- last2([1],E).
E = 1 ;
false.

И ситуация очень похожа: Опять же, Prolog будет рассматривать запрос так же, как last2([_|_],E), и сделает вывод, что оба предложения применяются. По крайней мере, теперь у нас есть постоянные накладные расходы, а не линейные накладные расходы.

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

Ответ 2

SWI-Prolog пытается избежать запроса дополнительных решений, когда он может определить, что их нет. Я думаю, что интерпретатор проверяет память, ищущую какой-то choice point слева, и если он не может найти ничего, просто укажите завершение. В противном случае он ждет, чтобы позволить пользователю выбрать ход.

Я попытался бы сделать last1 детерминированным следующим образом:

last1([_,H|Rest], Last) :- !, last1([H|Rest], Last).
last1([Last], Last).

но я не думаю, что это indistinguishable из last. Скрываясь в исходном коде библиотеки (это просто, как ?- edit(last).)

%%  last(?List, ?Last)
%
%   Succeeds when Last  is  the  last   element  of  List.  This
%   predicate is =semidet= if List is a  list and =multi= if List is
%   a partial list.
%
%   @compat There is no de-facto standard for the argument order of
%       last/2.  Be careful when porting code or use
%       append(_, [Last], List) as a portable alternative.

last([X|Xs], Last) :-
    last_(Xs, X, Last).

last_([], Last, Last).
last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).

мы можем оценить хорошо продуманную реализацию.

Ответ 3

этот код будет работать:

last1([Last], Last).
last1([_ | Rest], Last) :- last1(Rest, Last), !.

это потому, что пролог может иметь больше комбинаций, но с этим символом:!, пролог не вернется после достижения этой точки