Что происходит, когда я вызываю `even(3)`, где `even` является функцией-генератором?

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

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

Вам очень повезло, что вы использовали запрос even(3), который сразу показывает наличие проблемы. Вы могли бы использовать другой запрос, например even(2)., который не показывает проблему сразу. На самом деле Пролог отлично справляется с этим запросом. Все выглядит хорошо, если вы не попросите увидеть дополнительные ответы.

Итак, как мы можем убедиться, что столкнемся с проблемой как можно скорее? Один из способов сделать это — задать вместо этого запрос even(2), false. В этом случае мы ожидаем, что запрос завершится ошибкой, поскольку false никогда не завершается успешно. Однако вместо сбоя запрос может привести к бесконечному циклу (или ошибке). Добавляя false в конце, мы говорим: пропустить все ответы и просто показать, завершается ли запрос.

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

Вот минимальный фрагмент отказа, который все еще зацикливается:

even(0) :- false.
even(X) :- odd(Y), false, X is Y+1, X>0.

odd(1) :- false.
odd(X) :- even(Y), false, X is Y+1, X>1.

Именно эта крошечная оставшаяся часть отвечает за все циклы. Теперь вы можете не только обосновать, почему even(2) зацикливается, но и увидеть кое-что еще более общее: этот фрагмент отказа будет зацикливаться независимо от аргумента для even/1. Таким образом, он будет зацикливаться для любого запроса!

Дополнительную информацию см. в разделе failure-slice.

Цель X is Y + 1 становится 3 is 1 + 1 и не выполняется, что приводит к откату предыдущего вызова odd(Y). На этот раз используется второе предложение для предиката odd/1, чтобы попытаться найти альтернативное решение. Тело второго предложения вызывает even(Y), создавая экземпляр Y для 0, а затем пытается выполнить X is 0+1, X>1, что приводит к откату к предыдущему вызову предиката even/1. Это похоже на бесконечную игру в пинг-понг между предикатами odd/1 и even/1. Вы можете использовать функцию компилятора Пролога trace, чтобы шаг за шагом следить за тем, что происходит.

Также обратите внимание, что в Прологе переменные являются локальными для предложений. Может, это вас смущает?

Когда вы вызываете even(3) (так, в качестве теста), 3 не соответствует 0, поэтому попадает в составное предложение.

Первое, что делает это предложение, это вызывает odd для несвязанной переменной Y, то есть в качестве генератора. Единственный способ, которым это может закончиться успехом, - это если odd(Y) может вернуть нечетное Y, такое что 3 is Y+1. Генератор вернет 1, 3, 5 и т. д., так что этого никогда не произойдет. Но у Пролога нет возможности узнать это, поэтому все, что он может сделать, это попробовать их все. Так случилось, что их бесконечность [*], отсюда и бесконечный цикл.

[*] в зависимости от целочисленных настроек вашей реализации Пролога, но это займет много времени, независимо от того, завершится он на самом деле или нет.

Чтобы сделать код Пролога двунаправленным, вы должны добавить предложения для разных режимов и использовать тестер метапеременных var/1 для выбора между двумя вариантами:

Генератор:

even(0).
even(X) :- odd(Y), X is Y+1, X>0.

odd(1).
odd(X) :- even(Y), X is Y+1, X>1.

Тестер:

even(0).
even(X) :- X>0, Y is X-1, odd(Y).

odd(1).
odd(X) :- X>1, Y is X-1, even(Y).

Двунаправленный код:

even(0).
even(X) :- var(X), !, odd(Y), X is Y+1, X>0.
even(X) :- X>0, Y is X-1, odd(Y).

odd(1).
odd(X) :- var(X), !, even(Y), X is Y+1, X>1.
odd(X) :- X>1, Y is X-1, even(Y).

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

Но все не так просто, поскольку при объединении предикатов цели все же могут нуждаться в некоторой перестановке. Так что, возможно, мы делаем это только для сохранения пространства имен. Кстати, здесь двунаправленная реализация between/3.