Refal-6 basic

История разработки.

Особенности реализации.
Рефал-машина или машина языка сборки.
Данные.
Программы.
Представление символов-ссылок в программе.
Ввод-вывод.
Ввод и вывод выражений.
Начальная загрузка - запуск Рефал-машины.
Реализация модульности

История разработки.

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

Стандарт языка основывался на версии Рефал-5. Были немного изменены оформление модулей и набор встроенных функций.

Интерпретирующая часть была разработана, по возможности, максимально переносимой. По-видимому, даже переход на 64-битную реализацию будет относительно безболезненным, но такой попытки пока не делалось. Имеющаяся реализация компилируется под MS VC++, Linux, Cygwin, Eclipse CPP.

Разработка проекта прервалась по организационным причинам и все материалы были переданы Аркадию Климову, который существенно расширил реализацию Рефала-6.

Существующая старая версия (интерпретирующая часть) была постепенно доработана (в частности, реализована длинная арифметика) и использовалась автором для некоторой деятельности в рамках текущих проектов. Для отличия от реализации Аркадия Климова она называется Refal-6 basic или Refal-6b.

Особенности реализации.

Интерпретирующая часть Рефала-6b основана на ставших уже традиционными принципах, разработанными С.А.Романенко и В.Ф.Турчиным, и использует практически тот же язык сборки.

Рефал-машина или машина языка сборки.

Основу реализации составляет интерпретатор языка сборки, который оформлен как машина языка сборки и позволяет полностью управлять собой на уровне языка сборки. Имеется процедура начальной загрузки, которая описывается ниже. Такая конструкция позволяет написать все остальные функции системы на Рефале: компилятор в язык сборки, управление трассировкой и управление модульностью.

Данные.

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

Символы:

Сложные элементы - это выражения в скобках, длинные числа и ящики.

Все они реализованы как «подвешенные». Такой элемент представлен звеном, содержащим ссылку на звено-заголовок, к которому в виде кольца подвешено выражение, являющееся содержимым элемента.

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

Наличие счетчиков позволяет обходиться без сборки мусора. Проблему представляют только циклические ссылки в ящиках. Чтобы избежать потерь памяти достаточно обнулять содержимое ящиков после их использования. Так, например, делает встроенная функция DELETE, выбрасывая модуль из памяти.
Ящики могут быть поименованные и непоименованные. Поименованные ящики заводятся с помощью специального объявления ящика в программе. Непоименованный ящик создается с помощью специальной встроенной функции NEW.

Программы.

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

Оператор языка сборки - это короткое число, возможно с аргументами, которые могут быть числами или произвольными термами.

Например оператор

   27 3 (2)('abcde')((()))

Означает оператор TEXT ("вставить константное выражение"), состоящее из трех термов: (2)('abcde')((()))

Модуль вида

$ENTRY REFGO {
        e1 = <OUTEXP 1 <CPR *REFGO> (2)('abcde')((()))>;
};

после компиляции и запуска выдаст содержимое ящика REFGO:

4 1 27 2 *OUTEXP 1 1 27 2 *CPR *REFGO 2 40 2 40 27 3 (2) ('abcde') ((())) 34

в конце этого текста находятся операторы языка сборки:

TEXT 3 (2) ('abcde') ((()))
EST

Последний оператор – это конец шага.
Предыдущий оператор означает «вставить константное выражение, состоящее из 3 термов».
Этот оператор скопирует три терма непосредственно из программы на языке сборки.
При этом содержимое скобок копироваться не будет.

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

Представление символов-ссылок в программе.

Конструкция *слово обозначает поименованный символ-ссылку. слово должно быть объявлено в программе как ящик или имя функции.
Если некоторое слово объявлено в программе как ящик, то компилятор автоматически заменит слово на *слово в любом месте внутри программы.
Если некоторое слово объявлено в программе как имя функции, то компилятор автоматически заменит слово на *слово внутри программы в вызове функции. Конструкция <*F … > более соответствует реальному представлению данных, чем <F … > .

Ввод-вывод.

Функции ввода-вывода делятся на две группы.

1. Ввод из стандартного ввода - функция CARD
и вывод в стандартный вывод - функции PRINT, PROUT и PROUTN.

2. Ввод из каналов ввода и вывод в канал вывода.
Каждый канал обозначается числом от 0 до 20.
Каналы 0, 1 и 2 - привязаны к стандартным каналам stdin, stdout и stderr.
Другие каналы можно открыть указав номер канала от 3 до 20, режим (ввод, вывод или добавление) и имя файла.

Ввод и вывод выражений.

В Рефале-6b имеются две функции для ввода и вывода выражений: INPEXP и OUTEXP.

Их важное свойство заключается в том, что INPEXP может ввести выражение, выведенное OUTEXP, и результат ввода совпадет с выведенным выражением. Это не совсем тривиально, учитывая длинные числа, слова и ящики.
Основная проблема возникает с ящиками.
При вводе двух повторяющихся символов-ссылок *ABC *ABC можно создать поименованный ящик с именем ABC, но что делать при вводе второй ссылки - должна использоваться уже созданная ссылка или должен быть создан новый ящик с тем же именем?
Это решается с помощью словарей или таблиц.
Таблица – это ящик, в котором хранятся пары вида ABC *ABC, т.е. слово и символ-ссылка.
Первый элемент содержимого ящика, используемого в качестве таблицы, должен быть словом TABLE. Оставшаяся часть определяется реализацией. В настоящий момент – это просто последовательность пар.
Функция INPEXP вида <INPEXP канал таблица > проверяет, есть ли поименованная ссылка с тем же именем в таблице, и копирует старую ссылку или создает новую. Таблица в вызове функции INPEXP может отсутствовать, тогда изображения символов-ссылок (слова со звездочкой впереди) во входном потоке запрещены.


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

Скомпилированная программа записывается в файл в виде последовательности термов вида:
       (*функция функция на языке сборки)
Для загрузки такой программы необходимо ввести терм за термом и записать в ящик *функция остаток терма.

Начальная загрузка – запуск рефал-машины.

С точки зрения операционной системы реализация Рефала-6b включает только одну исполняемую программу - refal.exe (refal для Юних-подобных систем). Эта программа является Рефал-машиной или интерпретатором языка сборки.
Рефал-машина загружает и запускает специально подготовленную программу на языке сборки - refal.sys.
Файл refal.sys является неким простейшим аналогом операционной системы для Рефал-машины.

Запуск:

  1. Инициализируется пустое состояние рефал-машины.
  2. Открывается входной канал с номером 3 из файла с именем refal.sys и оттуда читается один терм с помощью функции INPEXP. Этот терм должен быть выражением в скобках, являющимся реализацией некоторой функции BOOT на языке сборки. Содержимое скобок записывается в ящик *BOOT
    Таким образом в памяти появляется определение функции BOOT.
  3. Создается начальное поле зрения вида
    <BOOT (таблица_встроенных_функций) (arg1)(arg2)…(argN)>

Функция BOOT в имеющейся реализации записывает в ящики с именами xx, xx1 и xx2 тексты на языке сборки, реализующие вспомогательные функции xx, xx1 и xx2 , которые продолжают читать термы из канала 3.

Вспомогательные функции, появляющиеся после выполнения вызова функции BOOT, могут быть записаны на Рефале следующим образом:


xx {
      (e1) e2 = <xx1 <NEW > (e1) e2>;
};

xx1 {
    sx (e1) e2 =
        <WTR sx e1>
        <xx2 sx <INPEXP 3 sx> >
        <WTR xx>
        <WTR xx1>
        <WTR xx2>
        <START e2 >;
};

xx2 {
    sx (sy e1) = <WTR sy e1> <xx2 sx <INPEXP 3 sx > >;
    sx = <CLOSE 3>;
};


На языке сборки первый терм refal.sys выглядит выглядит следующим образом:


( 4
1 28 *WTR 28 *XX
    27 20 13 4 41 4 2 4 1 28 *XX1 1 28 *NEW 2 40 42 4 9 2 40 34
2 40
1 28 *WTR 28 *XX1
    27 61 31 13 4 41 5 2 4 1 28 *WTR 9 4 8 8 2 40
        1 28 *XX2 9 4 1 28 *INPEXP 28 3 9 4 2 40 2 40
        1 28 *WTR 28 *XX 2 40
        1 28 *WTR 28 *XX1 2 40
        1 28 *WTR 28 *XX2 2 40
        1 28 *START 8 10 2 40 34
2 40
1 28 *WTR 28 *XX2
    27 35 30 (31 7 1 27 2 *CLOSE 3 2 40 34)
        31 13 31 4 41 5 2 7 1 28 *WTR 42 7 9 2 40
        1 28 *XX2 9 4 1 28 *INPEXP
        28 3 9 4 2 40 2 40 34
2 40
1 28 *XX 29 5 2 40 34 XXX)


Этот терм - оттранслированная в язык сборки функция BOOT следующего вида:


BOOT {
e1 = <WTR *XX "функция XX на языке сборки">
    <WTR *XX1 "функция XX1 на языке сборки">
   
<WTR *XX2 "функция XX2 на языке сборки">;
    <XX e1>;

};

Функция xx получает в качестве аргумента таблицу встроенных функций и список параметров вызова интерпретатора (arg1)…(argN).
Функции xx, xx1, хх2 прочитывают входной поток 3 до конца файла с помощью INPEXP и таблицы функций. Каждый вводимый терм является выражением в скобках, представляющем функцию Рефала на языке сборки. Среди вводимых функций должна иметься функция START, которая будет вызвана по окончании загрузки канала 3.

Файл refal.sys представляет из себя программу на языке сборки с прицепленным к ней в начале загрузчиком.
Эта программа анализирует параметры запуска программы refal.exe (refal для Юних-подобных систем) и определяет, что должно быть запущено дальше.

В зависимости от параметров могут быть запущены:

Таким образом вызов Рефала выглядит следующим образом:

   1. Компиляция
       refal -c  имя файла с модулем Рефала, расширение .ref можно опустить.
   2. Вызов Рефал-программы
       refal файл-1.rsx+файл-2.rsx+..., расширения .rsx можно опустить.
   3. Трассировка
       refal -t файл-1.rsx+файл-2.rsx+..., расширения .rsx можно опустить.

Реализация модульности.

Скомпилированный модуль имеет следующий вид:

( Список-внешних-функций )
( Список-глобальных-ящиков )
( Список-входных точек )
(*функция-1 операторы языка сборки для функции-1)
(*функция-2 операторы языка сборки для функции-2)
...

Первые три списка содержат имена, а не ящики. Система поддерживает таблицу глобальных имен, куда входят: Имена из первых трех списков заносятся в эту таблицу с помощью функции
   <NEW s.имя s.таблица>
После занесения первого списка в таблицу имен возможно, что некоторые ящики будут пустыми, поскольку модуль с соответствующими функциями еще не загружен. Это - нормальная ситуация. Модуль с такой функцией возможно будет загружен позже и соответствующий ящик получит содержимое.
Соответствующее имя функции должно содержаться в таблице имен, чтобы связать вызовы этой функции далее в модуле с соответствующим ящиком.

В самом начале таблица содержит только имена встроенных функций.

Ее начало имеет вид:

TABLE
CARD *CARD->(33 0 34)
GET *GET->(33 1 34)
PRINT *PRINT->(33 2 34)
PROUT *PROUT->(33 3 34)
PROUTN *PROUTN->(33 4 34)
PUT *PUT->(33 5 34)
PUTOUT *PUTOUT->(33 6 34)
READKEY *READKEY->(33 7 34)
...

Здесь знаки -> означают ссылку на содержимое ящика.
Содержимое ящиков содержит операторы языка сборки:

   BUILTIN Номер-встроенной-функции EST

Т.е. "выполнить встроенную функцию" Номер-встроенной-функции "конец шага".
После занесения первых трех списков в таблицу глобальных имен эта таблица копируется и используется как локальная таблица для ввода остатка модуля, который состоит из термов вида:

   (*функция операторы языка сборки для функции)

Эти термы вводятся с помощью функции

   <INPEXP канал локальная-таблица>

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

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