Логическое программирование

Алгоритм работы интерпретатора Пролога


Рекурсивный алгоритм ответа на запрос 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. СЕМАНТИКА ПРОЛОГА


Содержание раздела