Поиск запроса, для которого программа на прологе дает неверный результат

Это пример из учебника.

?- max(5,1,1).
true.

Домашнее задание: Почему программа неверна? Как сделать программу корректной?

ИЗМЕНИТЬ

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

Наше намерение состоит в том, чтобы сказать:

Если X больше Y, тогда Max равен X. В противном случае Max должен быть Y.

Вместо этого говорят:

Когда первый и третий аргументы (X и Max) могут быть объединены, а X больше Y, успех. В противном случае, если второй и третий аргументы (Y и Max) могут быть объединены, успешно.

Возникает очевидная проблема, когда первый и третий аргументы нельзя объединить, а второй и третий можно.

Вместо:

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

or

max(X, Y, Max) :- X >= Y, !, Max = X.
max(_, Max, Max).

Это работает нормально, если третий аргумент не конкретизирован. Опасность здесь была бы в том случае, если бы был способ вернуться ко второму правилу или если бы третьему аргументу присваивалось то же значение, что и второму. Это не особенно безопасно, потому что max(X, Y, Y). равно max(_, Y, Y), что просто устанавливает результат на второе значение без каких-либо размышлений. Сокращение в конце первого правила эффективно гарантирует, что поиск с возвратом не начнется, если X >= Y, поэтому второе правило следует вводить только тогда, когда X ‹ Y и Z еще не равно Y.

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

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

or

max(X, Y, Z) :- X >= Y -> Z = X ; Z = Y.

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

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y) :- X < Y.

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

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

perform(scan(target, X, Y)) :- ...
perform(scan(calibration, X)) :- ...

Это имеет тот же эффект: Пролог будет возвращаться назад до тех пор, пока не будет успешно объединен, затем он снова вернется, но исключительный характер сопоставления предотвратит выполнение другого тела. Если мы обнаружим, что возврат занимает слишком много времени, мы можем добавить сокращения для повышения производительности, но на практике это вряд ли будет проблемой.