Логическое программирование

Пролог ( Prolog, программирование в логике) - один из наиболее широко используемых языков логического программирования. Как и для других декларативных языков, при работе с ним мы описываем ситуацию (правила и факты) и формулируем цель (запрос), позволяя интерпретатору Пролога найти решение задачи за нас.

Под интерпретатором Пролога мы будем понимать механизм решения задачи при помощи языка Пролог. Другими словами, интерпретатор языка Пролог - это исполнитель Пролог -программ, т. е. та "активная сила", которая выполняет программы, написанные на Прологе.

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

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

Существует большое количество реализаций языка Пролог, как коммерческих, так и свободно распространяемых. Мы будем ориентироваться на SWI-Prolog, разработанный в университете города Амстердам. Возможностей данной реализации вполне достаточно для первоначального знакомства с основами логического программирования.

SWI-Prolog распространяется под лицензией GPL, что обеспечивает возможность его использования без нарушений чьих-либо коммерческих интересов. Эта версия языка Пролог доступна как пользователям ОС Linux, так и пользователям Windows.

Классическая логика и язык Пролог

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

Ранее мы уже познакомились с частью логики, называемой исчислением высказываний. Но исчисление высказываний не дает возможности выразить многие факты и рассуждения, которыми пользуются в обыденной жизни. Например, рассмотрим классическое рассуждение:

Все люди смертны (p); 
Сократ - человек (q); 
следовательно, (->) 
Сократ смертен (r).

Это рассуждение верное, но его невозможно доказать в рамках теории высказываний. Мы можем записать формулу (pq)->r, но доказать ее истинность уже не сможем. Таким образом, логика высказываний не позволяет достаточно точно выразить рассматриваемое рассуждение. Это связано с тем, что она рассматривает каждое высказывание как неделимый объект, в то время как многие из высказываний зависят от неких параметров.

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

Для всех x, если x является человеком, 
то x является смертным; 
Сократ является человеком; 
(следовательно) 
Сократ является смертным.

Изучение исчисления предикатов не является нашей задачей, однако, для того, чтобы применять язык логического программирования, не обязательно знать логику предикатов: она уже встроена в него. Достаточно изучить сам язык и привыкнуть к его выразительным средствам.

Язык Пролог, самый известный из представителей семейства языков логического программирования, вырос из работ Алана Колмерауэра (A. Colmerauer) по обработке естественного языка и независимых работ Роберта Ковальского (R. Kowalski) по приложениям логики к программированию. Дэвиду Уоррену (D. Warren) и его коллегам из Эдинбургского университета удалось осуществить достаточно эффективную реализацию Пролога. Имя Уоррена вошло в историю логического программирования. В его честь названа базовая техника реализации Пролога, получившая название абстрактной машины Уоррена.

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

Для запуска Пролога, наберите в командной строке pl и нажмите Enter. На экране появится приглашение для ввода запросов:

?-

Запрос (вопрос) вводится после приглашения и обязательно заканчивается точкой, например,

?- 5+4<3.
No

Пролог анализирует запрос и выдает ответ Yes (Да) в случае истинности утверждения и No (Нет) в противном случае или когда ответ не может быть найден.

Хранят программы на языке Пролог в текстовых файлах, чаще всего имеющих расширение pl, например, example1.pl. Для того чтобы Пролог мог оперировать информацией, содержащейся в файле, он должен ознакомится с его содержимым (проконсультироваться с ним). Это можно сделать несколькими способами. При использовании первого варианта в квадратных скобках записывается имя файла (без pl ), например,

?- [example1].

В случае удачного завершения этой операции будет выдано сообщение, аналогичное следующему:

% example1 compiled 0.00 sec, 612 bytes
Yes

В противном случае будет выдан список ошибок ( ERROR ) и/или предупреждений (Warning).

Второй способ состоит в вызове встроенного предиката consult, которому в качестве аргумента передается имя файла (также без расширения), например:

?- consult(example1).

Расширение pl часто используется для файлов, содержащих программы на языке программирования Perl, поэтому можно встретить и другие расширения для файлов с программами на Прологе. Для загрузки файлов с расширениями, отличными от pl, все имя файла следует обязательно заключать в апострофы:

?- consult('example2.prolog').
?- ['example2.prolog'].

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

?- [example1, 'example2.prolog'].

Важно помнить, что все запросы должны заканчиваться точкой. Если вы забудете ее поставить, то Пролог выведет символ '|' и будет ожидать дальнейшего ввода. В этом случае надо ввести точку и нажать клавишу Enter:

?- [example1]
| .
Yes

Термы и объекты

Программа на языке Пролог обычно описывает некую действительность. Объекты (элементы) описываемого мира представляются с помощью термов. Терм интуитивно означает объект. Существует 4 вида термов: атомы, числа, переменные и составные термы. Атомы и числа иногда группируют вместе и называют простейшими термами.

Атом - это отдельный объект, считающийся элементарным. В Прологе атом представляется последовательностью букв нижнего и верхнего регистра, цифр и символа подчеркивания '_', начинающейся со строчной буквы. Кроме того, любой набор допустимых символов, заключенный в апострофы, также является атомом. Наконец, комбинации специальных символов + - * = < > : также являются атомами (следует отметить, что набор этих символов может отличаться в различных версиях Пролога).

Пример

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

b, abcXYZ, x_123, efg_hij, коля, слесарь,
'Это также атом Пролога',
+, ::, <---->, ***

Числа в Прологе бывают целыми (Integer) и вещественными (Float).

Синтаксис целых чисел прост, как это видно из следующих примеров: 1, 1313, 0, -97. Не все целые числа могут быть представлены в машине, их диапазон ограничен интервалом между некоторыми минимальным и максимальным значениями, определенными конкретной реализацией Пролога. SWI-Prolog допускает использование целых чисел в диапазоне от -2147483648 (-2³¹) до 2147483647 (2³¹-1).

Синтаксис вещественных чисел также зависит от конкретной реализации. Мы будем придерживаться простых правил, понятных из следующих примеров: 3.14, -0.0035, 100.2. При обычном программировании на Прологе вещественные числа используются редко. Причина этого кроется в том, что Пролог - язык, предназначенный в первую очередь для обработки символьной, а не числовой информации. При символьной обработке часто используются целые числа, нужда же в вещественных числах невелика. Везде, где можно, Пролог старается привести число к целому виду.

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

X, _4711, X_1_2, Результат, _x23, Объект2, _

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

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

итого(клиент(X,23,_), 71)
'Что случилось?'(ничего)

При задании имен термов предпочтительнее использовать мнемонические ("говорящие") имена, так как терм a(ж), например, гораздо менее информативен, чем терм aвтор(жюль_верн).

Еще одной важной структурой данных в Прологе является список. Мы познакомимся с ним позднее. Сейчас отметим только один из видов списков - список символов. Такие списки могут быть представлены в виде строк, например, первый аргумент составного терма возраст("Борис",10) - строка. При записи строки заключаются в кавычки.

Факты

Программировать на Прологе - значит описывать некий мир. Программа на этом языке состоит из множества фраз, задающих взаимосвязь между термами. Каждый терм обозначает ту или иную сущность, принадлежащую миру. Один из способов описания - это задание фактов.

Факт - это утверждение о том, что соблюдается некоторое конкретное отношение. Он является безусловно верным. В разговорной речи под фактом понимается нечто вроде "Сегодня солнечно" или "Васе 10 лет". На Прологе это запишется в виде

'Сегодня солнечно'.
'Васе 10 лет'.

Если вы сохраните эти факты в файле и затем загрузите его, то можно задавать вопросы интерпретатору Пролога (напомним, что запрос вводится после приглашения Пролога, которое в большинстве версий имеет вид ?- ) , например,

?- 'Сегодня солнечно'.
Yes

?- 'Васе 10 лет'.
Yes

?- 'Сегодня солнечно', 'Васе 10 лет'.
Yes

Запятая между фактами в последнем запросе означает операцию логического и (конъюнкцию).

Такая форма записи соответствует логике высказываний, возможности которой, как уже говорилось, достаточно ограничены. Мы не можем задать, например, вопрос о том, сколько лет Васе. Гораздо удобнее использовать параметризованные факты, работу с которыми поддерживает логика предикатов. На Прологе факт может быть записан в виде предиката, аргументы которого являются символьными или числовыми константами.

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

имя_предиката(аргументы).

Аргументы перечисляются через запятую и представляют собой какие-то объекты или свойства объектов, а имя предиката обозначает связь или отношение между аргументами. Предикат однозначно определяется парой: имя и количество аргументов. Два предиката с одинаковым именем, но различным количеством аргументов, считаются различными. Количество параметров предиката называется его арностью (arity). При описании предиката арность указывают после его имени, разделяя их символом '/' (слэш).

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

Пример

Факт "Коля работает слесарем" на Прологе запишется следующим образом:

профессия(коля, слесарь).

Здесь предикат профессия/2 имеет два аргумента: первый означает имя человека, а второй - профессию. Факт "Борису 10 лет" можно представить в виде:

возраст("Борис", 10).

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

имя факта начинается со строчной буквы; 
запись каждого факта заканчивается точкой.

В приведенных выше примерах профессия/2 и возраст/2 - предикаты (составные термы), коля и слесарь - атомы, 10 - число, "Борис" - строка. Подробнее о видах термов Пролога рассказывается в следующем разделе.

База данных на Прологе - это совокупность фактов. В процессе работы в базу данных можно добавлять новые факты, удалять или изменять старые.

Пример

Составим базу данных из следующих фактов: "слон больше, чем лошадь", "лошадь больше, чем осел", "осел больше, чем собака" и "осел больше, чем обезьяна":

больше(слон, лошадь).
больше(лошадь, осел).
больше(осел, собака).
больше(осел, обезьяна).

Мы использовали предикат больше/2, имеющий два параметра.

Сохраним эту базу данных в текстовом файле и затем познакомим Пролог с ней. Теперь можно формулировать запросы к интерпретатору Пролога:

?- больше(слон, лошадь).
Yes

?- больше(лошадь, слон).
No

Задания

цвет(машина, красный).
цвет(светофор, зеленый).
цвет(солнце, желтый).
цвет(море, синий).

Сохраните ее в том же файле и сформулируйте несколько запросов к данной базе данных.

Запросы к базе данных

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

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

Пример

?- больше(слон, лошадь), больше(лошадь,осел).
Yes

?- больше(слон, собака).
No

Использование переменных в запросах позволяет задавать более сложные вопросы. Предположим, например, что мы хотим определить, какие животные больше осла? В следующем запросе переменная X обозначает искомый ответ:

?- больше(X, осел).
X = лошадь
Yes

При обработке запроса переменная X приняла значение "лошадь". Просматривая базу данных, интерпретатор обнаружил факт, утверждающий, что лошадь больше осла, и запрос был успешно выполнен.

Запросы с переменными могут иметь более одного решения. Первым всегда выводится то из решений, которое находится ближе к началу базы данных. Если нам достаточно только одного ответа, то можно нажать Enter и закончить поиск. В случае, если мы захотим получить очередной ответ, нужно нажать клавишу ; (точка с запятой), и Пролог начнет поиск других вариантов ответа на запрос. Сообщение "No" говорит об отсутствии очередного решения.

Пример

?- больше(осел, Х).
X = собака;
X = обезьяна;
No

?- больше(X,Y).
X = слон 
Y = лошадь;

X = лошадь
Y = осел;

X = осел
Y = собака;

X = осел
Y = обезьяна;
No

Задания

Сформулируйте запросы к измененной базе данных.

Унификация

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

Унификация термов, которыми являются аргументы, описывается приводимыми ниже правилами. В примерах используется предикат =, который пытается унифицировать свои аргументы.

?- X=коля.
X=коля
Yes

?- X=Y.
X = _G161
Y = _G161
Yes

?- автор(пушкин)=_.
Yes

?- коля=коля.
Yes

?- отец(борис)=отец(X).
X = борис 
Yes
?- дедушка(борис, Y)=отец(X).
No

Пример

Термы больше(Х, собака) и больше(осел, собака) унифицируются, потому что переменная X может быть конкретизирована атомом осел:

?- больше(Х,собака) = больше(осел,собака).
X = осел
Yes

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

?- p(X,2,2) = p(1,Y,X).
No

Если в этом примере вместо X мы используем анонимную переменную _, то унификация будет возможна, потому что при каждом использовании _ создается новая переменная. Смысл анонимности в том, что мы предоставляем Прологу возможность генерации имени для данной переменной и нам не нужны ни ее имя, ни ее значение. Переменная Y во время унификации конкретизируется значением 2:

?- p(_,2,2) = p(1,Y,_).
Y = 2
Yes

Пример

В следующем запросе унификация возможна, хотя и нет специфических переменных, которые могли бы быть связаны или унифицированы (как в предыдущих примерах):

?- f(a,g(X,Y)) = f(X,Z), Z = g(W,h(x)).
X = a
Y = h(x)
Z = g(a, h(x))
W = a
Yes

Правила

Кроме фактов программы на языке Пролог могут содержать правила, позволяющие получать дополнительные знания о том мире, который описывает программа. Правило задает новый предикат через определенные ранее.

Правило состоит из головы (предиката) и тела (последовательности предикатов, разделенных запятыми). Голова и тело разделены знаком :- и, подобно каждой фразе Пролога, правило должно заканчиваться точкой. Запятая в теле правила означает конъюнкцию (, логическое и ).

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

Пример

Правило, определяющее отношение ребенок/2 через отношение отец/2, запишется следующим образом:

ребенок(X, Y) :- отец(Y, X).

Это означает, что если человек Y является для человека X отцом, то X является ребенком Y. Здесь X и Y - переменные. Напомним, что запись ребенок/2 показывает, что предикат ребенок является функцией от двух аргументов.

Пример

Определим отношение мать/2 через отношения родитель/2 и женщина/1 следующим образом: матерью X для человека Y является его родитель женского рода.

мать(X, Y) :- родитель(X, Y), женщина(X).

Предикаты отличаются друг от друга не только именем, но и количеством аргументов. Можно, например, определить отношение мать/1 следующим образом:

мать(X) :- родитель(X, _), женщина(X).

Так как нам в данном предикате не важно, чьим родителем является данная женщина, то мы использовали анонимную переменную.

?- мать(X, Y).
X=анна
Y=юлия
Yes

?- мать(X).
X=анна
Yes

Пример

Определим отношение дедушка/2:

дедушка(X, Y) :- отец(X, Z), отец(Z, Y).
дедушка(X, Y) :- отец(X, Z), мать(Z, Y).

Эти правила утверждают, что дедушкой X для человека Y является отец человека Z, который в свою очередь является отцом или матерью человека Y.

Задания

женщина(анна).    мужчина(борис).       
женщина(юлия).	  мужчина(олег).  
женщина(галина).  мужчина(антон).      
женщина(елена).   мужчина(павел).

родитель(борис,павел).  %         кто  чей
родитель(анна,юлия).    родитель(анна,антон).
родитель(анна,борис).   родитель(олег,юлия).
родитель(олег,антон).   родитель(олег,борис).
родитель(галина,анна).  родитель(галина,елена).

Рекурсивные процедуры

Рекурсия в большинстве языков программирования - это такой способ организации обработки данных, при котором программа (процедура) вызывает сама себя непосредственно, либо с помощью другой программы (процедуры).

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

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

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

больше(слон, лошадь).
больше(лошадь, осел).
больше(осел, собака).
больше(осел, обезьяна).

Выполним запрос к базе данных

?- больше(осел, собака).
Yes

Цель больше(осел, собака) была достигнута потому, что этот факт был сообщен Прологу при загрузке базы. Теперь проверим, больше ли обезьяна слона?

Нет, не больше. Мы получили такой ответ, какой и ожидали: соответствующий запрос, а именно больше(обезьяна, слон) не подтвердился. Но, что случится, если мы зададим вопрос по-другому?

?- больше(слон, обезьяна).
No

Таким образом, слоны не больше, чем обезьяны. Полученный результат совершенно не согласуется с нашими представлениями о мире, но если посмотреть на базу данных, то легко заметить, что в ней действительно ничего не сказано об отношениях между слонами и обезьянами. Однако, мы знаем, что слоны больше, чем лошади, которые в свою очередь больше, чем ослы, которые больше обезьян, поэтому слоны также должны быть больше, чем обезьяны.

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

больше(слон, обезьяна).

Для нашего маленького примера это означает добавление еще 5 фактов. Однако гораздо лучшим решением будет добавление в программу нового отношения, которое мы назовем больше_2. Животное X больше, чем животное Y, если это определено как факт (первое правило) или существует животное Z, для которого определен факт, что животное X больше, чем животное Z и может быть показано, что животное Z больше, чем животное Y (второе правило). На Прологе это запишется так:

больше_2(X, Y) :- больше(X, Y).
больше_2(X, Y) :- больше(X, Z), больше(Z, Y).

Если в цепочке участвуют не три, а большее число объектов, то придется добавить новые правила:

больше_2(X, Y) :- больше(X, Z1), больше(Z1, Z2), 
                  больше(Z2, Y).
больше_2(X, Y) :- больше(X, Z1), больше(Z1, Z2),
                  больше(Z2, Z3), больше(Z3, Y).
...

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

Поэтому воспользуемся более корректной и элегантной формулировкой. Ключевая идея здесь - определить отношение больше_2 с помощью его самого. Теперь второе (и последнее!) правило выглядит так:

больше_2(X, Y) :- больше(X, Z), больше_2(Z, Y).

Таким образом, итоговая программа будет иметь вид

больше_2(X, Y) :- больше(X, Y). 
больше_2(X, Y) :- больше(X, Z), больше_2(Z, Y).

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

ERROR: Out of local stack

Если теперь в запросе использовать предикат больше_2 вместо больше, то программа будет работать так, как и предполагалось:

?- больше_2(слон, обезьяна).
Yes

Интерпретатор всегда просматривает базу данных сверху вниз. Поэтому он анализирует сначала первую фразу процедуры больше_2 и пытается унифицировать каждый аргумент запроса с соответствующим аргументом этой фразы. Это происходит при помощи сравнения запроса с началом правила больше_2(X, Y) (т. е. с его головой). После этого двум переменным присваиваются значения: X = слон и Y = обезьяна.

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

В данном случае Пролог не может найти в базе данных факта больше(слон, обезьяна) и переходит к рассмотрению второго правила. Оно гласит, что для того, чтобы получить ответ на вопрос больше_2(X,Y) (с фиксированными значениями переменных, то есть больше_2(слон, обезьяна)), Пролог должен ответить на два подвопроса больше(X, Z) и больше_2(Z, Y), опять же с соответствующими значениями переменных. Процесс просмотра базы знаний с самого начала повторяется до тех пор, пока факты, составляющие цепочку между слон и обезьяна, не будут найдены, а запрос успешно обработан.

Любая рекурсивная процедура должна включать по крайней мере по одной из ниже перечисленных компонент.

Задание

Дана база данных "Родители", в которой предикат родитель(коля, андрей) означает, что Коля является родителем Андрея:

родитель(коля, андрей). 
родитель(андрей, саша).
родитель(виктор, федор).
родитель(виктор, петр).
родитель(петр, елена).

Используя рекурсию, определите отношение предок/2 через отношение родитель/2. Будем говорить, что некоторый X является отдаленным предком некоторого Y, если между X и Y существует цепочка людей, связанных между собой отношением родитель - ребенок.

Базы знаний

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

Встроенные предикаты используются так же, как и определяемые пользователем предикаты. Единственное ограничение - встроенный предикат не может являться головой правила или появляться в факте.

Одним из наиболее часто используемых встроенных предикатов является предикат not/1 (отрицание). Этот предикат истиннен, если его аргумент ложен, и наоборот. Можно использовать и другую форму записи данного предиката \+.

Пример

Если мы определим правило

ложь(X) :- not(X).
ложь1(X) :- \+(X).

то следующие запросы будут эквивалентны:

?- not(больше(собака, лошадь)).
Yes;

?- ложь(больше(собака, лошадь)).
Yes

Другим часто используемым встроенным предикатом является =/2 (унификация): =(X, Y). Этот предикат допускает более удобную форму записи X = Y. Значение этого предиката истинно, если термы X и Y удается унифицировать.

На предикат not/1 похож встроенный предикат \=, зависящий от двух аргументов. Утверждение X \= Y эквивалентно утверждению not(X = Y).

Иногда бывает полезно использовать предикаты, про которые заранее известно, истинны они или ложны. Для этих целей используют предикаты true/0 и fail/0. Предикат true всегда истинен, в то время как fail всегда ложен.

Встроенный предикат read/1 позволяет считывать термы с клавиатуры. При этом приглашение Пролога ?- меняется на |:. Вводимый терм должен обязательно заканчиваться точкой.

Пример

?- read(Name), read(Age).
|: коля. 15.

Name = коля
Age = 15
Yes

?- read(X), больше_2(X,Y).
|: осел.

X = осел
Y = собака ;
 
X = осел
Y = обезьяна ;
No

Если при обработке запросов Пролога вы пожелаете получить более подробный вывод, то для этих целей можно использовать предикат write/1. Аргументом этого предиката может являться любой допустимый терм Пролога. В случае, когда аргументом является переменная, будет напечатано ее значение.

Выполнение предиката nl/0 осуществляет перевод строки: последующий вывод начнется с новой строки. Предикат tab/1 выводит количество пробелов, определяемое его аргументом.

Пример

?- write('Hello World!').
Hello World!
Yes

?- write('Hello'), nl, tab(5), write('World!').
Hello
     World!
Yes

?- X = слон, write(X), nl.
слон

X = слон
Yes

В последнем примере сначала переменная X унифицируется с атомом слон, а затем значение переменной X, т. е. слон, выводится на экран при помощи предиката write/1. После перехода на новую строку Пролог выдает отчет об унифицированной переменной, т. е. печатает X = слон.

Большинство Пролог-систем предоставляет доступ к справочной информации при вызове предиката help/1. Примененный к терму (обычно представляющему имя встроенного предиката) он осуществляет вывод краткого описания этого терма.

Пример

?- help(write).
write(+Term)
  Write Term to the current output, using brackets and operators 
  where appropriate. See feature/2 for contrillong   floating point
  output format.

write(+Stream, +Term) 
  Write Term to Stream.
Yes

И, напоследок, поговорим о комментариях. Комментарии никак не влияют на выполнение программы, но при правильном их использовании они оказываются весьма существенной частью исходного текста. Несколько удачно расположенных строк с комментариями могут оказать человеку, читающему программу, большую помощь. Пролог игнорирует произвольное число строк, заключенное между символами /* и */. Все, что находится между % и концом строки, также рассматривается как комментарий:

Пример

/* Это 
        комментарий */

% Это тоже комментарий

Решение логических задач

Интерпретатор Пролога можно заставить решать логические задачи, что недоступно большинству процедурных языков.

Многие логические задачи связаны с рассмотрением нескольких конечных множеств с одинаковым количеством элементов, между которыми устанавливается взаимно-однозначное соответствие. На языке Пролог эти множества можно описывать как базы данных, а зависимости между объектами устанавливать с помощью правил.

Пример

В автомобильных гонках три первых места заняли Алеша, Петя и Коля. Какое место занял каждый из них, если Петя занял не второе и не третье место, а Коля - не третье?

Традиционным способом задача решается заполнением таблицы.По условию задачи Петя занял не второе и не третье место, а Коля - не третье. Это позволяет поставить символ '-' в соответствующих клетках. Между множеством имен участников гонки и множеством мест должно быть установлено взаимно-однозначное соответствие. Поэтому определяем занятое место сначала у Пети, затем у Коли и, наконец, у Алеши. В соответствующих клетках проставляем знак '+'. В каждой строке и каждом столбце должен быть только один такой знак.

Из последней таблицы следует, что Алеша занял третье место, Петя - первое, Коля - второе.

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

/* База данных имен */
имя(алеша).
имя(петя).
имя(коля).

/* База данных призовых мест  */
место(первое).
место(второе).
место(третье).

/* Устанавливаем взаимно-однозначное соответствие
между базами данных, X - элемент из базы данных имен, 
Y - элемент из базы данных занятых мест */

/* Петя занял не второе и не третье место */
соответствие(X, Y) :- имя(X),  X=петя,  
         место(Y), not(Y=второе), not(Y=третье).

/* Коля занял не третье место */
соответствие(X, Y) :- имя(X), X=коля, 
         место(Y), not(Y=третье).

соответствие(X, Y) :- имя(X),  X=алеша, место(Y).

/* У всех ребят разные места */
решение(X1,Y1,X2,Y2,X3,Y3) :- 
         X1=петя, соответствие(X1,Y1), 
         X2=коля, соответствие(X2,Y2),
         X3=алеша, соответствие(X3,Y3), 
         Y1\=Y2, Y2\=Y3, Y1\=Y3.

Для получения ответа следует выполнить запрос

?- решение(X1,Y1,X2,Y2,X3,Y3).

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

Пример

Витя, Юра и Миша сидели на скамейке. В каком порядке они сидели, если известно, что Миша сидел слева от Юры, а Витя слева от Миши.

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

/* Миша сидел слева от Юры  */
слева(юра,миша).

/* Витя сидел слева от Миши */
слева(миша,витя).

Правило для установления следования объектов друг за другом будет таким:

/* Объекты X, Y и Z образуют ряд,
если X слева от Y и Y слева от Z */

ряд(X, Y, Z) :- слева(Y, X), слева(Z, Y).

Количество аргументов в голове данного правила равно количеству объектов в задаче. Запрос ?- ряд(X, Y, Z). даст нам решение задачи.

Задание

Решите следующие логические задачи с помощью интерпретатора Пролога.

Арифметические выражения

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

Еще раз отметим, что Пролог старается скрыть различие между арифметикой целых и вещественных чисел везде, где это можно.

Для вычисления арифметических выражений в Прологе используется встроенный бинарный оператор is, который интерпретирует правый терм как арифметическое выражение, после чего унифицирует (если возможно) результат вычисления с левым термом (обычно с переменной). Приоритет выполнения арифметических операций является традиционным. Круглые скобки используются для изменения порядка вычислений. В следующих примерах переменная X унифицируется со значениями арифметических выражений:

?- X is 2.5 + 2.5.
X = 5
Yes

?- X is 4/(2+1).
X =  1.33333
Yes

?- X is cos(3*pi).
X = -1
Yes

?- 1 is sin(pi/2).
Yes

?- 1.0 is sin(pi/2).
No

Поясним несколько неожиданный ответ Пролога в последнем запросе. Значение sin(pi/2) автоматически округляется предикатом is до целого значения 1, которое не удается унифицировать с вещественным числом 1.0. Предикат float заставит считать значение sin(pi/2) вещественным числом:

?- 1.0 is float( sin(pi/2)).
Yes

Для сравнения арифметических выражений используется ряд операторов. Цель X > Y (больше) будет успешна, если выражение X будет соответствовать большему числу, чем выражение Y.

Аналогично используются операторы < (меньше), =< (меньше или равно), >= (больше или равно), =\= (не равно) и =:= (арифметически равный). Различия между операторами =:= и = очень существенны. Первый оператор сравнивает значения арифметических выражений, тогда как последний пытается унифицировать их.

Пример

?- 2 ** 3 =:= 3 + 5.
Yes

?- 2 ** 3 = 3 + 5.
No

?- 1.0 = float(sin(pi/2)).
No

?- 1.0 =:= sin(pi/2).
Yes

Заметьте, что цель X =:= Y будет истинна, даже если один из термов есть целое число, а другой - равное ему вещественное.

Пример

Порядок подцелей в запросе влияет на его результат:

?- X is 4+Y, Y=3. 
ERROR: Arguments are not sufficiently instantiated  

?- Y=3, X is 4+Y.
Y = 3
X = 7
Yes

В первом запросе сообщение об ошибке появилось потому, что первая подцель запроса ( X is 4+Y ) потерпела неудачу, т. к. в момент ее обработки невозможно вычислить выражение 4+Y.

Задание

Какой ответ выдаст интерпретатор Пролога на следующие запросы?

Примеры программ

Рассмотрим некоторые программы, демонстрирующие обработку числовых данных. Отметим важную особенность процедур, создаваемых на языке Пролог: они, в отличии от встроенных функций, не могут появляться в арифметических выражениях. Если требуется, например, переменной R присвоить значение, равное умноженному на три большему из двух выражений X и Y, то, используя определенную ниже процедуру максимум, это можно записать так:

максимум(X,Y,Z), R is 3*Z.

(см. примеры 1.1)

максимум(X,X,X).
максимум(X,Y,X):- X>Y.
максимум(X,Y,Y):- X<Y.

гипотенуза(X,Y,Z):- number(X), number(Y), Z is sqrt(X**2 + Y**2).

мин_гип(A1,B1,A2,B2,Min):-
    гипотенуза(A1,B1,C1),
    гипотенуза(A2,B2,C2),
    Min is min(C1,C2).

сумма(X,Y):- integer(X), X<10, Y is X.
сумма(X,Y):- integer(X), X1 is X//10, сумма(X1,Y1),  
             Z is X mod 10, Y is Y1+Z.

печать_суммы:-  write('Введите число (не забудьте точку в конце): '),
    read(X), nl,
    write('Сумма цифр введенного числа равна '),
    сумма(X,Y), write(Y), nl.

факт(1,1).
факт(N,R):- integer(N), N>1, N1 is N-1, 
            факт(N1,R1), R is N*R1.

сумма_списка([],0).
сумма_списка([H|T],S):- сумма_списка(T,S1), number(H), S is S1+H.

Пример

Написать процедуру, вычисляющую максимум из двух чисел.

максимум(X,X,X).
максимум(X,Y,X):- X>Y.
максимум(X,Y,Y):- X<Y.

В предикате максимум/3 третий аргумент является максимумом из двух чисел - первого и второго его аргументов. Смысл каждого из правил данной процедуры вполне очевиден. Посмотрим на реакцию интерпретатора Пролога на запросы, содержащие данный предикат.

?- максимум(20,50,X).
X = 50
Yes

?- максимум(100,50,X).
X = 100
Yes

?- максимум(X,50,100).
X = 100
Yes

Последний ответ показывает, что наш предикат позволяет находить ответ на вопросы типа: "Каково должно быть число, чтобы максимум из искомого числа и числа 50 равнялся бы 100?".

Как вы думаете, почему был получен ответ "No" на следующий запрос?

?- максимум(X,50,40).
No

Пример

Составьте процедуру гипотенуза/3, которая по двум катетам прямоугольного треугольника вычисляет его гипотенузу.

Воспользуемся теоремой Пифагора и встроенной функцией sqrt для вычисления квадратного корня:

гипотенуза(X,Y,Z):- Z is sqrt(X**2 + Y**2).

Программа корректно вычисляет гипотенузу, но если мы попробуем при ее помощи найти один из катетов, то убедимся, что процедура работает не вполне правильно. Чтобы избежать этого добавим проверку того, что первые два аргумента предиката - положительные числа, для чего используем встроенный предикат number/1 и сравнение с нулем:

гипотенуза(X,Y,Z):- number(X), X>0, number(Y), Y>0,
                    Z is sqrt(X**2 + Y**2).

?- гипотенуза(3,4,X). X = 5 Yes ?- гипотенуза(3,'a',X). No ?- гипотенуза(3,X,5). No

Пример

Напишите предикат, который по двум парам чисел - длинам катетов прямоугольных треугольников - определяет величину меньшей из гипотенуз.

Воспользуемся процедурой гипотенуза/3, разобранной выше, и встроенной функцией min/2:

мин_гип(A1,B1,A2,B2,Min):-
                   гипотенуза(A1,B1,C1),
                   гипотенуза(A2,B2,C2),
                   Min is min(C1,C2).

Запросы к интерпретатору Пролога могут выглядеть так:

?- мин_гип(3,4,8,6,X).
X = 5
Yes

?- мин_гип(3,4,Y,6,X).
No

Пример

Факториалом натурального числа n называют произведение всех целых чисел от 1 до n включительно. Для записи факториала числа n используют обозначение n!.

Следующая процедура вычисляет факториал числа. Обратите внимание на использование рекурсии в данной процедуре:

факториал(1,1).
факториал(N,R):- integer(N), N>1, N1 is N-1, 
                 факториал(N1,R1), R is N*R1.

Первое правило (так называемый терминальный случай, то есть тот момент выполнения процедуры, когда она перестает вызывать сама себя) гласит, что факториал единицы равен единице. Второе правило есть просто запись определения факториала: результат R получается умножением числа N на факториал числа, на единицу меньшего. Оно будет срабатывать при всех n>1 потому, что интерпретатор Пролога просматривает базу данных сверху вниз и переходит к следующему правилу или факту только в том случае, когда он не может выполнить текущее правило.

Пример

Напишите программу на языке Пролог, печатающую сумму всех цифр введенного с клавиатуры числа.

Для решения данной задачи воспользуемся двумя предикатами. Предикат сумма/2 имеет своим первым аргументом число, сумма цифр которого является его вторым аргументом. Второй предикат - печать_суммы/0 - запрашивает число, вызывает предикат сумма/2 и печатает полученный результат.

сумма(X,Y):- integer(X), X<10, Y is X.
сумма(X,Y):- integer(X), X1 is X//10, сумма(X1,Y1),  
             Z is X mod 10, Y is Y1+Z.

печать_суммы:-  write('Введите число (в конце точка): '),
                read(X), nl, сумма(X,Y),
                write('Сумма цифр  числа '), write(X), 
		write(' равна '), write(Y), nl.

Правило печать_суммы не имеет аргументов, данные вводятся с клавиатуры и затем, при помощи механизма унификации, передаются другим подцелям данного правила.

Пример

Напишите программу на языке Пролог, вводящую с клавиатуры два числа - координаты точки на плоскости и определяющую, попадает ли данная точка в круг единичного радиуса с центром в начале координат.

inside(X,Y,попадает):- number(X), number(Y), 
                       X**2+Y**2=<1.
inside(X,Y,не_попадает):-number(X), number(Y), 
                       X**2+Y**2>1.

/* Ввести два числа и вызвать предикат inside/3 */

input:-write('Введите x-координату: '),
       read(X), nl,
       write('Введите y-координату: '),
       read(Y), nl,
       inside(X,Y,R), write(R).

Задание

Напишите процедуры на языке Пролог для решения следующих задач и приведите примеры использования этих процедур.

Списки

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

[слон, лошадь, обезьяна, собака]

Это список из четырех атомов - слон, лошадь, обезьяна, собака.

Элементами списка могут быть любые термы Пролога, т. е. атомы, числа, переменные и составные термы, что позволяет, в частности, составлять списки из списков. Пустой список записывается как [ ].

[слон, [ ], X, предок(Х, том), [a,b,c], f(22)]

Первый элемент непустого списка называется головой, а остальная часть списка носит название хвост. У списка, состоящего только из одного элемента головой является этот единственный элемент, а хвостом - пустой список. Обозначение [H|T] используется для представления списка с головой H и хвостом T. Если символ | помещен перед последним термом списка, то это означает, что этот последний терм определяет другой список. Полный список получится, если соединить этот подсписок с последовательностью элементов, расположенных до черты.

В следующем примере 1 - голова списка, а [2, 3, 4, 5] - хвост. Пролог покажет это при помощи сопоставления списка чисел с образцом, состоящим из головы и хвоста.

?- [1, 2, 3, 4, 5] = [Head | Tail].
Head = 1
Tail = [2, 3, 4, 5]
Yes

Здесь Head и Tail - только имена переменных. Мы могли бы использовать X и Y или какие-нибудь другие имена переменных с тем же успехом. Заметим, что хвост списка всегда является списком. Голова, в свою очередь, есть элемент списка, что верно и для всех других элементов, расположенных до вертикальной черты. Это позволяет получить, скажем, второй элемент списка.

Пример

Используем анонимные переменные для головы и списка, стоящего после черты, если нам нужен только второй элемент списка:

?- [слон, лошадь, осел, собака] = [_, X | _ ].
X = лошадь
Yes

Рассмотрим несколько процедур обработки списков. Обратите внимание, что все они используют рекурсию, в которой терминальное (базовое) правило определено для пустого списка.

Пример

Напишем предикат для вычисления суммы всех элементов списка чисел.

сумма_списка([],0).
сумма_списка([H|T],S):- number(H), сумма_списка(T,S1),
                        S is S1+H.

Пример

Предикат место/3 успешен, если третий аргумент есть список, полученный вставкой первого аргумента в произвольное место списка, являющегося вторым аргументом.

место(E, L, [E|L]).
место(E, [H|L], [H|Y]):-  место(E, L,Y).

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

?- место(1,[2,3],X).
X = [1, 2, 3] ;
X = [2, 1, 3] ;
X = [2, 3, 1] ;
No

?- место(1,L,[2,1,3]).
L = [2, 3] ;
No

?- место(X,[2,3],[2,1,3]).
X = 1 ;
No

Пример

Предикат перестановка/2 выдает списки, полученные перестановкой элементов своего первого аргумента.

перестановка([],[]).
перестановка([H|L],Z):- перестановка(L,Y), место(H,Y,Z).

Пример использования:

?- перестановка([a,b,c],X).
X = [a, b, c] ;
X = [b, a, c] ;
X = [b, c, a] ;
X = [a, c, b] ;
X = [c, a, b] ;
X = [c, b, a] ;
No

И, наконец, приведем правило для печати всех возможных перестановок списка:

все_перестановки(L):- перестановка(L,R), write(R), nl, fail.

Первая подцель предиката вычисляет очередную перестановку, печатает ее и переходит к последней подцели - fail. Эта подцель всегда неуспешна, что заставляет Пролог вернуться к началу правила и продолжить поиск решения. Работа процедуры завершится, когда все перестановки будут исчерпаны:

?- все_перестановки(['маркиза', 'ваши прекрасные глаза',
|            'сулят мне смерть от любви']).

[маркиза, ваши прекрасные глаза, сулят мне смерть от любви]
[ваши прекрасные глаза, маркиза, сулят мне смерть от любви]
[ваши прекрасные глаза, сулят мне смерть от любви, маркиза]
[маркиза, сулят мне смерть от любви, ваши прекрасные глаза]
[сулят мне смерть от любви, маркиза, ваши прекрасные глаза]
[сулят мне смерть от любви, ваши прекрасные глаза, маркиза]
 
No

Пример

В старояпонском календаре был принят 60-летний цикл, состоящий из пяти 12-летних подциклов. Подциклы обозначались названиями цветов: зеленый, красный, желтый, белый и черный. Внутри каждого подцикла года носили названия животных: крыса, корова, тигр, заяц, дракон, змея, лошадь, овца, обезьяна, курица, собака и свинья. Например, 1984 год - год начала очередного цикла - назывался Годом Зеленой Крысы.

Составим программу, которая по заданному номеру года нашей эры n печатает его название в старояпонском календаре. Рассмотрим два случая:

(1) значение n не меньше, чем 1984;

(2) значение n - любое натуральное число.

Воспользуемся встроенным предикатом nth0(индекс, список, элемент), который будет успешным, если элемент находится на месте с номером индекс, считая от 0. Для случая (1) используем предикат nam, для случая (2) предикат - nm.

color(N,X):- N1 is ((N-1984) mod 60)//12,  
             nth0(N1, ['зеленый',
                       'красный', 'желтый', 
                       'белый', 'черный'], 
                  X).

animal(N,X):- N1 is (N-1984) mod 12, 
              nth0(N1,
                   ['крыса',  'корова', 'тигр',
	            'заяц',   'дракон', 'змея', 
                    'лошадь', 'овца',   'обезьяна', 
                    'курица', 'собака', 'свинья'],
                   X).

nam(N,[X,Y]):- number(N), color(N,X), animal(N,Y).

nm(N,X):- N>1983, nam(N,X).
nm(N,X):- N<1984, N1 is N+60, nm(N1,X).

Задание

Напишите процедуры на языке Пролог для решения следующих задач и приведите примеры использования этих процедур.