Алгоритм работы интерпретатора Пролога
Рекурсивный алгоритм ответа на запрос G1,G2,...,Gm (список целей) следующий.
* Если список целей пуст - завершает работу успешно.
* Если список целей не пуст, продолжает работу, выполняя (описанную далее) операцию ПРОСМОТР.
* ПРОСМОТР: Просматривает предложения (º фразы, клаузы) программы от начала к концу до обнаружения первого предложения C, такого, что голова (левая часть) C унифицируема с первой целью G1. Если такого предложения обнаружить не удается, то работа заканчивается неуспехом.
Если C найдено и имеет вид
H :- B1, ..., Bn,
то переменные в C переименовываются, чтобы получить такой вариант C¢ предложения C, в котором нет общих переменных со списком G1,...Gm. Пусть C¢ - это
H¢ :- B1¢ , ..., Bn¢ .
Унифицируется G1 с H¢; пусть S - результирующая конкретизация переменных. В списке целей G1, G2, ...,Gm, цель G1 заменяется списком B1¢,..., Bn¢, что порождает новый список целей:
B1¢, ..., Bn¢, G2, ..., Gm.
(Заметим, что, если C - факт, тогда n=0, и в этом случае новый список целей оказывается короче, нежели исходный; такое уменьшение списка целей может в определенных случаях превратить его в пустой, а, следовательно, - привести к успешному завершению.)
Переменные в новом списке целей заменяются новыми значениями, как это предписывает конкретизация S, что порождает еще один список целей
B1¢¢, ..., Bn¢¢, G2¢, ... , Gm¢.
* Вычисляется (используя тот же самый алгоритм) этот новый список целей. Если его вычисление завершается успешно, то и вычисление исходного списка целей тоже завершается успешно.
Если же его вычисление порождает неуспех, тогда новый список целей отбрасывается и происходит возврат (бэктрекинг) к просмотру программы. Этот просмотр продолжается, начиная с предложения, непосредственно следующего за предложением C (C - предложение, использовавшееся последним) и делается попытка достичь успешного завершения с помощью другого предложения.
Вычисление целей интерпретатор Пролога осуществляет с помощью поиска в глубину с возвратом
(в дереве целей): правило вычислений всегда выбирает первую слева подцель в текущем списке целей, а правило поиска выбирает из программы первую клаузу, голова которой унифицируема с данной подцелью. Если вычисление заходит в тупик, т.е. ни одно из утверждений программы не применимо к текущему списку целей, то происходит возврат назад по построенной ветви и для предыдущего состояния пробуется первое из еще не применявшихся к нему утверждений программы.
3. СЕМАНТИКА ПРОЛОГА
