Философские аспекты проблемы систем ИИ
Язык Рефал - часть 4
Чтобы иметь возможность представлять обобщенные предложения, используются три типа переменных: е — для представления выражений; t — для термов; s — для символов. В простейшем случае переменные записываются в виде указателя типа (е, t, s) и индекса; например, е1, e2 — переменные, пробегающие в качестве значений выражения. Выражением в языке Рефал называется последовательность знаков, правильно построенная в соответствеии с синтаксисом языка Рефал. Терм языка Рефал — это либо символ, либо выражение в круглых или конкретизационных скобках. Выражения строятся из термов.
Пример. Предположим, требуется написать программу, которая выполняет раскрытие скобок в алгебраических выражениях, построенных из букв с помощью скобок, знаков сложения "+" и умножения"*". Рассмотрим процесс написания такой программы. Если некоторое выражение е имеет вид е1 + e1, где е1, e1 — выражения, то для раскрытия скобок надо: раскрыть скобки в e1, раскрыть скобки в е2, полученные результаты сложить. Эту мысль в компактном, но в то же время и наглядном виде выражает предложение:
§ 2.1 ke1 +e2^ --> ke1^ +ke2^
Если же выражение е имеет вид e1 * e2, то, вообще говоря, необходимо учитывать две возможности:
- хотя бы один из сомножителей есть сумма (например, е = (А + В) *С),
- ни одно из выражений е1 или е2 не представимо в виде суммы (например, е = (А * В) * (С * Л)).
В первом случае надо описать законы дистрибутивности:
§ 2.2ke1 * (e2 +e3) ^ --> ke1 * e2^ +ke1*e3^ ,
§ 2.3k(e1 +e2) * e3^ --> ke1 * e3^ + ke2*e3^ ,
§ 2.4ke1 * (e2 + e3) * e4 ^ --> k(e1 * е2 + e1 * e3) * e4^ .
Во втором случае по аналогии со сложением имеем
§ 2.5ke1 * е2^ --> ke1^ * ke2^ .
Наконец, осталось выразить возможность "снятия внешних скобок" и условие "терминальности" символов, что определяют предложения:
§ 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, то придем к абсурду! Например, выражение А *(В+С) будет приведено к виду: А *В + С.
