Основы языка Пролог (стандарт)

Особенности языка

 

Пролог имеет два главных отличия от процедурных языков:

1) Программирование на Прологе по-преимуществу является символьным. Данные в этом языке – это символы, которые никак не интерпретируются, и числа. (исключение – числа).

2) Так как Пролог относится к парадигме декларативного программирования, алгоритмы решения задач не задаются. Формулируется лишь условие задачи, после чего она решается с помощью встроенного (в интерпретатор) универсального алгоритма логического вывода, основанного, как уже упоминалось, на входной линейной резолюции.

    Программа на Прологе состоит из описания предметной области и вопроса. Предметная область задается описанием объектов и отношений между ними с помощью фактов и правил. Факты и правила представляются хорновскими дизъюнктами: факты – унитарными позитивными дизъюнктами, правила – точными дизъюнктами. При этом с помощью фактов указываются тождественно истинные утверждения – представленные предикатами со значениями аргументов (термов), при которых они являются истинными. С помощью правил задаются средства установления новых фактов. Каждое правило интерпретируется так: если истинными являются все предикаты, представленные негативными литерами, то истинным считается и предикат, представленный позитивной литерой.

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

Характерными чертами языка Пролог считаются:

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

2) наличие встроенного механизма сравнения с образцом (для реализации процедуры унификации);

3) простые синтаксис и структура данных.

Синтаксис языка.

Синтаксическими элементами языка являются:

Термы: константы, переменные, сложные термы.

Константы: целые и вещественные числа, атомы (любые цепочки символов, не начинающиеся с заглавных букв или любые цепочки символов в кавычках).

Целые числа представляются последовательностями цифр с возможным знаком «+» или «-».

Вещественные числа представляются в двух форматах:

1) В виде десятичной дроби, например: 10.12, -0.25, +35.1234. В некоторых случаях целые числа могут интерпретироваться как десятичные дроби – это зависит от контекста, в котором находится число.

2) В виде мантиссы и десятичного порядка: <десятичная дробь>Е<целое>, например: 1.012E1, -0.95Е+3, 125Е-2.

Как видно из примеров, перед вещественными числами могут находиться знаки «+» или «-»  

Переменные: цепочки букв, цифр и знака подчеркивания («_»), начинающиеся с заглавной буквы или знака подчеркивания. Особая переменная – анонимная. Она представляется знаком подчеркивания.

Сложный терм это:

1) структура, состоящая из атома-предиката ( или функтора) и компонент, т.е. термов в скобках через запятую; при этом компоненты сами могут являться сложными термами; например информация о книгах библиотеки может состоять из следующих данных: автор, название, издательство, год выпуска – книга(“Л.Н. Толстой”, “Война и мир”, “Художественная литература”, “2002”). 

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

Константы и структуры представляют объекты предметной области, а списки – упорядоченные наборы объектов. Роль структур заключается в группировке некоторых объектов, представляющих составной объект.

База знаний, описывающая предметную область, задается фактами и правилами.

Факты – это отдельные предикаты, состоящие из имени предиката и, возможно, термов, представляющих его аргументы.

Правила имеют вид:

p ₁ (…): – p ₂ (…), …, p_n (…), n ≥ 2,

где p_i – предикаты.  

Приведем примеры простых баз знаний, пояснив кроме синтаксиса также их семантику.

Фрагмент словаря синонимов и антонимов может быть представлен следующей базой знаний:

synonym("храбрый","отважный").

synonym("храбрый","бесстрашный").

synonym("современный","новый").

synonym("редкий","неупотребительный").

antonym("храбрый","трусливый").

antonym("честный","бесчестный").

antonym("современный","старый").

antonym("редкий","частый").

Фрагмент описания предметной области «Дифференцирование», который представляет правило дифференцирования суммы, может быть представлен следующими фактом и правилом:

              diff(Х,Х,1).

              diff (U+V, X, A+B): – diff (U, X, A), diff (V, X, B).

Отметим, что в первом из этих примеров мы использовали только факты. Все они представляют два предиката, для имен которых использованы функторы synonym и antonym. Вы можете без труда заметить, что их компоненты подобраны так, что они действительно являются, соответственно, синонимами и антонимами друг друга в общепринятом понимании этих терминов. Во втором примере имеется факт diff(Х,Х,1). Он отражает простейшее правило дифференцирования, согласно которому производная по X функции F(X) = X равна 1. Правило второго примера интерпретируется так: если производная по X функции U равна A, а производная по X функции V равна B, то производная по X суммы U+V равна A+B.

Вопросы представляются в виде одного или нескольких предикатов, называемых целями:

?- p ₁ (…), p ₂ (…), …, p_n (…), n ≥ 1.

Список целей, заданный этим вопросом, таков:

p ₁ (…), p ₂ (…), …, p_n (…).

Если вопрос состоит из одного предиката, то он называется простым, в противном случае – составным. Активная цель – это первая цель списка (в нашем примере p ₁). После осуществления логического вывода активной цели, она исключается из списка, который в случае нашего примера примет вид:

p ₂ (…), …, p_n (…).

В этом случае говорят, что цель доказана или достигнута и активной становится цель p ₂. Работа заканчивается либо после достижения последней цели списка p_n (в случае наличия решений), либо при возникновении тупиковой ситуации, когда вывод какой-нибудь активной цели оказывается невозможным. 

Программы на Прологе состоят из двух частей – описания предметной области и вопроса:

1) Факты и правила, описывающие предметную область.

2) Вопрос.

Например, приписав вопрос

?- synonym("храбрый",X), antonym("храбрый", Y)

к базе знаний первого примера, получим программу.

Ответы на вопросы пользователей формируются в процессе выполнения программ и в разных версиях языка представляются по-разному. Мы примем следующий вариант. Если ответ должен быть положительным или отрицательным, то он представляется в форме Yes и No соответственно. Если же требуется указать выполненные в процессе логического вывода подстановки, вместо переменных, входящих в цели, то они перечисляются в ответе, после чего указывается число найденных решений.

Например, ответ на приведенный выше вопрос выглядит так:

X = "отважный", Y = "трусливый"

X = "бесстрашный", Y = "трусливый" 

2 Solutions

   

Типы вопросов.

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

Различные варианты вопросов удобно рассмотреть на примере предметной области, представляющей родственные отношения (для удобства будем нумеровать предложения, описывающие предметную область).

 

1) мать («Вера», «Юлия»); 2) мать («Вера», «Павел»); 3) мать («Мария», «Петр»); 4) мать («Анна», «Вера»); 5) отец («Петр», «Юлия»); 6) отец («Петр», «Павел»);

7) отец («Иван», «Петр»); 8) отец («Андрей», «Вера»); 9) дед (X,Y): – отец(X,Z), мать (Z,Y); 10) дед (X,Y): – отец(X,Z), отец (Z,Y); 11) бабка (X,Y): – мать(X,Z), мать (Z,Y); 12) бабка (X,Y): – мать(X,Z), отец (Z,Y);

 

Граф родственных отношений, представленный этой таблицей, выглядит следующим образом (верхние вершины дуг – родители, нижние – дети):

 

Рассмотрим типы вопросов.

1) Вопросы, в целях которых отсутствуют переменные.

С помощью таких вопросов пользователь может спросить, верно или нет некоторое предположение (свойство, отношение). Например:

«Верно ли, что отцом Юлии является Петр?» На Прологе:

? – отец(«Петр», «Юлия»)

Или: «Верно ли, что Павел является дедушкой Марии?» На Прологе:

? – дед(«Павел», «Мария»)

На первый вопрос должен быть дан положительный ответ, который система выдаст в виде: Yes. Ответ на второй вопрос отрицательный: No.

Вопросы этого типа могут быть и составными, например:

«Верно ли, что Анна является бабушкой, а Андрей дедушкой Юлии?»

? – бабка(«Анна», «Юлия»), дед(«Андрей», «Юлия»).

Ответ: Yes.

Или: «Верно ли, что отцом и матерью Петра являются Иван и Мария?»

? – отец(«Иван», «Петр»), мать(«Мария», «Петр»).

Ответ: No.

Заметим, что во втором вопросе первая цель представлена правильным предположением, а вторая – неправильным. Так как для положительного ответа требуется, чтобы все предположения были правильными, в данном случае дается отрицательный ответ.

2) Вопросы с использованием переменных (не анонимных).

Семантика этих вопросов совсем другая. С их помощью пользователь может узнать, для каких объектов предметной области выполнены свойства или отношения, указанные в вопросе. Например:

«Кто является отцом Юлии?». На Прологе:

? –   отец (Х, «Юлия»).

Или: «Укажите дедушек и бабушек Павла». На Прологе:

? – дед(Х, «Павел»), бабка(Y, «Павел»).

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

Х = «Петр».

1 Solution.

На второй вопрос будет получен ответ: 

Х = «Андрей», Y = «Анна»

Х = «Иван», Y = «Мария».

2 Solutions.

Вопрос может быть таким, что вариантов ответов на него нет, например: «Кто является дедушкой Петра?»

? – дед(Х, «Петр»).

Тогда ответ системы будет выглядеть так:

No Solution.

3) Вопросы, в которых используется анонимная переменная.

Анонимная переменная играет в Прологе особую роль. С ее помощью пользователь может узнать, существуют ли в предметной области такие объекты, для которых его предположение оказывается истинным. При этом его интересует лишь существование таких объектов, но не они сами. Например: «Известен ли хоть один дедушка Юлии?» Или: «Указаны ли в предметной области внуки Петра?» На Прологе:

? – дед(_, «Юлия»).

? – дед(«Петр», _).

Ответы на подобные вопросы представляются в такой же форме, как в случае вопросов первого типа: Yes и No соответственно.

Как видно из приведенных типов вопросов, при отсутствии анонимных переменных их обработка предполагает полный перебор выводов (так как необходимо найти все варианты ответов). Если в вопросе используется анонимная переменная, перебор может быть сокращен. Так, обрабатывая вопрос? – дед(_, «Юлия»),системе достаточно обнаружить одного деда, хотя как видно из схемы родственных отношений примера, в БЗ их двое.

Приведем пример работы алгоритма логического вывода, представив ее в виде таблицы со следующими полями:

1) №№ варианта и шага вывода. Так как потребуется перебор, будет осуществляться возврат на уже выполненные шаги с целью поиска других вариантов их выполнения. Возврат будет осуществляться с помощью процедуры бэктрекинга.

2) Список целей.

3) № предложения (факта или правила), выбранного для резолюции.

4) Унификатор

5) Стек возвратов, используемый процедурой бэктрекинга. Задается в виде: пар: № шага, на который нужно вернуться, и № первого предложения, с которого нужно продолжить просмотр.

6) Примечания.

Пусть пользователь ввел вопрос:? – дед(«Иван»,Х). Работа алгоритма логического вывода может быть представлена следующей таблицей:  

  

№№ шаг. и вар.	список целей	№ предл.	унификатор	Стек возвратов	примеч.
1.1	дед(«Иван», Х)	9	{(Х, «Иван»), (Y, Х)}	(1,10)
2.1	отец(«Иван»,Z), мать(Z, Х)	7	{(Z, «Петр»)}	(1,10), (2,8)
3.1	мать(«Петр», Х)	–	–	(1,10), (2,8)	Тупик
2.2	отец(«Иван»,Z), мать(Z, Х)	–	–	(1,10)	Тупик
1.3	дед(«Иван», Х)	10	{(Х, «Иван»), (Y, Х)}	(1,11)
2.3	отец(«Иван»,Z), отец(Z, Х)	7	{(Z, «Петр»)}	(1,11), (2,8)
3.3	отец(«Петр», Х)	5	{(Х, «Юлия»)}	(1,11), (2,8), (3,6)
4.3	L	–	–	(1,11), (2,8), (3,6)	Получен 1-ый вывод
3.4	отец(«Петр», Х)	6	{(Х, «Павел»)}	(1,11), (2,8), (3,7)
4.4	L	–	–	(1,11), (2,8), (3,7)	Получен 2-ый вывод
3.5	отец(«Петр», Х)	–	–	(1,11), (2,8), (3,8)	Тупик
2.6	отец(«Иван»,Z), мать(Z, Х)	–	–	(1,11)	Тупик
1.7	дед(«Иван», Х)	­–	–	–	Тупик.

 

Так как после шага 1.7 стек возвратов оказался пустым, полный перебор осуществлен и алгоритм логического вывода заканчивает работу. В результате будет сформирован ответ:

 Х = «Юлия»

 Х = «Павел»

2 Solutions.