Волченков Логическое программирование язык пролог 2015
.pdfan_osn(osnova(X), C, C) --> |
% Анализ основы. |
|
[], {name(X, C)}. |
|
|
an_osn(Osn, T, C) --> |
|
|
[B], an_osn(Osn, [B|T], C). |
|
|
reverse(L, RL):- |
|
% Реверсирование списка. |
reverse(L, [], RL). |
|
|
reverse([], RL, RL). |
|
|
reverse([A|L], B, RL):- |
|
|
reverse(L, [A|B], RL). |
|
|
test1("красные"). |
% Запись "ab" эквивалентна |
|
|
% записи [97, 98]. |
|
test2("распрекрасной"). |
|
|
test3("весеннего"). test4("индиго").
Четыре предложения программы, относящиеся к анализу окончания, соответствуют четырём случаям: окончание может состоять из одной, двух, трёх букв или его вообще нет.
Анализ основы – это «сбор» всех оставшихся букв в один список методом входящей рекурсии.
Процедуру поиска в словаре fid/4 можно взять из кода 7.1. После отработки целевых утверждений
?-test1(L), |
an_morf(Res, L, []). |
?-test2(L), |
an_morf(Res, L, []). |
?-test3(L), |
an_morf(Res, L, []). |
?-test4(L), |
an_morf(Res, L, []). |
будут возвращены следующие значения переменной Res:
Res = morf(osnova(красн), okonch(pril:pad(именит): chislo(множ), ые))
Res = morf(osnova(распрекрасн), okonch(pril:pad(родит): rod(жен), ой))
Res = morf(osnova(весенн), okonch(pril:pad(родит): rod(муж), его))
Res = morf(osnova(индиго), okonch(void))
101
3.Синтаксический анализ кодов программ для упрощённой модели языка программирования операторного типа
Наш последний пример синтаксического анализатора взят из книги Л. Стерлинг, Э. Шапиро «Искусство программирования на языке Пролог» [7, гл. 23].
Речь пойдет о возможности использования Пролога для написания компиляторов традиционных языков программирования операторного типа (таких, например, как Паскаль). Сразу же может возникнуть следующий вопрос: «Какой смысл использовать для этой цели тихоходный Пролог?»
Ответить на этот вопрос можно так.
Во-первых, Пролог является «тихоходным» сейчас, будучи реализован на компьютерах с традиционной «фон неймановской» архитектурой. В будущем, в случае реализации на многопроцессорных машинах с высокой степенью распараллеливания, грядущие Пролог-системы по быстродействию не должны будут уступать самым эффективным системам программирования.
Во-вторых, даже в наше время «компиляторы» на Прологе могут служить прототипами будущих реальных систем. В силу наглядности, естественности и лаконичности Пролога в задачах символьного преобразования, его изначальной нацеленности на эффективный синтаксический анализ с широким использованием backtracking'а программирование всех этапов компиляции становится очень быстрым и нетрудоёмким делом. А прототип компилятора можно использовать для исследования его принципиальных возможностей, выявления изъянов и недостатков.
Компиляция программы, написанной на языке высокого уровня (здесь мы рассмотрим очень упрощённый вариант Паскаля – «учебный» язык PL) – это символьное преобразование текста этой программы в объектный код – программу на машинном языке. Компиляция обычно содержит несколько этапов: лексический и синтаксический анализ, генерацию кода, ассемблирование и, наконец, вывод объектной программы из абсолютной объектной структуры.
102
Продемонстрируем лишь один из указанных этапов – синтаксический анализ, так как именно он имеет непосредственное отношение к теме лекции.
На вход синтаксического анализатора поступает результат лексического анализа текста на языке PL – так называемый список лек-
сем (tokens).
Для примера рассмотрим три таких списка, соответствующих трем характерным языковым конструкциям:
program factorial; begin
read value; count := 1; result := 1;
while count < value do begin
count := count + 1; result := result * count end;
write result
end
program test1; begin
write x + y - z/2 end
program test2; begin
if a > b then max := a else max := b end
Эти списки таковы:
L1 = [program, factorial, ';', begin, read, value, ';', count, ':=', 1, ';', result, ':=', 1, ';', while, count, '<', value, do, begin, count, ':=', count, '+', 1, ';', result, ':=', result, '*', count, end, ';', write, result, end]
103
L2 = [program, test1, ';', begin, write, x, '+', y, '-', z, '/', 2, end]
L3 = [program, test2, ';', begin, if, a, '>', b, then, max, ':=', a, else, max, ':=', b, end]
Синтаксический анализатор, преобразующий списки такого рода в структуры, поступающие на вход генератора кода, представлен
следующим кодом:
Код 7.6
an_plprogram(ResStructure) --> [program], an_identifier(_), [';'], an_statement(ResStructure).
an_statement((S;Ss)) -->
[begin], an_statement(S), an_rest(Ss).
an_rest((S;Ss)) -->
[';'], an_statement(S), an_rest(Ss). an_rest(void) --> [end].
%Анализ операторов: присваивания (:=),
%условного (if then else),
%цикла с условием (while do), ввода и вывода. an_statement(assign(X, E)) -->
an_identifier(X), [':='], an_expr(E). an_statement(if(T, S1, S2)) -->
[if], an_test(T),
[then], an_statement(S1), [else], an_statement(S2). an_statement(while(T, S)) -->
[while], an_test(T), [do], an_statement(S).
an_statement(read(X)) --> [read], an_identifier(X). an_statement(write(X)) -->
[write], an_expr(X).
%Анализ "псевдоарифметических" выражений. an_expr(X) --> an_constant(X).
an_expr(expr(Op, X, Y)) -->
104
an_constant(X), an_arithmetic_op(Op), an_expr(Y).
% Анализ "констант" - идентификаторов и целых чисел an_constant(name(X)) -->
an_identifier(X). an_constant(number(X)) -->
an_integer(X).
an_identifier(X) -->
|
[X], {atom(X)}. |
an_integer(X) --> |
|
|
[X], {number(X)}. |
% |
Анализ условного выражения. |
an_test(compare(Op, X, Y)) --> |
|
|
an_expr(X), an_comparison_op(Op), |
|
an_expr(Y). |
% |
Анализ знаков операций. |
an_arithmetic_op(Op) --> [Op], {member(Op,['+','-','*','/'])}.
an_comparison_op(Op) --> [Op],
{member(Op,['=','<>','>','>=','<','<='])}.
В результате анализа трех приведенных выше списков лексем получаются следующие три структуры:
1)read(value); assign(count, number(1)); assign(result, number(1)); while(compare('<', name(count), name(value)), (assign(count, expr('+', name(count), number(1))); assign(result, expr('*', name(result), name(count))); void)); write(name(result)); void
2)write(expr('+', name(x), expr('-', name(y), expr('/', name(z), number(2))))); void
3)if(compare('>', name(a), name(b)), assign(max, name(a)), assign(max, name(b))); void
105
Полученные структуры таковы, что их уже можно «чисто технически», то есть, сравнительно легко интерпретировать с точки зрения реализации заложенного в них «алгоритмического смысла»: выполнить генерацию кода, ассемблирование и вывод объектной программы из абсолютной объектной структуры.
Отметим, что рассмотренный пример синтаксического анализатора использует довольно сильные упрощения и «огрубления». Так, арифметические выражения не являются таковыми в привычном толковании: выражение «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