|
Самым общим случаем Пролог программы является программа, включающая как факты, так и правила. Рассмотрим процесс вычисления запроса на основе такой логической программы. Процесс вычисления начинается с некоторого исходного вопроса Q, который в общем случае может быть конъюнктивным, и завершается получением одного из двух результатов:
- успешного согласования целей вопроса;
- неуспеха (или неудачи).
В случае успешного вычисления мы получаем конкретизацию переменных, входящих в вопрос. Неудача означает невозможность вывода какой-либо цели вопросы из программы.
Допустим, что логическая программа P состоит из фактов и правил, а вопрос Q конъюнктивный и содержит цели G1,G2,…Gn. Интерпретатор языка Пролог будет вычислять ответ на вопрос согласно следующим принципам, на которых он реализован:
- Цели запроса обрабатываются слева направо, G1 будет согласовываться первой, а Gn последней. Предложения программы просматриваются интерпретатором сверху вниз.
- Если цель Gi сопоставима с заголовком правила Hj, то она должна быть сопоставима с предикатами в правой части правила. Интерпретатор заменяет цель Gi на правую часть правила Hj. Это действие называется редукцией. Другими словами, редукцией цели G с помощью программы P называется замена цели Gi на тело правила Cj, заголовок которого Hj унифицируется с целью Gi. Вычисление вопроса выполняется в виде последовательности редукций, цепочки преобразований исходного вопроса. На каждом этапе вычисления существует некоторая конъюнкция целей (или одна цель), называемая резольвентой. Цели, которые добавляются в запрос в результате редукции, называются производными целями от цели Gi и правила Cj. Если цель Gi сопоставима с заголовком правила Hj, то список целей в запросе увеличивается.
- Если цель Gi сопоставима с фактом, то конкретизируются переменные этой цели, и общие переменные цели Gi и других целей, входящих в вопрос, затем осуществляется переход к сопоставлению следующей цели Gi+1 , и, таким образом, список целей, подлежащих согласованию, уменьшается.
- Когда мы, таким образом, достигнем последней цели в запросе, и она успешно будет согласована с каким-либо фактом программы, то текущая резольвента окажется пустой, и вычисление запроса будет успешным.
Чтобы вычислить список целевых утверждений
Gl, G2, ..., Gn
процедура вычислить делает следующее:
- Если список целей пуст - завершает работу успешно.
- Если список целей не пуст, продолжает работу, выполняя (описанную далее) операцию «ПРОСМОТР».
- ПРОСМОТР. Просматривает предложение программы от качала к концу до обнаружения первого предложения С, такого, что голова С сопоставима с первой целью G1.
- Если такого предложения обнаружить не удается, то работа заканчивается неуспехом.
ЧИТАТЬ ДАЛЕЕ
|
