#LyX 2.1 created this file. For more info see http://www.lyx.org/
\lyxformat 474
\begin_document
\begin_header
\textclass article
\begin_preamble
%вчегда ставить отступ, даже в начале
\usepackage{indentfirst}
%\renewcommand{\baselinestretch}{1.25}
%\usepackage[12pt]{extsizes}
\usepackage{float}
%переименовать объект алгоритм
\floatname{algorithm}{Листинг}
%\newcommand{\algorithmname}{Listing}
%позволить добавление списка литературы в содержание
%\usepackage{tocbibind}
\usepackage[nottoc]{tocbibind} %получаем ToC без включения его самого же
\end_preamble
\use_default_options true
\begin_modules
figs-within-sections
tabs-within-sections
eqs-within-sections
\end_modules
\maintain_unincluded_children false
\language russian
\language_package default
\inputencoding auto
\fontencoding global
\font_roman default
\font_sans default
\font_typewriter default
\font_math auto
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize 12
\spacing onehalf
\use_hyperref true
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks false
\pdf_pdfborder true
\pdf_colorlinks true
\pdf_backref false
\pdf_pdfusetitle true
\papersize a4paper
\use_geometry true
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\leftmargin 2cm
\topmargin 3cm
\rightmargin 2cm
\bottommargin 3cm
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language french
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Standard
При изучении различных реализаций RASL языков диалекта Рефал можно заметить,
 что большинство реализаций так или иначе позволяют описывать сборки в файловом
 представлении.
 В дорабатываемой версии языка в генерируемом коде активно используются
 переменные типа Iter, которые служат как ссылки на элементы поля зрения,
 то есть для описания сопоставляемых сущностей.
 Они часто передаются по ссылке в качестве аргументов для функций среды
 выполнения или команд интерпретатора.
 Одним из предлагаемых улучшений в рамках данной работы является переписывание
 выделения переменных Iter в отдельный массив памяти context и использование
 в качестве аргумента уже положение ссылки на узел в этом массиве, а не
 указатель.
 Также, все объявления скобок аналогично переносятся в массив context.
 Введём следующее соглашение: в начале массива context первые 2*n элементов
 выделяется для n скобок, остальное же место предназначено для описания
 сопоставляемых сущностей.
\end_layout

\begin_layout Standard
Будем хранить e-перменные и скобки в виде двух последовательных элементов
 массива context.
 Таким образом, по индексу скобки или e-переменной мы получаем описание
 для её начала, а по индексу + 1 получаем её конец.
 Код обращения и объявления выделенных переменных и скобок приведён в листинге
 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:context-opt"

\end_inset

.
 Она же, оттранслированная на версии компилятора до внесения улучшений,
 доступна для сравнения в приложении 2 
\begin_inset CommandInset ref
LatexCommand vpageref
reference "sub:attach-Func-master-1"

\end_inset

.
 Для повышения читаемости генерируемого кода и его наглядности будем объявлять
 индексы выделенных переменных по следующему соглашению:
\begin_inset Newline linebreak
\end_inset

 
\begin_inset listings
lstparams "language=C,basicstyle={\ttfamily}"
inline true
status open

\begin_layout Plain Layout

enum { __{тип}{имя}_{номер-вхождения}_{номер-скобки} = {индекс} };
\end_layout

\end_inset

.
 Тип переменной представляет собой ascii символ 's', 't', 'e' для соответствующе
го типа рефал данных.
 Для скобок же сохраним их численное представление.
 По индексу скобки легко восстановить её номер, ведь 
\begin_inset Formula $index=num*2$
\end_inset

.
\end_layout

\begin_layout Standard
В оригинальной версии компилятора не было предусмотрено нумерации переменных,
 что усложняет внедрение работы с сущностями по индексу в массиве context.
 Поэтому, первым шагом к реализации описанной выше модификации является
 добавление в генератор нумерации выделяемых переменных и скобок.
 В файле Algorithm.sref в функции GeneralizeResult (которая вкратце рассматривала
сь 
\begin_inset CommandInset ref
LatexCommand vpageref
reference "alg:GenerateResult-Interp-Algorithm"

\end_inset

) происходит вычленение неиспользуемых переменных и генерация сопоставления
 с образцом, построения результата и команд языка сборки.
 Воспользуемся тем фактом, что в генерации участвуют уже отфильтрованные
 сущности.
 Для них и будем строить индексы.
 Объект (e.CommonVars) представляет собой список переменных, который содержит
 не только переменные образцовой части, но и копируемые переменные результатной.
 В листинге 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:NumerateVars"

\end_inset

 приведён код функции, осуществляющей нумерацию переменных в порядке возрастания.
 Здесь же, разбирается тип переменной.
 Все переменные, кроме e-переменных должны занимать 1 слот, а e-переменные
 --- 2.
\end_layout

\begin_layout Standard
Нумерация скобок актуализируется достаточно тривиально.
 В функции DoGenPattern при построении объекта уже присутствует нумерация.
 Необходимо лишь заменить инкремент номера на увлечение на 2.
 В силу того, что переменные в массиве располагаются после выделения памяти
 для описания скобок, то необходимо в качестве начального значения для первого
 вызова функции NumerateVars передать диапазон на начало области переменных
 в массиве context, которое вычисляется, как 
\begin_inset listings
lstparams "language=C,basicstyle={\ttfamily}"
inline true
status open

\begin_layout Plain Layout

(число скобок + 1) * 2
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Нумерация переменных 
\begin_inset CommandInset label
LatexCommand label
name "alg:NumerateVars"

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset listings
lstparams "basicstyle={\ttfamily},tabsize=2"
inline false
status open

\begin_layout Plain Layout

NumerateVars {
\end_layout

\begin_layout Plain Layout

  s.Number ( s.Usings 'e' e.Index ) e.Etc =
\end_layout

\begin_layout Plain Layout

    (s.Number s.Usings 'e' e.Index)
\end_layout

\begin_layout Plain Layout

    <NumerateVars <Add s.Number 2> e.Etc>;
\end_layout

\begin_layout Plain Layout

  s.Number ( s.Usings s.Mode e.Index ) e.Etc =
\end_layout

\begin_layout Plain Layout

    (s.Number s.Usings s.Mode e.Index)
\end_layout

\begin_layout Plain Layout

    <NumerateVars <Inc s.Number> e.Etc>;
\end_layout

\begin_layout Plain Layout

  s.Number = (s.Number); 
\end_layout

\begin_layout Plain Layout

}
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Оптимизация с использованием массива context
\begin_inset CommandInset label
LatexCommand label
name "alg:context-opt"

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset listings
lstparams "basicstyle={\ttfamily},breaklines=true,tabsize=2"
inline false
status open

\begin_layout Plain Layout

refalrts::Iter context[13];
\end_layout

\begin_layout Plain Layout

refalrts::zeros( context, 13 );
\end_layout

\begin_layout Plain Layout

enum { __ePattern_1_1 = 6 };
\end_layout

\begin_layout Plain Layout

enum { __eVars_2_1 = 8 };
\end_layout

\begin_layout Plain Layout

enum { __sNumRanges_2_1 = 10 };
\end_layout

\begin_layout Plain Layout

enum { __eCommands_2_1 = 11 };
\end_layout

\begin_layout Plain Layout

context[0] = arg_begin;
\end_layout

\begin_layout Plain Layout

context[1] = arg_end;
\end_layout

\begin_layout Plain Layout

...
\end_layout

\begin_layout Plain Layout

static refalrts::RASLCommand raa[] = {
\end_layout

\begin_layout Plain Layout

  {refalrts::icBracketLeft, 0, 2, 0},
\end_layout

\begin_layout Plain Layout

  {refalrts::icBracketLeft, 0, 4, 0},
\end_layout

\begin_layout Plain Layout

  {refalrts::icContextSet, 0, __ePattern_1_1, 2},
\end_layout

\begin_layout Plain Layout

  {refalrts::icContextSet, 0, __eVars_2_1, 4},
\end_layout

\begin_layout Plain Layout

  {refalrts::icsVarLeft, 0, __sNumRanges_2_1, 0},
\end_layout

\begin_layout Plain Layout

  {refalrts::icContextSet, 0, __eCommands_2_1, 0},
\end_layout

\begin_layout Plain Layout

  {refalrts::icEmptyResult, 0, 0, 0},
\end_layout

\begin_layout Plain Layout

  ...
\end_layout

\begin_layout Plain Layout

  {refalrts::icBracket, 0, refalrts::ibCloseBracket, 0},
\end_layout

\begin_layout Plain Layout

  {refalrts::icEnd}
\end_layout

\begin_layout Plain Layout

};
\end_layout

\begin_layout Plain Layout

...
\end_layout

\begin_layout Plain Layout

if( ! refalrts::brackets_left( context[4], context[5], context[0], context[1]
 ) ) 
\end_layout

\begin_layout Plain Layout

 break;
\end_layout

\begin_layout Plain Layout

context[__ePattern_1_1] = context[2];
\end_layout

\begin_layout Plain Layout

context[__ePattern_1_1 + 1] = context[3];
\end_layout

\begin_layout Plain Layout

context[__eVars_2_1] = context[4];
\end_layout

\begin_layout Plain Layout

context[__eVars_2_1 + 1] = context[5];
\end_layout

\begin_layout Plain Layout

...
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Данное решение позволяет получить более читабельный и компактный генерируемый
 код, а также позволяет сократить размер структуры, описывающей команду
 языка сборки, о чем будет написано ниже по тексту.
\end_layout

\begin_layout Standard
В качестве дополнительной оптимизации А.В.
 Коноваловым было предложено сокращение размера элементарной команды языка
 сборки до 4 байт.
 Предполагается, что команда будет описана структурой, приведённой в листинге
 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:Описание-структуры-RASLCommand"

\end_inset

.
 Данный подход требует ввода дополнительного ограничения на максимальный
 индекс переменных и скобок в диапазоне до 255 в рамках одной порождаемой
 функции.
 Данное ограничение считается вполне приемлемым.
 Также, например, в реализации диалекта Рефал-5 введено аналогичное ограничение.
 
\end_layout

\begin_layout Standard
Структура ResultAction была переименована на более актуальное имя RASLCommand,
 что точнее передаёт её смысл.
 Поле cmd описывает тип операции, поля val1 и val2 служат для передачи индексов
 аргументов или некоторых значений.
 При этом индекс скобки обычно передаётся через поле bracket.
 Приведённая модификация уменьшает потребление памяти при выполнении в режиме
 интерпретации, также, позволяет современным процессорам более эффективно
 обрабатывать данные, так как вероятность попадания в кеш процессора цепочки
 команд, выровненных по границе в 4 байта достаточно существенна.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement H
wide false
sideways false
status open

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Описание структуры RASLCommand
\begin_inset CommandInset label
LatexCommand label
name "alg:Описание-структуры-RASLCommand"

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset listings
lstparams "language=C,basicstyle={\ttfamily},tabsize=2"
inline false
status open

\begin_layout Plain Layout

typedef struct RASLCommand {
\end_layout

\begin_layout Plain Layout

  unsigned char cmd;
\end_layout

\begin_layout Plain Layout

  unsigned char val1;
\end_layout

\begin_layout Plain Layout

  unsigned char val2;
\end_layout

\begin_layout Plain Layout

  unsigned char bracket;
\end_layout

\begin_layout Plain Layout

} RASLCommand;
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Модель интерпретатора, описанная в 
\begin_inset CommandInset citation
LatexCommand cite
key "key-1"

\end_inset

 при реализации новых команд сохранит часть своей кодовой базы.
 Только существующие операции (icChar, icInt, icFunc, icIdent, icString,
 icBracket, icSpliceSTVar, icSpliceEVar, icCopySTVar, icCopyEVar, icEnd)
 изменят свой формат на более актуальный --- четырехбайтный.
\end_layout

\begin_layout Standard
Рассмотрим полное множество команд для языка сборки Простого Рефала.
\end_layout

\begin_layout Standard
Команды интерпретатора можно разделить на несколько групп по их функциональности.
 В первую группу можем отнести команды выделения памяти для сущности.
 В нее входят команды для таких типов данных, как символ (icChar), без знаковое
 целое число (icInt, icHugeInt), объект типа функция (icFunc), идентификатор
 (icIdent), строка (icString), скобка (icBracket).
 Данная группа имеет следующий вид представления в RASL-представления: 
\begin_inset listings
lstparams "language=C,tabsize=2"
inline true
status open

\begin_layout Plain Layout

{код_операции, 0, аргумент, 0}
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
Стоит отметить, что при представлении команды в четырёхбайтной структуры
 передача в прямом виде в качестве аргумента указателя на функцию, идентификатор
 или значения целого без знакового числа, представление которого превышает
 размер 1 байт, не представляется возможным при таком подходе.
 Поэтому, будем передавать в качестве аргумента не значение, а индекс данного
 элемента в некотором хранилище.
 Выделим следующие виды хранилищ данных: 
\end_layout

\begin_layout Itemize
хранилище представлений функций (
\begin_inset listings
lstparams "language=C,basicstyle={\ttfamily},tabsize=2"
inline true
status open

\begin_layout Plain Layout

const RefalFunction functions[]
\end_layout

\end_inset

);
\end_layout

\begin_layout Itemize
хранилище представлений идентификаторов (
\begin_inset listings
lstparams "language=C,basicstyle={\ttfamily},tabsize=2"
inline true
status open

\begin_layout Plain Layout

const RefalIdentifier labels[]
\end_layout

\end_inset

);
\end_layout

\begin_layout Itemize
хранилище чисел (
\begin_inset listings
lstparams "language=C,basicstyle={\ttfamily},tabsize=2"
inline true
status open

\begin_layout Plain Layout

const RefalNumber numbers[]
\end_layout

\end_inset

).
\end_layout

\begin_layout Standard
Таким образом, для команд icHugeInt, icIdent, icFunc в качестве аргумента
 передаётся положение сущности в соответствующем хранилище.
 В для остальных команд первой группы аргументом является значение сущности.
 Рассмотрим подробнее команду выделения скобки icBracket.
 В качестве её аргумента выступает одно из значений перечисления BracketType,
 описывающее какой тип скобки должен быть помещён в память и открытая ли
 или закрытая ли скобка.
 Скобки представлены следующими значениями:
\end_layout

\begin_layout Itemize
ibOpenADT --- открытая скобка АТД-терма;
\end_layout

\begin_layout Itemize
ibCloseADT --- закрытая скобка АТД-терма;
\end_layout

\begin_layout Itemize
ibOpenBracket --- открытая структурная скобка;
\end_layout

\begin_layout Itemize
ibCloseBracket --- закрытая структурная скобка;
\end_layout

\begin_layout Itemize
ibOpenCall --- открытая функциональная скобка;
\end_layout

\begin_layout Itemize
ibCloseCall --- закрытая функциональная скобка.
\end_layout

\begin_layout Standard
Во вторую группу вынесем ряд команд, осуществлявшие перенос или копирование
 переменных в результатной части предложения (icSpliceSTVar, icSpliceEVar,
 icCopySTVar, icCopyEVar).
 RASL-представление данной группы схоже с первой группой, только в качестве
 аргумента всегда используется положение сущности в хранилище сущностей
 context.
 Представление --- 
\begin_inset listings
lstparams "language=C,basicstyle={\ttfamily},tabsize=2"
inline true
status open

\begin_layout Plain Layout

{код_операции, 0, аргумент, 0}
\end_layout

\end_inset

.
 Благодаря тому, что
\begin_inset Newline linebreak
\end_inset

 для e-переменных по их индексу в context можно однозначно определить начало
 и конец сущности, представление стало более лаконичнее, в отличии от ранее
 используемого
\begin_inset Newline linebreak
\end_inset

 
\begin_inset listings
lstparams "language=C,basicstyle={\ttfamily},tabsize=2"
inline true
status open

\begin_layout Plain Layout

{код_операции, указатель_начала, указатель_конца, 0}
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
Рассмотрим команды, отвечающие за образцовую часть предложения.
 Многие команды имеют суффикс Left
\backslash
Right --- обозначающий направление сопоставления.
 
\begin_inset Newline linebreak
\end_inset

Большая часть команд соответствуют RASL-представлению
\begin_inset Newline linebreak
\end_inset

 
\begin_inset listings
lstparams "language=C,basicstyle={\ttfamily},tabsize=2"
inline true
status open

\begin_layout Plain Layout

{код_операции, 0, аргумент, номер_скобки}
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
Данному описанию соответствуют команды:
\end_layout

\begin_layout Itemize
icBracketLeft, icBracketRight --- сопоставление со скобкой;
\end_layout

\begin_layout Itemize
icsVarLeft, icsVarRight --- сопоставление s-переменной;
\end_layout

\begin_layout Itemize
ictVarLeft, ictVarRight --- сопоставление t-переменной;
\end_layout

\begin_layout Itemize
icNumLeft, icNumRight, icHugeNumLeft, icHugeNumRight --- сопоставление с
 целым беззнаковым числом;
\end_layout

\begin_layout Itemize
icIdentLeft, icIdenrRight --- сопоставление с идентификатором;
\end_layout

\begin_layout Itemize
icFuncLeft, icFuncRight --- сопоставление с сущностью, описывающую функцию
 ;
\end_layout

\begin_layout Itemize
icCharLeft, icCharRight --- сопоставление с символом;
\end_layout

\begin_layout Itemize
icSave --- присвоение значения одной e-перменной или скобки в другую;
\end_layout

\begin_layout Itemize
icEStart --- сопоставление открытых e-переменных;
\end_layout

\begin_layout Itemize
icEPrepare --- подготовка к циклу удлинения открытых e-переменных.
\end_layout

\begin_layout Standard
Команды icBracket*, icsVar*, ictVar* в качестве аргумента принимают позицию
 сопоставляемой сущности в хранилище context.
 icNum*, icChar* принимает непосредственно значение сущности (целое беззнаковое
 до 255 или символ).
 Аналогично с командами построения результата для сущностей, представляющих
 собой описание функции, идентификатор, целое безнаковое больше 255 в качестве
 аргумента передается позиция сущности в соответствующем хранилище (functions,
 labels, numbers соответственно).
\end_layout

\begin_layout Standard
Команде icSave более точно соответствует RASL-представление:
\begin_inset Newline linebreak
\end_inset

 
\begin_inset listings
lstparams "language=C,basicstyle={\ttfamily},tabsize=2"
inline true
status open

\begin_layout Plain Layout

{код_операции, 0, цель, источник}
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
Рассмотрим команды сопоставления открытых e-переменных: icEPrepare, icEStart.
 Сопоставление с открытой e-переменной генерируется в виде двух команд ---
 подготовка к удлинению (icEPrepare) и само непосредственное удлинению (icEStart
).
 Подготовка к удлинению инициализирует значение сущности открытой переменной
 пустым выражением.
 Затем кладет на стек истории удлинения указатель на следующую команду (команду
 удлинения) в виде индекса команды в потоке RASL-команд.
 При этом, следующая команда пропускается на следующем шаге выполнения потока
 команд языка сборки.
 В случае, если текущее сопоставление не удалось, то интерпретатором языка
 сборки происходит проверка стека откатов удлинения.
 Если стек пуст, значит произошла ошибка сопоставления всей образцовой части
 предложения.
 Тогда просто результатом выполнения блока команд для данного предложения
 является код ошибки 
\begin_inset listings
lstparams "language=C,basicstyle={\ttfamily},tabsize=2"
inline true
status open

\begin_layout Plain Layout

cRecognitionImpossible
\end_layout

\end_inset

.
 В противном случае, снимаем с вершины стека индекс команды для отката,
 то есть на команды удлинения, соответствующей текущей сопоставляемой открытой
 e-переменной.
 На данном шаге интерпретатор пытается удлинить её.
 Если удлинение прошло успешно, то сохраняем на стек возвратов положение
 текущей команды удлинения и проводим выполнение последующих команд.
 В противоположном исходе, повторяем процедуру проверки стека откатов.
 Аналогичный способ обработки в языке сборки сопоставления открытых переменных
 был применён в 
\begin_inset CommandInset citation
LatexCommand cite
key "key-2"

\end_inset

.
\end_layout

\begin_layout Standard
Теперь, перейдем к описанию последней группы RASL-команд --- сопоставление
 повторных переменных iceRepeatRight, iceRepeatLeft, icsRepeatRight, ictRepeatRi
ght,
\begin_inset Newline linebreak
\end_inset

 icsRepeatLeft, ictRepeatLeft.
 Им соответствует RASL-представление: 
\begin_inset Newline linebreak
\end_inset


\begin_inset listings
lstparams "language=C,basicstyle={\ttfamily},tabsize=2"
inline true
status open

\begin_layout Plain Layout

{код_операции, повторная_переменная, оригнальная_переменная, номер_скобки}
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
Данные операции производят сопоставление с повторными переменными, устанавливая
 копии значений.
\end_layout

\end_body
\end_document
