Пролог не заканчивается после переупорядочения цели

Question

В настоящее время я работаю с примерами Learn Prolog Now, а для одного упражнения у меня есть килобайт, который выходит за пределы локального стека, если у меня есть небольшое изменение в одном правиле.это КБ:

byCar(auckland,hamilton). 
byCar(hamilton,raglan). 
byCar(valmont,saarbruecken). 
byCar(valmont,metz). 

byTrain(metz,frankfurt). 
byTrain(saarbruecken,frankfurt). 
byTrain(metz,paris). 
byTrain(saarbruecken,paris). 

byPlane(frankfurt,bangkok). 
byPlane(frankfurt,singapore). 
byPlane(paris,losAngeles). 
byPlane(bangkok,auckland). 
byPlane(singapore,auckland). 
byPlane(losAngeles,auckland).

travel(X,Y) :- byCar(X,Y).
travel(X,Y) :- byTrain(X,Y).
travel(X,Y) :- byPlane(X,Y).

и соответствующее правило:

travel(X,Y) :- travel(X,Z), travel(Z,Y).

, и этот запрос выходит за пределы стека:

?- travel(valmont,losAngeles).

Но если я изменю правило на

travel(X,Y) :- travel(Z,Y), travel(X,Z).

, тогда оно сработает.

Если я отслеживаю запрос, я быстро застреваю так:

   Redo: (17) travel(raglan, _6896) ? creep
   Call: (18) byPlane(raglan, _6896) ? creep
   Fail: (18) byPlane(raglan, _6896) ? creep
   Redo: (17) travel(raglan, _6896) ? creep
   Call: (18) travel(raglan, _6896) ? creep
   Call: (19) byCar(raglan, _6896) ? creep
   Fail: (19) byCar(raglan, _6896) ? creep
   Redo: (18) travel(raglan, _6896) ? creep
   Call: (19) byTrain(raglan, _6896) ? creep
   Fail: (19) byTrain(raglan, _6896) ? creep
   Redo: (18) travel(raglan, _6896) ? creep
   Call: (19) byPlane(raglan, _6896) ? creep
   Fail: (19) byPlane(raglan, _6896) ? creep
   Redo: (18) travel(raglan, _6896) ? creep
...

Но я не понимаю, почему.Разве он не должен просто понимать, что реглан является конечной станцией, и поэтому ему необходимо вернуться на один уровень больше?

Спасибо!

Редактировать: я использую SWI Prolog

Редактировать: я обнаружил проблему, пройдя ее шаг за шагом.В случае реглана, нигде нет никаких правил.Поэтому, после попытки byPlane, byTrain, byCar, он пытается снова travel(raglan, X) (первая цель последнего правила), таким образом, цикл.Но я не понимаю, как лучше другое правило.

Answer 1

Вы должны уточнить, что вы подразумеваете под "это работает".На самом деле обе версии предиката travel/2 не заканчиваются.Но можно найти решение для очень специфического запроса.

Теперь спросите ?- travel(hamilton, losAngeles)., который повторяется для обоих.

Так что ваше исправление работает только для некоторых запросов, но не для других.Разве нет более надежного выхода?

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

С другой стороны, существует очень родственное понятие (универсальное) завершение , которое намного легче предсказать, поскольку оно не зависит отмногие детали в вашей программе, такие как порядок появления ваших фактов.Самый простой способ запросить универсальное завершение - добавить цель false в конце вашего запроса.

Но вы можете пойти еще дальше, добавив цели false где хотите ¹ .Такая модифицированная программа называется fault-slice .Независимо от того, как вы вставляете false, выполняется следующее:

Если срез ошибки не завершается, то и ваша исходная программа не прерывается.

Теперь рассмотрим срез-срезы для двух вариантов travel/2:

<s>travel(X,Y) :- <b>false</b>, byCar(X,Y)</s>.
<s>travel(X,Y) :- <b>false</b>, byTrain(X,Y)</s>.
<s>travel(X,Y) :- <b>false</b>, byPlane(X,Y)</s>.
travel(X,Y) :- travel(X,Z), <b>false</b>, <s>travel(Z,Y)</s>.

и вашей другой версии:

<s>travel(X,Y) :- <b>false</b>, byCar(X,Y)</s>.
<s>travel(X,Y) :- <b>false</b>, byTrain(X,Y)</s>.
<s>travel(X,Y) :- <b>false</b>, byPlane(X,Y)</s>.
travel(X,Y) :- travel(Z,Y), <b>false</b>, <s>travel(X,Z)</s>.

В обоих случаях ни X, ни Y считается вообще!Таким образом, два аргумента не влияют на завершение.И поэтому обе версии не заканчиваются.То есть они никогда не заканчиваются.

Теперь сравните этот вывод с более традиционным подходом к просмотру следа.Хотя срезы сбоев позволили нам сделать общие выводы ("... никогда не завершается"), конкретная трассировка может показать вам только детали одного конкретного выполнения.

Для того, чтобы это исправить, вам нужноизменить что-то в видимой части.Мое предложение будет использовать closure/3.То есть:

travel(X, Y) :-
   closure(connexion, X, Y).

connexion(X,Y) :- byCar(X,Y).
connexion(X,Y) :- byTrain(X,Y).
connexion(X,Y) :- byPlane(X,Y).

Или используйте более общий path/4.

---

_{1 На самом деле, это работает только в чисто монотонных программах.Ваша программа одна из этих}

Answer 2

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

Ваша вторая формулировка совсем не лучше, она просто не работает в разных случаях:

travel(losAngeles, valmont).
ERROR: Out of local stack

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

connection(X,Y) :- byCar(X,Y).
connection(X,Y) :- byTrain(X,Y).
connection(X,Y) :- byPlane(X,Y).

travel(X,Y) :- connection(X,Y).
travel(X,Y) :- connection(X,Z), travel(Z,Y).

Порядок целей не имеет значения, поскольку travel всегда требует некоторой физической связисуществовать (а не рекурсия), чтобы продолжить.

Это также облегчает запись поездки, которую вы все равно захотите (верно?):

connection(X,Y, car(X,Y))   :- byCar(X,Y).
connection(X,Y, train(X,Y)) :- byTrain(X,Y).
connection(X,Y, plane(X,Y)) :- byPlane(X,Y).

travel(X,Y,[Part])       :- connection(X,Y,Part).
travel(X,Y,[Part|Parts]) :- connection(X,Z,Part), travel(Z,Y,Parts).

?- travel(valmont, losAngeles, Journey).
Journey = [car(valmont, saarbruecken), train(saarbruecken, paris), plane(paris, losAngeles)] 

А для случая, когда нет действительной поездки:

travel(losAngeles, valmont, Journey).
false.