Различные описания языка Рефал отличаются в некоторых деталях. Вариант Рефала, представленный в работах [2, 3], получил название “базисного Рефала”.
В языке программирования Рефал-2 для БЭСМ-6 в рамках мониторной системы “Дубна” [4, 5] в качестве языка было взято некоторое расширение базисного Рефала. Это же расширение было реализовано на ЕС ЭВМ [6, 7, 8, 9]. Описываемый в [1] язык программирования Рефал-2 для IBM PC, PDP-11 и VAX-11 совместим по языку с реализациями для БЭСМ-6 и ЕС ЭВМ и был переведен на платформы Windows (Windows-95/98/ME/NT/2000/XP) и UNIX (FreeBSD, Linux). Описываемый здесь язык программирования РефалАБ основан на данной реализации Рефал-2 и является современным диалектом языка Рефал-2.
Ниже описан язык программирования РефалАБ. При описании некоторых конструкций языка использована нотация аналогичная форме Бэкуса-Наура, в которой нетерминалы не обрамляются угловыми скобками “<” и “>”.
Язык Рефал (алгоритмический язык рекурсивных функций) был создан в качестве абстрактного метаалгоритмического языка, предназначенного для формализации семантики алгоритмических языков [10, 11].
Хотя Рефал был задуман как метаалгоритмический язык, он представляет собой некоторый язык для обработки символьной информации, поэтому, помимо описания семантики алгоритмических языков, он нашел и другие, не менее важные применения. В первую очередь это машинное выполнение громоздких аналитических выкладок в теоретической физике и прикладной математике, интерпретация и компиляция языков программирования, машинное доказательство теорем, моделирование целенаправленного поведения и т.п.
Общим для всех этих применений является то, что мы заставляем машину совершать сложные преобразования над объектами, определенными в некоторых формализованных языках (алгоритмические языки, язык алгебры, язык исчисления предикатов и т.д.).
Данные, обрабатываемые РефалАБ-программами, являются языковыми объектами, т.е. некоторыми последовательностями знаков.
Следующие знаки имеют в РефалАБ-программах особое (фиксированное) значение:
< > ( ) ' = s w v e . : ; { } # [ ]
Эти знаки называются специальными знаками.
Из знаков строятся более крупные единицы - символы, термы и выражения.
Символ является минимальной семантической единицей, не расчленимой на составные части средствами языка РефалАБ.
Символы делятся на два класса: составные символы и символы-литеры (или, как их еще называют, “объектные знаки”).
Составной символ имеет следующий вид:
тело_составного_символа
где тело_составного_символа - это последовательность литер.
Множество составных символов разбивается на непересекающиеся классы, в соответствии с тем, какой вид имеют их тела. В РефалАБ имеются следующие классы составных символов: символы-метки, символы-числа и символы-ссылки.
Символами-метками называются составные символы, тело которых состоит из идентификатора (имени), т.е. последовательности латинских букв, литеры “_” и цифр, начинающаяся с прописной буквы или литеры “_”. Длина идентификатора ограничена 255 литерами.
Например, следующие символы являются символами-метками:
ALPHA
L2а4
_xyz
Так как строчные буквы в идентификаторах заменяются прописными, то символы ALPHA, Alpha, AlphA и т.д. полностью эквивалентны.
Символами-числами (макроцифрами) называются составные символы, тело которых представляет собой целое неотрицательное число, т.е. последовательность десятичных цифр. Например:
0 1 512 23
Тело символа-числа должно находиться в диапазоне от 0 до 4294967295 (232-1).
Макроцифры можно писать в восьмеричной форме. Они начинаются с нуля и состоят из восьмеричных цифр от 0 до 7. Например, 01238 = 8310.
Макроцифры также можно писать в шестнадцатеричной форме. Они начинаются с 0x и состоят из шестнадцатеричных цифр от 0 до 9 и от A(a) до F(f). Например, 0xFF16 = 25510.
Можно писать неотрицательные длинные целые числа в десятичной системе счисления, начиная с символа “#”. Компилятор заменит это число на правильную последовательность макроцифр, так как целое число - это последовательность макроцифр (т.е. “цифр” в позиционной системе счисления по основанию 232). Примеры:
#0000000 -> 0
#123 -> 123
#4294967296 -> 1 0
Символами-ссылками называются составные символы, тело которых обрамляется символами ‘/’, внутри обрамления начинается с литеры “%”, вслед за которой идет адрес символа-ссылки в шестнадцатеричной форме (x32 или x64). Например:
/%00FFFAC9/ /%FFFFFFFF/ /%ABCDEFAB/
Символы-ссылки нельзя употреблять в качестве констант в РефалАБ-программах. Они порождаются в процессе работы РефалАБ-программы и входят в обрабатываемые выражения. Назначение и использование символов-ссылок будет описано ниже.
Символы-метки используются в программах в качестве имен функций.
Символы-числа служат для обозначения чисел.
Помимо составных символов имеется еще один класс символов - символы-литеры.
Символ-литера имеет следующий вид:
'литера'
где литера - произвольная литера, отличная от апострофа. Так как апостроф тоже является литерой, которую нужно уметь обрабатывать, для него имеется особое обозначение: ‘’, т.е. два апострофа, идущих подряд. Следует заметить, что символ ‘ ‘ обозначает не апостроф, а литеру “пробел”, которая является такой же полноценной литерой, как и все остальные.
По аналогии с языком Си в РефалАБ допускается использование специальных (управляющих) символов, для изображения которых служит обратная косая черта:
Любой символ может быть представлен последовательностью до трех восьмеричных цифр, обрамленных апострофами с предшествующей обратной косой чертой ‘\ddd’, которая задает значение символа в 8-битном коде, например, символ ‘A’ эквивалентен ‘\101’.
Любой символ может быть представлен последовательностью до двух шестнадцатеричных цифр, обрамленных апострофами с предшествующей последовательностью “\x” ‘\xdd’, которая задает значение символа в 8-битном коде, например, символ ‘A’ эквивалентен ‘\x41’.
Более сложным элементом РефалАБ является выражение. Оно строится из символов, круглых скобок “(“ и “)” (именуемых структурными скобками), угловых скобок “<” и “>” (именуемых функциональными или конкретизационными скобками) и переменных.
Структурные скобки придают обрабатываемым объектам структуру дерева.
Назначение функциональных скобок и переменных объясняется в следующих разделах.
Выражением называется произвольная последовательность символов, переменных и скобок, правильно построенная относительно скобок. Например:
'A' 'B' 'C' ()
(('A') 'B'()) ()
< < X > ( < Y > )>
Термом называется выражение, которое представляет собой либо символ, либо выражение, заключенное в структурные или функциональные скобки. Например:
'+'
( 'A' 'B' 'C' () )
((()) ())
< P1 1>
Таким образом, всякое выражение есть последовательность из некоторого (быть может нулевого) числа термов.
Приведенные выше определения выражения и терма можно формализовать следующим образом:
выражение ::= пусто | терм выражение
терм ::= символ |
переменная |
структурный_терм |
функциональный_терм
структурный_терм ::= ( выражение )
функциональный_терм ::= < выражение >
пусто ::=
Очень часто приходится иметь дело не с отдельными символами-литерами, а с цепочками из нескольких подряд идущих литер. Для таких случаев предусмотрено сокращенное обозначение. а именно, литеры записываются подряд и вся цепочка литер заключается в апострофы. Например, цепочку литер “ABC”, изображаемую как
'A' 'B' 'C'
можно в сокращенной форме записывать как
'ABC'
Если цепочка литер содержит апострофы, они изображаются парами апострофов. При этом цепочка, составленная из одних апострофов, удваивается, но апострофами дополнительно не обрамляется. Например:
ABC --> 'ABC'
A'C --> 'A''C'
' --> ''
'' --> ''''
'A'B --> '''A''B'
A'B' --> 'A''B'''
где стрелка “–>” обозначает слова “изображается в виде”.
Таким образом, одну и ту же цепочку символов-литер можно изобразить многими способами. Например, цепочка литер “A’B” может быть представлена любым из следующих способов:
'A' '' 'B'
'A''' 'B'
'A' '''B'
'A''B'
Для повышения наглядности РефалАБ-программы можно вставлять любое количество пробелов между переменными, скобками, составными символами и цепочками литер. Цепочку литер можно разбить на несколько цепочек, но при этом между получившимися частями обязательно должен стоять по крайней мере один пробел, так как
'A' 'B' обозначает AB
'A''B' обозначает A'B
Кроме того, следует обратить внимание на то, что структурные скобки “(“ и “)” в РефалАБ не являются символами. Поэтому структурные скобки не имеют ничего общего с символами-литерами ‘(‘ и ‘)’.
Всякая программа, написанная на РефалАБ, определяет некоторый набор функций. Каждая из этих функций имеет один аргумент, значениями которого могут быть выражения.
Аргументами функций могут быть не произвольные выражения, а только такие, которые не содержат функциональных скобок и переменных. Такие выражения в дальнейшем именуются объектными.
В общепринятой математической записи обращение к функции FUNC с аргументом имеет следующий вид:
FUNC(аргумент)
В РефалАБ же принят другой синтаксис для вызовов функций:
< FUNC аргумент>
Т.е. вызов функции заключается в функциональные скобки “<” и “>”, а имя функции указывается с помощью символа-метки после хотя бы одного пробела после “<”.
Символ-метку, являющуюся именем функции, допускается записывать сразу за “<”, т.е. проще:
<FUNC аргумент>
Возникает вопрос, почему же в РефалАБ функции имеют только один аргумент? Ответ заключается в том, что список из нескольких аргументов является некоторым выражением, поэтому всякое обращение к функции от нескольких аргументов
FUNC(аргумент1, аргумент2, ..., аргументn)
можно рассматривать как обращение к функции от одного “большого” аргумента:
<FUNC (аргумент1) (аргумент2) ... (аргументn) >
Программа на языке РефалАБ представляет собой описание набора функций. Описание каждой функции имеет вид:
$FUNC FUNC
{
лев_часть_1 = прав_часть_1;
лев_часть_2 = прав_часть_2;
. . .
лев_часть_n = прав_часть_n;
}
где FUNC - имя функции, а лев_часть_i = прав_часть_i; - суть предложения (правила конкретизации).
Каждое предложение является указанием для замены одного выражения на другое, поэтому оно состоит из левой части (заменяемое выражение) и правой части (результат замены). Синтаксически лев_частьi и прав_частьi являются выражениями.
Если предложение не помещается в очередной строке, его можно перенести на следующие строки. Перенос допускается делать в тех местах, где разрешается вставлять пробелы. Предложение заканчивается знаком “;”.
Семантика РефалАБ-программы описывается в терминах абстрактной РефалАБ- машины. РефалАБ-машина имеет два запоминающих устройства: поле памяти и поле зрения.
Перед началом работы в поле памяти заносится описание набора функций, а в поле зрения - выражение, подлежащее обработке.
Пусть, например, в поле памяти находится единственное предложение:
$FUNC XXX
{
= '137';
}
а в поле зрения - выражение
<XXX >
Тогда РефалАБ-машина заменит содержимое поля зрения на выражение
'137'
и остановится, поскольку в поле зрения не осталось ни одной пары функциональных скобок. А что будет, если занести в поле памяти два предложения:
$FUNC XXX
{
= '137';
= '274';
}
Теперь для вычисления
Неоднозначность устраняется следующим образом. РефалАБ-машина просматривает
предложения в том порядке, в котором они стоят в описании функции и
применяет первое из них, которое окажется подходящим. Таким образом, в
данном случае
Поле зрения может содержать сколь угодно много функциональных термов, которые могут быть как угодно вложены друг в друга (но уровень вложения не более 511). Поэтому нужно договориться, каким образом РефалАБ-машина будет выбирать выражение, с которого надо начинать процесс вычисления.
Пусть в поле зрения находится выражение, в котором имеются функциональные термы. Тогда некоторые из этих термов являются самыми внутренними, т.е. не содержат внутри себя других функциональных термов. Самый левый из таких термов мы будем называть ведущим.
Теперь опишем работу РефалАБ-машины (для частного случая, когда РефалАБ -программа не содержит переменных).
Работа РефалАБ-машины разбивается на шаги. В начале каждого шага РефалАБ- машина находит ведущий функциональный терм. Пусть этот терм имеет вид:
<FUNC аргумент>
где FUNC - имя некоторой функции, а аргумент - объектное выражение.
Таким образом, предполагается, что содержимое ведущего терма начинается с символа-метки. (Случай, когда это не выполнено, будет рассмотрен позже.)
РефалАБ-машина находит описание функции FUNC и начинает сравнивать аргумент с левыми частями предложений в описании этой функции.
Пусть i - это номер самого первого предложения, для которого лев_часть_i совпадает с аргументом.
Тогда РефалАБ-машина производит замену ведущего функционального терма, т.е.
<FUNC аргумент>
заменяется на правую часть этого предложения, т.е. прав_часть_i, после чего РефалАБ-машина переходит к исполнению следующего шага.
Если же РефалАБ-машина не находит ни одного предложения, для которого левая часть совпадает с аргументом, она сообщает, что “Recognition impossible” (“Отождествление невозможно”) и останавливается. Это означает, что либо программа на РефалАБ, либо исходные данные для нее заданы неверно.
Работа РефалАБ-машины продолжается до тех пор, пока в поле зрения имеется хотя бы один функциональный терм. Если же в поле зрения после завершения очередного шага не остается ни одного функционального терма, РефалАБ-машина останавливается. При этом в режиме отладки она сообщает, что “Concretization is executed” (“Вычисление окончено”). При этом результатом работы РефалАБ-машины считается выражение, которое находится в поле зрения.
Пусть, например, поле памяти содержит следующий набор функций:
$FUNC XXX
{
= '137';
= '274';
}
$FUNC YYY
{
= '2';
}
$FUNC ADD
{
('137') '2' = '139';
}
А в поле зрения находится выражение
<ADD (<XXX >) <YYY > >
Тогда на первом шаге ведущим будет терм
<ADD ('137') <YYY >>
Теперь подлежит вычислению терм
<ADD ('137') '2'>
На третьем шаге применяется функция ADD, и в поле зрения оказывается выражение
'139'
которое уже не содержит функциональных скобок и является окончательным результатом работы РефалАБ-машины.
Средства, описанные в предыдущих разделах, позволяют описывать только функции, области определения которых - конечные множества, ибо для каждого конкретного значения аргумента приходилось предусматривать особое предложение. Ясно, что так мы далеко не уйдем. Нужно уметь записывать предложения, применимые более, чем к одному объектному выражению. Для этого нужно ввести в предложения переменные, которые при различных применениях предложения могут принимать различные значения.
Языковые объекты, с которыми имеет дело РефалАБ-машина, это всегда выражения, которые могут быть, в частности, термами или символами. Поэтому в РефалАБ используются переменные четырех типов:
Любая переменная имеет следующий вид:
признак_типа спецификация . имя_переменной
Признак_типа - это один из специальных знаков “s”, “w”, “v”, “e”. Он указывает, к какому из четырех вышеперечисленных типов принадлежит переменная.
Спецификация - это описание дополнительных условий, налагаемых на множество допустимых значений переменной. Спецификация может быть пустой. В этом случае считается, что на возможные значения переменной не налагается никаких дополнительных ограничений. Т.е. значением s-переменной может быть любой символ, значением w-переменной - любой терм, значением v-переменной - любое непустое выражение, значением e-переменной - любое (в том числе и пустое) выражение.
Имя переменной - это идентификатор. Имена переменных служат для того, чтобы различать между собой различные переменные.
Например, s-переменными являются “s.S1”, “s._” и “s.A”, w-переменными являются “w.Var” и “w.X”, v-переменными являются “v._r1” и “v.Zy4”, e-переменными являются “e.R_1”, “e.__” и “e.A_f”.
Разрешив употреблять переменные в левых и правых частях предложений, мы получаем мощное изобразительное средство. Теперь, чтобы решить, применимо ли предложение
лев_часть_i = прав_часть_i;
к некоторому объектному выражению (аргументу), РефалАБ-машина должна определить, является ли оно частным случаем левой части предложения, т.е. можно ли вместо переменных, входящих в нее подставить такие значения, чтобы получившееся объектное выражение совпало с аргументом. При этом значения переменных должны быть допустимыми, т.е. соответствовать их типам и спецификациям. Кроме того, все вхождения одной и той же переменной должны заменяться на одно и то же значение.
Описанное выше действие РефалАБ-машины, по подбору значений переменных, называется синтаксическим отождествлением.
В том случае, если отождествление левой части с аргументом возможно, предложение является применимым, в противном случае - неприменимым.
Теперь мы следующим образом уточним описание работы РефалАБ-машины.
На каждом шаге РефалАБ-машина просматривает описание функции и находит самое первое применимое предложение. Затем она заменяет ведущий функциональный терм на правую часть этого предложения, предварительно подставив в нее вместо переменных те значения, которые получили эти переменные в результате синтаксического отождествления. Если же окажется, что все предложения функции неприменимы, РефалАБ-машина сообщает, что “Отождествление невозможно” и останавливается.
Разумеется, в правой части предложения разрешается использовать только такие переменные, которые входят в левую часть. Кроме того, все вхождения одной и той же переменной в левую и правую часть должны иметь одинаковый указатель типа переменной.
Рассмотрим несколько примеров. Допустим, что нужно описать функцию FIRST_SYM, которая в качестве значения выдает первый символ аргумента. Например, чтобы результатом вычисления терма
<FIRST_SYM 'Z'('AB')'+F' >
был символ ‘Z’, а результатом вычисления
<FIRST_SYM X1 X2>
был символ X1.
Для этого достаточно ввести в поле памяти РефалАБ-машины следующее описание функции:
$FUNC FIRST_SYM
{
s.A e.X = s.A;
}
Аналогично можно описать функцию, значением которой является последний символ аргумента:
$FUNC LAST_SYM
{
e.X s.A = s.A;
}
Поскольку правые части предложений могут содержать функциональные скобки, можно описывать функции в терминах других функций или применять рекурсию.
Опишем, например, функцию REV, определенную для всех выражений. Значением этой функции является “зеркально перевернутое” исходное выражение. Так, вычисление терма
<REV 'A'('B'('CD')'F') >
должно давать
('F'('DC')'B')'A'
Функция REV описывается тремя предложениями:
$FUNC REV
{
e.A s.X = s.X <REV e.A>;
e.A (e.X) = ( <REV e.X> ) <REV e.A>;
= ;
}
Обратите внимание на то, что структурные скобки “(“ и “)” не являются символами, и, в отличие от символов-литер ‘(‘ и ‘)’, не могут быть значениями s-переменной. Поэтому, если аргумент кончается на правую структурную скобку, то первое предложение функции - не применимо. В этом случае применяется второе предложение.
Рассмотрим другой пример. Функция SYMM принимает значение ‘Т’ если аргумент - симметричное выражение (т.е. такое, которое не изменяется в результате применения к нему функции REV), и принимает значение ‘F’, если аргумент не является симметричным выражением.
$FUNC SYMM
{
e.X = <EQUAL (e.X) <REV e.X>>;
}
$FUNC EQUAL
{
(e.X) e.X = 'T';
(e.X) e.Y = 'F';
}
Функцию SYMM можно описать и без обращения к функции REV:
$FUNC SYMM
{
= 'T';
s.X = 'T';
s.X e.A s.X = <SYMM e.A>;
(e.A) = <SYMM e.A>;
() e.A () = <SYMM e.A>;
(w.X e.B) e.A (e.E w.Y) = <SYMM w.X (e.B) e.A (e.E) w.Y>;
e.A = 'F';
}
Будем говорить, что некоторая переменная является ve-переменной, если она является v-переменной или e-переменной.
Если левая часть предложения содержит несколько ve-переменных, то может случиться, что существует несколько вариантов приписывания переменным значений, приводящих к отождествлению левой части предложения с аргументом функции. Пусть, например, в поле памяти находится функция
$FUNC F
{
e.B ';' e.E = <G e.B> <F e.E>;
}
а в поле зрения - выражение
<F 'A1:=A2;B1:=B2;C1:=C2'>
Это выражение может быть отождествлено с левой частью таким образом, что переменные E.B и E.E примут следующие значения:
e.B <-- 'A1:=A2'
e.E <-- 'B1:=B2;C1:=C2'
Однако, возможен и другой вариант отождествления, при котором переменные примут такие значения:
e.B <-- 'A1:=A2;B1:=B2;'
e.E <-- 'C1:=C2'
Следовательно, необходимо договориться, как поступает РефалАБ-машина при наличии такой неоднозначности.
Для устранения неоднозначности в РефалАБ могут использоваться два метода: отождествление слева направо и отождествление справа налево.
При отождествлении слева направо РефалАБ-машина выбирает тот вариант отождествления, при котором первая слева ve-переменная принимает самое короткое значение. Если это не устраняет неоднозначности, то такой же отбор производится по второй слева ve-переменной, затем - третьей слева и т.д. В нашем примере будет выбран первый из двух способов отождествления.
При отождествлении справа налево РефалАБ-машина выбирает тот вариант отождествления, при котором первая справа ve-переменная принимает самое короткое значение. Если это не устраняет неоднозначности, то такой же отбор производится по второй справа ve-переменной, затем третьей справа и т.д. В нашем примере будет выбран второй из двух способов отождествления.
Если мы хотим, чтобы при применении некоторого предложения использовалось отождествление справа налево, следует сообщить об этом РефалАБ-машине, поместив перед левой частью предложения ключевое слово $RIGHT. Если же мы хотим, чтобы при применении некоторого предложения использовалось отождествление слева направо, следует сообщить об этом РефалАБ-машине, поместив перед левой частью предложения ключевое слово $LEFT.
Если направление отождествления не указано явно, РефалАБ-машина считает, что отождествление следует выполнять слева направо, поэтому ключевое слово $LEFT указывать не обязательно (и он отсутствовал во всех приведенных ранее примерах). Например, описанная выше функция F, выдаст в результате замены
<G 'A1:=A2'> <F 'B1:=B2;C1:=C2'>
Но если описать F следующим образом:
$FUNC F
{
$RIGHT e.B ';' e.E = <G e.B> <F e.E>;
}
то результатом замены будет
<G 'A1:=A2;B1:=B2'> <F 'C1:=C2'>
Отождествления слева направо и справа налево широко используются при программировании на РефалАБ. В качестве примера рассмотрим функцию MAKE_SET, которая порождает множество термов, входящих в аргумент на нулевом уровне скобочной структуры. Эта функция просматривает выражение слева направо терм за термом. Для очередного терма проверяется, не стоит ли справа от него точно такой же терм. Если да, то очередной терм вычеркивается, в противном случае - оставляется. Оставшееся выражение обладает тем свойством, что составляющие его термы попарно различны. Например, результатом вычисления
<MAKE_SET 'AAACBDBEAAF'>
будет выражение
'СDBEAF'
Функция MAKE_SET описывается следующим образом:
$FUNC MAKE_SET
{
e.B w.X e.M w.X e.E = e.B <MAKE_SET e.M w.X e.E>;
e._ = e._;
}
Функция MAKE_SET вычеркивает все вхождения каждого терма, кроме последнего. Нетрудно, однако, описать функцию MAKE_SETR, которая будет вычеркивать все вхождения терма, кроме первого. Для этого можно воспользоваться отождествлением справа налево.
$FUNC MAKE_SETR
{
$RIGHT e.B w.X e.M w.X e.E = <MAKE_SETR e.B w.X e.M> e.E;
e._ = e._;
}
При желании можно описать функцию MAKE_SET так, чтобы при отождествлении не возникало неоднозначностей:
$FUNC MAKE_SET
{
w.A e.E = <MAKE_SETX w.A () e.E>;
= ;
}
$FUNC MAKE_SETX
{
w.A (e.B) w.A e.E = <MAKE_SET e.B w.A e.E>;
w.A (e.B) w.B e.E = <MAKE_SETX w.A (e.B w.B) e.E>;
w.A (e.E) = w.A <MAKE_SET e.E>;
}
Очевидно, что первоначальное описание было короче и нагляднее. Кроме того, во втором описании пришлось использовать вспомогательную функцию MAKE_SETX.
Любая переменная может иметь спецификацию, которая располагается между признаком типа переменной и точкой.
Спецификации позволяют накладывать дополнительные ограничения на множества допустимых значений переменных. Например, значением s.X может быть любой символ, в то время как значением s(‘ABC’).X могут быть только символы-литеры ‘A’, ‘B’ и ‘C’.
Спецификация может иметь одну из следующих форм:
пусто
имя_спецификатора
( спецификатор )
Таким образом, если спецификация не пуста, она представляет собой либо имя_спецификатора, либо непосредственно сам спецификатор, заключенный в скобки. Между левой скобкой “(“ и спецификатором, а также между спецификатором и правой скобкой “)” можно вставлять пробелы. В то же время нельзя вставлять пробелы между указателем типа переменной и спецификацией, а также между спецификацией и точкой. Во всех местах, где можно вставлять пробелы, можно перенести предложение на следующую строку.
Имя_спецификатора имеет вид
:идентификатор:
Каждый спецификатор представляет собой описание некоторого множества термов. Это описание строится исходя из некоторого набора элементарных множеств, которые будут перечислены ниже. Обозначения этих множеств именуются элементами.
Допустимы следующие элементы:
Последовательность элементов спецификатора называется цепочкой элементов. Цепочка элементов обозначает множество, которое представляет собой объединение тех множеств, которые соответствуют элементам цепочки.
Таким образом, если цепочка имеет вид
X1 X2 ... Xn
то она обозначает множество
X1 + X2 + ... + Xn
где “+” обозначает объединение множеств. Например, ld обозначает множество букв и цифр.
Между элементами цепочки можно вставлять произвольное число пробелов. Если в цепочке элементов записано несколько символов-литер подряд, их можно слить в одну цепочку литер. Например,
'A' 'B' '' 'C'
эквивалентно
'AB''C'
В общем случае спецификатор имеет вид:
P1(Q1)P2(Q2)...Pn(Qn)P0
где Pi и Qi - произвольные (может быть пустые) цепочки элементов спецификатора.
Множество значений, изображаемое спецификатором, вычисляется так:
После этого значение спецификатора вычисляется рекурсивно следующим образом. Пусть R1 - это множество термов, изображаемых спецификатором
P2(Q2)...Pn(Qn)P0
Тогда множество термов, изображаемое спецификатором
P1(Q1)P2(Q2)...Pn(Qn)P0
вычисляется по формуле
R = P1 + (R1 - Q1)
где “+” обозначает объединение множеств, а “-“ обозначает разность множеств.
Ниже приведены примеры спецификаторов. Для каждого спецификатора описано множество, которое он изображает:
Множество значений, обозначаемое спецификатором, можно найти и другим способом. Можно рассматривать спецификатор как предикат, который определен на множестве термов и для каждого терма вырабатывает одно из двух значений: “истина” или “ложь”.
Допустим, что задан некоторый терм и нужно узнать, удовлетворяет он спецификатору или нет. Для этого просматриваем спецификатор слева направо, элемент за элементом, пока не встретим самый первый элемент, которому удовлетворяет проверяемый терм. После этого спецификатор дальше не просматривается и вырабатывается значение “истина” или “ложь”.
Если найденный элемент принадлежит Qi, т.е. находится внутри скобок, то вырабатывается значение “ложь”, а если принадлежит Pi, т.е. находится не в скобках, - то вырабатывается значение “истина”.
Если же мы дошли до конца спецификатора и не нашли ни одного элемента, которому удовлетворял бы проверяемый терм, то следует посмотреть, чем заканчивается спецификатор. Если он оканчивается на правую скобку, вырабатывается значение “истина”, в противном случае - “ложь”.
В соответствии с принятыми соглашениями пустой спецификатор обозначает пустое множество, а спецификатор вида “()” - множество всех термов.
Элементарные множества, обозначаемые элементами спецификатора, обладают следующим свойством: для любых двух элементарных множеств X1 и X2 либо пересечение X1 и X2 пусто, либо X1 - подмножество X2, либо X2 - подмножество X1. Поэтому можно доказать, что если два спецификатора представляют множества R1 и R2, то можно представить некоторыми спецификаторами также R1+R2, R1*R2 и R1-R2, где “+”, “*” и “-“ обозначают объединение, пересечение и разность множеств соответственно. Таким образом, множество спецификаторов замкнуто относительно теоретико-множественных операций.
Имена спецификаторов описываются с помощью ключевого слова $SPEC. Эти описания имеют следующий вид:
$SPEC идентификатор спецификатор;
где идентификатор - имя спецификатора без ограничителей “:”, например:
$SPEC ADDOP '+-';
$SPEC MULTOP '*/';
Теперь имена :ADDOP: и :MULTOP: можно употреблять в качестве спецификаций и в качестве элементов других спецификаторов. Например, значением переменных s:ADDOP:.X и s:ADDOP:.Y может быть только ‘+’ или ‘-‘.
Опишем более подробно, какой смысл имеют спецификации для переменных различных типов.
Спецификация вида :ID: равносильна спецификации (:ID:). Например, переменная s:ZZZ:.X имеет то же множество допустимых значений, что и переменная s(:ZZZ:).X.
Если спецификатор задан для s- или w-переменной, то это означает, что значение переменной должно принадлежать множеству, которое описывает спецификатор.
Если спецификатор задан для ve-переменной, то это означает, что каждый терм значения переменной, стоящий на нулевом уровне скобочной структуры, должен удовлетворять спецификатору.
Например, e(‘+-‘).X - это последовательность (может быть пустая) из литер ‘+’ и ‘-‘, e(b).X - это выражение вида (e.E1) (e.E2) … (e.EN), а s(l).X e(ld’-‘).Y - это последовательность латинских букв, литеры “-“ и цифр, начинающаяся с буквы.
В то же время, e((‘+-‘)).X - это выражение, которое не содержит на нулевом уровне скобок ни одной литеры ‘+’ или ‘-‘. Например, в качестве значения годится (‘+’)(‘-‘) , но не годится ‘+’(‘-‘) .
Если у переменной есть несколько вхождений в левую часть, то у каждого вхождения может быть своя спецификация.
Во время отождествления значение каждого вхождения должно удовлетворять спецификации этого вхождения. Таким образом, получается, что множество допустимых значений переменной - это пересечение множеств допустимых значений ее вхождений. Например, предложение:
s(('A')).X s(('B')).X = s.X;
равносильно
s(('AB')).X s.X = s.X;
Все спецификации, которые заданы для вхождений переменных в правую часть предложения - игнорируются.
На использование имен спецификаторов наложено следующее ограничение: если имя некоторого спецификатора используется при описании другого спецификатора, то оно должно быть описано раньше.
Благодаря этому ограничению, запрещаются циклические определения, вроде
$SPEC SPC1 :SPC2:;
$SPEC SPC2 :SPC1:;
Приведем примеры использования спецификаторов.
Функция IDENT отщепляет от аргумента слева последовательность латинских букв и цифр, начинающуюся с буквы, максимальной длины.
$FUNC IDENT
{
s(l).X e.E = <IDENT1 (s.X) e.E>;
e.E = '*' e.E;
}
$FUNC IDENT1
{
(e.I) s(ld).A E.E = <IDENT1 (e.I s.A) e.E>;
(e.I) e.E = (e.I) e.E;
}
Если использовать отождествление справа налево и специфицированные e-переменные, ту же функцию можно записать короче:
$FUNC IDENT
{
$RIGHT s(l).X e(ld).Y e.E = (s.X e.Y) e.E;
e.E = '*' e.E;
}
По семантике РефалАБ в первом предложении нужно подобрать самое короткое e.E, при котором возможно отождествление. Но ведь самому короткому e.E соответствует самое длинное e.Y!
Компилятор распознает такие случаи, и вместо того, чтобы несколько раз удлинять значение e.E, он сразу же, слева направо наберет максимально возможное e.Y.
Еще один пример. Функция ERASE_BL просматривает цепочку символов и заменяет каждую группу из нескольких последовательно идущих пробелов на один пробел.
$FUNC ERASE_BL
{
e.B ' ' e.E = e.B ' ' <ERASE_BL_ e.E>;
e._ = e._;
}
$FUNC ERASE_BL_
{
$RIGHT e(' ').X e.E = <ERASE_BL_ e.E>;
}
Для некоторых s-переменных с определенными спецификаторами существуют эквивалентные записи:
Например, переменной s(l).X соответствуют эквивалентная запись l.X.
Далее идет описание диапазонов символов.
В качестве элемента спецификатора может использоваться диапазон символов. Диапазон обозначает множество всех символов, находящихся между двумя граничными символами включительно.
Диапазон имеет вид:
[ первый .. последний ]
где первый и последний — граничные символы диапазона. Обе границы должны быть одного типа: либо оба символа-литеры, либо обе макроцифры.
Допустимы пробелы между любыми элементами диапазона, кроме двух точек, так как две точки есть один элемент диапазона.
Допустимы следующие формы диапазонов:
[X..Y] Все символы от X до Y включительно
[..Y] Все символы от минимума до Y включительно
[X..] Все символы от X до максимума включительно
Формы [] и [..] некорректны и вызывают ошибку компиляции.
Диапазон символов-литер обозначает множество символов-литер, коды которых находятся в указанном диапазоне. Например:
Диапазон макроцифр обозначает множество макроцифр, значения которых находятся в указанном диапазоне. Например:
При использовании диапазонов компилятор проверяет следующие условия:
Приведем примеры использования диапазонов символов.
Описание спецификатора для латинских букв любого регистра и цифр:
$SPEC ALNUM ['a'..'z']['A'..'Z']['0'..'9'];
Функция, проверяющая, что все символы аргумента являются строчными латинскими буквами:
$FUNC LOWER
{
e(['a'..'z']).X = 'YES';
e._ = 'NO';
}
Диапазон [‘0’..’9’] является эквивалентом элемента d.
Спецификатор, состоящий из двух диапазонов [‘A’..’Z’][‘a’..’z’] является эквивалентом элемента l.
РефалАБ-программа представляет собой последовательность записей. Запись - это отдельная строка текстового файла с расширением “.ref”.
Все записи состоят из комментариев и директив.
Комментарии могут начинаться там, где можно вставлять пробелы.
Однострочные комментарии начинаются с литер “//”. В позициях после “//” до конца записи они содержат произвольную информацию.
Многострочные комментарии начинаются с литер “/*” и заканчиваются литерами “*/” на любой позици текущей или одной из следующих записей. Вложенные комментарии не поддерживаются.
Комментарии игнорируются компилятором РефалАБ и не влияют на смысл РефалАБ-программы.
Та часть записей, которая не содержит комментарии, содержит директивы.
РефалАБ-программа представляет собой последовательность директив.
Каждая директива занимает одну или несколько рядом расположенных записей. Пока что будем предполагать, что каждая директива занимает отдельную запись. Правило переноса директив с одной записи на другую будут описано ниже.
В одной записи могут быть несколько директив. Между директивами могут быть пробелы.
Все директивы имеют следующий вид:
ключ идентификатор информация
где ключ - это ключевое слово (состоит из латинских букв и начинается со знака “$”), а информация зависит от типа директивы.
Присутствие всех трех компонентов директивы не обязательно: часть из них может отсутствовать.
Директива может начинаться с любой позиции записи.
Допускаются записи, состоящие из одних пробелов. Они не влияют на смысл РефалАБ-программы и могут использоваться для улучшения ее читаемости.
В качестве ключевых слов допускаются следующие цепочки литер (литеры могут быть любого регистра):
$EMPTY
$END
$ENTRY
$EQU
$EXTERN
$LEFT
$RIGHT
$SPEC
$START
$SWAP
Основное место в РефалАБ-программах занимают предложения, которые служат для описания функций и с которыми мы познакомились ранее. Предложения представляют собой директивы с ключевым словом $LEFT или $RIGHT, причем слово $LEFT разрешается опускать.
Другой известный нам тип директив - это SPEC-директивы, которые имеют ключевое слово $SPEC и служат для описания спецификаторов.
Директива, в которой после ключевого слова $FUNC присутствует идентификатор, является признаком начала описания новой функции. Далее идут директивы-предложения функции, находящиеся между знаками “{“ и “}”.
Все прочие директивы будут описаны в последующих разделах.
В заключение опишем правило переноса директив с одной записи на другую.
Назовем элементами предложения следующие объекты: цепочку объектных знаков (заключенную в апострофы), составной символ, свободную переменную, знаки “<”, “>”, “=”, “(“, “)”.
Между любыми двумя элементами предложения разрешается вставлять произвольное число пробелов. Кроме того, разрешается вставлять пробелы и между элементами спецификатора и скобками, входящими в спецификатор. Например, спецификатор (‘A’)ld эквивалентен ( ‘A’ ) l d. В то же время, нельзя вставлять пробелы между любыми элементами переменной.
В остальных случаях, между элементами директив можно вставлять пробелы.
Теперь правило переноса формулируется следующим образом: в любом месте, где могут быть вставлены дополнительные незначащие пробелы, можно продолжить директиву с любой позиции следующей записи.
Пример. Функцию
$FUNC FUNC
{
e.B '+' e.E = (e.B) '+' (e.E) <PSI >;
s(('+-')on).X = s.X;
e._ = e._;
}
можно записать следующим образом:
$FUNC FUNC {
e.B
'+'
e.E
=
( e.B
) '+' (e.E) <PSI >;
s(
(
'+-'
)
o
n
).X = s.X;
e._ = e._; }
В некоторых случаях возникает желание описывать пустые функции, т.е. функции, описания которых содержат нулевое число предложений. Эти функции имеют пустую область определения, т.к. при любом обращении к такой функции возникает останов “Отождествление невозможно”.
Пустые функции обычно бывают полезны, если нужны символы, которые заведомо отличаются от всех остальных и которые имеют удобные для человека графические представления.
Пустые функции могут быть описаны с помощью EMPTY-директивы, которая имеет следующий вид:
$EMPTY идент_1,идент_2,...,идент_n;
где идент_1, идент_2, …, идент_n - имена определяемых пустых функций.
Например:
$EMPTY ALPHA,PSI;
Пустые функции можно описывать еще двумя способами:
$FUNC ALPHA;
$FUNC PSI
{
}
В некоторых случаях возникает желание описывать эквивалентные (тождественные) имена, т.е. альтернативные имена функций и спецификаторов. Эти имена можно использовать в коде РефалАБ-программ вместо основных имен функций или спецификаторов.
Альтернативные имена обычно бывают полезны, если хочется использовать другие имена библиотечных функций, которые заведомо отличаются от всех остальных и которые имеют удобные для человека графические представления.
Альтернативное имя может быть описано с помощью директивы EQU, которая имеет один из следующих видов:
$EQU экв_идент идент;
$EQU идент экв_идент;
где идент - имя функции или спецификатора, экв_идент - эквивалентное имя функции или спецификатора.
Например:
$EQU WRITELN PRINT;
$EQU CARD READLN;
Часто бывает удобно разбить РефалАБ-программу на части, которые могут обрабатываться компилятором РефалАБ независимо друг от друга.
Наименьшая часть РефалАБ-программы, которая может быть обработана компилятором независимо от других, называется модулем.
Исходный РефалАБ-модуль должен начинаться с директивы START и кончаться директивой END. Эти директивы имеют следующий вид:
$START имя_модуля;
$END.
где имя_модуля - идентификатор. Имя модуля может быть опущено.
Функции, описанные в разных модулях, могут обращаться друг к другу. Если в некотором модуле используется функция, которая описана в другом модуле, эту функцию следует объявить внешней по отношению к данному модулю с помощью директивы EXTERN.
Если в некотором модуле описана функция, к которой есть обращения из других модулей, эта функция должна быть объявлена в качестве входной точки данного модуля с помощью директивы ENTRY.
Директивы ENTRY и EXTERN имеют идентичный формат:
$ENTRY идент_1,идент_2,...,идент_n;
$EXTERN идент_1,идент_2,...,идент_n;
где идент_i - описание входной точки или внешней метки, соответственно.
Идентi может иметь одну из двух следующих форм:
идентификатор
идентификатор(внешний_идентификатор)
где внешний_идентификатор - это идентификатор.
Если кроме имени функции задан еще внешний идентификатор, это означает, что за пределами модуля (в среде, “окружающей модули”) функция имеет “внешнее” имя, которое отличается от “внутреннего” имени функции, употребляемого внутри модуля. Таким образом одна и та же функция может иметь разные внутренние имена во всех модулях, в которых она используется.
Если при описании функции в директиве ENTRY или EXTERN внешнее имя не задано, то считается, что внешнее имя совпадает с внутренним.
Пример. Пусть имеется два модуля M1 и M2. В модуле M1 описана функция COMMUNICATION, а в модуле M2 - функция DREAM и пусть эти функции используются в модулях M2 и M1, соответственно. Тогда эти модули могут иметь следующую структуру:
$START M1;
$ENTRY COMMUNICATION(COMMUN);
$EXTERN DREAM;
$FUNC COMMUNICATION
{
e.B '+' e.E = <DREAM e.B> <DREAM e.E>;
}
$END.
$START M2;
$ENTRY DREAM;
$EXTERN Communication(COMMUN);
$FUNC DREAM
{
s.X e.E = s.X <Communication e.E>;
}
$END.
Здесь функция, которая имеет внутреннее имя COMMUNICATION в модуле M1, имеет внутреннее имя “Communication” в модуле M2 и внешнее имя COMMUN.
С помощью директив ENTRY и EXTERN можно объявлять входными и внешними не только функции, но и спецификаторы.
Каждое имя, которое употребляется внутри модуля, должно быть описано либо как имя внутренней функции или спецификатора, либо как имя внешней функции или спецификатора в директиве EXTERN.
Любое имя в директиве ENTRY может употребляться несколько раз, а в директиве EXTERN только один раз.
Каждое внешнее имя, должно быть описано либо в директиве ENTRY, либо в директиве EXTERN.
Любое внешнее имя в директиве EXTERN может употребляться несколько раз, а в директиве ENTRY только один раз.
Во многих случаях возникает необходимость из программ, написанных на РефалАБ вызывать программы, написанные на языке Си. Эта необходимость возникает, в частности, в тех случаях, когда требуется выполнять операции ввода/вывода, операции над числами и другие, которые РефалАБ-машина “не умеет” выполнять непосредственно.
Функции, описанные не на РефалАБ, а на Си, которые, тем не менее, можно вызывать обычным способом из программ, написанных на РефалАБ, называются первичными.
Собственно говоря, с точки зрения РефалАБ-модуля первичные функции - это просто некоторые функции, внешние по отношению к данному модулю, поэтому, вызывая какую-либо функцию можно даже не знать, что это - первичная функция или функция, написанная на РефалАБ. Разница состоит только в том, что исполнение вызова первичной функции занимает только один шаг с точки зрения РефалАБ-машины, в то время как исполнение вызова обычной функции может занять несколько шагов, а также в том, что при выполнении этих обращений может возникать побочный эффект, т.е. взаимодействие со средой, внешней по отношению к РефалАБ-машине. В частности, с помощью первичных функций реализуются операции ввода-вывода. Кроме того, некоторые первичные функции могут менять состояние РефалАБ-машины.
Набор первичных функций, предоставляемых в библиотеке РефалАБ, будет описан отдельно. Помимо этих первичных функций пользователь может писать и собственные на языке Си. Как это сделать будет описано отдельно.
До сих пор мы считали, что РефалАБ-машина имеет два запоминающих устройства: поле памяти и поле зрения. В действительности у нее имеется еще одно запоминающее устройство: копилка, доступ к которому возможен с помощью первичных функций BR, DG, CP, RP, DGALL.
Имена этих функций имеют следующий смысл: ВR - закопать (bury), DG - выкопать (dig out), СР - скопировать (copy), RР - заменить (replace), DGALL - выкопать все (dig out all).
Содержимое копилки всегда имеет следующий вид:
(e.E1'='e.E_1) (e.E2'='e.E_2) ... (e.En'='e.E_n)
где e.E1, e.E2, …, e.En и e.E_1, e.E_2, …, e.E_n - произвольные объектные выражения. Смысл содержимого копилки следующий: e.Ei - есть имя выражения e.E_i.
Перед началом работы программы копилка содержит пустое выражение.
Функции ВR, DG, RР и СР предназначены для перемещения выражений из поля зрения в копилку и обратно. обращения к ним имеют следующий вид:
<ВR e.E1 '=' e.E_1>
<DG e.E1>
<RР e.E1 '=' e.E_1>
<СР e.E1>
где e.E_1 - произвольное выражение, а e.E1 - выражение, не содержащее символа ‘=’ на нулевом уровне скобочной структуры.
При обращении к функции ВR терм (e.Ex’=’e.E_x) добавляется к копилке слева, т.е. копилка преобразуется следующим образом:
e.E0 --> (e.Ex'='e.E_x) e.E0
где e.E0 - содержимое копилки до обращения к ВR. Результат обращения к ВR в поле зрения - пусто.
Можно закапывать несколько выражений под одним и тем же именем. Например, в результате выполнения
<ВR 'V=A'> <ВR 'V=B'>
копилка преобразуется следующим образом:
e.E0 --> ('V=B')('V=A') e.E0
Функция DG просматривает копилку слева направо в поисках терма вида (e.Ex’=’e.E_x) и, если находит, удаляет его из копилки и выдает e.E_x в качестве результата замены. Это можно изобразить следующим образом:
поле зрения: <DG e.Ex> --> e.E_x
копилка: e.E1 (e.Ex'='e.E_x) e.E2 --> e.E1 e.E2
Если в копилке несколько выражений закопаны под одним именем, то выкапывается самое левое из них, т.е. то, которое закапывалось последним. При повторном обращении к DG с тем же аргументом e.Ex будет выкопано выражение, закопанное предпоследним и т.д.
Если DG не находит в копилке нужного терма, она выдает в качестве результата замены пустое выражение.
Функция СР, так же, как и функция DG, находит в копилке выражение по имени и выдает его в качестве результата, но копилка при этом не изменяется, т.е. в поле зрения формируется копия выражения. Таким образом СР работает так:
поле зрения: <CP e.Ex> --> e.E_x
копилка: e.E1 (e.Ex'='e.E_x) e.E2 --> e.E1 (e.Ex'='e.E_x) e.E2
Если под именем e.Ex ничего не закопано, СР выдает “пусто”. Функцию СР можно было бы следующим образом описать через ВR и DG:
$FUNC CP
{
e.X = <CP1 (e.X) <DG e.X>>;
}
$FUNC CP1
{
(e.X) e.Y = e.Y <BR e.X '=' e.Y>;
}
Это описание несколько отличается от алгоритма, реализованного в первичной функции СР, тем, что терм (e.Ex’=’e.E_x) переставляется в начало копилки, в то время как первичная функция оставляет его на месте.
Функция RР добавляет в копилку новое выражение и выбрасывает выражение, закопанное в последний раз под тем же именем:
поле зрения: <RP e.Ex '=' e.E_x> -->
копилка: e.E1 (e.Ex'='e.E_y) e.E2 --> e.E1 (e.Ex'='e.E_x) e.E2
Если под именем e.Ex ничего не закопано, то функция RР делает то же самое, что и ВR.
Эквивалентное описание на РефалАБ имеет вид:
$FUNC RP
{
e.X '=' e.Y = <RP1 <DG e.X>> <BR e.X '=' e.Y>;
}
$FUNC RP1
{
e._ = ;
}
Функция DGАLL позволяет вынуть из копилки все содержимое и поместить его в поле зрения. Обращение к DGАLL имеет вид:
<DGALL >
Пусть копилка содержит выражение e.E0. Тогда результатом обращения к DGALL будет e.E0, причем в копилке останется пустое выражение.
Выражение e.E0 можно вернуть в копилку. Для этого достаточно описать на РефалАБ функцию ВRАLL:
$FUNC BRALL
{
e.E1 (e.E2) = <BR e.E2> <BRALL e.E1>;
= ;
}
После этого следует обратиться к ВRАLL следующим образом:
<BRALL e.E0>
Объектами обработки для программ, написанных на РефалАБ, являются выражения. Выражение представляет собой по существу способ представления древовидных структур в виде одномерных цепочек символов и скобок.
При решении некоторых задач, однако, оказывается, что требуется обрабатывать структуры данных, которые сложнее, чем древовидные.
Конечно, в принципе, любые конструктивные объекты можно представить в виде деревьев, однако это не всегда удобно, а иногда приводит к существенному замедлению работы программы (в тех случаях, когда прямой доступ к данным приходится моделировать с помощью ассоциативных поисков).
Средством РефалАБ, дающим возможность обрабатывать произвольные графы, являются статические и динамические ящики.
До сих пор предполагалось, что РефалАБ-машина состоит из трех запоминающих устройств: поля памяти, в котором находится набор предложений, поля зрения и копилки. Теперь будем считать, что имеется еще потенциально бесконечное множество запоминающих устройств, называемых ящиками. Каждый ящик содержит произвольное объектное выражение, которое может изменяться в процессе работы. Это выражение мы будем называть содержимым ящика.
Каждому ящику соответствует функция, с помощью которой можно получить доступ к содержимому ящика. Эти функции мы будем называть обменными.
Таким образом, имеется взаимно-однозначное соответствие между множеством обменных функций и множеством ящиков. Обменная функция, соответствующая некоторому ящику, будет называться также именем этого ящика.
Наглядно взаимосвязь между ящиком и обменной функцией можно изобразить следующим образом:
--------
FUNC : | e.E0 |
--------
где FUNC - имя обменной функции (ящика), а e.E0 - содержимое ящика.
Обменные функции работают следующим образом. После вычисления терма
<FUNC e.E1>
в поле зрения останется выражение e.E0 - содержимое ящика с именем FUNC, а выражение e.E1 станет содержимым ящика. Таким образом, происходит обмен информацией между полем зрения и ящиком (откуда и произошло название обменных функций).
Все ящики делятся на статические и динамические. Статические ящики существуют в течение всего времени выполнения программы и не могут ни порождаться, ни уничтожаться во время работы. Напротив, динамические ящики порождаются только во время работы и могут уничтожаться.
Все статические ящики должны быть описаны в программе. Для этого используются директивы SWAP, которые выглядят следующим образом:
$SWAP идент_1,идент_2,...,идент_n;
Т.е. следует записать ключевое слово $SWAP, затем перечислить через запятую имена обменных функций и завершить директиву знаком “;”.
Таким образом, статические ящики описываются одновременно со своими обменными функциями. Перед началом работы программы все статические ящики содержат пустые выражения.
Пример. Рассмотрим следующий фрагмент программы:
$SWAP X1,X2;
$FUNC SWX1X2
{
= <X1 'A'> <X2 'B'> <SW2 X1 X2>;
}
$FUNC SW2
{
s.X s.Y = < s.X < s.Y < s.X>>>;
}
В процессе вычисления обращения
<SWX1X2 >
в ящики X1 и X2 сначала занесутся символы ‘A’ и ‘B’, соответственно. Затем, в результате вычисления терма
<SW2 X1 X2>
ящики поменяются содержимым. Т.е. в ящике X1 окажется символ ‘B’, в ящике X2 - символ ‘A’ , а в поле зрения останется пустой результат замены.
Динамические ящики порождаются в процессе работы программы первичной функцией NEW.
В результате вычисления терма
<NEW e.E1>
создается новый ящик и в него помещается выражение e.E1. Одновременно порождается новый символ-ссылка r.R, который остается в поле зрения в качестве результата замены. Символ r.R является именем новой обменной функции, обеспечивающей доступ к созданному ящику.
Имена динамических ящиков являются символами особого типа - символами-ссылками. В отличие от имен статических ящиков, являющихся обычными символами-метками, символы-ссылки нельзя употреблять в виде констант в РефалАБ-программах. Тем не менее, при отладке РефалАБ-программ возникает необходимость как-то печатать символы-ссылки. Они печатаются в виде
/%hhhhhhhh/
где “hhhhhhhh” - шестнадцатеричные цифры, представляющие собой адрес места (x32 или x64), по которому расположен динамический ящик в памяти машины.
В каждый момент работы программы различным символам-ссылкам соответствуют различные адреса.
Один и тот же символ-ссылка имеет один и тот же адрес на протяжении одного запуска программы.
Пример. Рассмотрим следующий фрагмент программы, аналогичный приведенному в предыдущем примере:
$EXTERN NEW;
$FUNC SWR1R2
{
= <SW2 <NEW 'A'> <NEW 'B'>>;
}
$FUNC SW2
{
s.X s.Y = < s.X < s.Y < s.X>>>;
}
В результате вычисления терма
Обратите внимание на следующий факт: обращение к функции SWR1R2 привело к появлению двух новых ящиков. Можно ли теперь как-нибудь извлечь содержимое этих ящиков? Очевидно, что нельзя. Ни в поле зрения, ни в копилке, ни в других ящиках не сохранилось имен этих ящиков. Поэтому дальнейшая работа программы не изменится, если эти ящики уничтожить.
Ясно, что если обращаться к функции SWR1R2 много раз, то память РефалАБ-машины будет забиваться ненужными ящиками. Конечно, для абстрактной РефалАБ-машины это не имеет никакого значения, ибо ее память потенциально бесконечна, но память реальной вычислительной машины рано или поздно должна исчерпаться. Поэтому предусмотрен механизм сборки мусора.
Сборка мусора автоматически запускается каждый раз, когда исчерпается свободная память. При этом обнаруживаются и удаляются все ящики, к которым невозможно добраться прямо или косвенно из поля зрения, копилки или статических ящиков. На следующем рисунке изображены поле зрения, копилка и динамические ящики, пронумерованные цифрами от 1 до 8. Звездочки изображают некоторые элементы выражений, которые не являются символами-ссылками. Символы-ссылки обозначены цифрами.
поле зрения копилка ___________________
* 1 * * * * * 2 * * * * * | |
| | (7): 3 * * 8 (8): 7 *
(1): * 4 * * (2): * * 4 * 5 _____________ / |_____|
|_______________| |/ \ /
(4): * * (5): * 6 * 3 * \
| / \ / \
| (6):* 4 (3):* 5 * *
|____________________________|
Очевидно, что по ссылке из поля зрения можно добраться до ящика 1, а из него - до ящика 4. Из копилки можно непосредственно добраться до ящика 2 и косвенно (через ящик 2) до ящиков 4, 5, 6, 3. Таким образом, нет способа извлечь информацию из ящиков 7 и 8. Если в этот момент запустить сборку мусора, то ящики 7 и 8 будут уничтожены. Если теперь убрать символ-ссылку из поля зрения, то станет недоступным и ящик 1. Если же символ-ссылку в поле зрения оставить, но убрать ссылку из копилки, то окажутся ненужными все ящики, кроме 1 и 4.
Опишем теперь пять первичных функций, которые часто оказываются удобными для работы с содержимым ящиков.
Извлекает содержимое ящика. Результатом замены при вычислении терма
<GTR s.R>
где s.R - имя статического или динамического ящика, является содержимое ящика. При этом в ящике остается пустое выражение.
Как и GTR выдает содержимое ящика в поле зрения, но ящик при этом не изменяется, т.е. происходит копирование его содержимого.
Добавляет в ящик новую информацию. В результате вычисления терма
<PTR s.R e.E1>
где s.R - имя ящика, а e.E1 - произвольное объектное выражение, ящик меняется так:
e.E0 --> e.E0 e.E1
где e.E0 - старое содержимое ящика. Результатом замены является пустое выражение.
Помещает в ящик новую информацию, при этом старое содержимое ящика уничтожается. Т.е. при вычислении терма
<WTR s.R e.E1>
где s.R - имя ящика, e.E1 - произвольное объектное выражение, содержимое ящика меняется так:
e.E0 --> e.E1
где e.E0 - старое содержимое ящика. Результатом замены является пустое выражение.
Записывает в ящик новую информацию, а старую выдает в поле зрения. Таким образом происходит такое преобразование:
поле зрения: <SWR s.R e.E1> --> e.E0
ящик: e.E0 --> e.E1
где s.R - имя ящика; e.E0 и e.E1 - объектные выражения.
Эти функции можно было бы описать на РефалАБ следующим образом:
$FUNC GTR
{
s.X = < s.X>;
}
$FUNC RDR
{
s.X = <RDR1 s.X < s.X>>;
}
$FUNC RDR1
{
s.X e.Y = e.Y < s.X e.Y>;
}
$FUNC PTR
{
s.X e.Y = < s.X < s.X> e.Y>;
}
$FUNC WTR
{
s.X e.Y = <WTR1 < s.X e.Y>>;
}
$FUNC WTR1
{
e.Y = ;
}
$FUNC SWR
{
s.X e.Y = < s.X e.Y>;
}
Отличие этих функций от соответствующих первичных функций состоит в том, что они не проверяют, что s.X - имя ящика, поэтому их область определения шире, чем у соответствующих первичных функций.