Говоря о неформальных процедурах, мы обычно хорошо понимаем, что имеется в виду, и без затруднений можем привести примеры таких процедур, связанных с
Трудности возникают при попытке точного определения подобных процедур. Так, если рассматривать неформальные процедуры всего лишь как абстрактные функции, которые для каждого значения аргумента "выдают" некоторое значение, то категория неформальности вообще исчезает из рассмотрения.
В практике программирования алгоритмы принято описывать с помощью алгоритмических языков программирования. Широко используются также разного рода блок-схемы алгоритмов, позволяющие представить алгоритмы в наглядном и общедоступном виде, не привлекая в тоже время сложных конструкций из конкретных языков программирования.
Чтобы оценить возможности использования алгоритмов для представления неформальных процедур, рассмотрим простую задачу.
ЗАДАЧА. Описать процедуру, реализующую преобразование из именительного падежа в родительный для существительных следующих типов: ДОМ, МАМА, ВИЛКА, КИНО, НОЧЬ, ТОКАРЬ, КИЛЬ.
Решение 1 указано на рис. 6.1 в виде блок-схемы соответствующего алгоритма.
(рис 6.1) Решение 1. АлгоритмС точки зрения программирования на алгоритмических языках достоинства подобного представления очевидны — эта блок-схема без затруднений переводится в текст программы, например, на языке Ассемблер или С++. Однако само составление подобной блок-схемы при появлении существительных новых типов становится, очевидно, все более и более утомительным занятием. Для иллюстрации этого предположим, что дана
ДОПОЛНИТЕЛЬНАЯ ЗАДАЧА. Расширить алгоритм, представленный на рис. 6.1, на слова ВАСЯ, ВРЕМЯ, АКЦИЯ, ЗАДАЧА.
Разумеется, программист без особого труда составит соответствующую блок-схему алгоритма. И все же, если учесть, что подобные изменения и расширения алгоритма при программировании неформальных процедур происходят многократно (реальная сложность неформальной процедуры как раз и проявляется в практической невозможности предусмотреть заранее все случаи), следует признать, что, вполне правильное в статике, решение 1 в динамике неудачно!
В подобных случаях для обеспечения динамичности процессов модификации программ используются те или иные варианты таблиц решений. С учетом этого для исходной задачи более приемлемо решение 2.
| Ситуация | Действие | Ситуация | Действие |
|---|---|---|---|
| КИНО | КИНО | -Ь | -И |
| -ча | -чи | -ие | -ия |
| -КА | -КИ | -мя | -мени |
| -А | -Ы | -я | -и |
| -АРЬ | -АРЯ | - | -А |
| -Ь М:хЬ | -Я |
Соответствующая таблица решений содержит две графы: слева приведены описания ситуаций, справа — соответствующие действия. Предполагается, что программист разработал интерпретирующую программу для подобных таблиц. Эта программа работает следующим образом. Для конкретного входного слова, пусть это будет для примера слово РОЗА, осуществляется последовательный просмотр ситуаций, указанных в таблице, и сравнение их со входным словом. Если слово соответствует некоторой ситуации, то выполняется действие, указанное для этой ситуации.
Для слова РОЗА будет обнаружено соответствие с ситуацией "-А". В результате выполнения действия "-Ы" будет получено выходное слово РОЗЫ.
Теперь значительно упрощается расширение на новые классы слов — необходимо лишь обеспечить внесение вставок на нужное место в таблице решений.
Таблицы решений представляют собой частный случай так называемых продукционных систем. В этих системах правила вычислений представляются в виде продукций. Продукции представляют собой операторы специального вида и состоят из двух основных частей, для краткости называемых обычно "ситуация — действие".
"Ситуация" содержит описание ситуации, в которой применима продукция. Это описание задается в виде условий, называемых посылками продукции. "Действие" — это набор инструкций, подлежащих выполнению в случае применимости продукции.
Таблица решений, приведенная в Таблице 6.1, иллюстрирует так называемую безвозвратную процедуру. В этом случае на каждом шаге выбирается единственное решение — так, для слова РОЗА таким решением будет РОЗЫ, — проблема выбора решения не возникает. В общем случае неформальные процедуры являются многозначными, а правильность конкретного выбора, сделанного на некотором шаге, проверяется на следующих шагах. При этом используется так называемый режим возвратов.
МАТЬ ——————> ЛЮБИТ ——————> ?
что делать? кого?
МАТЬ <—————— ЛЮБИТ <—————— ?
кого? что делать?
Пусть предложение начинается со слов МАТЬ ЛЮБИТ ... . Проанализировав эти слова в первоначальном предположении именительного падежа для слова МАТЬ, система вправе построить структуру, представленную в случае 1). Если следующее слово после слова ЛЮБИТ представляет собой существительное в винительном падеже, например, вся фраза имеет вид МАТЬ ЛЮБИТ СЫНА, то эта структура является окончательной. Если же фраза имеет вид МАТЬ ЛЮБИТ СЫН, то возникает противоречие или, как говорят, сигнал неуспеха — очередное слово СЫН противоречит ожиданию прямого дополнения. В этом случае система должна вернуться на ближайший из предыдущих шагов, где можно принять другую альтернативу анализа. В данном примере это шаг анализа слова МАТЬ — система должна принять теперь альтернативу винительного падежа для этого слова. Далее будет построена структура, указанная в случае 2).
Тривиальность рассмотренного примера убеждает в необходимости режима возвратов при реализации неформальных процедур.
Важность логического вывода становится очевидной уже при рассмотрении простейших информационно-логических процедур. Предположим, что некоторая база данных содержит сведения об отношениях " х — ОТЕЦ у " и " х — МАТЬ у ". Чтобы обработать запросы типа:
ИВАНОВ А.И. — ДЕД ПЕТРОВА В.А.?
ПЕТРОВ В.А. — ВНУК ИВАНОВА А.И.?
необходимо либо ввести в базу данных также и сведения об отношениях " х — ДЕД у " и " х — ВНУК у ", либо объяснить системе, как из отношений ОТЕЦ, МАТЬ извлечь искомую информацию. Реализация первой возможности связана с неограниченным ростом избыточности базы данных. Вторая возможность при традиционном
Логический вывод позволяет расширять возможности "общения" наиболее просто и наглядно. Так, для приведенных типов запросов системе достаточно будет сообщить три правила:
х —ДЕД у если х —ОТЕЦ а и а —РОДИТЕЛЬ у ;х —РОДИТЕЛЬ у если х —ОТЕЦ у или х —МАТЬ у ;х —ВНУК у если у —ДЕД х.Эти правила содержат естественные и очевидные определения понятий ДЕД, РОДИТЕЛЬ, ВНУК. Поясним, в чем состоит логический вывод для запроса " А —ДЕД В?" в предположении, что в базе данных имеются факты: А —ОТЕЦ Б и Б —МАТЬ В. При этом для упрощения опустим тонкости, связанные с падежными окончаниями. Пользуясь определением 1, система придет к необходимости проверки существования такого индивидуума а, что факты А —ОТЕЦ а и а —РОДИТЕЛЬ В истинны. Если такой а существует, то А —ДЕД В, если не существует такого а, то А не является дедом В.
Продукционные системы, содержащие аппарат логического вывода, отличает высокая степень общности правил обработки данных. Однако именно эта общность приводит к ухудшению
Мы могли бы использовать в таблице решений только конкретные факты, например правила ДОМ -> ДОМА, МАМА -> МАМЫ и т. д., и динамичность соответствующей таблицы решений была бы восстановлена — подобные правила можно было бы вводить в произвольном порядке! Однако цена подобной "динамичности" окажется непомерно высокой — полный отказ от обобщенных правил.
Желательно восстановить динамичность продукционно-логических систем, сохранив при этом в полном объеме возможность использования обобщенных правил. Продукционная система должна взять на себя функции распознавания и интерпретации приоритета продукций — программист должен только описывать ситуации и соответствующие им действия.
Если отношение "правило—исключение" встроено в систему, она сама может понять, что преобразование ПАЛКА -> ПАЛКЫ неверно. При этом система должна руководствоваться простым принципом: если применимо исключение, общее правило запрещено. Соответствующие системы будем называть системами с исключениями.
Отношение "общее правило — исключение" безусловно полезно для понимания системой уместности правил. Можно сказать, что это отношение устанавливает автоматически (по умолчанию) наиболее типичное для неформальных процедур взаимодействие правил:
Разумеется, возможны ситуации, когда необходимо поступать наоборот:
Пусть дано, например, общее правило $$х \to р_1$$ и его исключение $$Ах \to р_2$$. Таким образом, для произвольного слова необходима реакция р1. Для слова же, начинающегося с буквы А, исполняется реакция р2 — по умолчанию для таких слов реакция р1 незаконна.
Предположим, однако, что по условию конкретной задачи для слов, начинающихся с А, реакция р1 также допустима. В этом случае введение нового правила $$Ах \to р_1$$ снимает запрет на реакцию р1 в ситуации Ах.
Аналогичный способ годится для пересечения правил.
Таким образом, аппарат исключений позволяет устанавливать произвольные способы взаимодействия правил, в том числе и отличные от взаимодействия по умолчанию.
При развитии продукционной системы с исключениями программист сосредотачивает свое внимание на выявлении новых правил и на обобщении уже имеющихся. Аппарат исключений освобождает программиста от решения трудоемких вопросов согласования правил — распознавание и интерпретация исключений осуществляется автоматически.
Название языка происходит от "РЕкурсивных Функций АЛгоритмический язык". Нас будут также интересовать соображения, которые привели к построению этого языка — эти соображения имеют, на наш взгляд, весьма общий характер и полезны для лучшего понимания причин возникновения продукционного подхода в программировании.
Разработчики языка
Языки второй группы называются языками сентенциального, или декларативного типа (
Можно назвать прообразы указанных типов алгоритмических языков в естественных языках. Для операторных языков это повелительное наклонение (императив, приказание), для сентенциальных – изъявительное наклонение (описание, повествование). Обращаясь к естественному языку, нетрудно заметить, что "изъявительное наклонение является несравненно более распространенным и образует, в сущности, основу языка, в то время как повелительное наклонение предстает в виде некоторой специальной модификации". Таким образом, можно сделать вывод о том, что "относительный вес изъявительного наклонения является мерой развитости языка".
§ (параграф).
Каждое правило конкретизации определяет раскрытие смысла некоторого понятия через более элементарные. Операцию конкретизации можно также определить как переход от имени к значению. Введем два знака: k и $$\perp$$, которые будем называть конкретизационными скобками, и которые будут содержать объект, подлежащий конкретизации. Так, если х — некоторая переменная, то $$kx\perp$$ (конкретизация х ) будет изображать значение этой величины. Другой пример: объект $$k28 +7\perp$$ при правильном определении операции сложения рано или поздно будет заменен на объект 35.
Выполнение конкретизации — переход от имени к значению — объявляется основной и, по существу, единственной операцией в языке
Поскольку правило конкретизации есть указание для замены одного объекта (слова в некотором алфавите) на другой, предложения языка
Пример. Предложение, выражающее тот факт, что значение переменной Х есть 137, записывается в виде $$§kX \perp \to 137$$.
Между знаком § и первым знаком k можно вставлять последовательность знаков, которая будет служить номером предложения, или комментарием к нему, например:
$$§ l.l kX \perp \to 137$$. (ф. 1)
Опишем теперь структуру
Пусть программа машины состоит из единственного предложения (ф. 1), а в поле зрения находится выражение $$kX\perp$$. Тогда за один шаг машина заменит содержимое поля зрения на 137, после чего она остановится, т. к. знаков конкретизации больше нет и, следовательно, делать ей больше нечего.
Так как
$$§ 1.2 kX \perp \to 274$$.
Неоднозначность, которая отсюда может возникнуть, устраняется так же, как это принято в нормальных алгоритмах Маркова (читатель, видимо, уже заметил, что
Поле зрения может содержать сколько угодно конкретизационных скобок, причем они могут быть как угодно вложены друг в друга. В этом случае k, в области действия которого (т.е. в последовательности знаков до парной скобки $$\perp$$ ) нет ни одного знака k. Выражение, находящееся в области этого знака k, последовательно сравнивается с левыми частями предложений
Пример. Пусть
$$kX \perp \to 137$$
$$kX \perp \to274$$
$$kY \perp \to 2$$
$$k137+2 \perp \to 139$$,
а поле зрения содержит выражение
$$kkX \perp +kY \perp \perp$$.
На первом шаге замене подлежит подвыражение $$kX\perp$$ — получим в поле зрения $$kl37 + kY\perp \perp$$. Теперь в первую очередь конкретизируется $$kY\perp$$ — получим в результате применения третьего предложения $$k137 +2\perp$$ и на последнем шаге получим 139, не содержащее символов k. (Разумеется для реального сложения используются соответствующие встроенные функции, а этот пример — лишь простейшая иллюстрация принципов работы машины).
Чтобы иметь возможность представлять обобщенные предложения, используются три типа переменных: е — для представления выражений; t — для термов; s — для символов. В простейшем случае переменные записываются в виде указателя типа (е, t, s) и индекса; например, е1, e2 — переменные, пробегающие в качестве значений выражения.
Пример. Предположим, требуется написать программу, которая выполняет раскрытие скобок в алгебраических выражениях, построенных из букв с помощью скобок, знаков сложения "+" и умножения"*". Рассмотрим процесс написания такой программы. Если некоторое выражение е имеет вид е1 + e1, где е1, e1 — выражения, то для раскрытия скобок надо: раскрыть скобки в e1, раскрыть скобки в е2, полученные результаты сложить. Эту мысль в компактном, но в то же время и наглядном виде выражает предложение:
$$§ 2.1 ke_1 +e_2\perp \to ke_1\perp +ke_2\perp$$
Если же выражение е имеет вид e1 * e2, то, вообще говоря, необходимо учитывать две возможности:
е = (А + В) *С ),е1 или е2 не представимо в виде суммы (например, е = (А * В) * (С * Л) ).В первом случае надо описать законы дистрибутивности:
$$§ 2.2ke_1 * (e_2 +e_3) \perp \to ke_1 * e_2\perp +ke_1*e_3\perp$$,
$$§ 2.3k(e_1 +e_2) * e_3\perp \to ke_1 * e_3\perp + ke_2*e_3\perp$$,
$$§ 2.4ke_1 * (e_2 + e_3) * e_4 \perp \to k(e_1 * е_2 + e_1 * e_3) * e_4\perp$$.
Во втором случае по аналогии со сложением имеем
$$§ 2.5ke_1 * е_2\perp \to ke_1\perp * ke_2\perp$$.
Наконец, осталось выразить возможность "снятия внешних скобок" и условие "терминальности" символов, что определяют предложения:
$$§ 2.6k(e) \perp \to ke\perp$$,
$$§ 2.7ks\perp \to s$$
(буквы не подлежат конкретизации).
Приведенные семь предложений § 2.1 — § 2.7 решают задачу. Рассмотрим как эта программа обрабатывает выражение
$$k(A +B) * (С +D) \perp$$.
Последовательно получим в результате работы программы (для удобства слева указываем номер правила, которое непосредственно привело к данному выражению):
$$§2.2 k(A +В)*С\perp . + k(A +B)*D\perp$$,
$$§2.3 kA *C\perp +kB*C\perp + k(A+B)*D\perp$$,
$$§2.3 kA *C\perp + kB*C\perp + kA *D\perp + kB*D\perp$$.
Далее ограничимся рассмотрением первого слагаемого:
$$§ 2.5 kA\perp * kC\perp + ..$$.,
$$§2.7 A * kC\perp + ..$$.,
§ 2.7 А * С + ....
После аналогичной обработки остальных слагаемых получим искомое выражение
А*С+D*С+А * D + В * D.
Если на вход поступит выражение
$$kA + (B + С) \perp$$,
то получим последовательно:
$$§ 2.1 kA\perp + k(B + С) \perp$$,
$$§ 2.7 А + k (Д + С) \perp$$,
$$§ 2.6 А + kB + C\perp$$,
§2.1, 2.7 A + B + С.
Обратите внимание, что если расположить правило § 2.5 перед правилами § 2.2 и § 2.3, то мы придем к абсурду! Например, выражение А *(В+С) будет приведено к виду: А *В + С.
Говоря о неформальных процедурах, мы обычно хорошо понимаем, что имеется в виду, и без затруднений можем привести примеры таких процедур, связанных с
Трудности возникают при попытке точного определения подобных процедур. Так, если рассматривать неформальные процедуры всего лишь как абстрактные функции, которые для каждого значения аргумента "выдают" некоторое значение, то категория неформальности вообще исчезает из рассмотрения.
В практике программирования алгоритмы принято описывать с помощью алгоритмических языков программирования. Широко используются также разного рода блок-схемы алгоритмов, позволяющие представить алгоритмы в наглядном и общедоступном виде, не привлекая в тоже время сложных конструкций из конкретных языков программирования.
Чтобы оценить возможности использования алгоритмов для представления неформальных процедур, рассмотрим простую задачу.
ЗАДАЧА. Описать процедуру, реализующую преобразование из именительного падежа в родительный для существительных следующих типов: ДОМ, МАМА, ВИЛКА, КИНО, НОЧЬ, ТОКАРЬ, КИЛЬ.
Решение 1 указано на рис. 6.1 в виде блок-схемы соответствующего алгоритма.
(рис 6.1) Решение 1. АлгоритмС точки зрения программирования на алгоритмических языках достоинства подобного представления очевидны — эта блок-схема без затруднений переводится в текст программы, например, на языке Ассемблер или С++. Однако само составление подобной блок-схемы при появлении существительных новых типов становится, очевидно, все более и более утомительным занятием. Для иллюстрации этого предположим, что дана
ДОПОЛНИТЕЛЬНАЯ ЗАДАЧА. Расширить алгоритм, представленный на рис. 6.1, на слова ВАСЯ, ВРЕМЯ, АКЦИЯ, ЗАДАЧА.
Разумеется, программист без особого труда составит соответствующую блок-схему алгоритма. И все же, если учесть, что подобные изменения и расширения алгоритма при программировании неформальных процедур происходят многократно (реальная сложность неформальной процедуры как раз и проявляется в практической невозможности предусмотреть заранее все случаи), следует признать, что, вполне правильное в статике, решение 1 в динамике неудачно!
В подобных случаях для обеспечения динамичности процессов модификации программ используются те или иные варианты таблиц решений. С учетом этого для исходной задачи более приемлемо решение 2.
| Ситуация | Действие | Ситуация | Действие |
|---|---|---|---|
| КИНО | КИНО | -Ь | -И |
| -ча | -чи | -ие | -ия |
| -КА | -КИ | -мя | -мени |
| -А | -Ы | -я | -и |
| -АРЬ | -АРЯ | - | -А |
| -Ь М:хЬ | -Я |
Соответствующая таблица решений содержит две графы: слева приведены описания ситуаций, справа — соответствующие действия. Предполагается, что программист разработал интерпретирующую программу для подобных таблиц. Эта программа работает следующим образом. Для конкретного входного слова, пусть это будет для примера слово РОЗА, осуществляется последовательный просмотр ситуаций, указанных в таблице, и сравнение их со входным словом. Если слово соответствует некоторой ситуации, то выполняется действие, указанное для этой ситуации.
Для слова РОЗА будет обнаружено соответствие с ситуацией "-А". В результате выполнения действия "-Ы" будет получено выходное слово РОЗЫ.
Теперь значительно упрощается расширение на новые классы слов — необходимо лишь обеспечить внесение вставок на нужное место в таблице решений.
Таблицы решений представляют собой частный случай так называемых продукционных систем. В этих системах правила вычислений представляются в виде продукций. Продукции представляют собой операторы специального вида и состоят из двух основных частей, для краткости называемых обычно "ситуация — действие".
"Ситуация" содержит описание ситуации, в которой применима продукция. Это описание задается в виде условий, называемых посылками продукции. "Действие" — это набор инструкций, подлежащих выполнению в случае применимости продукции.
Таблица решений, приведенная в Таблице 6.1, иллюстрирует так называемую безвозвратную процедуру. В этом случае на каждом шаге выбирается единственное решение — так, для слова РОЗА таким решением будет РОЗЫ, — проблема выбора решения не возникает. В общем случае неформальные процедуры являются многозначными, а правильность конкретного выбора, сделанного на некотором шаге, проверяется на следующих шагах. При этом используется так называемый режим возвратов.
МАТЬ ——————> ЛЮБИТ ——————> ?
что делать? кого?
МАТЬ <—————— ЛЮБИТ <—————— ?
кого? что делать?
Пусть предложение начинается со слов МАТЬ ЛЮБИТ ... . Проанализировав эти слова в первоначальном предположении именительного падежа для слова МАТЬ, система вправе построить структуру, представленную в случае 1). Если следующее слово после слова ЛЮБИТ представляет собой существительное в винительном падеже, например, вся фраза имеет вид МАТЬ ЛЮБИТ СЫНА, то эта структура является окончательной. Если же фраза имеет вид МАТЬ ЛЮБИТ СЫН, то возникает противоречие или, как говорят, сигнал неуспеха — очередное слово СЫН противоречит ожиданию прямого дополнения. В этом случае система должна вернуться на ближайший из предыдущих шагов, где можно принять другую альтернативу анализа. В данном примере это шаг анализа слова МАТЬ — система должна принять теперь альтернативу винительного падежа для этого слова. Далее будет построена структура, указанная в случае 2).
Тривиальность рассмотренного примера убеждает в необходимости режима возвратов при реализации неформальных процедур.
Важность логического вывода становится очевидной уже при рассмотрении простейших информационно-логических процедур. Предположим, что некоторая база данных содержит сведения об отношениях " х — ОТЕЦ у " и " х — МАТЬ у ". Чтобы обработать запросы типа:
ИВАНОВ А.И. — ДЕД ПЕТРОВА В.А.?
ПЕТРОВ В.А. — ВНУК ИВАНОВА А.И.?
необходимо либо ввести в базу данных также и сведения об отношениях " х — ДЕД у " и " х — ВНУК у ", либо объяснить системе, как из отношений ОТЕЦ, МАТЬ извлечь искомую информацию. Реализация первой возможности связана с неограниченным ростом избыточности базы данных. Вторая возможность при традиционном
Логический вывод позволяет расширять возможности "общения" наиболее просто и наглядно. Так, для приведенных типов запросов системе достаточно будет сообщить три правила:
х —ДЕД у если х —ОТЕЦ а и а —РОДИТЕЛЬ у ;х —РОДИТЕЛЬ у если х —ОТЕЦ у или х —МАТЬ у ;х —ВНУК у если у —ДЕД х.Эти правила содержат естественные и очевидные определения понятий ДЕД, РОДИТЕЛЬ, ВНУК. Поясним, в чем состоит логический вывод для запроса " А —ДЕД В?" в предположении, что в базе данных имеются факты: А —ОТЕЦ Б и Б —МАТЬ В. При этом для упрощения опустим тонкости, связанные с падежными окончаниями. Пользуясь определением 1, система придет к необходимости проверки существования такого индивидуума а, что факты А —ОТЕЦ а и а —РОДИТЕЛЬ В истинны. Если такой а существует, то А —ДЕД В, если не существует такого а, то А не является дедом В.
Продукционные системы, содержащие аппарат логического вывода, отличает высокая степень общности правил обработки данных. Однако именно эта общность приводит к ухудшению
Мы могли бы использовать в таблице решений только конкретные факты, например правила ДОМ -> ДОМА, МАМА -> МАМЫ и т. д., и динамичность соответствующей таблицы решений была бы восстановлена — подобные правила можно было бы вводить в произвольном порядке! Однако цена подобной "динамичности" окажется непомерно высокой — полный отказ от обобщенных правил.
Желательно восстановить динамичность продукционно-логических систем, сохранив при этом в полном объеме возможность использования обобщенных правил. Продукционная система должна взять на себя функции распознавания и интерпретации приоритета продукций — программист должен только описывать ситуации и соответствующие им действия.
Если отношение "правило—исключение" встроено в систему, она сама может понять, что преобразование ПАЛКА -> ПАЛКЫ неверно. При этом система должна руководствоваться простым принципом: если применимо исключение, общее правило запрещено. Соответствующие системы будем называть системами с исключениями.
Отношение "общее правило — исключение" безусловно полезно для понимания системой уместности правил. Можно сказать, что это отношение устанавливает автоматически (по умолчанию) наиболее типичное для неформальных процедур взаимодействие правил:
Разумеется, возможны ситуации, когда необходимо поступать наоборот:
Пусть дано, например, общее правило $$х \to р_1$$ и его исключение $$Ах \to р_2$$. Таким образом, для произвольного слова необходима реакция р1. Для слова же, начинающегося с буквы А, исполняется реакция р2 — по умолчанию для таких слов реакция р1 незаконна.
Предположим, однако, что по условию конкретной задачи для слов, начинающихся с А, реакция р1 также допустима. В этом случае введение нового правила $$Ах \to р_1$$ снимает запрет на реакцию р1 в ситуации Ах.
Аналогичный способ годится для пересечения правил.
Таким образом, аппарат исключений позволяет устанавливать произвольные способы взаимодействия правил, в том числе и отличные от взаимодействия по умолчанию.
При развитии продукционной системы с исключениями программист сосредотачивает свое внимание на выявлении новых правил и на обобщении уже имеющихся. Аппарат исключений освобождает программиста от решения трудоемких вопросов согласования правил — распознавание и интерпретация исключений осуществляется автоматически.
Название языка происходит от "РЕкурсивных Функций АЛгоритмический язык". Нас будут также интересовать соображения, которые привели к построению этого языка — эти соображения имеют, на наш взгляд, весьма общий характер и полезны для лучшего понимания причин возникновения продукционного подхода в программировании.
Разработчики языка
Языки второй группы называются языками сентенциального, или декларативного типа (
Можно назвать прообразы указанных типов алгоритмических языков в естественных языках. Для операторных языков это повелительное наклонение (императив, приказание), для сентенциальных – изъявительное наклонение (описание, повествование). Обращаясь к естественному языку, нетрудно заметить, что "изъявительное наклонение является несравненно более распространенным и образует, в сущности, основу языка, в то время как повелительное наклонение предстает в виде некоторой специальной модификации". Таким образом, можно сделать вывод о том, что "относительный вес изъявительного наклонения является мерой развитости языка".
§ (параграф).
Каждое правило конкретизации определяет раскрытие смысла некоторого понятия через более элементарные. Операцию конкретизации можно также определить как переход от имени к значению. Введем два знака: k и $$\perp$$, которые будем называть конкретизационными скобками, и которые будут содержать объект, подлежащий конкретизации. Так, если х — некоторая переменная, то $$kx\perp$$ (конкретизация х ) будет изображать значение этой величины. Другой пример: объект $$k28 +7\perp$$ при правильном определении операции сложения рано или поздно будет заменен на объект 35.
Выполнение конкретизации — переход от имени к значению — объявляется основной и, по существу, единственной операцией в языке
Поскольку правило конкретизации есть указание для замены одного объекта (слова в некотором алфавите) на другой, предложения языка
Пример. Предложение, выражающее тот факт, что значение переменной Х есть 137, записывается в виде $$§kX \perp \to 137$$.
Между знаком § и первым знаком k можно вставлять последовательность знаков, которая будет служить номером предложения, или комментарием к нему, например:
$$§ l.l kX \perp \to 137$$. (ф. 1)
Опишем теперь структуру
Пусть программа машины состоит из единственного предложения (ф. 1), а в поле зрения находится выражение $$kX\perp$$. Тогда за один шаг машина заменит содержимое поля зрения на 137, после чего она остановится, т. к. знаков конкретизации больше нет и, следовательно, делать ей больше нечего.
Так как
$$§ 1.2 kX \perp \to 274$$.
Неоднозначность, которая отсюда может возникнуть, устраняется так же, как это принято в нормальных алгоритмах Маркова (читатель, видимо, уже заметил, что
Поле зрения может содержать сколько угодно конкретизационных скобок, причем они могут быть как угодно вложены друг в друга. В этом случае k, в области действия которого (т.е. в последовательности знаков до парной скобки $$\perp$$ ) нет ни одного знака k. Выражение, находящееся в области этого знака k, последовательно сравнивается с левыми частями предложений
Пример. Пусть
$$kX \perp \to 137$$
$$kX \perp \to274$$
$$kY \perp \to 2$$
$$k137+2 \perp \to 139$$,
а поле зрения содержит выражение
$$kkX \perp +kY \perp \perp$$.
На первом шаге замене подлежит подвыражение $$kX\perp$$ — получим в поле зрения $$kl37 + kY\perp \perp$$. Теперь в первую очередь конкретизируется $$kY\perp$$ — получим в результате применения третьего предложения $$k137 +2\perp$$ и на последнем шаге получим 139, не содержащее символов k. (Разумеется для реального сложения используются соответствующие встроенные функции, а этот пример — лишь простейшая иллюстрация принципов работы машины).
Чтобы иметь возможность представлять обобщенные предложения, используются три типа переменных: е — для представления выражений; t — для термов; s — для символов. В простейшем случае переменные записываются в виде указателя типа (е, t, s) и индекса; например, е1, e2 — переменные, пробегающие в качестве значений выражения.
Пример. Предположим, требуется написать программу, которая выполняет раскрытие скобок в алгебраических выражениях, построенных из букв с помощью скобок, знаков сложения "+" и умножения"*". Рассмотрим процесс написания такой программы. Если некоторое выражение е имеет вид е1 + e1, где е1, e1 — выражения, то для раскрытия скобок надо: раскрыть скобки в e1, раскрыть скобки в е2, полученные результаты сложить. Эту мысль в компактном, но в то же время и наглядном виде выражает предложение:
$$§ 2.1 ke_1 +e_2\perp \to ke_1\perp +ke_2\perp$$
Если же выражение е имеет вид e1 * e2, то, вообще говоря, необходимо учитывать две возможности:
е = (А + В) *С ),е1 или е2 не представимо в виде суммы (например, е = (А * В) * (С * Л) ).В первом случае надо описать законы дистрибутивности:
$$§ 2.2ke_1 * (e_2 +e_3) \perp \to ke_1 * e_2\perp +ke_1*e_3\perp$$,
$$§ 2.3k(e_1 +e_2) * e_3\perp \to ke_1 * e_3\perp + ke_2*e_3\perp$$,
$$§ 2.4ke_1 * (e_2 + e_3) * e_4 \perp \to k(e_1 * е_2 + e_1 * e_3) * e_4\perp$$.
Во втором случае по аналогии со сложением имеем
$$§ 2.5ke_1 * е_2\perp \to ke_1\perp * ke_2\perp$$.
Наконец, осталось выразить возможность "снятия внешних скобок" и условие "терминальности" символов, что определяют предложения:
$$§ 2.6k(e) \perp \to ke\perp$$,
$$§ 2.7ks\perp \to s$$
(буквы не подлежат конкретизации).
Приведенные семь предложений § 2.1 — § 2.7 решают задачу. Рассмотрим как эта программа обрабатывает выражение
$$k(A +B) * (С +D) \perp$$.
Последовательно получим в результате работы программы (для удобства слева указываем номер правила, которое непосредственно привело к данному выражению):
$$§2.2 k(A +В)*С\perp . + k(A +B)*D\perp$$,
$$§2.3 kA *C\perp +kB*C\perp + k(A+B)*D\perp$$,
$$§2.3 kA *C\perp + kB*C\perp + kA *D\perp + kB*D\perp$$.
Далее ограничимся рассмотрением первого слагаемого:
$$§ 2.5 kA\perp * kC\perp + ..$$.,
$$§2.7 A * kC\perp + ..$$.,
§ 2.7 А * С + ....
После аналогичной обработки остальных слагаемых получим искомое выражение
А*С+D*С+А * D + В * D.
Если на вход поступит выражение
$$kA + (B + С) \perp$$,
то получим последовательно:
$$§ 2.1 kA\perp + k(B + С) \perp$$,
$$§ 2.7 А + k (Д + С) \perp$$,
$$§ 2.6 А + kB + C\perp$$,
§2.1, 2.7 A + B + С.
Обратите внимание, что если расположить правило § 2.5 перед правилами § 2.2 и § 2.3, то мы придем к абсурду! Например, выражение А *(В+С) будет приведено к виду: А *В + С.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.