Проблема завершения программ. Используемый в Прологе принцип обхода дерева в глубину приводит к серьзным проблемам. Если дерево поиска цели относительно некоторой программы содержит бесконечную ветвь, то вычисление не завершится. Пролог может не найти решение цели, даже если существует конечное вычисление, решающее вопрос.
Бесконечные вычисления появляются при использовании рекурсивных правил. Рекурсивные правила, в которых рекурсивная цель является первой целью в теле правила, называются левыми рекурсивными правилами. Левые рекурсивные правила в Прологе приносят немало хлопот. В случае несоответствующих аргументов использование этих правил приводит к бесконечным вычислениям. Лучшее решение этой проблемы отказаться от использования левой рекурсии. В общем случае невозможно избавиться от всех появлений левой рекурсии.
Однако соответствующий анализ позволяет определить вопросы, решение которых относительно рекурсивных программ приводит к результату. Другой, не всегда замечаемый случай, который заведомо приводит к не завершающимся вычислениям это порочный круг. Ввиду порочного круга дерево поиска обязательно содержит бесконечную ветвь. 2.3.3. Порядок целей. Порядок целей более существен, чем порядок предложений. Порядок целей имеет решающее значение при определении последовательности действий в программе на Прологе.
Причина, по которой порядок целей в предложении влияет на порядок решений, отличается от причины, по которой порядок правил в процедуре влияет на порядок решений. Изменение порядка правил не изменяет дерево поиска, которое используется при решении данной цели. Просто обход дерева производится в ином порядке. Изменение порядка целей приводит к изменению дерева поиска. Порядок целей определяет дерево поиска. По этой причине порядок целей влияет на количество проверок, выполняемых программой при решении.
Существенен не порядок правил, а порядок целей. Программа будет завершающейся, если первый аргумент цели полный список. Цели, у которых первый аргумент неполный список приводят к бесконечным вычислениям. 2.3.4.