Материал: Волченков Логическое программирование язык пролог 2015

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

Отметим, что рассмотренный пример синтаксического анализатора использует довольно сильные упрощения и «огрубления». Так, арифметические выражения не являются таковыми в привычном толковании: выражение «x*2 + y» здесь будет интерпретироваться как «x*(2 + y)»; константами могут быть только идентификаторы или целые числа и т.д.

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

О системах восходящего разбора можно прочитать в книге Дж. Малпаса «Реляционный язык Пролог и его применение» [6]. Однако, как считает автор, применение Пролога для реализации восходящих методов синтаксического анализа выглядит несколько искусственным, так как эксплуатирует процедурную сторону Пролога, которая не демонстрирует его преимуществ перед другими языками программирования.

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

106

Лекция 8

Пролог и базы данных

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

1. Пролог и реляционные базы данных

Общепринятое понятие базы данных неразрывно связано с по-

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

В Прологе понятие «база данных» имеет несколько иной, более «узкий» смысл. Как было отмечено в Лекции 2, базой данных Пролога называется множество определений предикатов или просто определений – упорядоченных совокупностей фактов и правил, которые в равной степени доступны Пролог-системе, осуществляющей логический вывод, то есть интерпретацию утвержденийзапросов.

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

107

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

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

Действительно, отношение как двумерная таблица, имеющая n строк, m столбцов и имя p, может быть представлено с помощью n фактов, имеющих спецификацию p/m. Строго говоря, отношение не есть таблица, так как строки в таблице (как и факты в определении Пролога) упорядочены, чего нельзя сказать об элементах множества, коим является отношение. Таким образом, определения Пролога даже ближе к таблицам, чем отношения в строгом понимании.

2. Экстенсиональная и интенсиональная базы данных

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

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

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

Пример 8.1.

Пусть ЭБД содержит факты

parent('Иван', 'Галина'). parent('Дарья', 'Галина'). parent('Дарья', 'Софья'). parent('Галина', 'Николай'). parent('Николай', 'Елена').

108

ИБД содержит правила

ancestor(X, Y) :- parent(X, Y).

ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

При ответе на запрос пользователя

?-ancestor(X, 'Елена').

будет использована одна из строк (один из кортежей) неявно присутствующего в ИБД отношения ancestor/2:

ancestor('Николай', 'Елена').

Многократно вынуждаемый возврат – требование поиска других ответов на данный запрос – побудит использовать другие строки этого отношения (но, разумеется, не все, всего их в данном отношении 10):

ancestor('Галина', 'Елена'), ancestor('Иван', 'Елена'), ancestor('Дарья', 'Елена').

Надо сказать, что при поиске ответа на запрос отношение целиком не строится – ищется лишь одна его строка.

В адрес Пролога высказывается критика относительно его возможностей для реализации дедуктивных баз данных. В частности, Л. А. Калиниченко, редактор перевода книги «Логическое программирование и базы данных» [8], утверждает, что Пролог, якобы, не может выдавать в качестве ответа на запрос всё множество кортежей, а выдает лишь отдельные кортежи.

На это замечание можно возразить (по крайней мере, по отношению к системам LPA Prolog): такие встроенные предикаты как bagof/3 и setof/3 позволяют получать сразу все множество ответов на данный запрос!

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

109

служат «встроенные» предикаты Пролога: assert/1, asserta/1, retract/1.

Первые два из них предназначены для добавления в базу данных Пролога новых фактов и правил. Они безвозвратного действия, первый из них добавляет факт или правило в конец соответствующего определения, второй – в начало. (Для предиката assert/1 есть синоним: assertz/1.)

Третий предикат возвратного действия, с помощью него из базы данных удаляется факт или правило, сопоставимое с его аргументом. Если таковых нет, цель retract/1 дает отказ.

К сожалению, предикаты добавления в базу данных могут создавать «дубликаты» – повторяющиеся факты. Чтобы избежать это-

го, можно определить другой предикат добавления фактов (код

8.1).

Код 8.1

assert_new_fact(Fact) :- call(Fact), !.

assert_new_fact(Fact) :- !, assert(Fact).

3. Глобальные переменные

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

По этому поводу необходимо сделать следующее замечание. В Прологе все переменные принципиально являются локальными – они локализованы внутри одного утверждения (факта, правила или целевого утверждения). Как только переменная «означивается», все ее вхождения в данное утверждение получают то же значение.

Иногда бывает крайне желательно передавать какие-то значения из одного места программы в другое, явно не связанное с первым. Для этой цели можно предложить такой механизм: в базу данных с помощью предиката assert/1 заносится факт bag/2, первый аргумент которого – это имя глобальной переменной, а второй – ее значение. В ходе работы программы можно, по необходимости, извлекать по имени глобальной переменной ее значение, используя всё

110