- Кое о чем можно было и умолчать или хотя бы соблюдать меру в
изложении фактов. Единственное, что заслуживает внимания в этом деле, -
цепь рассуждений от следствия к причине.
Это и привело к успешному раскрытию дела.
Артур Конан Дойл. "Знак Четырёх".
«Пользователь: Кошки едят мышей. Том – кошка, которая не любит мышей, которые едят сыр. Джерри – мышь, которая ест сыр. Макс – не мышь. Что делает Том ?
Компьютер: Том не любит мышей, которые едят сыр. Том ест мышей.
Пользователь: Кто кошка ?
Компьютер: Том.
Пользователь: Что ест Джерри ?
Компьютер: Сыр.
Пользователь: Кто не любит мышей, которые едят сыр ?
Компьютер: Том.»
Примерно такой диалог (только по-французски) вели в 1971 году в Марсельском университете Жан Трудель, Роберт Пасеро, Филип Руссель и Алан Колмеро со своим компьютером IBM 360-44, на котором они разрабатывали язык логического программирования - Prolog (от французского PROgrammation en LOGique).
Пролог – язык удивительный. В общем-то, это даже не просто язык программирования, а настоящий Шерлок Холмс компьютерного мира. Он умеет делать логические выводы на основании фактов. Он, например, может рассказать вам целую историю о том, кого родил праотец Авраам, его сын, сын его сына и так далее, а также поведать обо всех их братьях, сестрах, племянниках и свояченицах до седьмого колена[1]. Конечно, в Пролог не заложен текст Библии, как, впрочем, и никакой другой текст. В Пролог закладываются факты и правила. Программа на Прологе – это база данных (или попросту – множество) таких фактов и правил, общее название которых - предикаты. Задавая Прологу некую базу данных, программист тем самым создает целый мир, в рамках которого Пролог будет делать свои выводы. Ничто из того, что не является частью этого мира (то есть, не задано фактами), не может быть выведено Прологом в качестве заключения. В отличие от Сократа, который говорил «я знаю только то, что ничего не знаю», Пролог мог бы сказать: «я знаю только то, что знаю – не больше и не меньше». Однако, вернемся к аналогии с Шерлоком Холмсом. Тот тоже делал свои дедуктивные выводы на основании только того, что видел, только тех фактов, которые были у него перед глазами. Задача была в том, чтобы, исходя из увиденного сделать правильные выводы - шаг, который простые смертные сделать были не в состоянии. Точно так же, Пролог помогает нам сделать этот шаг, обычно далеко не очевидный. При этом мы сами задаем Прологу знания о мире (о той части мира, которая интересует нас в данный момент), ожидая от него ответа на все наши вопросы.
Читателю уже должна стать понятной разница между императивным и логическим программированием. Императивный язык программирования помогает описывать алгоритм, то есть последовательность действий, которая приводит к решению поставленной задачи. Язык логического программирования помогает описывать задачу в виде фактов, известных о мире, которому принадлежит задача, и правил, с помощью которых можно будет делать умозаключения об этом мире.
Познакомимся сначала с фактами.
Чтобы сообщить Прологу, что Адам – мужчина, а Ева – женщина (останемся верны библейской тематике), нужно просто написать:
male(adam).
female(eve).
Каждый факт заканчивается точкой. Обратите также внимание, что все имена собственные написаны с маленькой буквы; заглавная буква используется для имен переменных.
В этом примере факты состоят из одного аргумента (adam – единственный аргумент предиката[2] male, а eve – единственный аргумент предиката female). Следующие факты (состоящие из двух аргументов) будут описывать родственные отношения между родителями и детьми:
parent(adam, abel).
parent(adam, kain).
parent(eve, abel).
parent(eve, kain).
Примеры эти говорят сами за себя и не нуждаются в объяснениях – мы просто определили отношение «родитель». Давайте определим то же самое, но только чуть более конкретно:
father(adam, abel).
father(adam, kain).
mother(eve, abel).
mother(eve, kain).
Это тоже понятно, но читатель в недоумении – какая нам польза от всего этого ? Остановимся на этом этапе и объясним.
Пролог – система интерактивная, то есть пользователь сидит у терминала и задает Прологу вопросы, которые обычно предваряются приглашением ?-.
Предположим, что «мир», который мы создали в текущей сессии работы с Прологом, ограничен только что приведенными десятью фактами. Начнем сеанс:
?- male(adam).
yes
Все, что пишет Пролог, будем обозначать жирным шрифтом; все, что пишет пользователем – обычным.
Итак, мы задали Прологу простой вопрос – «мужчина ли Адам». «Да» - справедливо отвечает Пролог. Продолжим:
?- male(eve).
no
И это верно. Еще вопрос:
?- male(kain).
no
Стоп! Это еще что такое ? Пролог хочет убедить нас в том, что Каин – женщина ? Еще одна попытка:
?- female(kain).
no
Мы подошли к очень важному моменту, необходимому для понимания сути логического программирования. Как видим, на оба вопроса о половой принадлежности Каина Пролог ответил отрицательно. Это случилось потому, что Пролог не знает о том, мужчина Каин или женщина – мы просто не ввели в систему мира текущей сессии Пролога факт о том, что Каин – мужчина. Пролог честно отвечает «нет», потому что все, что не является фактом, известным Прологу, есть для него ложь.
Очень важный вывод, который можно сделать из этого эксперимента таков:
Пролог ничего не знает о семантике (то есть о смысловом значении) понятий, с которыми он имеет дело[3]. В том, что мы написали слово “male” нет никакого смысла (во всяком случае для Пролога). С равным успехом мы могли бы написать elephant(adam) или даже abc(adam)и получили бы те же ответы. Единственное, что имеет здесь значение – это взаимосвязи между фактами и аргументами, которые мы задаем Прологу, и тот смысл, который мы (а не Пролог!) будем в них вкладывать. Как справедливо заметил Шалтай-Болтай Алисе – «когда я беру слово, оно означает то, что я хочу, не больше и не меньше»[4].
Таким образом, мы употребляем слова «мужчина», «женщина», «родитель», «отец», «мать» только в качестве удобных мнемонических обозначений для понятий, с которыми собираемся работать.
Пришло время продолжить сессию:
?- father(adam, abel).
yes
?- father(adam, eve).
no
?- parent(eve, kain).
yes
?- parent(kain, abel).
no
?- mother(X, abel).
X = eve;
no
Последний пример заслуживает нашего особого внимания. Здесь мы впервые встречаемся с переменной X (как и было сказано, переменные всегда пишутся с заглавной буквы). Этот вопрос на привычном языке можно переформулировать так: «Кто мать Авеля ?». После этого Пролог просматривает свою базу данных (то есть факты, известные ему об окружающем мире) и находит единственный нужный факт, содержащий ответ:
mother(eve, abel).
Этот самый ответ («eve») мы и получаем. Следующее “no” означает, что больше ответов у Пролога нет.
Попробуем спросить по-другому:
?- mother(eve, X).
X = avel;
X = kain
no
Как несложно догадаться, этот вопрос буквально означает «чьей матерью является Ева?».
И действительно, на этот раз Пролог находит два факта, отвечающих на заданный вопрос:
mother(eve, abel).
mother(eve, kain).
Теперь, когда мы впервые почувствовали настоящие возможности Пролога, пришло время рассказать о том, как же он все это делает.
Одним из основных механизмов работы Пролога является механизм унификации[5]. Получив в качестве вопроса[6] mother(eve, X), Пролог попытается найти предикат с именем и числом аргументов такими же как у mother/2 (условное обозначение числа аргументов предиката), так, чтобы его первый аргумент был равен eve. Это процесс и называется унификацией. Очевидно, что в нашем случае оба факта mother/2 будут успешно унифицированы.
Более подробно мы рассмотрим механизм работы Пролога после того, как познакомимся с правилами.
Правила образуются с помощью заголовка и тела правила, разделенных знаком :-, который читается как “if” («если»). Так, например, простое правило
child(C,P) :- parent(P,C).
можно прочитать как «С является ребенком Р, если Р – родитель С». Логично, не правда ли ?
Правила предоставляют нам очень мощную возможность расширения базы знаний Пролога «вглубь», а не «вширь». Вот что имеется в виду. Мы могли бы, конечно, добавить в текущую сессию нашей работы четыре новых факта о семье Адама и Евы:
child(abel, adam).
child(kain, adam).
child(abel, eve).
child(kain, eve).
Вместо этого, единственное обобщенное правило child(C,P) :- parent(P,C) решит ту же задачу гораздо быстрее, а главное – оно будет применимо для любого другого набора фактов о родителях. Сколько бы новых фактов parent мы не добавляли в базу знаний Пролога, это правило будет работать для них всех автоматически. Это и называется «расширением вглубь».
Чуть более сложное правило son решает более сложную задачу:
son(S,P) :- parent(P,S), male(S).
Здесь запятая играет роль связывающего союза «и». Правило может быть прочитано так: «S является сыном P, если P – родитель S и S – мужчина».
Аналогично:
daughter(S,P) :- parent(P,S), female(S).
И наоборот:
mother(M,S) :- parent(M,S), female(M).
father(F,S) :- parent(F,S), male(S).
Основываясь на такой обширной базе данных, мы можем задавать Прологу самые разные вопросы. Например:
?- son(S, kain).
no
?- son(S, adam).
S = abel;
S = kain;
no
?- child(adam,eve).
no
?- child(kain,P).
P = adam;
P = eve;
no
Немного освоившись в мире Пролога, мы, пожалуй, готовы рассмотреть более подробный пример с генеалогией - в нём примут участие и бабушки, и внуки, и дяди, и тёти. Призовём на помощь древнегреческих богов - их генеалогическое древо проще изобразить и понять. Но этим мы займёмся на следующей лекции.
[1] На самом деле этот пример очень популярен в книгах о Прологе.
[2] Факт – это простейшая форма предиката.
[3] И в этом, конечно, его принципиальное отличие от Шерлока Холмса.
[4] Здесь уместно также привести комментарий Мартина Гарднера (с которым мы уже встречались в главе об игре «Жизнь») к этому отрывку из Кэрролла: «Шалтай-Болтай становится на точку зрения, известную в средние века как номинализм, точку зрения, согласно которой общие имена не относятся к объективным сущностям, а являются чисто словесными знаками. Эту точку зрения защищал Уильям Оккам (XIVв.) (с которым мы познакомимся в главе о языке параллельного программирования Оккам – прим. автора). В настоящее время ее придерживаются почти все логические эмпирики. Даже в логике и математике, там, где термины, как правило, боле точны, чем в других науках, нередко возникает чудовищная путаница из-за того, что люди не понимают, что слова означают только то, что в них вложено – «не больше и не меньше»».
[5] Унификация напоминает pattern matching – механизм, использующийся также и в некоторых функциональных языках программирования.
[6] В Прологе такие вопросы называются целями. Работа Пролога заключается в том, чтобы достичь поставленной цели.