ДАННЫE ЯЗЫКА РЕФАЛ-6

• Контейнеры
  • Слова
  • Числа
• Объекты и значения
• Операции с термами
• Доступ к содержимому контейнеров
• Операции арифметики и логики
• Программы как данные
• Ввод объектов

Рефал - язык бестиповый. Это значит, что каждое значение данных содержит в себе всю информацию о типе. Все переменные Рефала принимают значения из некоторого единого универсума, который здесь будет подробно описан.

В этом универсуме имеется три синтаксических типа: символы, термы и выражения, которым соответствуют три типа переменных Рефала: s-, t,- и e-переменные. (Их нельзя назвать типами в обычном программистском смысле. Скорее им соответствуют в обычных языках разделение типов данных на такие категории как записи, массивы, указатели и простые типы.)

На синтаксическом уровне универсум может быть описан следующими синтаксическими уравнениями:

терм = символ | ( выражение ) .

выражение = | терм выражение .

Вертикальная черта обозначает объединение альтернатив.  Таким образом, всякое выражение есть последовательность (список, цепочка, массив) нуля или более термов. Заметим, что начало и конец выражения равноправны: непустое выражение можно с равным успехом представить и как на выражение терм так и на терм выражение. Иными словами, на множестве выражений определена ассоциативная операция конкатенации (приписывания). С другой стороны, никакое окончание одного терма не может быть началом другого, поэтому разложение всякого выражения в последовательность конечного числа термов производится однозначно.

Исходным в определении множества выражений является понятие символа. К нему мы вернемся чуть ниже.

Обратим внимание на круглые скобки, которые входят в основной алфавит. Они играют роль конструктора, позволяющего по всякому выражению построить терм.

КОНТЕЙНЕРЫ

Термы являются базой для построения выражения как конечной последовательности термов. С другой стороны скобки есть механизм, позволяющий из выражения сделать скобочный терм - выражение в скобках. Разные скобочные термы различаются постольку, поскольку внутри себя содержат разные выражения. Это дает основания характеризовать такие термы как контейнеры, содержимым которых являются выражения.

Ниже, рассматривая символы, мы увидим и другие способы построения терма по выражению. Они также содержат в себе образующие их выражения, и потому также являются контейнерами.

Среди символов базовыми (первичными) являются символы-литеры. Им соответствуют знаки кода ASCII. Более сложные образования - это символы слова и символы-числа.

Слова

Символ-слово есть частный случай контейнера, когда образующее его выражение может состоять только из символов-литер. Во входном языке слова записываются при помощи знаков " (двойные кавычки), окружающих образующую цепочку литер, например: "1.5$a". Некоторые литеры в рамках цепочки приходится выражать комбинацией знаков, как-то:

Новая строка (перевод строки) LF             \n

Горизонтальная табуляция HT                  \t

Вертикальная табуляция VT                    \v

Возврат на шаг BS                            \b

Возврат каретки CR                           \r

Перевод формата FF                           \f

Обратный слеш \                              \\

Апостроф '                                   \'

Двойная кавычка "                            \"

Десятичный код символа                       \nnn

Шестнадцатеричный код символа                \xnn

здесь n - десятичная или шестнадцатеричная цифра. В записи слов, состоящих из букв, цифр и начинающихся с заглавной буквы, обрамляющие кавычки могут опускаться.

Числа

Символы-числа в компьютере представлены в двоичном коде. Поэтому их можно считать контейнерами, содержащими последовательности двоичных цифр 0 и 1, которые будем также называть масками, причем самый младший разряд - слева (это важно для единообразия!). Но поскольку в двоичной системе записывать числа неудобно (тем более с единицами слева), в исходном языке используется либо десятичная запись (возможно со знаком): 0, 1, -10, 256, либо шестнадцатеричная: 0x12 = 18, -0xff = -255, с обычным старшинством разрядов.

Возникает вопрос: из какой двоичной последовательности: 011, 0110 или 01100 - образовано число 6? Ведь нужно, чтобы два числа были равны тогда и только тогда, когда образующие их последовательности равны.

Естественно считать, что самый правый разряд числа выражает его знак, при этом отрицательные числа представлены в дополнительном коде. Отсюда следует, что 011 представляет не 6, а -2, но 0110 и 01100 представляют 6. Ясно, что значение числа не изменится, если старший знаковый разряд повторять вправо сколько угодно раз. Для того чтобы обеспечить взаимнооднозначное соответствие между целыми числами и их двоичными образующими (выражениями), будем считать допустимыми лишь самые короткие образующие каждого числа, содержащие ровно один знаковый бит (то есть отбрасываются справа все биты, равные знаковому, кроме одного). После операций модификации длина значения нормализуется до этой минимальной. (А пустая маска нормализуется до '0').

ОБЪЕКТЫ И ЗНАЧЕНИЯ

Все разобранные выше термы (символы и скобочные термы) относятся к категории чистых значений в следующем смысле: если сделать две или более копии одного терма, то далее, что бы ни происходило с одной копией, значение и содержимое другой измениться не может (для скобочных термов сказанное верно лишь постольку, поскольку при его построении были использованы лишь уже рассмотренные виды термов). 

В Рефале-6 имеются также другие символы, называемые символы-ссылки, для которых это свойство уже не верно. Эти символы являются именами объектов, в том смысле, что имена однозначно идентифицируют объект. Однако объекты внутри себя содержат другие значения, которые могут время от времени изменяться, т.е. один и тот же объект в разные моменты времени может содержать в себе разные значения. А это означает, что можно сделать копию символа-ссылки и затем, воздействуя на объект через одну из них, изменить содержимое объекта, доступного через другую ссылку, поскольку это фактически один и тот же объект.

Ряд видов объектов Рефала-6 (термов) определяются как контейнеры, в том смысле, что их содержимое является выражением и оно полностью определяет состояние объекта. Имеется гомологическое соответствие между классами объектов-контейнеров и классами термов-контейнеров, являющихся чистыми значениями. Оно выражено следующей таблицей:

В таблице в двух последних столбцах: ЗНАЧЕНИЕ и ОБЪЕКТ - перечисляются конкретные виды контейнеров. Строки таблицы различаются прежде всего способом представления контейнера в памяти компьютера. Но вследствие особенностей того или иного представления накладывается ограничение и на значения используемого выражения. Так, для строк и слов (представление - "Массив литер") допускаются только выражения из символов-литер, а для чисел и масок (представление - "Двоичная строка") - из '0' и '1'.

Список  состоит из любых термов. Только константы этого типа являются выражениями в скобках. Все остальные виды являются символами.

Массив (вектор) также может содержать любые термы.

Массив литер состоит из любых символов-литер.

Двоичная строка состоит из символов-литер '0' и '1'.

Язык может быть расширен какими-то другими представлениями выражений в контейнерах, т.е. таблица в принципе быть еще расширена. 

Полный список операций с контейнерами всех видов приводится ниже. Если в операции модификации участвует контейнер-объект, то его содержимое, вообще говоря, изменяется. Результатом этой операции является, как правило, ссылка на тот же объект с новым содержимым. Те же операции с контейнерами-значениями вырабатывают новое значение с аналогичным новым содержимым.

Свойства объектов и значений

Выше упоминалось одно важное свойство, по которому различаются значения и объекты - это изменяемость во времени. Ниже приводятся два других свойства.

Способ сравнения. Сравнение значений-контейнеров (одного вида) сводится к сравнению содержащихся в них выражений. То есть сравнение значений экстенсионально. Для сравнения объектов (на равенство) одинаковости содержимого недостаточно (фактически же и не требуется), а требуется более сильное условие: что два объекта - это в действительности один и тот же объект. То есть сравнение объектов интенсионально. На практике он осуществляется путем сравнения ссылок.

Ранжируемость. Этим свойством обладает универсум чистых значений. Оно предполагает, что всем термам можно приписать целочисленный ранг так, что ранг каждого терма будет строго больше ранга терма, в него входящего. Это означает, в частности, что никакой терм-значение не может быть частью себя самого.

Для термов-объектов это не верно, хотя бы потому, что ящик может содержать символ-ссылку на себя самого. Это очень существенная возможность, так как она позволяет посредством ссылок реализовать произвольный граф. 

Функции доступа

В Рефале-6 имеется сравнительно небольшой набор функций доступа, общий для всех видов контейнеров. Благодаря этому удалось в целом заметно сократить число различных имен встроенных функций, чем, в частности, облегчить их запоминание. Важно также и то, что программа может не зависеть от вида объекта, с которым она работает: функция, допускающая слово будет почти всегда допускать и строку, а при некоторых условиях и число (маску). Досадное исключение - функция COMPARE, поскольку слова и выражения сравниваются лексикографически слева направо, а числа справа налево (при условии расширения более короткого вправо до длины более длинного).

ОПЕРАЦИИ С ТЕРМАМИ

Константность
                       <CONST tR> == T | F

Тип терма
                       <MODE tX> == CHAIN | VECTOR | STRING | MASK | 
                                                  EMPTY | CHAR | FUNC | TABLE
                                                  REAL | VIDEO

Создание объекта данного типа
                       <MAKE s.mode> == tR
                       <MAKE s.mode tR> == t.R1

Создание нового пустого объекта
                       <NEW> == tR
                       <NEW s.word> == tR

Выдать значение
                       <GET tR> == tV

Установить новое значение
                       <SET tR tV> == t.R1

Переместить объект
                       <Move tS tD> == tD

Копировать объект
                       <Copy tS tD> == tD

CONST позволяет про любой терм узнать, является он значением (T) или модифицируемым объектом (F).

MODE для любого терма позволяет узнать его тип: CHAIN - выражение в скобках или ящик, VECTOR - вектор, STRING - слово или строка, MASK - число или битовая шкала, EMPTY - пустой объект (например, после операции NEW), CHAR - символ-литера, FUNC - функция, TABLE - таблица, REAL - вещественное.

Таким образом, в совокупности, CONST и MODE позволяют узнать все про вид терма.

MAKE создает новый объект указанного вида (кроме CHAR). Если имеется второй аргумент - ссылка на объект, то он инициализируется как объект указанного вида. Контейнерный объект инициализируется содержимым длины 0.

NEW создает новый пустой объект (вида EMPTY). Если указан аргумент - слово, то это слово будет использовано в качестве имени данного объекта при печати. (Фактически новый объект под указанным именем будет зарегистрирован в таблице *SYSID).

GET превращает всякий терм в соответствующий неизменяемый терм. То есть если он был неизменяемым (значением), то результат совпадает с аргументом, а если он был изменяемым (объектом), то вырабатывается неизменяемое значение того же типа и с тем же содержимым.

SET модифицирует первый (изменяемый!) аргумент типом и значением второго. Например, чтобы получить изменяемую копию любого значения, можно написать <SET <NEW> tV>.

MOVE перемещает содержимое изменяемого первого аргумента tS в изменяемый второй tD. При этом объект tS становится пустым (EMPTY).

COPY делает из второго аргумента копию первого. Первый аргумент не изменяется.

ДОСТУП К СОДЕРЖИМОМУ КОНТЕЙНЕРОВ

Чтение содержимого
                       <GETV tR> == eX

Замена содержимого
                       <SETV tR eX> == t.R1

Чтение n-го терма содержимого
                       <GETN tR sn> == tX

Замена n-го терма содержимого
                       <SETN tR sn tX> == t.R1

Номер терма
                       <POS tR tX> == en

Чтение подпоследовательности
                       <GETS tR sn sl> == eX

Замена подпоследовательности
                       <SETS tR sn sl eX> == t.R1

Сдвиг подпоследовательности
                       <SHIFT tR sn sl> == t.R1

Добавление
                       <APPEND tR eV ...> == t.R1

Длина содержимого
                       <LENCONT tR> == sL

В операциях модификации (SET_, SHIFT) результат t.R1 определяется так. Если tR - объект, то t.R1 - тот же самый объект с изменившимся значением. Если же tR - значение, то t.R1 - новое значение того же вида, что и tR, с новым содержимым.

В операциях номер позиции sn выражает номер элемента (терма) содержимого слева направо, начиная с 0.  Если номер отрицателен, то он нумерует элементы справа: -1 - позиция правее самого последнего (правого), -2 - последний, -3 - предпоследний и т.д. Если все же при чтении номер выходит за пределы содержимого, то считается, что в нем виртуально содержится пробел (кроме масок, которые расширяются вправо знаковым битом). При записи элементы записываемые левее самого левого пропадают, а при записи правее правого конца содержимое предварительно наращивается вправо необходимым числом пробелов (для масок - знаковых битов).

Функция POS ищет слева направо внутри содержимого терма-контейнера tR термы, равные tX, и выдает список их номеров (пустой, если ни одного такого терма не найдено).

В операциях чтения/замены подпоследовательности (GETS/SETS) sn - это номер первого читаемого/заменяемого терма, начиная с 0, sl - количество подряд идущих читаемых/заменяемых термов старого подвыражения. При замене цепочка термов eX, вставляемая на место удаляемой цепочки длины sl, дополняется до длины sl путем повторения eX нужное число раз и отбрасывания лишних термов справа. Если eX пусто, а также когда пишется недопустимый для данного вида терм, то в качестве заполнителя используется пробел (для масок - нуль).

Операция сдвига подпоследовательности SHIFT оставляет на месте элемены левее указанной позиции sn (нулевой позиции, если sn указывает левее левого края) , а остальное сдвигает на sl позиций: вправо, если sl>0 и влево, если sl<0. При сдвиге влево первые sl элементов сдвигаемой части пропадают, а при сдвиге вправо освобождаемые позиции заполняются пробелом ' ' (для масок - нулем).

Операция APPEND добавляет второй аргумент eV в хвост содержимому контейнера tR. Ее можно так определить на Рефале-6:

     APPEND  tR eV = <SETV tR <GETV tR> eV>;

ОПЕРАЦИИ АРИФМЕТИКИ И ЛОГИКИ

Для специальных видов контейнеров могут быть определены свои операции. Например, имеется набор функций для выполнения операций арифметики над числами и операций булевой алгебры над битовыми строками (масками). Аргументами могут быть как значения, так и ссылки (объекты). В результате - всегда значение. Если нужно его присвоить объекту, следует использовать функцию SET. Ниже приводится список форматов этих функций.

Сложение                 <ADD sA sB> == sC
Вычитание                <SUB sA sB> == sC
Умножение                <MUL sA sB> == sC
Деление с остатком       <DIVREM sA sB> == sQ sR
Частное                  <DIV sA sB> == sC
Остаток                  <REM sA sB> == sC
Объединение (ИЛИ)        <OR  sA sB> == sC
Пересечение (И)          <AND sA sB> == sC
Симметрическая разность  <XOR sA sB> == sC

Функция DIVREM дает два результата: частное (объект или значение) sQ и остаток (всегда значение) sR. Величины частного Q и остатка R подчиняются правилу:

A = Q * B + R причем остаток имеет знак делимого. Функции DIV и REM дают те же частное и остаток по-отдельности.

Побитовые операции выполняются так. Сначала значения двоичных строк выравниваются по длине путем расширения старшего бита более короткой строки, далее выполняется операция, а затем у полученного значения отбрасываются лишние старшие биты.

Все арифметические операции применимы также и к вещественным числам (как значениям, так и ссылкам). Причем, если один аргумент целый, а другой вещественный, то целое предварительно превращается в вещественное.

ПРОГРАММЫ КАК ДАННЫЕ

Символы-функции рефала-6 - это тоже символы ссылки. А связанные с ними объекты - тоже контейнеры. Для функции F содержимое контейнера *F, с одной стороны, является объектным выражением, то есть может быть прочитано или записано средствами рефала, а с другой стороны, являет собой исполняемый код, который выполняется при вызове <F e.arg>.

Объект *F  имеет тип FUNC. В реализации его представление практически не отличается от вектора. Элементами содержимого (термами) являются либо операторы языка сборки с упрятанными в них непосредственными аргументами, либо термы-константы Рефала-6, которые были в исходной программе (в частности - ссылки на другие функции). Переходы внутри функции кодируются символами числами, выражающими смещение относительно текущего оператора.

Операторы языка сборки представлены словами длиной не более трех. Первая литера - код оператора, другие - операнды (номера элементов). Слова до трех символов представляются в Рефале-6 непосредственно в звене,  поэтому код в памяти хранится достаточно компактно.

Все это имеет следующие интересные последствия:

1. Скомпилированные модули рефала-6 являют собой запись обычного Рефал-6-выражения в текстовом файле, содержащие определения объектов. (См. Ввод объектов.)

2. Компилятор с Рефала-6 в язык сборки написан полностью на Рефале-6. Функция <COMP file-names> (модуль С) доступна пользователю Рефала-6. Аргумент - список контейнеров, содержащих имена файлов и другие параметры командной строки. Функция <CL file-names> (compile-and-load) компилирует непосредственно в поле памяти.

3. Загрузчик модулей написан на Рефале и пользуется только штатными средствами ввода выражений.

4. Загрузка может быть вызвана динамически из программы пользователя, посредством функции <LOAD file-names>. А функция <DELETE file-names> освобождает память от указанных модулей. При этом все определенные в них функции становятся пустыми объектами.

5. Исполняемая программа может динамически подменить тело функции. Этим пользуется отладчик, который тоже написан на Рефале: функции BRK - установить break-point, TRC, TRCA - трассировать вызовы (модуль TR), подменяют тела указанных в аргументе функций на новые, которые вызывают старые, спрятанные в новых объектах. А функция REST восстанавливает указанные функции обратно.

6. Пользователь может легко выполнять некоторые простые операции редактирования тела функции, например, типа замены одних констант (символов-ссылок) на другие. Этим пользуются функции, упомянутые в предыдущем абзаце.

Таким образом, система Рефал-6 замкнута, в том смысле, что может служить операционной системой (включающей компилятор и загрузчик) для себя самой.

ВВОД ОБЪЕКТОВ

При вводе и выводе объектных выражений символы-ссылки изображаются именами со звездочкой впереди. Для отождествления одинаковых символов ссылок используются таблицы, в которых хранится соответствие между именами (словами) и символами ссылками. Таблица указывается в аргументе функции ввода-вывода (см. Ввод-вывод).

Когда при вводе во входном потоке изображение некоторого  символа-ссылки встречается впервые, создается новый пустой объект и заносится под своим именем в таблицу. Когда такое изображение встречается вновь, из таблицы извлекается старая ссылка.

Когда при выводе встречается символ-ссылка, то из таблицы извлекается ее имя, которое выводится со звездочкой впереди. Если в таблице этого символа не было, то формируется автоматически имя вида X$nnnnnn.

Для контейнеров (и других специальных объектов) имеется возможность вместе со ссылкой во входном потоке поместить ее содержимое. Для этого сразу после имени  надо поставить знак равенства, за которым поместить букву типа, а за ней - выражение в скобках (или что-то специфическое для этого типа). До левой скобки не должно быть пробелов. Между буквой типа и левой скобкой может стоять число термов в содержимом скобок. Для контейнеров используются следующие буквы: C - CHAIN (ящик), V - VECTOR, S - STRING,  M - MASK, F - FUNC, T - TABLE. Например:

      *Str=S('abc')
      *Expr=C(*N '+' 1)
      *Map=F16(K u 12 K O a gE lB k *Map dD gG lB p P p)
      *MyTable=T(A *A B *B)

Особо могут записываться числовые значения (для чисел-объектов типа MASK и FLOAT): после знака "=" сразу пишется число, например:

      *N=5 *PI=3.14159

Вывод символов-ссылок в указанной форме необходимо программировать "вручную", например:

EncodeContainer s.Table s.Ref = 
      <ENCODE s.Table s.Ref>
      '=' <GETN 0 <MODE s.Ref>> <LENCONT s.Ref> 
      '('<GETV s.Ref>')';