Языки продукционного программирования

К настоящему времени создано несколько универсальных язы­ков продукционного программирования. Одним из наиболее известных языков этого класса является OPS5 [95], разработанный в университете Карнеги-Меллона. Рассмотрим осо­бенности этого языка. База данных в языке называется рабочей памятью (working memory) и состоит из нескольких сотен объектов, каждый из ко­торых имеет свой набор атрибутов. Объект вместе с парами < атрибут — значение> называется элементом рабочей памяти. Синтаксически эле­мент рабочей памяти выглядит следующим образом

(Expression | Name Expr1 | Arg1 2 | Oр * | Arg2 X),

здесь знак | является оператором языка OPS5 и отделяет имя атрибута от его значения. В данном примере сказано, что объект класса Expression имеет четыре атрибута: Name, Arg1, Ор, Arg2, которые имеют следую­щие значения: Name = Expr1, Arg1 = 2, Ор = *, Arg2 = X.

Программа на OPS5 — это множество продукций, каждая из которых имеет следующие особенности. Левая часть продукции — это последо­вательность образцов, каждый из которых представляет собой частич­ное описание элементов рабочей памяти. Некоторые образцы начинаются символом "-". Такие образцы являются средством задания отрицатель­ного контекста.

Условия левой части правила выполнены тогда, когда:

- для каждого образца данной продукции существует элемент рабо­чей памяти, который соответствует этому образцу;

- для образцов, помеченных символом "-" нет подходящих элементов в рабочей памяти.

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

Предикаты OPS5 традиционны и включают: =, ¹, £, >, <, ³. На­пример, следующий образец

(Expression |Arg1 < Left > | Arg 2 ¹ < Left >)

будет соответствовать любому элементу рабочей памяти, у которого пер­вый аргумент не равен второму.

Правая часть продукции состоит из последовательности безусловных действий. Все эти действия меняют рабочую память (базу данных). Вы­делены три типа действий:

MAKE — создает новый элемент рабочей памяти;

MODIFY — изменяет один или несколько значений атрибутов у существующего элемента рабочей памяти;

REMOVE — удаляет элемент рабочей памяти.

Каждая продукция в OPS5 состоит из символа Р, имени продукции, левой части, символа ®и правой части. Следующий пример иллюстри­рует типичную продукцию OPS5:

(Р TimeOx

(Goal | Type Simplify | Object <X>)

(Expression | Name <X> | Arg1 0 | Op *)

®

(MODIFY 2 | 0p NL |Arg2 NIL))

Основная задача, которую поставили перед собой разработчики языка OPS5, добиться максимально высокой эффективности выполнения про­дукционной программы. Интерпретатор системы порождает конфликт­ное множество, каждый элемент которого представляет собой пару <имя продукции, список элементов рабочей памяти, которые являются означи­ваниями для образцов продукции>.

Авторами языка OPS5 был предложен эффективный алгоритм по­строения конфликтного множества, получивший название RETE алго­ритм [94]. Эффективность интерпретатора зависит от перебора элемен­тов рабочей памяти и перебора продукций. RETE алгоритм позволяет избежать обоих этих переборов.

RETE алгоритм связывает с каждым образцом список тех элемен­тов рабочей памяти, которые означивают этот образец. Когда элемент добавляется в рабочую память, интерпретатор находит все образцы, ко­торым он соответствует и связывает этот элемент со всеми подходящими образцами. Когда элемент удаляется из рабочей памяти, то происходит обратное. Это означает, что интерпретатор никогда не делает поиска по образцу в рабочей памяти.

Второй вид циклов, снижающий эффективность работы системы, — это перебор продукционных правил. RETE алгоритм позволяет избегать этого перебора. Для этого над правилами строится сеть, которая позво­ляет сортировать продукции. Сеть строится из образцов левых частей продукций. Компилятор образцов строит из них сеть, связывая вместе одинаковые образцы из разных продукций. Было показано, что RETE ал­горитм реализует самую эффективную процедуру построения конфликт­ного множества в системах продукций [94].

Данный алгоритм обладает высокой степенью внутреннего паралле­лизма, и позднее было предложено большое количество его обобщений и расширений для параллельных архитектур [109]. В настоящее время известно большое количество интеллектуальных систем, реализованных на языке OPS5 [108,95,61].

Другой известный язык продукционного программирования — Рефал. Язык Рефал задуман и функционирует как универсальный метаязык для описания преобразований языковых объектов [58]. Рефал позволяет описывать сколь угодно сложные преобразования одного текста в другой без каких-либо ограничений на характер пре­образований. Эта ориентация языка получила название преобразование символьной информации. Одной из базовых операций языка является опе­рация конкретизации, которую можно определить как переход от имени к значению. В OPS5 этой операции соответствует операция означивания.

Знаки К и ! являются выделенными и называются конкретизационными скобками, в которые заключается языковой объект, подлежащий конкретизации. Так, например, если X'есть некоторая переменная вели­чина, то КХ! (конкретизация X) будет изображать значение этой величи­ны. Конкретизация — переход от имени к значению — является основной операцией в языке Рефал.

Минимальную семантическую единицу в языке называют символом и обозначают последовательностью любых знаков (букв и цифр), взятых в кавычки. Из простых объектов строятся структурные. Простейший вид задания структурных объектов — это скобки. Выражение определяет­ся как последовательность знаков, правильно построенная относительно скобок. Пример выражения: К 'ЕСЛИ' А<В 'ТО' А 'ИНАЧЕ' В!

Программа на языке Рефал представляет собой набор правил конкре­тизации. Поскольку правило конкретизации есть указание для замены одного языкового объекта на другой, то предложение состоит из левой части (заменяемый объект) и правой части (объект, заменяющий левую часть). Левая и правая части отделяются друг от друга символом -->. Например, предложение, выражающее тот факт, что значение перемен­ной Х есть 137, запишется в виде

К X! ®137

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

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

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

Приведенное краткое описание свойств Рефала наглядно демонстри­рует насколько близко данный язык совпадает с парадигмой продукци­онного программирования. К середине 70-х годов были разработаны эф­фективные программные версии Рефала, на которых был реализован ряд системдля решения задач символьных преобразований [3] и продукцион­ных систем [64].

Большое количество прикладных систем и моделей сделали возмож­ным разработать общую метамодель систем продукций и построить фор­мальные модели.