Автор: Сотник С.Л.

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

Разработчики языка Рефал делят алгоритмические языки на две группы. Первую группу образуют языки, которые называются языки операторного, или процедурного типа. Элемен-тарными единицами программы являются здесь операторы, т.е. приказы, выполнение которых сводится к четко оп¬ределенному изменению четко определенной части памяти машины. Ти¬пичным представителем этой группы является язык машины Поста. Сюда же относятся машин-ные языки конретных ЭВМ, а также массовые языки программирования типа Фортран, Алгол, ПЛ/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) и индекса; например, е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, то придем к абсурду! Например, выражение А *(В+С) будет приведено к виду: А *В + С.