Пролог
Программа на языке Пролог, ее иногда называют базой знаний, состоит из предложений (или утверждений), каждое предложение заканчивается точкой.
Предложения бывают трех видов: факты, правила, вопросы(целевые утверждения).
Предложение имеет вид
A:-
B1,..., Bn.
A называется заголовком или головой предложения, а B1,..., Bn - телом.
Факт констатирует, что между объектами выполнено некоторое отношение. Он состоит только из заголовка. Можно считать, что факт - это предложение, у которого тело пустое.
Например, известный нам факт, что Наташа является мамой Даши, может быть записан в виде:
мама(Наташа, Даша).
Факт представляет собой безусловно истинное утверждение.
Напомню, что в математической логике, с которой мы познакомились в предыдущей лекции, отношения принято называть предикатами.
Если воспользоваться нормальной формой Бэкуса-Науэра, то предикат можно определить следующим образом:
<Предикат>::=<Имя> <Имя>(<аргумент>[,<аргумент>]*),
т.е. предикат состоит либо только из имени, либо из имени и следующей за ним последовательности аргументов, заключенной в скобки.
Аргументом или параметром предиката может быть константа, переменная или составной объект. Число аргументов предиката называется его арностью или местностью. Про переменные мы поговорим чуть-чуть позже, а подробное рассмотрение констант отложим до пятой лекции. Пока отметим, что константа получает свое значение в разделе описания констант, а переменная означивается в процессе работы программы.
В Турбо Прологе имя предиката должно состоять из последовательности латинских букв, цифр, знаков подчеркивания и начинаться с буквы или знака подчеркивания. В других версиях Пролога имя предиката может содержать символы не только из английского алфавита, но и из национального, например, из русского.
Соответственно, приведенный выше пример факта можно записать в Турбо Прологе, например, так:
mother("Наташа", "Даша").
Некоторые предикаты уже известны системе, они называются стандартными или встроенными.
В Турбо Прологе предложения с одним и тем же предикатом в заголовке должны идти одно за другим. Такая совокупность предложений называется процедурой.
В приведенном выше примере про то, что Наташа является мамой Даши, мама - это имя двухаргументного предиката, у которого строковая константа "Наташа" является первым аргументом, а строковая константа "Даша" - вторым.
Правило - это предложение, истинность которого зависит от истинности одного или нескольких предложений. Обычно правило содержит несколько хвостовых целей, которые должны быть истинными для того, чтобы правило было истинным.
В нотации БНФ правило будет иметь вид:
<Правило>::=<предикат>:-<предикат>[,<предикат>]*.
Пример. Известно, что бабушка человека - это мама его мамы или мама его папы.
Соответствующие правила будут иметь вид:
бабушка(X,Y):-
мама(X,Z),мама(Z,Y).
бабушка(X,Y):-
мама(X,Z),папа(Z,Y).
Символ ":-" означает "если", и вместо него можно писать if.
Символ "," - это логическая связка "и" или конъюнкция, вместо него можно писать and.
Первое правило сообщает, что X является бабушкой Y, если существует такой Z, что X является мамой Z, а Z - мамой Y. Второе правило сообщает, что X является бабушкой Y, если существует такой Z, что X является мамой Z, а Z - папой Y.
В данном примере X, Y и Z - это переменные.
Имя переменной в Турбо Прологе может состоять из букв латинского алфавита, цифр, знаков подчеркивания и должно начинаться с прописной буквы или знака подчеркивания. При этом переменные в теле правила неявно связаны квантором всеобщности. Переменная в Прологе, в отличие от алгоритмических языков программирования, обозначает объект, а не некоторую область памяти. Пролог не поддерживает механизм деструктивного присваивания, позволяющий изменять значение инициализированной переменной, как императивные языки.
Переменные могут быть свободными или связанными.
Свободная переменная - это переменная, которая еще не получила значения. Она не равняется ни нулю, ни пробелу; у нее вообще нет никакого значения. Такие переменные еще называют неконкретизированными.
Переменная, которая получила какое-то значение и оказалась связанной с определенным объектом, называется связанной. Если переменная была конкретизирована каким-то значением и ей сопоставлен некоторый объект, то эта переменная уже не может быть изменена.
Областью действия переменной в Прологе является одно предложение. В разных предложениях может использоваться одно имя переменной для обозначения разных объектов. Исключением из правила определения области действия является анонимная переменная, которая обозначается символом подчеркивания "_". Анонимная переменная применяется в случае, когда значение переменной не важно. Каждая анонимная переменная - это отдельный объект.
Третьим специфическим видом предложений Пролога можно считать вопросы.
Вопрос состоит только из тела и может быть выражен с помощью БНФ в виде:
<Вопрос>::=<Предикат>[,<Предикат>]*
Вопросы используют для выяснения выполнимости некоторого отношения между описанными в программе объектами. Система рассматривает вопрос как цель, к которой надо стремиться. Ответ на вопрос может оказаться положительным или отрицательным, в зависимости от того, может ли быть достигнута соответствующая цель.
Программа на Прологе может содержать вопрос в программе (так называемая внутренняя цель). Если программа содержит внутреннюю цель, то после запуска программы на выполнение система проверяет достижимость заданной цели.
Если внутренней цели в программе нет, то после запуска программы система выдает приглашение вводить вопросы в диалоговом режиме (внешняя цель). Программа, компилируемая в исполняемый файл, обязательно должна иметь внутреннюю цель.
Если цель достигнута, система отвечает, что у нее есть информация, позволяющая сделать вывод об истинности вопроса ("Yes"). При этом если в вопросе содержатся переменные, то система либо выдает их значения, приводящие к решению, если решение существует, либо сообщает, что решений нет ("No solution"). Если достичь цели не удалось, система ответит, что у нее нет положительного ответа ("No").
Следует заметить, что ответ "No" на вопрос не всегда означает, что отношение, о котором был задан вопрос, не выполняется. Система может дать такой ответ и в том случае, когда у нее просто нет информации, позволяющей положительно ответить на вопрос.
Можно сказать, что утверждение - это правило, а факт или вопрос - это его частный случай.
Рассмотрим несколько примеров. Пусть в программе заданы следующие отношения:
мама("Наташа","Даша").
мама("Даша","Маша").
Можно спросить у системы, является ли Наташа мамой Даши. Этот вопрос можно ввести в виде:
мама("Наташа","Даша")
Найдя соответствующий факт в программе, система ответит "Yes" (то есть "Да"). Если мы спросим:
мама("Наташа","Маша")
то получим ответ "No" (то есть "Нет"). Можно также попросить вывести имя мамы Даши:
мама(X,Даша).
Система сопоставит вопрос с первым фактом, конкретизирует переменную X значением "Наташа" и выдаст ответ:
X=Наташа
1 Solution
Вопрос об имени дочери Наташи записывается в виде:
мама(Наташа,X).
Соответствующим ответом будет:
X=Даша
1 Solution
Можно попросить систему найти имена всех известных ей мам и дочек, задав вопрос:
мама(X,Y).
Система последовательно будет пытаться согласовывать вопрос с имеющимися в программе предложениями от первого до последнего. В случае успешной унификации соответствующих термов переменная X будет означена именем матери, а переменная Y - именем ее дочери.
В итоге получим ответ:
X=Наташа Y=Даша
X=Даша Y=Маша
2 solutions
Если надо получить только имена всех мам, можно воспользоваться анонимной переменной и записать вопрос:
мама(X,_).
Получим ответ:
X=Наташа
X=Даша
2 solutions
И, наконец, если надо получить ответ на вопрос: есть ли информация о людях, находящихся в отношении "мама - дочка", то его можно сформулировать в виде:
мама(_,_),
В данном случае нам не важны конкретные имена, а интересует, есть ли в нашей базе знаний хотя бы один соответствующий факт. Ответом в данном случае будет просто "Yes". Система сообщит о том, что у нее есть информация об объектах, связанных отношением "мама".
Введем в нашу программу правило, определяющее отношение "бабушка - внучка", в терминах "быть мамой":
бабушка(X,Y):-
мама(X,Z),
мама(Z,Y).
По сути дела здесь записано, что один человек является бабушкой другого, если это он является мамой его мамы. Конечно, для полноты картины не помешает записать еще и второе правило, которое говорит, что бабушка - это мама папы, если в программу добавить факты еще и про пап.
Заметим, что в нашей программе нет ни одного факта, связанного с отношением бабушка. Тем ни менее, система оказывается способна найти ответы на вопросы о
бабушках, пользуясь введенными фактами и правилом. Например, если нас интересует, чьей бабушкой является Наташа, то мы можем записать этот вопрос следующим образом:
бабушка("Наташа",X).
Для того чтобы найти ответ на вопрос, система просмотрит нашу базу сверху вниз, пытаясь найти предложение, в заголовке которого стоит предикат бабушка. Найдя такое предложение (это предложение бабушка(X,Y):-мама(X,Z),мама(Z,Y)), система конкретизирует переменную из заголовка предложения X именем "Наташа", переменную Y с переменной X из вопроса, после чего попытается достигнуть цели: мама("Наташа",Z) и мама(Z,Y). Для этого она просматривает базу знаний в поиске предложения, заголовок которого можно сопоставить с предикатом мама("Наташа",Z).
Это можно сделать, конкретизировав переменную Z именем "Даша". Затем система ищет предложение, в заголовке которого стоит предикат мама с первым аргументом "Даша" и каким-то именем в качестве второго аргумента. Подходящим предложением оказывается факт мама("Даша","Маша"). Система установила, что обе подцели мама("Наташа",Z) и мама(Z,Y) достижимы при Z="Даша", Y="Маша". Она выдает ответ:
X=Маша
Напомним, что наша переменная X из вопроса была связана с переменной Y из правила. После этого, если есть такая возможность, система пытается найти другие решения, удовлетворяющие вопросу. Однако в данном случае других решений нет.
Вообще говоря, цель может быть согласована, если она сопоставляется с заголовком какого-либо предложения. Если сопоставление происходит с фактом, то цель согласуется немедленно. Если же сопоставление происходит с заголовком правила, то цель согласуется только тогда, когда будет согласована каждая подцель в теле этого правила, после вызова ее в качестве цели. Подцели вызываются слева направо. Поиск подходящего для сопоставления предложения ведется с самого начала базы. Если подцель не допускает сопоставления, то система совершает возврат для попытки повторного согласования подцели. При попытке повторного согласования система возобновляет просмотр базы с предложения, непосредственно следующего за тем, которое обеспечивало согласование цели ранее.
В программе на Прологе важен порядок предложений внутри процедуры, а также порядок хвостовых целей в теле предложений. От порядка предложений зависит порядок поиска решений и порядок, в котором будут находиться ответы на вопросы. Порядок целей влияет на количество проверок, выполняемых программой при решении.
Структура программы на Турбо Прологе
Почему мы говорим именно о версии Турбо Пролог?
Во-первых, Турбо Пролог - это компилируемый язык, а не интерпретируемый, как некоторые другие версии Пролога. Во-вторых, в Турбо Прологе принята строгая типизация данных (для повышения скорости трансляции и выполнения программ). В начале программы на Турбо Прологе обычно располагаются разделы описаний объектов программы. В-третьих, в Турбо Прологе отсутствует возможность рассматривать правила как данные, т.е. добавлять и удалять их во время работы. В процессе выполнения программы в нее можно добавлять и из нее можно удалять только факты. В-пятых, в нем нельзя определять операции. Многое из перечисленного можно считать недостатками, однако в целом все это приводит к тому, что Турбо Пролог отличается высокой скоростью компиляции и выполнения.
Программа на Турбо Прологе состоит из следующих семи разделов:
- директивы компилятора;
- CONSTANTS - раздел описания констант;
- DOMAINS - раздел описания доменов;
- DATABASE - раздел описания предикатов внутренней базы данных;
- PREDICATES - раздел описания предикатов;
- CLAUSES - раздел описания предложений;
- GOAL - раздел описания внутренней цели.
В программе не обязательно должны быть все эти разделы. Так, например, она может состоять из одного описания цели:
GOAL
write("hello"),readchar(_).
Эта программа, вполне в императивном духе, выведет сообщение (с помощью стандартного предиката write) и будет ожидать нажатия пользователем любой клавиши (стандартный предикат readchar читает символ).
Однако, как правило, программа содержит, по меньшей мере, разделы PREDICATES и CLAUSES.
Если программа запускается в среде разработки Турбо Пролога, то раздел GOAL необязателен. При написании же программы, не зависящей от среды разработки, в ней необходимо указать внутреннюю цель.
В программе может быть несколько разделов описаний DOMAINS, PREDICATES, DATABASE и CLAUSES. Однако разделов GOAL не может быть в программе более одного.
Порядок разделов может быть произвольным, но при этом константы, домены и предикаты должны быть определены до их использования. Однако в разделе DOMAINS можно ссылаться на домены, которые будут объявлены позже.
Рассмотрим разделы немного подробнее.
