Различные описания языка Рефал отличаются в некоторых деталях. Вариант Рефала, представленный в работах [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 s w v e . : +
Эти знаки называются специальными знаками.
Из знаков строятся более крупные единицы - символы, термы и выражения.
Символ является минимальной семантической единицей, не расчленимой на составные части средствами языка РефалАБ.
Символы делятся на два класса: составные символы и символы-литеры (или, как их еще называют, “объектные знаки”).
Составной символ имеет следующий вид:
тело_составного_символа
где тело_составного_символа - это последовательность литер.
Множество составных символов разбивается на непересекающиеся классы, в соответствии с тем, какой вид имеют их тела. В РефалАБ имеются следующие классы составных символов: символы-метки, символы-числа и символы-ссылки.
Символами-метками называются составные символы, тело которых начинается с символа ‘&’, за которым следует идентификатор (имя), т.е. последовательность латинских букв, литеры “_” и цифр, начинающаяся с буквы или литеры “_”. Длина идентификатора ограничена 40 литерами.
Например, следующие символы являются символами-метками:
&ALPHA
&L2а4
&_xyz
Так как строчные буквы в идентификаторах заменяются прописными, то символы &ALPHA, &Alpha, &alpha и т.д. полностью эквивалентны.
Символами-числами (макроцифрами) называются составные символы, тело которых представляет собой целое неотрицательное число, т.е. последовательность десятичных цифр. Например:
0 1 512 23
Тело символа-числа должно находиться в диапазоне от 0 до 4294967295 (2^32-1).
Символами-ссылками называются составные символы, тело которых обрамляется символами ‘/’, внутри обрамления начинается с литеры “%”, вслед за которой идет адрес символа-ссылки в шестнадцатеричной форме (x32 или x64). Например:
/%00FFFAC9/ /%FFFFFFFF/ /%ABCDEFAB/
Символы-ссылки нельзя употреблять в качестве констант в РефалАБ-программах. Они порождаются в процессе работы РефалАБ-программы и входят в обрабатываемые выражения. Назначение и использование символов-ссылок будет описано ниже.
Символы-метки используются в программах в качестве имен функций.
Символы-числа служат для обозначения чисел.
Помимо составных символов имеется еще один класс символов - символы-литеры.
Символ-литера имеет следующий вид:
'литера'
где литера - произвольная литера, отличная от апострофа. Так как апостроф тоже является литерой, которую нужно уметь обрабатывать, для него имеется особое обозначение: ‘’, т.е. два апострофа, идущих подряд. Следует заметить, что символ ‘ ‘ обозначает не апостроф, а литеру “пробел”, которая является такой же полноценной литерой, как и все остальные.
По аналогии с языком Си в РефалАБ допускается использование специальных (управляющих) символов, для изображения которых служит обратная косая черта:
Кроме того любой символ может быть представлен последовательностью из трех восьмеричных цифр, обрамленных апострофами с предшествующей обратной косой чертой ‘\ddd’, которая задает значение символа в 8-битном коде, например, символ ‘A’ эквивалентен ‘\061’.
Более сложным элементом РефалАБ является выражение. Оно строится из символов, круглых скобок “(“ и “)” (именуемых структурными скобками), угловых скобок “<” и “>” (именуемых функциональными или конкретизационными скобками) и переменных.
Структурные скобки придают обрабатываемым объектам структуру дерева.
Назначение функциональных скобок и переменных объясняется в следующих разделах.
Выражением называется произвольная последовательность символов, переменных и скобок, правильно построенная относительно скобок. Например:
'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 лев_часть_1 = прав_часть_1
лев_часть_2 = прав_часть_2
. . .
лев_часть_n = прав_часть_n
где FUNC - имя функции, а лев_часть_i = прав_часть_i - суть предложения (правила конкретизации).
Каждое предложение является указанием для замены одного выражения на другое, поэтому оно состоит из левой части (заменяемое выражение) и правой части (результат замены). Синтаксически лев_частьi и прав_частьi являются выражениями.
Перед левой частью каждого предложения должен находиться хотя бы один пробел.
Если предложение не помещается в очередной строке, его можно перенести на следующие строки. Перенос допускается делать в тех местах, где разрешается вставлять пробелы. В любом из таких мест можно поставить знак “+” и продолжить предложение с любой позиции следующей строки.
Семантика РефалАБ-программы описывается в терминах абстрактной РефалАБ- машины. РефалАБ-машина имеет два запоминающих устройства: поле памяти и поле зрения.
Перед началом работы в поле памяти заносится описание набора функций, а в поле зрения - выражение, подлежащее обработке.
Пусть, например, в поле памяти находится единственное предложение:
XXX = '137'
а в поле зрения - выражение
<XXX >
Тогда РефалАБ-машина заменит содержимое поля зрения на выражение
'137'
и остановится, поскольку в поле зрения не осталось ни одной пары функциональных скобок. А что будет, если занести в поле памяти два предложения:
XXX = '137'
= '274'
Теперь для вычисления
Неоднозначность устраняется следующим образом. РефалАБ-машина просматривает
предложения в том порядке, в котором они стоят в описании функции и
применяет первое из них, которое окажется подходящим. Таким образом, в
данном случае
Поле зрения может содержать сколь угодно много функциональных термов, которые могут быть как угодно вложены друг в друга (но уровень вложения не более 511). Поэтому нужно договориться, каким образом РефалАБ-машина будет выбирать выражение, с которого надо начинать процесс вычисления.
Пусть в поле зрения находится выражение, в котором имеются функциональные термы. Тогда некоторые из этих термов являются самыми внутренними, т.е. не содержат внутри себя других функциональных термов. Самый левый из таких термов мы будем называть ведущим.
Теперь опишем работу РефалАБ-машины (для частного случая, когда РефалАБ -программа не содержит переменных).
Работа РефалАБ-машины разбивается на шаги. В начале каждого шага РефалАБ- машина находит ведущий функциональный терм. Пусть этот терм имеет вид:
<FUNC аргумент>
где FUNC - имя некоторой функции, а аргумент - объектное выражение.
Таким образом, предполагается, что содержимое ведущего терма начинается с символа-метки. (Случай, когда это не выполнено, будет рассмотрен позже.)
РефалАБ-машина находит описание функции FUNC и начинает сравнивать аргумент с левыми частями предложений в описании этой функции.
Пусть i - это номер самого первого предложения, для которого лев_часть_i совпадает с аргументом.
Тогда РефалАБ-машина производит замену ведущего функционального терма, т.е.
<FUNC аргумент>
заменяется на правую часть этого предложения, т.е. прав_часть_i, после чего РефалАБ-машина переходит к исполнению следующего шага.
Если же РефалАБ-машина не находит ни одного предложения, для которого левая часть совпадает с аргументом, она сообщает, что “Recognition impossible” (“Отождествление невозможно”) и останавливается. Это означает, что либо программа на РефалАБ, либо исходные данные для нее заданы неверно.
Работа РефалАБ-машины продолжается до тех пор, пока в поле зрения имеется хотя бы один функциональный терм. Если же в поле зрения после завершения очередного шага не остается ни одного функционального терма, РефалАБ-машина останавливается. При этом в режиме отладки она сообщает, что “Concretization is executed” (“Вычисление окончено”). При этом результатом работы РефалАБ-машины считается выражение, которое находится в поле зрения.
Пусть, например, поле памяти содержит следующий набор функций:
XXX = '137'
= '274'
YYY = '2'
ADD ('137') '2' = '139'
А в поле зрения находится выражение
<ADD (<XXX >) <YYY > >
Тогда на первом шаге ведущим будет терм
<ADD ('137') <YYY >>
Теперь подлежит вычислению терм
<ADD ('137') '2'>
На третьем шаге применяется функция ADD, и в поле зрения оказывается выражение
'139'
которое уже не содержит функциональных скобок и является окончательным результатом работы РефалАБ-машины.
Средства, описанные в предыдущих разделах, позволяют описывать только функции, области определения которых - конечные множества, ибо для каждого конкретного значения аргумента приходилось предусматривать особое предложение. Ясно, что так мы далеко не уйдем. Нужно уметь записывать предложения, применимые более, чем к одному объектному выражению. Для этого нужно ввести в предложения переменные, которые при различных применениях предложения могут принимать различные значения.
Языковые объекты, с которыми имеет дело РефалАБ-машина, это всегда выражения, которые могут быть, в частности, термами или символами. Поэтому в РефалАБ используются переменные четырех типов:
Любая переменная имеет следующий вид:
признак_типа спецификация . имя_переменной
Признак_типа - это один из специальных знаков “S” или “s”, “W” или “w”, “V” или “v”, “E” или “e”. Он указывает, к какому из четырех вышеперечисленных типов принадлежит переменная.
Спецификация - это описание дополнительных условий, налагаемых на множество допустимых значений переменной. Спецификация может быть пустой. В этом случае считается, что на возможные значения переменной не налагается никаких дополнительных ограничений. Т.е. значением S-переменной может быть любой символ, значением W-переменной - любой терм, значением V-переменной - любое непустое выражение, значением E-переменной - любое (в том числе и пустое) выражение.
Имя переменной - это идентификатор. Имена переменных служат для того, чтобы различать между собой различные переменные.
Например, S-переменными являются “S.S1”, “S._” и “S.A”, W-переменными являются “W.Var” и “W.х”, 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.
Для этого достаточно ввести в поле памяти РефалАБ-машины следующее описание функции:
FIRST_SYM S.A E.X = S.A
Аналогично можно описать функцию, значением которой является последний символ аргумента:
LAST_SYM E.X S.A = S.A
Поскольку правые части предложений могут содержать функциональные скобки, можно описывать функции в терминах других функций или применять рекурсию.
Опишем, например, функцию REV, определенную для всех выражений. Значением этой функции является “зеркально перевернутое” исходное выражение. Так, вычисление терма
<REV 'A'('B'('CD')'F') >
должно давать
('F'('DC')'B')'A'
Функция REV описывается тремя предложениями:
REV E.A S.X +
= S.X <REV E.A>
E.A (E.X) +
= ( <REV E.X> ) <REV E.A>
=
Обратите внимание на то, что структурные скобки “(“ и “)” не являются символами, и, в отличие от символов-литер ‘(‘ и ‘)’, не могут быть значениями S-переменной. Поэтому, если аргумент кончается на правую структурную скобку, то первое предложение функции - не применимо. В этом случае применяется второе предложение.
Рассмотрим другой пример. Функция SYMM принимает значение ‘Т’ если аргумент - симметричное выражение (т.е. такое, которое не изменяется в результате применения к нему функции REV), и принимает значение ‘F’, если аргумент не является симметричным выражением.
SYMM
E.X = <EQUAL (E.X) <REV E.X>>
EQUAL
(E.X) E.X +
= 'T'
(E.X) E.Y +
= 'F'
Функцию SYMM можно описать и без обращения к функции REV:
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-переменных, то может случиться, что существует несколько вариантов приписывания переменным значений, приводящих к отождествлению левой части предложения с аргументом функции. Пусть, например, в поле памяти находится функция
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-переменной, затем третьей справа и т.д. В нашем примере будет выбран второй из двух способов отождествления.
Если мы хотим, чтобы при применении некоторого предложения использовалось отождествление справа налево, следует сообщить об этом РефалАБ-машине, поместив перед левой частью предложения ключевой знак R, за которым следует хотя бы один пробел. Если же мы хотим, чтобы при применении некоторого предложения использовалось отождествление слева направо, следует сообщить об этом РефалАБ-машине, поместив перед левой частью предложения ключевой знак L, за которым следует хотя бы один пробел.
Если направление отождествления не указано явно, РефалАБ-машина считает, что отождествление следует выполнять слева направо, поэтому ключевой знак L указывать не обязательно (и он отсутствовал во всех приведенных ранее примерах). Например, описанная выше функция F, выдаст в результате замены
<G 'A1:=A2'> <F 'B1:=B2;C1:=C2'>
Но если описать F следующим образом:
F R 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 описывается следующим образом:
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, которая будет вычеркивать все вхождения терма, кроме первого. Для этого можно воспользоваться отождествлением справа налево.
MAKE_SETR
R E.B W.X E.M W.X E.E +
= <MAKE_SETR E.B W.X E.M> E.E
E._ = E._
При желании можно описать функцию MAKE_SET так, чтобы при отождествлении не возникало неоднозначностей:
MAKE_SET
W.A E.E +
= <MAKE_SETX W.A () E.E>
=
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.
Любая переменная может иметь спецификацию, которая располагается между признаком типа переменной и ее индексом.
Спецификации позволяют накладывать дополнительные ограничения на множества допустимых значений переменных. Например, значением SX может быть любой символ, в то время как значением 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, где “+”, “*” и “-“ обозначают объединение, пересечение и разность множеств соответственно. Таким образом, множество спецификаторов замкнуто относительно теоретико-множественных операций.
Имена спецификаторов описываются с помощью ключевого знака S. Эти описания имеют следующий вид:
идентификатор S спецификатор
где идентифтикатор - имя спецификатора без ограничителей “:”, например:
ADDOP S '+-'
MULTOP S '*/'
Теперь имена :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
Все спецификации, которые заданы для вхождений переменных в правую часть предложения - игнорируются.
На использование имен спецификаторов наложено следующее ограничение: если имя некоторого спецификатора используется при описании другого спецификатора, то оно должно быть описано раньше.
Благодаря этому ограничению, запрещаются циклические определения, вроде
SPC1 S :SPC2:
SPC2 S :SPC1:
Приведем примеры использования спецификаторов.
Функция IDENT отщепляет от аргумента слева идентификатор максимальной длины.
IDENT
S(L).X E.E +
= <IDENT1 (S.X) E.E>
E.E = '*' E.E
IDENT1
(E.I) S(LD).A E.E +
= <IDENT1 (E.I S.A) E.E>
(E.I) E.E +
= (E.I) E.E
Если использовать отождествление справа налево и специфицированные E-переменные, ту же функцию можно записать короче:
IDENT
R 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 просматривает цепочку символов и заменяет каждую группу из нескольких последовательно идущих пробелов на один пробел.
ERASE_BL
E.B ' ' E.E +
= E.B ' ' <ERASE_BL_ E.E>
E._ = E._
ERASE_BL_
R E(' ').X E.E +
= <ERASE_BL_ E.E>
Для некоторых S-переменных с определенными спецификаторами существуют эквивалентные записи:
Например, переменной S(L).X соответствуют эквивалентные записи L.X и l.X.
РефалАБ-программа представляет собой последовательность записей. Запись - это отдельная строка текстового файла с расширением “.ref”.
Компилятор РефалАБ использует только первые 88 позиции, остальные позиции игнорируются и обычно используются для нумерации записей. Любой знак в 88 позиции эквивалентен знаку “+”, т.е. означает продолжение РефалАБ-предложения в следующей записи.
Все записи делятся на два класса: комментарии и директивы.
Записи-комментарии начинаются с литеры “*” (перед которой разрешается вставлять от 1 до 86 пробелов).
В позициях после “*” они содержат произвольную информацию. Эти записи игнорируются компилятором РефалАБ и не влияют на смысл РефалАБ-программы.
Записи, которые не являются записями-комментариями, содержат директивы.
РефалАБ-программа представляет собой последовательность директив.
Каждая директива занимает одну или несколько рядом расположенных записей. Пока что будем предполагать, что каждая директива занимает отдельную запись. Правила переноса директив с одной записи на другую будут описаны ниже.
Все директивы имеют следующий вид:
идентификатор ключ информация
где ключ - это ключевой знак или слово, а информация зависит от типа директивы.
Присутствие всех трех компонентов директивы не обязательно: часть из них может отсутствовать. Идентификатор отделяется от ключа одним или несколькими пробелами. Если идентификатор опущен, запись должна начинаться хотя бы с одного пробела. Ключ отделяется от информации одним или несколькими пробелами. Если ключ опущен, а инофрмация начинается с буквы, перед ней должен быть хотя бы один пробел.
Допускаются записи, состоящие из одних пробелов. Они не влияют на смысл РефалАБ-программы и могут использоваться для улучшения ее читаемости.
В качестве ключевых слов допускаются следующие цепочки литер (литеры могут быть любого регистра):
EMPTY
END
ENTRY
EQU
EXTRN
IMPL
L
R
S
START
SWAP
Основное место в РефалАБ-программах занимают предложения, которые служат для описания функций и с которыми мы познакомились ранее. Предложения представляют собой директивы с ключевым знаком L или R, причем знак L разрешается опускать.
Другой известный нам тип директив - это S-директивы, которые имеют ключевой знак S и служат для описания спецификаторов.
Директива, в которой присутствует идентификатор, а ключ опущен или представлен знаками L или R, является признаком начала описания новой функции. А именно, все последующие директивы-предложения, вплоть до начала описания следующей функции, считаются относящимися к этой функции.
Все прочие директивы будут описаны в последующих разделах.
В заключение опишем правила переноса директив с одной записи на другую.
Для перехода с одной записи на другую имеется два способа: 1) литера “+” в любой позиции, в которой допустимо вставить пробел; 2) любая литера, отличная от пробела, в 88 позиции.
Назовем элементами предложения следующие объекты: цепочку объектных знаков (заключенную в апострофы), составной символ, свободную переменную, знаки “<”, “>”, “=”, “(“, “)”.
Между любыми двумя элементами предложения разрешается вставлять произвольное число пробелов. Кроме того, разрешается вставлять пробелы и между элементами спецификатора и скобками, входящими в спецификатор. Например, спецификатор (‘A’)LD эквивалентен ( ‘A’ ) L D. В то же время, нельзя вставлять пробелы между любыми элементами переменной.
Теперь правило переноса с помощью “+” формулируется следующим образом: в любом месте, где могут быть вставлены дополнительные незначащие пробелы, можно вставить знак “+” и продолжить директиву с любой позиции следующей записи.
Пример. Функцию
FUNC E.B '+' E.E = (E.B) '+' (E.E) <PSI >
S(('+-')ON).X = S.X
E._ = E._
можно записать следующим образом:
FUNC +
E.B +
'+' +
E.E +
= +
( E.B +
) '+' (E.E) <PSI >
S( +
( +
'+-' +
) +
O +
N +
).X = S.X
E._ = E._
Второй способ переноса - любая литера, отличная от пробела, в 88 позиции.
В этом случае (если перенос не был уже сделан с помощью знака “+”) первая позиция следующей записи считается непосредственно следующей за 87 позицией текущей записи. Таким образом, директива может быть “разрезана” в любом месте.
Второй способ переноса особенно удобен при автоматической генерации РефалАБ-программ, так как можно сначала породить директиву нужного размера, а затем нарезать ее на куски размером в 87 литеру.
В некоторых случаях возникает желание описывать пустые функции, т.е. функции, описания которых содержат нулевое число предложений. Эти функции имеют пустую область определения, т.к. при любом обращении к такой функции возникает останов “Отождествление невозможно”.
Пустые функции обычно бывают полезны, если нужны символы, которые заведомо отличаются от всех остальных и которые имеют удобные для человека графические представления.
Пустые функции могут быть описаны с помощью директивы EMPTY, которая имеет следующий вид:
EMPTY идент_1,идент_2,...,идент_n
где идент_1, идент_2, …, идент_n - имена определяемых пустых функций.
Например:
EMPTY ALPHA,PSI
Пустые функции можно описывать и еще одним способом: с первой позиции записывается идентификатор, а в следующих позициях директивы остаются пробелы.
Например:
ALPHA
PSI
В некоторых случаях возникает желание описывать эквивалентные (тождественные) имена, т.е. альтернативные имена функций и спецификаторов. Эти имена можно использовать в коде РефалАБ-программ вместо основных имен функций или спецификаторов.
Альтернативные имена обычно бывают полезны, если хочется использовать другие имена библиотечных функций, которые заведомо отличаются от всех остальных и которые имеют удобные для человека графические представления.
Алтернативное имя может быть описано с помощью директивы EQU, которая имеет следующий вид:
экв_идент EQU идент
где идент - имя функции или спецификатора, экв_идент - эквивалентное имя функции или спецификатора.
Например:
WRITELN +
EQU PRINT
READLN +
EQU CARD
Часто бывает удобно разбить РефалАБ-программу на части, которые могут обрабатываться компилятором РефалАБ независимо друг от друга.
Наименьшая часть РефалАБ-программы, которая может быть обработана компилятором независимо от других, называется модулем.
Исходный РефалАБ-модуль должен начинаться с директивы START и кончаться директивой END. В модуле находится IMPL-секция, которая начинается директивой IMPL. Эти директивы имеют следующий вид:
имя_модуля START
IMPL
END
где имя_модуля - идентификатор. Имя модуля может быть опущено.
Функции описываются только в IMPL-секции. Остальные директивы, включая спецификаторы, можно использовать только перед IMPL-секцией.
Функции, описанные в разных модулях, могут обращаться друг к другу. Если в некотором модуле используется функция, которая описана в другом модуле, эту функцию следует объявить внешней по отношению к данному модулю с помощью директивы EXTRN.
Если в некотором модуле описана функция, к которой есть обращения из других модулей, эта функция должна быть объявлена входной точкой данного модуля с помощью директивы ENTRY.
Директивы ENTRY и EXTRN имеют идентичный формат:
ENTRY идент_1,идент_2,...,идент_n
EXTRN идент_1,идент_2,...,идент_n
где идент_i - описание входной точки или внешней метки, соответственно.
Идентi может иметь одну из двух следующих форм:
идентификатор
идентификатор(внешний_идентификатор)
где внешний_идентификатор - это идентификатор, но длиной не более 32 литер.
Если кроме имени функции задан еще внешний идентификатор, это означает, что за пределами модуля (в среде, “окружающей модули”) функция имеет “внешнее” имя, которое отличается от “внутреннего” имени функции, употребляемого внутри модуля. Таким образом одна и та же функция может иметь разные внутренние имена во всех модулях, в которых она используется, но ровно одно, одинаковое для всех модулей внешнее имя.
Если при описании функции в директиве ENTRY или EXTRN внешнее имя не задано, то считается, что внешнее имя совпадает с внутренним.
Внешние имена могут иметь длину не более 32. Поэтому, в тех случаях, когда внутреннее имя имеет длину более 32 литер, следует указывать внешнее имя. В случае слишком длинного имени оно усекается до 32 символов.
Пример. Пусть имеется два модуля M1 и M2. В модуле M1 описана функция COMMUNICATION, а в модуле M2 - функция DREAM и пусть эти функции используются в модулях M2 и M1, соответственно. Тогда эти модули могут иметь следующую структуру:
M1 START
ENTRY COMMUNICATION(COMMUN)
EXTRN DREAM
IMPL
COMMUNICATION
E.B '+' E.E +
= <DREAM E.B> <DREAM E.E>
END
M2 START
ENTRY DREAM
EXTRN communication(COMMUN)
IMPL
DREAM
S.X E.E +
= S.X <communication E.E>
END
Здесь функция, которая имеет внутреннее имя COMMUNICATION в модуле M1, имеет внутреннее имя “communication” в модуле M2 и внешнее имя COMMUN.
С помощью директив ENTRY и EXTRN можно объявлять входными и внешними не только имена функций, но и имена спецификаторов.
Каждое имя, которое употребляется внутри модуля, должно быть описано либо как имя внутренней функции или спецификатора, либо как имя внешней функции или спецификатора в директиве EXTRN.
Во многих случаях возникает необходимость из программ, написанных на РефалАБ вызывать программы, написанные на языке Си. Эта необходимость возникает, в частности, в тех случаях, когда требуется выполнять операции ввода/вывода, операции над числами и другие, которые РефалАБ-машина “не умеет” выполнять непосредственно.
Функции, описанные не на РефалАБ, а на Си, которые, тем не менее, можно вызывать обычным способом из программ, написанных на РефалАБ, называются первичными.
Собственно говоря, с точки зрения РефалАБ-модуля первичные функции - это просто некоторые функции, внешние по отношению к данному модулю, поэтому, вызывая какую-либо функцию можно даже не знать, что это - первичная функция или функция, написанная на РефалАБ. Разница состоит только в том, что исполнение вызова первичной функции занимает только один шаг с точки зрения РефалАБ-машины, в то время как исполнение вызова обычной функции может занять несколько шагов, а также в том, что при выполнении этих обращений может возникать побочный эффект, т.е. взаимодействие со средой, внешней по отношению к РефалАБ-машине. В частности, с помощью первичных функций реализуются операции ввода-вывода. Кроме того, некоторые первичные функции могут менять состояние РефалАБ-машины.
Набор первичных функций, предоставляемых в библиотеке РефалАБ, будет описан отдельно. Помимо этих первичных функций пользователь может писать и собственные на языке Си. Как это сделать будет описано отдельно.
До сих пор мы считали, что РефалАБ-машина имеет два запоминающих устройства: поле памяти и поле зрения. В действительности у нее имеется еще одно запоминающее устройство: копилка, доступ к которому возможен с помощью первичных функций BR, DG, CP, RP, DGALL.
Имена этих функций имеют следующий смысл: ВR - закопать (bury), DG - выкопать (dig out), СР - скопировать (copy), RР - заменить (replace), DGALL - выкопать все (dig out all).
Содержимое копилки всегда имеет следующий вид:
(V.V1'='E.E1) (V.V2'='E.E2) ... (V.Vn'='E.En)
где V.V1, V.V2, …, V.Vn и E.E1, E.E2, …, E.En - произвольные объектные выражения. Смысл содержимого копилки следующий: V.Vi - есть имя выражения E.Ei.
Перед началом работы программы копилка содержит пустое выражение.
Функции ВR, DG, RР и СР предназначены для перемещения выражений из поля зрения в копилку и обратно. обращения к ним имеют следующий вид:
<ВR V.V1 '=' E.E1>
<DG V.V1>
<RР V.V1 '=' E.E1>
<СР V.V1>
где V.V1 - произвольное выражение, а E.E1 - выражение, не содержащее символа ‘=’ на нулевом уровне скобочной структуры.
При обращении к функции ВR терм (V.Vx’=’E.Ey) добавляется к копилке слева, т.е. копилка преобразуется следующим образом:
E.E0 --> (V.Vx'='E.Ey) E.E0
где E.E0 - содержимое копилки до обращения к ВR. Результат обращения к ВR в поле зрения - пусто.
Можно закапывать несколько выражений под одним и тем же именем. Например, в результате выполнения
<ВR 'V=A'> <ВR 'V=B'>
копилка преобразуется следующим образом:
E.E0 --> ('V=B')('V=A') E.E0
Функция DG просматривает копилку слева направо в поисках терма вида (V.Vx’=’E.Ey) и, если находит, удаляет его из копилки и выдает E.Ey в качестве результата замены. Это можно изобразить следующим образом:
поле зрения: <DG V.Vx> --> E.Ey
копилка: E.E1 (V.Vx'='E.Ey) E.E2 --> E.E1 E.E2
Если в копилке несколько выражений закопаны под одним именем, то выкапывается самое левое из них, т.е. то, которое закапывалось последним. При повторном обращении к DG с тем же аргументом V.Vx будет выкопано выражение, закопанное предпоследним и т.д.
Если DG не находит в копилке нужного терма, она выдает в качестве результата замены пустое выражение.
Функция СР, так же, как и функция DG, находит в копилке выражение по имени и выдает его в качестве результата, но копилка при этом не изменяется, т.е. в поле зрения формируется копия выражения. Таким образом СР работает так:
поле зрения: <CP V.Vx> --> E.Ey
копилка: E.E1 (V.Vx'='E.Ey) E.E2 --> E.E1 (V.Vx'='E.Ey) E.E2
Если под именем V.x ничего не закопано, СР выдает “пусто”. Функцию СР можно было бы следующим образом описать через ВR и DG:
CP E.X = <CP1 (E.X) <DG E.X>>
CP1 (E.X) E.Y +
= E.Y <BR E.X '=' E.Y>
Это описание несколько отличается от алгоритма, реализованного в первичной функции СР, тем, что терм (V.Vx’=’E.Ey) переставляется в начало копилки, в то время как первичная функция оставляет его на месте.
Функция RР добавляет в копилку новое выражение и выбрасывает выражение, закопанное в последний раз под тем же именем:
поле зрения: <RP V.Vx '=' E.Ey> -->
копилка: E.E1 (V.Vx'='E.Ey) E.E2 --> E.E1 (V.Vx'='E.Ey) E.E2
Если под именем V.Vx ничего не закопано, то функция RР делает то же самое, что и ВR.
Эквивалентное описание на РефалАБ имеет вид:
RP E.X '=' E.Y +
= <RP1 <DG E.X>> <BR E.X '=' E.Y>
RP1 E._ =
Функция DGАLL позволяет вынуть из копилки все содержимое и поместить его в поле зрения. Обращение к DGАLL имеет вид:
<DGALL >
Пусть копилка содержит выражение E.E0. Тогда результатом обращения к DGALL будет E.E0, причем в копилке останется пустое выражение.
Выражение E.E0 можно вернуть в копилку. Для этого достаточно описать на РефалАБ функцию ВRАLL:
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
SWX1X2 = <X1 'A'> <X2 'B'> <SW2 &X1 &X2>
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), по которому расположен динамический ящик в памяти машины.
В каждый момент работы программы различным символам-ссылкам соответствуют различные адреса.
Один и тот же символ-ссылка имеет один и тот же адрес на протяжении одного запуска программы.
Пример. Рассмотрим следующий фрагмент программы, аналогичный приведенному в предыдущем примере:
EXTRN NEW
SWR1R2 = <SW2 <NEW 'A'> <NEW 'B'>>
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 - объектные выражения.
Эти функции можно было бы описать на РефалАБ следующим образом:
GTR S.X = < S.X>
RDR S.X = <RDR1 S.X < S.X>>
RDR1
S.X E.Y +
= E.Y < S.X E.Y>
PTR S.X E.Y +
= < S.X < S.X> E.Y>
WTR S.X E.Y +
= <WTR1 < S.X E.Y>>
WTR1
E.Y =
SWR S.X E.Y +
= < S.X E.Y>
Отличие этих функций от соответствующих первичных функций состоит в том, что они не проверяют, что S.X - имя ящика, поэтому их область определения шире, чем у соответствующих первичных функций.