Основы программирования на языке prolog

Prolog как декларативный язык

Разработка языка Prolog началась в 1970 г. Аланом Кулмероэ и Филиппом Русселом. Они хотели создать язык, который мог бы делать логические заключения на основе заданного текста. Название Prolog является сокращением от «PROgramming in LOGic». Этот язык был разработан в Марселе в 1972 г.

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

Программирование на языке Пролог состоит из следующих этапов:

• • объявления некоторых фактов об объектах и отношениях между ними,
• • определения некоторых правил об объектах и отношениях между ними;
• • формулировки вопросов об объектах и отношениях между ними.

Понятие предиката

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

Рассмотрим понятие предиката в Прологе на примере звездной семьи Пугачевой — Киркорова, правда, теперь уже бывшей. Вначале запишем отношения типа родитель — ребенок. В синтаксисе Пролога выражение «Борис является родителем Аллы» выглядит следующим образом: parent (boris, alia).

Здесь parent — это имя предиката, a boris и alia — аргументы. Аргументы boris и alia являются константами, поэтому записаны строчными буквами. С прописной буквы в Прологе начинаются переменные. Точка означает конец предиката, так же, как и конец предложения на естественном языке. Запишем также родительские отношения для других членов семьи:

parent (bedros, filipp). parent (edmuntas, kristina). parent (alia, kristina). parent (kristina, denis), parent (vladimir, denis).

Теперь дадим понятие «супруг» (spouse):

spouse (filipp, alia), spouse (vladimir, kristina).

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

ю.

Как видим, на уровне представления данных сходство налицо. Но на этом оно и кончается. Но на уровне извлечения данных имеет место большое различие. Реляционной базе данных для того, чтобы извлечь знания, требуется создать запрос на выборку данных, например, на языке SQL.

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

SELECT Parent FROM Родители WHERE Child = «Kristina» .

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

parent (alia, kristina).

Эта цель может быть прочитана следующим образом: Является ли Алла родителем Кристины? Сопоставив эту цель с содержимым базы знаний, Пролог установит, что данное утверждение истинно и сообщит об этом.

Вышеприведенный SQL запрос (Кто является родителем Кристины?) в Прологе выглядит следующим образом:

parent (X, kristina).

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

X = alia.

X = edmuntas.

Мы можем сформулировать вопрос следующим образом: Есть ли у Кристины родители?

parent (_, kristina).

Пролог выдаст ответ: Yes.

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

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

parent (X, kristina), parent (Y, X).

Данная запись означает: Найти Y, являющийся родителем X, который, в свою очередь, является родителем Кристины. Запятая в прологе идентична союзу «И» или конъюнкции. В ответ на такой запрос Пролог выдаст следующий ответ:

X = alia.

Y = edmuntas.

Можно выдать следующий запрос:

parent (alia, _).

Теперь анонимная переменная использована в качестве второго аргумента. Этот запрос можно прочитать следующим образом: Есть ли у Аллы дети? Пролог выдаст ответ: Yes.

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

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