Geum.ru

Язык Пролог Пролог (Prolog)

Вид материалаДокументы

Содержание


Пример. Бабушка человека - это мама его мамы или мама его папы. бабушка(X,Y)
Наташа мамой Даши
X=Наташа Y=Даша
Подобный материал:
Язык Пролог

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

Название языка "Пролог" происходит от слов ЛОГическое ПРОграммирование (PROgramming in LOGic).

В 1965 году в работе "A machine oriented logic based on the resolution principle" Дж Робинсон представил метод автоматического поиска доказательства теорем в исчислении предикатов первого порядка, получивший название "принцип резолюции". На самом деле, идея данного метода была предложена Эрбраном еще в 1931 году.

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

Большое значение для развития логического программирования имела работа Роберта Ковальского "Логика предикатов как язык программирования", в которой он показал, что для того чтобы добиться эффективности, нужно ограничиться использованием множества хорновских дизъюнктов.

В 1976 г. Ковальский вместе с его коллегой Маартеном ван Эмденом предложил два подхода к прочтению текстов логических программ: процедурный и декларативный.

В 1977 году в Эдинбурге Уоррен и Перейра создали очень эффективный компилятор языка Пролог для ЭВМ DEC–10 (реализация Пролога, известная как "эдинбургская версия", фактически стала первым и единственным стандартом языка), который послужил прототипом для многих последующих реализаций Пролога.

В 1980 году Кларк и Маккейб в Великобритании разработали версию Пролога для персональных ЭВМ.

На сегодня существует довольно много реализаций Пролога, как коммерческих, так и свободно распространяемых (BinProlog, AMZI-Prolog, Arity Prolog, CProlog, Micro Prolog, МПролог, Prolog-2, Quintus Prolog, SICTUS Prolog).

Будем ориентироваться на PDC Prolog, возможностей которого вполне достаточно для первоначального знакомства с основами языка Пролог. Эта версия языка Пролог доступна для свободного использования пользователями ОС Windows.

В 1990 PDC получила монопольное право на Турбо Пролог и продвигала его под названием PDC Prolog. В 1992 вышла версия PDC Prolog 3.31. В 1996, при участии группы питерских программистов, Prolog Development Center выпустила систему Visual Prolog 4.0.

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


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


Программа на языке Пролог (ее иногда называют БЗ), состоит из предложений (или утверждений), каждое предложение заканчивается точкой.

Предложения бывают двух видов: факты (БД), правила.

Предложение имеет вид

A:-

B1,... , Bn.

A называется заголовком или головой предложения, а B1,..., Bn - телом.

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

Например, известный нам факт, что Наташа является мамой Даши, может быть записан в виде: мама(Наташа, Даша).

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

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

Пример. Бабушка человека - это мама его мамы или мама его папы.

бабушка(X,Y):-

мама(X,Z),мама(Z,Y).

бабушка(X,Y):-

мама(X,Z),папа(Z,Y).

Символ ":-" означает "если", и вместо него можно писать if. Символ "," - это конъюнкция, вместо него можно писать and. В примере X, Y и Z - переменные.

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

Свободная (неконкретизированная) переменная - это переменная, которая еще не получила значения. Переменная, которая получила какое-то значение и оказалась связанной с определенным объектом, называется связанной и она уже не может быть изменена.

Областью действия переменной в Прологе является одно предложение. В разных предложениях может использоваться одно имя переменной для обозначения разных объектов. Исключением является анонимная переменная, которая обозначается символом подчеркивания "_".

Третьим специфическим видом предложений Пролога можно считать вопросы.


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

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

Если внутренней цели в программе нет, то после запуска программы система выдает приглашение вводить вопросы в диалоговом режиме (внешняя цель).

Рассмотрим несколько примеров. Пусть заданы следующие отношения:

мама("Наташа","Даша").

мама("Даша","Маша").

Можно спросить у системы, является ли Наташа мамой Даши.

Этот вопрос можно ввести в виде: мама("Наташа","Даша")

Найдя соответствующий факт, система ответит "Yes" ("Да").

Можно найти имена всех известных системе мам и дочек, задав вопрос:

мама(X,Y).

Система последовательно будет пытаться согласовывать вопрос с имеющимися в программе предложениями от первого до последнего. В итоге получим ответ:

X=Наташа Y=Даша

X=Даша Y=Маша

2 solutions

Если надо получить только имена всех мам, можно воспользоваться анонимной переменной и записать вопрос:

мама(X,_).

Получим ответ:

X=Наташа

X=Даша

2 solutions

И, наконец, если надо получить ответ на вопрос: есть ли информация о людях, находящихся в отношении "мама - дочка", то его можно сформулировать в виде:

мама(_,_),

В данном случае нам не важны конкретные имена, а интересует, есть ли в БЗ хотя бы один соответствующий факт. Ответ в данном случае будет "Yes".