Язык логического программирования Пролог.

Пролог – наиболее известный язык логического программирования, хотя существуют и другие языки. Начальный вариант языка Пролог был разработан Аланом Кольмероэ с сотрудниками в 1972 г. в марсельском университете.

В плане синтаксиса Пролог является очень простым языком (в нем насчитывается небольшое количество лексикографических символов).

Рассмотрим краткую характеристику языка программирования Пролог.

В начале 70-х годов группа специалистов Марсельского университета во главе с А.Колмероэ разработала специализированную систему для доказательства теорем. Она была написана на языке Фортран и использовалась для обработки естественного языка. Система доказательства теорем, названная Пролог, воплощала процедурную семантику Р.Ковальского. Позже Ван Энден и Р.Ковальский разработали формальную семантику для языка логических программ.

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

Пролог применяется при создании приложений в следующих областях:

· разработка быстрых прототипов прикладных программ;

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

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

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

Формальная точность и возможность интерпретации Пролога делают его чрезвычайно подходящим языком для представления знаний.

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

На Прологе удобно описывать различные структуры данных, такие как списки и деревья.

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

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

Свое название Пролог получил от слов " ПРО граммирование на языке ЛОГ ики". На самом деле Пролог не является чистым языком логического программирования, но его создание - важный этап в этом направлении.

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

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

Основные понятия и определения

Каждая логическая программа состоит из следующих этапов:

– установка логических связей (отношений) между объектами;

– формулировка правил, которым подчинены эти связи;

– постановка запроса (или формулировка целевого утверждения).

В следующей конструкции

лекция (дисциплина, лектор, группа, время, аудитория)

слово перед скобками обозначает имя отношения, слова в скобках – объекты, которые связаны этим отношением. В зависимости от конкретного содержания этих объектов отношение может быть истинным или ложным. Например, нетрудно определить истинность этого отношения в случае

лекция (теология, тайсон, сп, обед, 40).

Имя отношения называется предикатом (логическое сказуемое).

Предикат – это функция, которая может принимать лишь два возможных значения – истина (true) или ложь (false). Имя предиката (предикатный символ) должно начинаться с маленькой латинской буквы или со знака подчеркивания. Общая форма записи предиката имеет следующий вид

name_pred (arg₁ ,.., arg_n).

Предикат может не иметь аргументов и в этом случае его значения является постоянным (true или false) по определению.

Введем отношение

книга (автор, жанр).

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

книга (стаут, детектив)

книга (по, поэзия)

книга (по, детектив)

книга (шевченко, поэзия).

Если поставить запрос к этой базе знаний

? книга (стаут, детектив)

то получим решение истина. Значение запроса

? книга (пушкин, поэзия)

будет ложь, так как в Прологе принято соглашение о замкнутости мира. Т.е. если какое-то отношение не содержится в базе, то его значение ложь.

Для запроса

? книга (Х, детектив)

согласно нашей базе знаний получаем решение

Х1=стаут, Х2=по

В этом случае в запросе фигурирует объект X, имя которого не определено. Переменная – это значение аргумента, которое он может получить из области интерпретации предиката. Решением задачи является такая совокупность аргументов предиката, которая придает ему значение истина.

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

Если переменная не имеет значения в контексте поставленного запроса и сформулированного правила, она называется анонимной и обозначается знаком подчеркивания.

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

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

? книга (Х, Y) и книга (Х, Z) и Y< > Z.

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

разные_жанры (Х) если книга (Х, Y) и книга (Х, Z) и Y< > Z,

которое имеет название правила.

Правило имеет следующую структуру

name (arg , arg , …, arg ) P (b ,..., b ),..., P (c ,..., c ),...

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

Каждая переменная должна встречаться в теле правила не меньше двух раз. Если содержание задачи предполагает однократное употребление переменной, то на ее место ставится анонимная переменная. Анонимная переменная – это переменная, значение которой в данном контексте не является существенным. Она обозначается знаком подчеркивания и в фактах применяться не может.

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

? столица (_, X, Y), Y> 1 000 000.

В Прологе существует альтернатива форм записи логических операций

: - или іf, или and; или or

Например, правило Р: - Р1, Р2,..., Р4 может быть записано в виде

P if P1 and P2 and... P4