Язык ПРОЛОГ предназначен для представления и использования знаний в различных предметных областях. Математическую основу языка составляет исчисление предикатов первого порядка (ИППП), при этом объекты предметной области, их свойства и связи представляются конъюнкцией правильно построение формул специального вида, называемых дизъюнктами Хорна. Для решения задачи получения новой информации об отношениях предметной области, формулируемой как задача доказательства теоремы, в интерпретаторе системы программирования ПРОЛОГ реализован метод резолюции.

Примечание. Дизъюнктом Хорна называется формула, имеющая следующий общий вид записи:

Программа на языке ПРОЛОГ состоит из утверждений (предложений, дизъюнктов Хорна), составляющих базу фактов и базу правил, к которым допустимо обращение с запросами. Запросы называются также целевыми утверждениями или просто целями.
Термин "программа" мы применяем к ПРОЛОГу по "традиции", т.к. ПРОЛОГ - декларативный язык!

Большинство существующих систем программирования ПРОЛОГ являются комбинированными в том смысле, что допускают как интерпретацию программ, так и их компиляцию.

Утверждения (предложения) языка ПРОЛОГ конструируются из термов.

Терм - это

либо константа, либо переменная, либо структура.

Примечание. Отметим, что понятие терма в ПРОЛОГе отличается от этого понятия в ИППП.

Константа - это

либо атом, либо число.

Атомы бывают трех типов:

1. последовательность букв, цифр и знака "подчёркивание", обязательно начинающаяся со строчной буквы (маленькой буквы);
2. последовательность спецзнаков ":-", "?-", "=", ">=", "--" и др.;
3. заключённая в апострофы (одинарные кавычки) последовательность любых символов.

Переменная - последовательность букв, цифр и знака "_", обязательно начинающаяся с прописной (большой) буквы или знака "_".
Переменные ПРОЛОГа полностью аналогичны предметным переменным ИППП. В утверждениях языка ПРОЛОГ переменные связаны не указываемыми явно кванторами общности.
Среди переменных выделена переменная "_" (один знак подчёркивания), называемая анонимной. Она используется в ситуациях, когда нас не интересует её значение.

Структура представляется на языке ПРОЛОГ с помощью указания её функтора и компонент в следующем виде:

• предикатов (т.е. отношений предметной области), при этом функтор играет роль предикатной буквы ИППП;
• операций (т.е. операций предметной области), при этом функтор играет роль функциональной буквы;
• информации сложной структуры, при этом функтор играет роль имени типа данных (ср. со структурами данных языка СИ).

Базу фактов в программе па языке ПРОЛОГ составляют утверждения, описывающее факты предметной области в виде структур, функторами которых являются атомы - имена отношений (предикатные буквы), а компонентами - предметные константы.
Пример. Факты из рассматриваемой в пособии предметной области конструирования башен могут быть представлены в виде утверждений языка ПРОЛОГ следующим образом:

roof(prizm, 4).			/* 1 */
roof(plane, 1).			/* 2 */
block(cyl, 5).			/* 3 */
block(cyl, 3).			/* 4 */
block(par, 4).			/* 5 */
block(par, 2).			/* 6 */

Система программирования ПРОЛОГ позволяет ставить запросы к базе фактов, касающиеся непосредственного ее содержимого. Простейшим видом запроса является запрос на проверку наличия в базе какого-либо факта, имеющий вид:

Пример. Ниже представлены запросы к нашей базе фактов (левая колонка символов) и ответы на них (правая колонка).

?-block(cyl, 3).	Yes
?-roof(plane, 2).	No
?-block(prizm, 4).	No
?-roof(plane).		No
?-base(strip, 1).	No

Более полезными с точки зрения пользователя и более сложными с точки зрения формирования ответа являются запросы, содержащие переменные в качестве компонент структуры. Поиск ответа на такой запрос связан с использованием механизма конкретизации переменных значениями в процессе сопоставления структур, представляющих собой запрос и факт. В рамках языка ПРОЛОГ считается, что переменная, как компонента структуры, всегда сопоставима с компонентой (любым термом) другой структуры, находящейся в той же самой позиции, что и переменная (естественно, при условии, что функторы структур совпадают). Если переменная сопоставляется с константой или структурой, то значением переменной становится эта константа или структура. Случай сопоставления двух переменных (называемый связыванием) будет рассмотрен ниже. Ответом на запрос, содержащий переменные, служат значения этих переменных.
Пример. Ниже представлен фрагмент диалога пользователя с системой программирования ПРОЛОГ, касающийся фактов об элементах строительных конструкций.

?-roof(prizm, H).	H = 4
?-block(F, 3).		F = cyl
?-block(F, H).		F = cyl, H = 5
;			F = cyl, H = 3
;			F = par, H = 4
;			F = par, H = 2
;			No

Рассмотрим подробно процесс обработки интерпретатором последнего запроса в примере. Получив его, интерпретатор просматривает базу фактов, начиная с самого первого утверждения, пока не удастся сопоставить целевое утверждение с третьим фактом. Здесь интерпретатор выдает значения конкретизированных переменных запроса, устанавливает специальный маркер (указатель) на утверждение 3 и переходит в состояние ожидания реакции пользователя. Пользователь, желая продолжить просмотр базы фактов, вводит специальный символ ";" (точка с запятой), сигнализируя интерпретатору о продолжении поиска. Интерпретатор а) расконкретизирует переменные, делая их опять неопределенными, и б) продолжает сопоставление, начиная с утверждения, непосредственно следующего за отмеченным маркером.

Приведенные выше запросы к базе фактов являются лишь частным случаем допустимых в языке ПРОЛОГ целевых утверждений. Но прежде, чем рассмотреть их общий случай, необходимо ознакомиться с организацией арифметических вычислений в языке ПРОЛОГ и с некоторыми встроенными в него предикатами.

Для описания арифметических операций в языке ПРОЛОГ используются структуры, функторами которых выступают знаки арифметических действий, а компонентами - термы, являющиеся операндами. В качестве операндов могут использоваться числа, переменные и структуры. Последние, в свою очередь, должны представлять собой арифметические выражения. С точки зрения ИППП знаки арифметических операций в таких структурах выступают в качестве функциональных букв.
Однако запись арифметических выражений в форме структур (в префиксной форме) для человека непривычна, поэтому синтаксис языка ПРОЛОГ допускает для них и альтернативную - инфиксную - форму. Ниже даны примеры записи арифметических выражений в обеих формах.

+(2,2)	=	2+2
-(Y,X)	=	Y-X
*(+(X,2),-(16,Y))	=	(X+2)*(16-Y)
/(*(X,Y),Z)	=	(X*Y)/Z
mod(X,3)	=	X mod 3

Встроенные предикаты, осуществляющие сравнение термов, также имеют две формы записи, однако в программах на языке ПРОЛОГ чаще используется более привычная - инфиксная. Этими предикатами являются: равно (=), не равно (\=), больше (>), меньше (<), больше-равно (>=), меньше-равно (=<). Четыре последние могут быть использованы для сравнения только чисел или переменных, конкретизированных числами. Два первых годятся для сравнения любых термов. Ниже даются примеры использования этих предикатов в запросах.

?- 4 > 2.		Yes
?- abc = 'abc'.		Yes
?- cad \= cam.		Yes
?- x = X.		X = x
?- Y = cat.		Y = cat
?- X = Y.		Yes

Примеры с предикатом равно иллюстрируют важное его свойство - конкретизацию переменной, являющейся одним из его аргументов, значением другого аргумента, что дает положительный результат проверка. Ответом на запрос X = Y будет Yes, поскольку предикат "равно" в случае, когда оба его аргумента являются неконкретизированными переменными, связывает их, делая синонимами, указывающими на одно и то же значение (пока неопределённое).

Важно чётко представлять себе работу предиката "равно". При согласовании с базой данных цели вида X=Y действуют следующие правила:

• если X (или Y) - неконкретизированная переменная, а Y (или X) - конкретизирована, то Х (или Y) конкретизируется значением Y (или X) (обе переменные теперь указывают на один и тот же объект), ответ - Yes;
• если обе переменные X (или Y) неконкретизированы, то они связываются (сцепляются), ответ - Yes. В дальнейшем, при конкретизации какой-либо одной из них автоматически будет конкретизирована и другая тем же самым значением;
• константы всегда равны сами себе;
• две структуры равны, если они имеют один и тот же функтор и одинаковое количество аргументов, при этом все аргументы попарно равны.

?- a(B,c,D,e(f,H)) = a(b,C,x(y,z),e(F,h)).
        B=b, C=c, D=x(y,z), F=f, H=h

?- point(X,Y,15) = point(25,Y1,Z1).
?- bEAr = 'bEAr'.
?- f(X,X) = f(a,b).
?- f(X,a(b,c)) = f(Z,a(Z,c)).

Расширенной версией предиката "=" является встроенный предикат "is". Дело в том, что перед собственно сравнением двух своих аргументов этот предикат осуществляет вычисление своего правого аргумента (при условии, конечно, что этот аргумент можно интерпретировать как арифметическое выражение).

Примеры.

?- X = +(2,2).		X = 2+2
?- X is 2+2.		X = 4
?- 2+2 = +(2,2).	Yes
?- 2+2 is +(2,2).	No

Введенные элементы языка ПРОЛОГ позволяют рассмотреть более сложные типы запросов к базе фактов. В общем виде запрос (целевое утверждение) формулируется в следующем виде:

Здесь каждая структура представляет собой предикат, возможно содержащий переменные. Причем областью действия переменной является всё утверждение в целом, т.е одна и та же переменная в пределах утверждения означает один и тот же объект. Символ "," (запятая) между предикатами трактуется как логическая связка И, т.е. запрос необходимо рассматривать как требование на поиск в базе фактов информации, удовлетворяющей одновременно всем предикатам целевого утверждения. Предикаты, объединенные связкой И в таком запросе, называются подцелями (имея в виду весь запрос целью).

Пример. Пусть необходимо получить из базы фактов информацию о наличии строительных блоков высотой более 2 и менее 5. Тогда соответствующий диалог с интерпретатором ПРОЛОГа будет иметь следующий вид.

?- block(F, H), H>2, H<5.		F = cyl, H = 3
;					F = par, H = 4
;					No

Получив запрос (целевое утверждение), состоящий из нескольких предикатов, интерпретатор пытается выполнить его, используя линейную по входу стратегию метода резолюции, реализуя следующую схему вычислений, поясняемую последним рассмотренным примером. Выбирается первый в последовательности запроса предикат и делается попытка (если этот предикат не встроенный) согласовать его с базой фактов, для чего выполняется сопоставление этого предиката последовательно со всеми утверждениями базы до тех пор, пока оно не даст положительного результата. Если этого не происходит, интерпретатор выдает в качестве ответа No. В ходе согласования возможна конкретизация переменных значениями. В нашем примере на этом этапе будет выполнено согласование предиката block(F,H) с третьим утверждением базы фактов, при этом переменная F получит значение cyl, переменная Н - 5, а маркер будет установлен на утверждении 3.
Удовлетворив один предикат (подцель) запроса, интерпретатор переходит к соседнему справа (у нас это H>2). Этот предикат - встроенный, для его проверки нет необходимости обращаться к базе фактов, поскольку интерпретатор в состоянии сам установить его истинность (5>2). Далее следует проверка (попытка "согласовать") последнего предиката в запросе, которая заканчивается неудачей. Здесь включается в работу механизм бэктрекинга (возврата), который заставляет интерпретатор, передвигаясь по предикатам целевого утверждения справа налево, вновь согласовывать эти предикаты, но уже на новых утверждениях базы фактов. Если попытка пересогласовать какой-либо предикат (подцель) интерпретатору удается, то он продолжает рассмотрение подцелей от данной в обычном порядке (слева направо). В нашем примере бэктрекинг достигнет предиката block(F,H), это приведет к расконкретизации переменных F и H и поиску нового утверждения, согласующегося с ним, начиная со следующего после отмеченного маркером (т.е. начиная с четвертого) факта.
Этот (четвертый) факт согласуется с подцелью, F получает значение cyl, H - 3, и это значение H удовлетворяет двум оставшимся в запросе предикатам. Таким образом будет найден первый ответ на запрос. Ввод пользователем символа ";" инициирует механизм бэктрекинга и, следовательно, дальнейший поиск с использованием рассмотренной схемы.

Описанные выше возможности языка ПРОЛОГ для работы с базой фактов во многом совпадают с возможностями, предоставляемыми системами управления реляционными базами данных. Языком представления знаний ПРОЛОГ делают имеющиеся в нем средства для описания базы правил. Правило представляет собой дизъюнкт Хорна, содержащий один положительный литерал и несколько отрицательных, и записывается следующим образом:

Пример. Правила, задающие различные допустимые конструкции башен в рассматриваемой нами предметной области, записываются на языке ПРОЛОГ так, как это показано ниже.

tower(Fr, Fc, Nbl, H) :- roof(Fr, Hr), col(Fc, Nbl, Hc), H is Hr + Hc.	 /* 7 */
col(F, 1, H) :- block(F, H).						 /* 8 */
col(F, 2, H) :- block(F, H1), block(F, H2), H is H1+H2.		 	 /* 9 */
col(F, 3, H) :- block(F, H1), block(F, H2), block(F, H3), H is H1+H2+H3. /* 10 */

Часто при интерпретации правил атом ":-" удобно читать как "это есть". Тогда правило 7 может быть прочитано следующим образом: башня высотой Н , состоящая из Nbl блоков формы Fc и имеющая крышу формой Fr - это есть крыша формой Fr и высотой Hr, ствол высотой Hc, состоящий из Nbl блоков формы Fc, и высота башни H равна сумме высот крыши Hr и ствола Hc.

Наличие правил в программах на языке ПРОЛОГ позволяет интерпретатору находить ответ на запросы, не касающиеся непосредственно содержимого базы фактов. В вашей предметной области таким запросом может быть, например, запрос на конструирование башни высотой 11 из блоков цилиндрической формы:

?-tower(F_roof, cyl, N_blocks, 11).

Рассмотренные примеры позволяют сделать ряд важных заключений, касающихся языка ПРОЛОГ. Во-первых, язык ПРОЛОГ позволяет создавать программы, обладающие свойством недетерминизма, т.е. программы, способные давать ответы на запросы, в которых априорно не фиксируются объекты, являющиеся исходными и результирующими. Так, для нашей программы с башнями вполне корректен будет запрос на проектирование башни с призматической крышей из трех блоков:

?-tower(prizm, F, 3 ,H).

tower(Fr,Fc,Nbl,H):-roof(Fr,Hr),Hc is H-Hr,col(Fc,Nbl,Hc).
col(F,1,H):-H>1,H<6,block(F,H).
col(F,2,H):-H>3,H<11,block(F,H1),H2 is H-H1,block(F,H2).
col(F,3,H):-H>5,H<16,block(F,H1),block(F,H2),H3 is H-H1-H2,block(F,H3).

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

col(F, 1, H) :- block(F, H).
col(F, Nbl, H) :- block(F, Hbl), col(F, N, Hc), H is Hbl+Hc, Nbl is N+1.

Необходимо отметать, что использование рекурсивных определений такого типа в программах на языке ПРОЛОГ связано с опасностью бесконечного "зацикливания" в рекурсиях. Такой, например, будет ситуация в нашем примере при запросе на конструирование башни высотой 11, когда интерпретатор будет исследовать бесконечное число проектов башен с призматической крышей и цилиндрическим стволом высотой кратной пяти. В этом проявляется упомянутое ранее свойство полуразрешимости ИППП, лежащего в основе языка ПРОЛОГ.

Отмеченные достоинства языка ПРОЛОГ - декларативная форма представления знаний о предметной области, недетерминизм, легкая модифицируемость программ - обусловили его широкое применение в различных проектах ИИ. Системы программирования ПРОЛОГ имеются для всех универсальных ЭВМ.

Список - упорядоченная последовательность элементов, имеющая произвольную длину. В ПРОЛОГЕ элементы списка не обязаны принадлежать одному типу и могут быть в свою очередь списками.
Список в ПРОЛОГе - это либо пустой список, обозначаемый [], либо структура с функтором "."(точка) и двумя компонентами: головой и хвостом списка. Признаком конца списка служит хвост, являющийся пустым списком [].
Например:

[]	- пустой список
.(a,[])	- список из одного элемента a
.(a,.(b,.(c,[])))	- список из трёх элементов a, b, c

В некоторых реализациях ПРОЛОГа функтор "." определён как инфиксный оператор, тогда третий пример будет иметь вид a.(b.(c.[])).
Однако в любом случае использование "." оказывается неудобным, поэтому в ПРОЛОГе предусмотрена привычная форма записи списков: [], [a], [a,b,c].

Списки, как и любые другие структуры, могут содержать переменные, например, допустим такой список [X,a,[b,X,Y],Z].

Работа со списками основана на расщеплении их на голову и хвост. Голова - это первый элемент списка, хвост - список из остальных элементов.
Пример.

Список	Голова	Хвост
[a, b, c]	a	[b, c]
[[a, b], c]	[a, b]	[c]
[a]	a	[]
[]	Нет	Нет

Пустой список [] не имеет ни головы, ни хвоста.
В ПРОЛОГе используется специальная форма представления списка с головой H и хвостом T - [H|T].

Примеры сопоставления списков:

?- [X,Y,Z]=[a,b,c].		X = a, Y = b, Z = c
?- [cat]=[X|Y].			X = cat, Y = []
?- [[a,Y]|Z]=[[X,b],[c,d]].	X = a, Y = b, Z = [[c,d]]

Примечание. Существует ещё одна область применения списков - представление строк литер (символов): строка, заключённая в двойные кавычки (") эквивалентна списку десятичных значений ASCII.

Для работы со списками в ПРОЛОГе используется рекурсия. Рассмотрим пример, в котором необходимо определить правила проверки принадлежности элемента списку. Для этого дадим рекурсивное определение принадлежности - некоторый элемент принадлежит списку, если а) он является первым элементом списка (головой списка) или б) принадлежит хвосту списка.

member(X, [Y|Z]):- X=Y.		или
member(X, [Y|_]):- X=Y.		или
member(X, [X|_]).
member(X, [_|Y]):- member(X,Y).

• граничные условия (в примере: элемент содержится в списке или нет), которые обязательно должны учитываться в программе;
• способ использования рекурсии (она каждый раз должна применяться к более короткому списку).

Рассмотрим, как работают наши правила на следующих запросах: member(a,[a,b,c,d,e]) и member(d,[a,b,c,d,e]).

При получении запроса в виде

?-member(a,[a,b,c,d,e]).

При получении запроса в виде

?-member(d,[a,b,c,d,e]).

Задание. Самостоятельно рассмотреть процесс поиска ответов ПРОЛОГом на следующие запросы:

?-member(a,[]).
?-member(a,X).
?-member(a,[b,C,d,e]).

Отсечение - это специальный механизм ПРОЛОГа, использование которого позволяет указать, какие из ранее сделанных выборов не следует пересматривать при возврате по цепочке согласованных целевых утверждений.
Отсечение используется для повышения эффективности программ как по времени (не тратится время на попытки найти новые сопоставления для целей, для которых заранее известно, что они не внесут в решение ничего продуктивного), так и по памяти (нет необходимости хранить маркеры точек возврата). Часто отсечение является необходимым элементом программы - без него она правильно не работает.

Синтаксически отсечение представляется функтором "!" структуры без аргументов. Встроенный предикат "!" всегда согласуется с базой правил и не может быть пересогласован. Однако он имеет существенный побочный эффект, изменяющий порядок последующего возврата.
Рассмотрим следующий пример:

C:-F,G,H,!,P,Q,R.  /* 1 */
C:-S,T,U.          /* 2 */
?-A,B,C,D,E.

Можно выделить 3 основных случая использования отсечения.

1. Указание интерпретатору ПРОЛОГа, что найдено необходимое правило для заданной цели.
2. Указание интерпретатору ПРОЛОГа, что необходимо немедленно прекратить доказательство конкретной цели, не пытаясь рассматривать какие-либо альтернативы (конструкция "!,fail").
3. Указание интерпретатору ПРОЛОГа, что в ходе перебора альтернативных вариантов найдено необходимое решение, и нет смысла вести перебор далее.

Пример. Пусть необходимо написать правила для вычисления суммы ряда натуральных чисел 1, 2, ... N. Напрашивается пара следующих утверждений:

sum(1,1).                                    /* 1 */
sum(N,S):-N1 is N-1, sum(N1,S1), S is S1+N.  /* 2 */

?-sum(5,X).      X=15
;                в результате - бесконечная рекурсия!

sum(1,1):-!.                                 /* 1' */

?-sum(-5,X).     в результате - опять бесконечная рекурсия!

sum(N,_):-N=<0, !, fail.                  /* 0 */

Примером третьего случая использования отсечения может служить ПРОЛОГ-программа для игры в "крестики-нолики". В этой игре (как и во многих других) существует понятие "вынужденный ход", не подразумевающий альтернативы. Понятно, что код, отвечающий за анализ игровой позиции должен содержать отсечение в правилах, диагностирующих "вынужденный ход".

Следует отметить, что использование отсечения требует хорошего знания стратегии работы ПРОЛОГ-системы!

Классификация термов
var(X) - согласуется, если X - неконкретизированная переменная.
nonvar(X) - согласуется, если X - конкретизированная переменная.
atom(X) - согласуется, если X - атом.
integer(X) - согласуется, если X - число.
atomic(X) - согласуется, если X - атом или число.

Работа с утверждениями
asserta(X), assertz(X) - добавляют утверждение в ПРОЛОГ-программу, при этом значение X должно быть таким, чтобы могло интерпретироваться как утверждение.
retract(X) - удаляет из программы первое утверждение, соспоставимое (унифицируемое) с X.
Примечание. Рассмотренные предикаты необратимы, т.е. их действие не отменяется при возврате.
clause(X,Y) - X и Y сопоставляются с заголовком и телом имеющегося в программе утверждения К этому моменту X должен быть достаточно конкретизирован. При возврате - переход на следующее утверждение. Для фактов Y конкретизируется значением true.
Примечание. Напоминаем, что любое утверждение ПРОЛОГа - структура, где ":-", "?-", "," и т.п. - функторы, имеющие вид инфиксных операторов.

Работа со стуктурами
functor(S,F,N) - согласуется при условии, что S - структура с функтором F и количеством аргументов N. Используется а) для анализа существующих структур и б) для создания структур с заданными функтором и количеством аргументов.
arg(N,S,X) - сопоставляет N-ый аргумент структуры S с X.
S=..L - сопоставляет структуру S со списком L, первый элемент которого рассматривается как функтор, а остальные - как аргументы. Также используется двояко.
name(A,L) - сопоставляет атом A и список десятичных ASCII-кодов L.

Составные цели
"," - коньюнкция целевых утверждений.
";" - дизъюнкция целевых утверждений.
call(X) - согласуется, если согласуется X, рассматриваемое как целевое утверждение.
not(X) - согласуется, если не согласуется X, рассматриваемое как целевое утверждение.
bagof(T,G,L) - порождает список L всех объектов T, удовлетворяющих цели G, принимая во внимание одинаковость конкретизации остальных переменных цели G.
setof(T,G,L) - аналогичен bagof(), но дополнительно упорядочивает список L, исключая дублирующие элементы.
findall(T,G,L) - порождает список L всех объектов T, удовлетворяющих цели G, игнорируя различия в конкретизации остальных переменных цели G.

Ввод-вывод
write(X) - записывает терм X в текущий поток вывода.
nl - выводит символ "новая строка".
tab(N) - выводит N пробелов.
put(X) - выводит символ, имеющий десятичный ASCII-код X.
read(X) - читает очередной терм из входного потока, сопоставляя его с X (при этом читаемый терм должен заканчиваться точкой).
get0(X) - сопоставляет X и следующий символ из входного потока.
get(X) - то же, что и get0(X), но только для символов, имеющих графическое изображение.
skip(X) - пропускает символы входного потока, пока не встретится сопоставимый с X.
Примечание. Все предикаты ввода-вывода необратимы, т.е. их действие при возврате не отменяется, пересогласовать их невозможно.