Материал: Волченков Логическое программирование язык пролог 2015

На рис. 2.1 показано дерево классификации термов Пролога.

Рис. 2.1 Виды термов в языке Пролог

Рассмотрим примеры представителей всех классов, которые соответствуют «висячим вершинам» этого дерева.

Атомоподобные термы:

атомы: a, banana, Иванов_Иван_Иванович;

целые числа: 0, 25, 32767; десятичные числа: 3.1415, 0.5e-20;

строки: ’Email: ngvolchenkov@yandex.ru’, ’A & B => C’.

Переменные: _, _X, List25.

Структуры в форме со скобками: предок(Иван, Марья), p(a, b, q(c, d, e), f, g, h).

Структуры в бесскобочной форме: not A, Сократ человек,

X is A + 25.

Списки (пустой список: [], непустые списки: [H | T], [a, b, c]).

У каждого терма, в частности, у каждой структуры и, в частности, у каждого предиката есть две синтаксические характеристики: имя и арность (число аргументов).

Пример 2.1. Рассмотрим 4 терма: больше(X, 25); X is (2+3)*6; Сократ человек; p(a, b, q(c, d, e), f, g, h).

26

У1-го терма имя больше, арность 2, аргументы X и 25.

У2-го терма имя is, арность 2, аргументы X и (2+3)*6.

У3-го терма имя человек, арность 1, аргумент Сократ.

У4-го терма имя p, арность 6, аргументы a, b, q(c, d, e), f, g, h.

Пример 2.2. Пусть в данной области интерпретации Иван – отец Петра, Пётр – отец Сергея. Пусть атомы Иван, Пётр и Сергей соответствуют перечисленным лицам, а предикаты father(Иван, Пётр) и father(Пётр, Сергей) – перечисленным отношениям.

Можно рассмотреть другой терм с тем же именем, но только с одним аргументом: father(X). Он соответствует не предикату, а функции, возвращающей значение Иван или Пётр в зависимости от значения переменной X. Тогда допустимым с точки зрения Пролога будет следующий предикат: father(father(father(Сергей)), Пётр). Его значением будет истина.

Однако Пролог реализован так, что в нём весьма ограниченный набор встроенных функциональных термов, а определять собственные функциональные термы программист права не имеет.

Но есть решение этой проблемы: любой функциональный терм f(t1, …, tn), значением которого является r, можно заменить предикатом, имеющим большее число (n+1) аргументов: f(t1, …, tn, r).

В программах на Прологе часто используется структура данных, называемая списком. Для этой структуры данных, в силу её популярности, в Прологе используется особая нотация.

По определению список – это:

Либо пустой список – атом, для обозначения которого используется специальная комбинация из двух скобок: [].

Длина такого списка равна 0;

Либо непустой список – структура без имени с двумя аргументами: Head и Tail. Первый аргумент («голова» списка) – это терм произвольного вида. Второй аргумент («хвост» списка) –

это список. Для обозначения непустого списка используется структура вида [Head | Tail].

Длина непустого списка равна длине его «хвоста» плюс 1.

Данное определение рекурсивное. Очевидно, что, согласно этому определению список – это правоассоциативное бинарное дерево, число вершин которого может быть любым. Чаще всего, это дерево изображают «растущим вниз» (рис. 2.2).

27

ском понимании этого термина. Реально, это множество подмножеств клозов, причем каждое из этих подмножеств принципиально упорядочено, то есть представляет собой последовательность. Эта последовательность и называется определением некоторого предиката.

Кроме определений, в состав программы входит особый клоз, представляющий отрицание теоремы. Этот клоз называют также

запросом к базе данных Пролога. Он имеет вид

?– R.

(Здесь R – последовательность предикатов C1, …, Cm, которые называются подцелями.)

Почему отрицание теоремы имеет такой вид?

В Прологе отрицание теоремы – это отрицание утверждения, которое на ЯИП-1П выглядит так:

X1 X2 … Xn R(X1, X2, … Xn),

где X1, X2, … Xn – переменные, входящие в состав ППФ R. Отрицание указанной формулы в исчислении предикатов эквива-

лентно формуле

X1 X2 … Xn R(X1, X2, … Xn).

(Отрицание существования есть всеобщность отрицания.)

Эту формулу можно представить в видеR(X1, X2, … Xn) false

(отбросив знаки квантора всеобщности) или в виде

R(X1, X2, … Xn) false,

а это и есть целевой клоз:

?– R(X1, X2, …, Xn).

И ещё одна особенность программ на Прологе. Иногда в начале программы (перед первым определением) ставятся директивы –

утверждения, напоминающие правила без левой части:

:– D1.

…

:– Dm.

Директивы – это цели, которые заведомо выполняются, вызывая полезные для дальнейшей (основной) работы программы побочные эффекты.

Директивы располагаются перед определениями предикатов, а запрос к базе данных – в конце программы (или, обычно, в отдель-

29

ном окне, называемом консолью). Таким образом, структура Про- лог-программы имеет вид, показанный на рис. 2.3.

3. Структура определения предиката

Утверждения каждого определения предиката – это факты, имеющие спецификацию p/n, или правила, левые части которых имеют ту же спецификацию.

Пример 2.3. Рассмотрим определение предиката ancestor/2. Будем считать, что этот предикат используется только для поиска предков какого-нибудь человека, то есть, второй аргумент этого предиката в целевом утверждении должен быть атомом, а не переменной. Допустим, что в нашей базе данных все значения переменных – это имена людей. Примем также (без доказательства!), что все люди произошли от Адама (даже Ева – «из адамова ребра»).

30