Подготовка программ Prolog к выполнению может осуществляться в двух режимах: интерпретация и компиляция. Интерпретация по существу представляет собой применение алгоритма FOL-BC-Ask, приведенного в листинге 9.3, к программе, представленной в виде базы знаний. Предыдущее предложение включает слова "по существу", поскольку в интерпретаторах Prolog предусмотрены всевозможные усовершенствования, предназначенные для максимального повышения скорости работы. Здесь рассматриваются только два таких усовершенствования.

Во-первых, вместо формирования списка всех возможных ответов для каждой подцели перед переходом к следующей подцели интерпретаторы Prolog вырабатывают один ответ и "дают обещание" выработать остальные после того, как будет полностью исследован текущий ответ. Такое "обещание" оформляется как точка выбора (choice point). После того как в процессе поиска в глубину завершается исследование возможных решений, вытекающих из текущего ответа, и происходит возврат к точке выбора, в этой точке используемые структуры данных дополняются, чтобы в них можно было включить новый ответ для данной подцели и сформировать новую точку выбора. Такой подход позволяет экономить и время, и пространство, а также обеспечивает создание очень простого интерфейса для отладки, поскольку постоянно существует лишь единственный путь решения, подлежащий рассмотрению.

Во-вторых, в приведенной в данной главе простой реализации алгоритма FOL-BC-Ask много времени затрачивается на выработку и компоновку подстановок. В языке Prolog подстановки реализуются с использованием логических переменных, позволяющих сохранить в памяти их текущее связывание. В любой момент времени каждая переменная в программе является либо несвязанной, либо связанной с некоторым значением. Эти переменные и значения, вместе взятые, неявно определяют подстановку для текущей ветви доказательства. Любая попытка продления пути позволяет лишь добавить новые связывания переменных, поскольку стремление ввести другое связывание для уже связанной переменной приводит к неудачному завершению унификации. После того как попытка продления пути поиска оканчивается неудачей, система Prolog возвращается к предыдущей точке выбора и только после этого получает возможность отменить связывания некоторых переменных. Такая операция отмены выполняется благодаря тому, что данные обо всех переменных, для которых было выполнено связывание, отслеживаются в стеке, называемом контрольным стеком (trail). По мере того как в функции Unify-Var осуществляется связывание каждой новой переменной, эта переменная задвигается в контрольный стек. Если попытка достижения некоторой цели оканчивается неудачей и наступает время возвратиться к предыдущей точке пункта выбора, отменяется связывание каждой из этих переменных по мере их выталкивания из контрольного стека.