Язык Рефал

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

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