Есть мысль изменить текущий формат RASL на приближенный к классическому.

Обзор классического представления

Пишу по памяти, поскольку лень искать диссертацию Романенко.

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

Любая команда сопоставления работает с неявным текущим диапазоном, парой указателей, которые указывают на номера ячеек стека хранящими уже сопоставленные элементы начала и конца диапазона. В результате успешного сопоставления указатель на вновь сопоставленный элемент кладётся на вершину стека, при этом модифицируется одна из границ (указывает на новый элемент). Для перехода к другому диапазону используется команда установить_границы L, R (SETB L, R).

Команды аллокации одновременно являются командами сборки и новые элементы помещают перед открывающей скобкой вызова. Поэтому при неудаче распределения памяти нового элемента поле зрения становится испорченным.

Большинство инструкций не принимает аргументов, поэтому RASL представляет собой байткод, перемежаемый значениями символов (включая функции) или номерами диапазонов (для команд SETB, команд переноса и копирования значений переменных).

Для обработки неуспешного сопоставления используется внутренний стек переходов. На него помещается цель перехода командами типа icOnFailGoTo (так называется эта команда в Рефале-5λ, упрощённо — переход на начало следующего предложения) и командами инициализации цикла по открытым переменным.

Обзор текущего формата

Работа Вадима Сухарева

Текущий формат начал формироваться ещё 10 лет назад в работе Вадима Сухарева. Это был его курсовой проект на кафедре ИУ9, я в то время ещё учился на кафедре СМ5 и выступал в роли консультанта. Фактически, мы вместе делали.

На тот момент в Простом Рефале была реализована кодогенерация в C++, сразу порождались фрагменты кода для операций сопоставления, распределения памяти и сборки результата (это три отдельные фазы). Я тогда ничего не знал о диссертации Романенко, также не представлял себе, как генерировать код для сопоставления с образцом, поэтому был реализован интерпретируемый код только для результатной части.

Понятно, что для каждого предложения генерировался отдельный массив команд (статический массив в коде на C++). Выглядело это так:

#ifdef INTERPRET
  const static refalrts::ResultAction raa = {
    {refalrts::icSpliceEVar, & eX_b_1, & eX_e_1},
    {refalrts::icIdent, (void*) & B<int>::name},
    {refalrts::icBracket, 0, 0, refalrts::ibOpenCall},
    {refalrts::icFunc, (void*) & Fab, (void*) "Fab"},
    {refalrts::icSpliceEVar, & eY_b_1, & eY_e_1},
    {refalrts::icBracket, 0, 0, refalrts::ibCloseCall},
    {refalrts::icEnd}
  };
  refalrts::Iter allocs[2*sizeof(raa)/sizeof(raa[0])];
  refalrts::FnResult res = refalrts::interpret_array( raa, allocs, arg_begin, arg_end );
  return res;
#else
  // код прямой кодогенерации
#endif

Можно заметить, что в константный статический массив кладутся указатели на локальные переменные. А потому что эти локальные переменные тоже статические.

Адреса выделенных элементов клались в массив allocs, размер которого генерировался заведомо достаточного размера — в два раза длиннее raa. Идея в том, что каждая команда может распределить не более двух новых указателей (для копируемых e-переменных).

Ссылки на работу Сухарева:

Массив команд практически повторял правую часть предложения, проход «вперёд» выполнял операции аллокации, проход «назад» переносил инициализированные элементы из списка свободных узлов в поле зрения. Команды интерпретируемого кода по своей структуре наблюдали элементы поля зрения: поле тега + поле информации.

Работа Игоря Дрогунова

Следующим этапом в развитии стала работа Игоря Дрогунова. Он добавил в интерпретируемый код команды сопоставления с образцом, частично изменил команды построения правой части. Вместо указателей на локальные переменные клались их смещения в локальном массиве, который назывался context.

Но выбранный подход сохранился. Интерпретируемые команды представляли собой структуры, содержащие код операции и операнды. Кстати, обратный проход по массиву для переноса распределённых элементов так и остался. Также осталась независимая генерация массивов для предложений.

Ссылки на работу Дрогунова:

Дальнейшее развитие

После завершения работы Дрогунова я постепенно перерабатывал RASL:

Убрал обратный проход при построении результатного выражения — команды аллокации стали принимать адрес в контексте, куда надо положить новый элемент, новые команды переноса стали принимать адреса переносимых элементов.
Объединил интерпретируемые массивы у отдельных предложений в одно.
Перешёл к единому интерпретируемому коду на весь файл (объекты функций получали указатели со смещением).
И наконец перешёл к интерпретируемому коду, загружаемому из файла.

Но формат RASL’а и его идеология остались той же — команды богаты на операнды (не более трёх), в частности:

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

Команды перехода реализованы точно также, как у Романенко.

Сами команды четырёхбайтовые (из соображений выравнивания): https://github.com/bmstu-iu9/simple-refal/blob/cde40fa126726fae560e4317868fa9fb01a71957/src/srlib/refalrts.h#L323-L328

Недостатки:

Очевидный расход памяти, безоперандные команды несут три нулевых байта.
Явная передача значений там, где она избыточна — последовательные команды сопоставления оперируют с одним и тем же диапазоном.
Косвенное обращение к значениям — в val1 или в val2 хранится смещение функции в таблице функций, смещение идентификатора в таблице идентификаторов.
Команда icScale используется для преодоления диапазона val1, val2 и bracket на 0..255 — она содержит старшие половины этих операндов. Команда может идти несколько раз подряд, в частности, для записи числа 4 000 000 000 потребуется 3 команды icScale перед операцией, требующей числового аргумента. Недостаток — команда реализована через goto, что может затруднять оптимизацию компиляторами C++.

Предлагаемое изменение RASL’а

Предлагается перейти к следующему представлению:

union RASL {
  Command command;
  RefalFunction *function;
  RefalIdentifier *identifier;
  RefalNumber number;
  RASL *jump;
};

struct Command {
  unsigned short opcode;
  unsigned short shortarg;
};

Команда по-прежнему будет четырёхбайтовой из соображений быстродействия. Либо даже восьмибайтовой на x64. Но размер не важен — так команда будет выглядеть в памяти после предобработки.

Несмотря на то, что команда icScale исходного RASL’а позволяет записывать числа какой угодно длины, на практике для смещений в контексте и переходов вперёд достаточно двух байт. Поэтому используются short’ы.

Идеи данного представления:

Отдельные элементарные команды могут занимать несколько слов в массиве команд.
Используется внутренний указатель на текущий диапазон, поэтому команды сопоставления его явно не используют. Для установки диапазона используется команда типа SETB. Диапазон, как и ранее, представляется парой соседних ячеек в контексте, следовательно, достаточно только одного операнда — он передаётся в shortarg.
Элементарные команды сопоставления состоят из трёх слов (по именам union’а): command, поле информации и jump. Например, команда сопоставления с идентификатором состоит из command, identifier и jump. Если сопоставление возможно, то счётчик команд инкрементируется на длину команды, сопоставленный элемент сохраняется по смещению shortarg (если команда сохраняющая). Если сопоставление невозможно, счётчик команд устанавливается на jump.
Элементарные команды распределения состоят из command и необязательного поля информации. Созданный элемент сохраняется по смещению shortarg.
Аналогично устроены команды переинициализации.
Команды переноса используют поле shortarg и необязательное поле number, если команда требует два указателя (для оптимизации построения результата).
Очевидно, реальное смещение указателей на функции и идентификаторы в файл не положишь — требуется предобработка, которая по исходному RASL’у строит указанный формат в памяти.

Преимущества:

Команды и операнды выровнены по машинному слову.
Косвенный доступ используется только для контекста (по-другому никак). Даже не используется стек переходов.
Может сочетаться с текущим RASL’ом — в ходе предобработки правильно расставляются указатели на поля информации и jump’ы, разумно добавляются команды SETB.

Недостатки:

Представление очень «рыхлое» — каждая команда сопоставления содержит указатель jump, что будет заполнять кэш процессора. Это может привести к падению производительности.
Требуется предобработка.
Операции с short’ами на x86 медленнее операций с байтами и 32-битными словами (я не измерял, по словам Макарова Андрея Владимировича, он измерял). Возможно, придётся разбирать command на опкод и короткий аргумент при помощи … & 0xFFFF и … >> 16. Но это частности.

Не смотря на то, что представление совместимо с текущим RASL’ом, для него можно придумать более удобный для предобработки язык сборки.

Вывод

Новое представление интересно, но прирост производительности не сильно очевиден. Имеет смысл это дело исследовать.

Aug 06 '18 15:08 Mazdaywik

Диссертация Романенко:

Отсканированная: https://pat.keldysh.ru/~roman/doc/1978-Romanenko--Mashinno-nezavisimyj_kompilyator_s_yazyka_rekursivnyx_funkcij--PhD_thesis.pdf
Перепечатанная в LaTeX: https://pat.keldysh.ru/~roman/doc/1978-Romanenko--Mashinno-nezavisimyj_kompilyator_s_yazyka_rekursivnyx_funkcij--PhD_thesis--LaTeX.pdf

Aug 06 '18 15:08 Mazdaywik

1000 строк кода получится вполне (switch в refalrts::VM::main_loop() занимает 908 строк кода, новый интерпретатор и предобработчик займут не меньше). Текст постановки задачи уже занимает 5 страниц 14 шрифтом Times New Roman в Word. Так что задачи вполне хватит на курсовой проект.

Aug 06 '18 16:08 Mazdaywik

Никто не взял как тему курсового.

Dec 07 '18 12:12 Mazdaywik

refal-5-lambda
refal-5-lambda copied to clipboard

Обдумать и исследовать другой формат RASL

Обзор классического представления

Обзор текущего формата

Работа Вадима Сухарева

Работа Игоря Дрогунова

Дальнейшее развитие

Предлагаемое изменение RASL’а

Вывод

refal-5-lambda refal-5-lambda copied to clipboard

Обдумать и исследовать другой формат RASL

Обзор классического представления

Обзор текущего формата

Работа Вадима Сухарева

Работа Игоря Дрогунова

Дальнейшее развитие

Предлагаемое изменение RASL’а

Вывод

refal-5-lambda
refal-5-lambda copied to clipboard