Теоретические сведения

В этой работе Вы познакомитесь с языком логического программирования Пролог. Теоретической основой языка Пролога является раздел символьной логики, называемый исчислением предикатов. Название Пролог (Prolog) произошло от словосочетания «программирование при помощи логики» (PROgramming in LOGic).

Создание логического программирования можно приписать Роберту Ковальскому и Алэну Колмероэ. Р. Ковальский разработал процедурную интерпретацию хорновских дизъюнктов. В начале 70-х годов А. Колмероэ и его группа создали в Марсельском университете (Франция) специальную, написанную на Фортране программу, предназначенную для доказательства теорем. Программа доказательства теорем, названная Прологом, включала в себя интерпретатор Р. Ковальского. С тех пор было сделано несколько расширений и усовершенствований языка. Здесь можно отметить работу группы из Эдинбургского университета (Шотландия). Шотландский вариант получил название C&M Prolog в честь авторов классической работы «Программирование на языке Пролог» Уильяма Клоксина и Кристоффера Меллиша. Сегодняшней своей популярности Пролог во многом обязан эффективной реализации этого языка, полученной в Эдинбурге Дэвидом Уорреном и его коллегами в конце 70-х годов. Написанный ими компилятор (компилятор был почти полностью написан на Прологе) остается и поныне одной из лучших реализаций Пролога.

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

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

При выполнении лабораторных работ мы будем использовать визуальную среду программирования – VisualProlog. Существует реализация системы VisualProlog для таких платформ как: DOS, Windows 3.x, Windows 95/98, Windows NT, OS/2, SCO Unix, Linux. VisualProlog прекрасное средство для разработки клиент-серверных приложений. В настоящее время Visual Prolog также включает оболочку для разработки экспертных систем – ESTA.

Факты и правила

Программирование на языке Пролог состоит их 3-х этапов:

1. Определение фактов предметной области.

Факты могут описывать свойства объектов и отношения между объектами. Например, факт «нравится ellen tennis» можно записать так:

likes(ellen, tennis).

Этот факт включает в себя два объекта, обозначенных словами ellen и tennis, и отношение, обозначенное словом likes (нравится). Обратите внимание, что каждый факт и каждое правило предметной области должны заканчиваться точкой. Имена объектов, список которых в каждом факте заключен в круглые скобки, называются аргументами. Имя отношения – называется предикатом. Таким образом, likes – предикат с двумя аргументами.

2. Определение правил.

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

Общий вид правила:

A :- B1, ..., Bn. (n>0)

Здесь A – заголовок правила, Bi – тело правила. Символ «:-» читается «если».

Возможны два варианта прочтения данного правила:

- декларативное прочтение – «A истинно, если истинны Bi»;

- процедурное прочтение – «чтобы решить задачу A, сначала надо решить подзадачу B1, затем подзадачу B2, ..., затем подзадачу Bn»

Таким образом, для выполнения цели в заголовке правила, необходимо вначале выполнить (согласовать) все подцели из тела правила.

Например, правило «тому нравится футбол, если футбол является видом спорта» на Прологе можно записать следующим образом:

likes(tom, football) :- sport(football).

Цель likes(tom, football) будет истинной в том случае, если выполняются все подцели из тела правила. В данном случае подцель sport(football).

3. Формулировка вопросов об объектах предметной области и отношениях между ними.

Имея некоторую совокупность фактов, мы можем обращаться к Прологу с вопросами о них.

Например, пусть имеется следующая совокупность фактов:

likes(ellen, tennis).

likes(tom, football).

likes(tom, swimming).

Теперь мы можем задать системе вопрос «нравится ли тому футбол»:

?-likes(tom, football)

yes

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

Переменные

До сих пор мы рассматривали отношения, аргументами которых выступали конкретные объекты – константы, такие как, ellen, tennis, и т.д. Такие объекты называются атомами. Аргументами отношений могут выступать также абстрактные объекты – переменные. Переменные используются для задания общих правил и формулировки общих вопросов. Переменные должны начинаться с большой буквы. Например, правило «биллу нравится то же, что и тому» на Прологе можно записать так:

likes(bill, X) :- likes(tom, X).

В этом правиле объект X – переменная, объекты bill и tom – константы (начинаются с маленькой буквы). Если Вы хотите, чтобы константа начиналась с большой буквы, необходимо заключить ее в двойные кавычки, например: «Bill».

Переменная может также встречаться в запросе. Если в запрос переменная не входит, то ответом будет либо да (yes), либо нет (no). Если же в запрос входит переменная, то Пролог найдет все значения этой переменной и вернет ответ. Например, вопрос «что нравится биллу» можно записать на Прологе следующим образом:

?- likes(bill, What). % What переменная

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

What = football

What = swimming

2 Solutions

Иногда возникает необходимость в использовании переменной, имя которой не будет потом нигде употребляться. Например, если необходимо определить «нравится ли что-то тому» и при этом не важно, что именно, можно использовать анонимную переменную. Анонимная переменная обозначается одиночным знаком подчеркивания: «_». Например, вопрос «нравится ли что-то тому» на Прологе можно записать так:

?- likes(tom, _).

yes

Вопрос «нравится ли эллен теннис и нравится ли тому теннис» можно задать следующим образом:

?- likes(ellen, tennis), likes(tom, tennis).

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

?- likes(ellen, X), likes(tom, X).

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

Выполнение запроса

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

1. Идентичные структуры сопоставляются друг с другом.

2. Свободная переменная сопоставляется с константой или с ранее связанной переменной (и становится связанной с соответствующим значением).

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

Механизм поиска с возвратом

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

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

2. Предикатные предложения проверяются в том порядке, в каком они появляются в программе.

3. Когда подцель соответствует заголовку правила, тело этого правила образует новое множество подцелей для согласования.

4. Целевое утверждение считается согласованным, когда соответствующий факт найден для каждой оконечности (листа) целевого дерева.

Основные программные секции программ на VisualProlog

Обычно программа на VisualProlog состоит из 4-х программных секций. Каждой секции предшествует свое ключевое слово.

Секция доменов (domains) служит для объявления всех используемых нестандартных доменов. VisualProlog позволяет создавать свои собственные типы объектов из базисных типов доменов. Существует несколько встроенных стандартных доменов:

Домен	Описание
short	диапазон значений –32768 .. 32767
ushort	диапазон значений 0 .. 65535
long	диапазон значений -2147483648 .. 2147483647
ulong	диапазон значений 0 .. 4294967295
integer	для 32-битных платформ диапазон значений -2147483648 .. 2147483647
unsigned	для 32-битных платформ диапазон значений 0 .. 4294967295
byte	диапазон значений 0 .. 255
word	диапазон значений 0 .. 65535
dword	диапазон значений 0 .. 4294967295
char	отдельный символ, заключенный в апострофы, например: 'a'
real	число с плавающей точкой, эквивалент типу double в языке C
string	1. Последовательность букв, цифр и знаков подчеркивания, которая начинается со строчной буквы, например: telephone_number. 2. Любая последовательность символов, заключенная в двойные кавычки, например: “Visual Prolog”.
symbol	Синтаксис такой же, как и для строк. Данные типа symbol в отличие от данных типа string запоминаются в таблице символов. Это обеспечивает более быстрый поиск.

Пример описания нестандартных типов данных: