Продукционные системы с исключениями

Если отношение "правило—исключение" встроено в систему, она сама может понять, что преобразование ПАЛКА à ПАЛКЫ незаконно. При этом система должна руководствоваться простым принципом: если применимо исключение, общее правило запрещено. Соответствующие системы будем называть системами с исключениями.

Отношение "общее правило — исключение" безусловно полезно для понимания системой уместности правил. Можно сказать, что это отношение устанавливает автоматически (по умолчанию) наиболее типичное для неформальных процедур взаимодействие правил:

— исключение "вытесняет" общее правило.

— при пересечении разрешены оба правила.

Разумеется, возможны ситуации, когда необходимо поступать наоборот:

— исключение не запрещает общего правила

— при пересечении одно из правил запрещено.

Пусть дано, например, общее правило х à р­₁ и его исключение Ах à р₂. Таким образом, для произвольного слова необходима реакция р₁. Для слова же, начинающегося с буквы А, исполняется реакция р₂ — по умолчанию для таких слов реакция р₁ незаконна.

Предположим, однако, что по условию конкретной задачи для слов, начинающихся с А, реакция р₁ также допустима. В этом случае введение нового правила Ах à р₁ снимает запрет на реакцию р₁ в ситуации Ах.

Аналогичный способ годится для пересечения правил.

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

При развитии продукционной системы с исключениями программист сосредотачивает свое внимание на выявлении новых правил и на обобщении уже имеющихся. Аппарат исключений освобождает программиста от решения трудоемких вопросов согласования правил — распознавание и интерпретация исключений осуществляется автоматически.

Язык Рефал

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

Разработчики языка Рефал делят алгоритмические языки на две группы. Первую группу образуют языки, которые называются языки операторного, или процедурного типа. Элементарными единицами программы являются здесь операторы, т.е. приказы, выполнение которых сводится к четко оп­ределенному изменению четко определенной части памяти машины. Ти­пичным представителем этой группы является язык машины Поста. Сюда же относятся машинные языки конретных ЭВМ, а также массовые языки программирования типа Фортран, Алгол, ПЛ/1.

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

Можно указать прообразы указанных типов алгоритмических языков в естественных языках. Для операторных языков это повелительное накло­нение (императив, приказание), для сентенциалышх - изъявительное нак­лонение (описание, повествование). Обращаясь к естественному языку, нетрудно заметить, что "изъявительное наклонение является несравненно более распространенным и образует, в сущности, основу языка, в то время как повелительное наклонение предстает в виде некоторой специальной модификации". Таким образом, можно сделать вывод о том, что "относительный вес изъявительного наклонения является мерой развитос­ти языка".

Язык РЕФАЛ является сентенциальным в своей основе, а вся информа­ция в этом языке представляется в виде правил конкретизации. Каждое правило записывается в виде предложения, которое представляет собой продукцию с определенными синтаксисом и семантикой. Предложения в Рефал-программе отделяются друг от друга знаком § (параграф).

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

k и ^, которые будем называть конкретизационными скобками, и кото­рые будут содержать объект, подлежащий конкретизации. Так, если х — некоторая переменная, то kx^. (конкретизация х) будет изображать значе­ние этой величины. Другой пример: объект k28 +7^ при правильном опре­делении операции сложения рано или поздно будет заменен на объект 35.

Выполнение конкретизации — переход от имени к значению — объявляется основной и, по существу, единственной операцией в языке Рефал. Эту опера­цию будет выполнять Рефал-машина (имеется в виду машина на логи­ческом уровне, имитируемая соответствующим транслятором на уни­версальной ЭВМ; возможно, разумеется, и построение реальной "физи­ческой" Рефал-машины).

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

Пример 3.5. Предложение, выражающее тот факт, что значение переменной Х есть 137, записывается в виде

§kX^à137.

Между знаком § и первым знаком k можно вставлять последовательность знаков, которая будет служить номером предложения, или комментарием к нему, например:

§ l.l kX^à137.

(ф. 27)

Опишем теперь структуру Рефал-машины, которая, используя предло­жения Рефал-программы, будет выполнять конкретизации. Будем считать, что объектом обработки является некоторое выражение (слово), которое находится в поле зрения машины. Работа машины осуществляется по шагам, каждый из которых представляет выполнение одного акта, конкрети­зации.

Пусть программа машины состоит из единственного предложения (ф. 27), а в поле зрения находится выражение kX^. Тогда за один шаг машина заме­нит содержимое поле зрения на 137, после чего она остановится, т. к. знаков конкретизации больше нет, и следовательно, делать ей больше нечего.

Так как Рефал-программа содержит, вообще говоря, набор (последова­тельность) предложений, может оказаться, что для выполнения данной кон­кретизации пригодно не одно, а несколько предложений. Например, в поле памяти, кроме (ф. 27), может находиться еще предложение

§ 1.2 kX^à274.

Неоднозначность, которая отсюда может возникнуть, устраняется так же, как это принято в нормальных алгоритмах Маркова (читатель, видимо, уже заметил, что Рефал-машина следует идеологии этих алгоритмов): машина просматривает предложения в том порядке, в котором они рас­положены в Рефал-программе, и применяет первое из них, которое окажет­ся подходящим.

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

Пример. Пусть Рефал-программа имеет вид

kX^à137

kX^à274

kY^à2

k137+2^à139,

а поле зрения содержит выражение

kkX^+kY^^.

На первом шаге замене подлежит подвыражение kX^ — получим в поле зрения kl37 + kY^^. Теперь в первую очередь конкретизируется kY^ — получим в результате применения третьего предложения k137 +2^ и на последнем шаге получим 139, не содержащее символов k. (Разумеется для реального сложения используются соответствующие встроенные функции, а этот пример — лишь простейшая иллюстрация принципов рабо­ты машины [21]).

Чтобы иметь возможность представлять обобщенные предложения, ис­пользуются три типа переменных: е — для представления выражений; t — для термов; s — для символов. В простейшем случае переменные записы­ваются в виде указателя типа (е, t, s) и индекса; например, е₁, e₂ — пере­менные, пробегающие в качестве значений выражения. Выражением в язы­ке Рефал называется последовательность знаков, правильно построенная в соответствеии с синтаксисом языка Рефал. Терм языка Рефал — это либо символ, либо выражение в круглых или конкретизационных скобках. Выражения строятся из термов.

Пример. Предположим, требуется написать программу, кото­рая выполняет раскрытие скобок в алгебраических выражениях, построен­ных из букв с помощью скобок, знаков сложения "+" и умножения"*". Рассмотрим процесс написания такой программы. Если некоторое выра­жение е имеет вид е₁ + e₁, где е₁, e₁ — выражения, то для раскрытия ско­бок надо: раскрыть скобки в e₁, раскрыть скобки в е₂, полученные резуль­таты сложить. Эту мысль в компактном, но в то же время и наглядном ви­де выражает предложение:

§ 2.1 ke₁ +e₂^à ke₁^ +ke₂^

Если же выражение е имеет вид e₁ * e₂, то, вообще говоря, необходимо учитывать две возможности:

— хотя бы один из сомножителей есть сумма (например, е = (А + В) *С),

— ни одно из выражений е₁ или е₂ не представимо в виде суммы (на­пример, е = (А * В) * (С * Л)).

В первом случае надо описать законы дистрибутивности:

§ 2.2ke₁ * (e₂ +e₃) ^àke₁ * e₂^ +ke₁*e₃^,

§ 2.3k(e₁ +e₂) * e₃^àke₁ * e₃^ + ke₂*e₃^ ,

§ 2.4ke₁ * (e₂ + e₃) * e₄ ^ à k(e₁ * е₂ + e₁ * e₃) * e₄^.

Во втором случае по аналогии со сложением имеем

§ 2.5ke₁ * е₂^ à ke₁^* ke₂^.

Наконец, осталось выразить возможность "снятия внешних скобок" и условие "терминальности" символов, что определяют предложения:

§ 2.6k(e) ^ à ke^,

§ 2.7ks^ à s

(буквы не подлежат конкретизации).

Приведенные семь предложений § 2.1 - § 2.7 решают задачу. Рассмот­рим как эта программа обрабатывает выражение

k(A +B) * (С +D) ^.

Последовательно получим в результате работы программы (для удобства слева указываем номер правила, которое непосредственно привело к дан­ному выражению):

§2.2 k(A +В)*С^. + k(A +B)*D^,

§2.3 kA *C^ +kB*C^ + k(A+B)*D^,

§2.3 kA *C^ + kB*C^ + kA *D^ + kB*D^.

Далее ограничимся рассмотрением первого слагаемого:

§ 2.5 kA^ * kC^ + ...,

§2.7 A * kC^ + ...,

§ 2.7 А * С + ... .

После аналогичной обработки остальных слагаемых получим искомое выражение

А*С+D*С+А * D + В * D.

Если на вход поступит выражение

kA + (B + С) ^,

то получим последовательно:

§ 2.1 kA^ + k(B + С) ^,

§ 2.7 А + k (Д + С) ^,

§ 2.6 А + kB + C^,

§2.1, 2.7 A + B + С.

Обратите внимание, что если расположить правило § 2.5 перед правила­ми § 2.2 и § 2.3, то придем к абсурду! Например, выражение А *(В+С) будет приведено к виду: А *В + С.

Пролог

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

Синтаксис

ТЕРМЫ

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

0, -l, 123.4, 0.23E-5,

(некоторые реализации Пролога не поддерживают действительные числа).

К константам относятся также атомы, такие, как:

голди, а, атом, +, :, 'Фред Блогс', [].

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

abcd, фред, ':', Джо.

Полный синтаксис атомов описан ниже.

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

Имена переменных начинаются с заглавных букв или с символа подчеркивания "_". Примеры переменных:

X, Переменная, _3, _переменная.

Если переменная используется только один раз, необязательно называть ее. Она может быть записана как анонимная переменная, состоящая из одного символа подчеркивания "_". Переменные, подо­бно атомам, являются элементарными объектами языка Пролог.

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

Теперь перейдем к более детальному описанию термов.

КОНСТАНТЫ

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

ATOM

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

1) атом, состоящий только из чисел, букв и символа подчеркива­ния и начинающийся со строчной буквы;

2) атом, состоящий целиком из специальных символов. К специ­альным символам относятся:

+ - * / ^ = : ; ? @ $ &

Заметим, что атом, начинающийся с /*, будет воспринят как на­чало комментария, если он не заключен в одинарные кавычки.

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

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

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

ЧИСЛА

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

ПЕРЕМЕННЫЕ

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

Синтаксис переменной довольно прост. Она должна начинаться с прописной буквы или символа подчеркивания и содержать только символы букв, цифр и подчеркивания.

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