Prolog #3.3.1

Вычисление

Предыдущие разделы проиллюстрировали как декларативные выражения (факты и правила) могут быть использованы для написания программы, которая определяет базу знаний, в данном случае, знаний о конкретном ориентированном графе. Но программа не будет считаться полезной, если мы не можем неявно извлечь или вывести полезное знание из неё. В приведённом выше примере, например, мы можем хотеть вывести все узлы, которые могут быть достигнуты путями длиной менее 4-ех узлов, начиная от узла d. Императивная, или вычислительная компонента Prolog делает подобное выведение возможным.
Для следующих разделов мы будем использовать программу, которая обсуждалась ранее (с предикатом path). Для определённости, она представлена здесь:

edge(a,b).
edge(a,e).
edge(b,d).
edge(b,c).
edge(c,a).
edge(e,b).
tedge(Node1,Node2) :- edge(Node1,SomeNode),
    edge(SomeNode,Node2).
path(Node1,Node2) :- edge(Node1,Node2).
path(Node1,Node2) :- edge(Node1,SomeNode),
    path(SomeNode,Node2).

Основные запросы

Вычисления в Prolog выполняются с помощью запросов, говоря простым языком – конъюнкцией атомов. Запрос представляет собой вопрос программе на Prolog: верен ли запрос в контексте программы? Например, рассмотрим следующий запрос:

edge(a, b)

Данный запрос называется основным запросом, потому что он не содержит переменных. Когда задаётся базовый вопрос, мы ожидаем получить в ответ только “Да” или “Нет”. Как определяется ответ?
Отвечая на запрос, система Prolog просматривает программу в поисках правила, или факта, который “совпадает” с запросом. Если мы посмотрим на программу выше, мы увидим, что запрос совпадает с фактом(идентично) на строке 1, так что запрос должен быть истинен в контексте данной программы.
Ну, это было легко. Что насчет этого запроса?

path(a, b)

Это также основной запрос, но когда мы просматриваем программу, мы не можем найти правила, которое один в один совпадает с запросом. Суть именно в том, ЧТО мы подразумеваем под “совпадением” в данном контексте. Когда мы просматриваем программу, у нас есть только 2 правила, 8 и 9, с предикатом path в голове. Конечно, мы знаем, что это правило истинно(голова), только если тело истинно. Таким образом, если path(a, b) предполагается истинным, оно должно быть истинным на основании истинности правил, определяющих path, то есть, тех правил, у которых path находится в голове. Но головы каждого из этих правил содержат переменные, а не константы. Неудивительно, что Prolog находит совпадение, когда идентификаторы констант и переменных совпадают. В этом случае, мы видим, что если переменные Node1 и Node2 заменены на a и b, соответственно, тогда тело правила 8 истинно. Отсюда, голова правила с той же самой подстановкой должна быть истинной. Prolog заключит, что запрос истинен.
Для того, чтобы подвести итог: когда Prolog пытается вывести запрос, он начинает с поиска правил с головами, которые совпадают с предикатом в запросе. Этот поиск всегда выполняется сверху вниз, таким образом порядок определений влияет на вычисления. Совпадение считается найденным, если параметры запроса идентичны параметрам в голове правила или если соответствующий параметр в голове правила является переменной.
Но запрос не обязательно должен быть одним атомом. Определение гласит, что запрос – это конъюнкция атомов. Но свойства этого отношения говорят нам о том, что конъюнкция истинна тогда и только тогда, когда каждый атом в ней является истинным. Таким образом, для того, чтобы определить истинность запроса система Prolog должна проверить на истинность каждый атом в запросе.