Лекция 6. Логическое программирование

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

Парадигма логического программирования использует идею автоматиче- ского вывода информации на основе заданных фактов и правил. Логическое программирование основано на теории и аппарате формальной логики. Напи- санная согласно формальной логике программа является множеством логи- ческих форм, представляющих факты и правила относительно некоторой предметной области. Основным языком логического программирования при- знан Prolog, хотя известны и другие – Planner, ASP и Datalog. Во всех таких языках правила имеют форму клауз:

H                   :- B1₁, …, BN_n,

понимаемую как логическое следование

if                       (B1₁ and … and BN) then H

или

B11 & … & BN → H

H называют головой правила, а B1₁, …, BN – телом.

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

to solve H, solve B₁, and... and solve B_n.

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

 

 

Операционная семантика

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

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

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

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

Если варианты в таком выражении рассматривать как равноправные ком- поненты, то неясно, как предотвратить преждевременный выбор пустого списка при непустом перечне вариантов. Чтобы решить эту задачу, в систе- мах ЛП вводится специальная форма ESC (ТУПИК), действие которой за- ключается в том, что она как бы «старается» по возможности не исполняться. Иными словами, при выборе вариантов предпочитаются варианты, не приво- дящие к исполнению формы ESC. Такая же проблема возникает при обра- ботке пустых цепочек в грамматиках. Аналогичная проблема решена при мо- делировании процессов интерпретированными сетями Петри соглашением о приоритете нагруженных переходов в сравнении с пустыми.

 

 

Абстрактный синтаксис сводим к формуле (факт | (предикат цель) | ESC)

Абстрактная машина (AML:

AML =        <SCL,  RL>,   где RL = <S, E, C, D, R>

AML – абстрактная машина для ЛП, SCL – система команд для ЛП,

S – стек результатов,

E – значения локальных переменных,

C – текущая позиция в вычисляемом варианте, D – дамп текущих вычислений,

R – невычислявшиеся варианты.

 

s e c d r → s' e' c' d' r' – переход от старого состояния к новому.

s e c d те же, что и в ФП, r – предназначен для хранения не опробованных вариантов.

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

Таблица 31