Реализация "последнего" в прологе
Я пытаюсь почувствовать программирование на Прологе, просматривая лекционные заметки Улле Эндрисса. Когда мое решение для упражнения не ведет себя должным образом, я затрудняюсь дать хорошее объяснение. Я думаю, что это связано с моим шатким пониманием того, как Prolog оценивает выражения.
Упражнение 2.6 на странице 20 требует рекурсивной реализации предиката last1 который ведет себя как встроенный предикат last, Моя попытка заключается в следующем:
last1([_ | Rest], Last) :- last1(Rest, Last). last1([Last], Last).
Он дает правильный ответ, но для списков с более чем одним элементом мне нужно ввести точку с запятой, чтобы завершить запрос. Это делает last1 отличается от встроенного last,
?- last1([1], Last).
Last = 1.
?- last1([1, 2], Last).
Last = 2 ;
false.
Если я поменяю порядок, в котором я объявил правило и факт, то мне нужно ввести точку с запятой в обоих случаях.
Я думаю, я знаю, почему Пролог так думает last1 может иметь еще одно решение (таким образом, точка с запятой). Я предполагаю, что это следует за последовательностью оценки
last1([1, 2], Last).
==> last1([2], Last).
==> last1([], Last). OR Last = 2.
==> false OR Last = 2.
Это, кажется, говорит о том, что я должен искать способ избежать соответствия Rest с [], Несмотря на это, у меня нет объяснения, почему изменение порядка объявления должно иметь какой-либо эффект.
Вопрос 1: Как правильно объяснить поведение last1?
Вопрос 2: Как я могу реализовать предикат last1 который неотличим от встроенного last?
3 ответа
Вопрос 1:
Системы Prolog не всегда могут решить, будет ли пункт применяться до его выполнения. Точные обстоятельства зависят от реализации. То есть вы не можете полагаться на это решение в целом. Системы улучшаются здесь от выпуска к выпуску. Рассмотрим как простейший случай:
? - Х = 1; 1 = 2 Х = 1; ложный.
Очень умный Пролог мог обнаружить это 1 = 2 всегда терпит неудачу, и, таким образом, просто ответить X = 1. вместо. С другой стороны, такая "хитрость" очень дорога в реализации, и время лучше тратить на оптимизацию более частых случаев.
Так почему Прологи показывают это вообще? Основная причина заключается в том, чтобы избегать кроткого запроса другого ответа, если Пролог уже знает, что ответа больше нет. Таким образом, до этого улучшения вам было предложено еще один ответ для всех запросов, содержащих переменные, и получили false или "нет" на каждый запрос с ровно одним ответом. Раньше это было настолько обременительно, что многие программисты никогда не просили следующий ответ и, следовательно, не были предупреждены о непреднамеренных ответах.
И вторичная причина заключается в том, чтобы держать вас в курсе ограничений реализации: если Prolog запрашивает другой ответ на этот общий запрос, это означает, что он все еще использует некоторое пространство, которое может накапливать и поглощать все ваши вычислительные ресурсы.
В вашем примере с last1/2 Вы сталкиваетесь с таким случаем. И вы уже сделали что-то очень умное, кстати: вы пытались свести к минимуму запрос, чтобы увидеть первое появление неожиданного поведения.
В вашем примере запроса last1([1,2],X) система Пролог не смотрит на весь список [1,2] но только смотрит на главный функтор. Таким образом, для системы Prolog запрос выглядит так же, как last1([_|_],X) когда он решает, какие пункты применять. Эта цель теперь соответствует обоим пунктам, и именно поэтому Prolog запомнит второй пункт в качестве альтернативы.
Но подумайте: этот выбор теперь возможен для всех элементов, кроме последнего! Это означает, что вы платите немного памяти за каждый элемент! Вы можете наблюдать это, используя очень длинный список. Это я получаю на своем крошечном 32-битном ноутбуке - вам может потребоваться добавить еще один ноль или два в большей системе:
? - длина (L,10000000), последняя1(L,E). ОШИБКА: вне локального стека
С другой стороны, предопределенный last/2 работает плавно:
? - длина (L,10000000), последняя (L, E). L = [_G343, _G346, _G349, _G352, _G355, _G358, _G361, _G364, _G367 |...].
На самом деле, он использует постоянное пространство!
Теперь есть два выхода из этого:
Попробуйте оптимизировать ваше определение. Да, вы можете сделать это, но вам нужно быть очень умным! Например, определение @back_dragon неверно. Часто бывает, что новички пытаются оптимизировать программу, когда фактически разрушают ее семантику.
Спросите себя, действительно ли вы определяете тот же предикат, что и
last/2, На самом деле, вы не.
Вопрос 2:
Рассматривать:
? - последний (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). ** петли **
Таким образом, ваше определение отличается в этом случае от определения SWI. Обменяйте порядок пунктов.
? - длина (L,10000000), последняя2 (L, E). L = [_G343, _G346, _G349, _G352, _G355, _G358, _G361, _G364, _G367 |...]; ложный.
Опять же это false! Но на этот раз большой список работает. И на этот раз минимальный запрос:
? - last2 ([1], E). Е = 1; ложный.
И ситуация довольно похожа: опять Пролог будет смотреть на запрос так же, как last2([_|_],E) и придет к выводу, что применяются оба пункта. По крайней мере, теперь у нас постоянные издержки вместо линейных.
Есть несколько способов преодолеть эти издержки в чистом виде, но все они очень сильно зависят от внутренней реализации.
SWI-Prolog старается избегать запроса о большем количестве решений, когда он может определить, что их нет. Я думаю, что переводчик проверяет память в поисках некоторых choice point слева, и если он не может найти, просто заявить о прекращении. В противном случае он ждет, чтобы пользователь мог выбрать ход.
Я бы попытался сделать last1 детерминированным таким образом:
last1([_,H|Rest], Last) :- !, last1([H|Rest], Last).
last1([Last], Last).
но я не думаю, что это indistinguishable от последнего Скрывается в исходном коде библиотеки (это просто как ?- 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).
мы можем оценить хорошо продуманную реализацию.
Этот код будет работать:
last1([Last], Last).
last1([_ | Rest], Last) :- last1(Rest, Last), !.
это потому, что в прологе может быть больше комбинаций, но с этим символом:! пролог не вернется после достижения этой точки