Prolog #3.1 & #3.2

Подробный взгляд на Prolog

В предыдущем разделе вы работали с Prolog в контексте простого примера и узнали об основных компонентах Prolog: факты, правила и интерпретатор. В этом разделе мы более подробно рассмотрим эти же компоненты.

3.1. Факты

Не так уж много можно дополнительно рассказать о фактах. Важно уяснить, что если предикат появляется в последовательности фактов, это не означает, что он не может быть головой(не фактом) правила. Например, мы можем взять предикаты edge и tedge из Примера 2.1 и определить новый, более сложный граф.

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

Добавьте это новое правило в вашу программу и посмотрите, как это отразится на следующих запросах:

?- edge(a, c).
?- edge(a, b).
?- edge(e, c).

Заметьте, что каждый из этих запросов выдаст “Да” в качестве ответа. Мы будем избегать запросов, которые выдают “Нет”, потому что они могут действовать неожиданным(пока что) для нас способом.

3.2. Правила

Настоящая сила любого языка программирования это его механизмы абстракции. В Prolog правила представляют механизмы абстракции. Тогда как факт может только определить кортеж значений, удовлетворяющий некоторому предикату, правило может задать эти самые условия, при которых набор значений будет удовлетворять задаваемому предикату.

Базовым строительным блоком правила является атом: предикат, за которым следует кортеж термов, где и константы и переменные являются термами(мы увидим, что терм может иметь более сложную структуру). Каждый факт является атомом. Когда кортеж значений удовлетворяет предикату атома, мы говорим что атом истинен. Каждое правило поделено на две части с помощью символа “:-“: левая часть называется головой правила, тогда как правая – телом правила. В общем виде мы читаем правило

Atom :- Atom1, ..., Atomn

как

Если каждый из Atom1, …, Atomn истинен, тогда Atom – так же истинен.

tedge(Node1, Node2) :- edge(Node1, SomeNode), edge(SomeNode, Node2).

Мы видим эту структуру в правиле, определяющем tedge:

В этом правиле 3 атома, 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. Мы можем прочитать эти два правила как

path(Node1, Node2) истинен, если edge(Node1, Node2) истинен или если существует узел SomeNode для которого оба edge(Node1, SomeNode) и path(SomeNode, Node2) истины.

Вторая особенность в том, что голова второго правила появляется в теле этого правила. Вместе, два этих правила показывают как определять рекурсивные правила в Prolog.

Задачи № 2

1.  Добавьте предикат path. в программу, которую вы написали при решении Задач № 1 в разделе 2.2. Проверьте этот предикат, чтобы удостовериться, что он работает, как нужно. Проверяйте на узлах, которые соединены гранями! [Вы можете проверить на несоединенных узлах, но будьте готовы к неожиданному поведению]

2. Измените определение path, так, чтобы пути длиной 0 были допустимы. [ФАКТ!]