\documentclass{psiras}
%[russian,cp1251]
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage [T2A] {fontenc}
\usepackage{alltt}
\usepackage{graphics}


\usepackage{listings}

\renewcommand{\topfraction}{1}

\usepackage{fancyvrb}
\usepackage{color}

\newcommand{\ignore}[1]{{\color{green}{#1}}}
\newcommand{\convertL}{\,$[\![$\,}
\newcommand{\convertR}{\,$]\!]_{C+\!\!+}$\,}
\newcommand{\convert}[1]{{\convertL}#1{\convertR}}

\lstnewenvironment{myC++}
 {\lstset{language=C++, 
   otherkeywords={RF\_FUNC, RF\_END, RF\_CALL},
   basicstyle=\scriptsize,
   commentstyle=\emph, 
   extendedchars=true,
 }}
 {}
  
\lstdefinelanguage{refal+}
  {keywords={Class, Table, \$func, \$func?, \#use, Dos, Main,=,\{,\},;,[,],::,\&, \_, \#, \$},
   sensitive={true},
   comment=[l]{//},
   comment=[s]{/*}{*/},
   string=[b]{"},
   string=[d]{'}
  } 

\lstnewenvironment{refal}
 { \lstset{language=refal+, 
   basicstyle=\scriptsize\ttfamily,  
   commentstyle=\emph, 
   extendedchars=true,
   }
 }
 {}
 
 \lstdefinelanguage{syntax}
  {keywords={\{,\},;,[,],::,\&, \_, \#, \$, |, \%},
   sensitive={true},
   comment=[s]{/*}{*/},
   morecomment=[l]{//},
   string=[b]{"},
   string=[d]{'}
  } 

\lstnewenvironment{syntax}
 { \lstset{language=syntax, 
   basicstyle=\small\ttfamily,  
   commentstyle=\emph, 
   extendedchars=true,
   moredelim=[is][commentstyle]{@}{@}
   }
 }
 {}
 
  
\subjclass[UDK]{519.68}

\selectlanguage{english}

\title[Refal Plus]{Refal~Plus implementation: new approach}

\author[S.~Abramov]{Sergey~Mikhailovich~Abramov}
     \address{Program Systems Institut of RAS}
       \email{abram@botik.ru}
  
 \author[A.~Orlov]{Anton~Yurievich~Orlov}
   \address{Research Center for Multiprocessor Systems of PSI RAS}
      \email{orlov@mccme.ru}

 \author[L.~Parmyonova]{Lyubov'~Valer'evna~Parmyonova}
    \address{Research Center for Multiprocessor Systems of PSI RAS}
      \email{luba@blackcat.botik.ru}
      
       \author[S.~Ponomareva]{Svetlana~Mikhailovna~Ponomareva}
     \address{Program Systems Institut of RAS}
      \email{psm@kbse.botik.ru}
      
       \author[A.~Slepukhin]{Andrei~Feliksovich~Slepukhin}
   \address{Moscow State University}
      \email{pooh@msu.ru}

\begin{document}             
\begin{abstract}
The article describes Refal Plus programming lan\-gu\-age im\-ple\-men\-ta\-ti\-on based on array refal\-/expression rep\-re\-sen\-ta\-ti\-on and direct com\-pi\-la\-ti\-on into imperative languages. The desc\-rip\-tions of developed formalisms, runtime support library structure are given. Testing results of developed soft\-ware and other imple\-men\-ta\-tions of Refal Plus programming language are represented.
\end{abstract}


\selectlanguage{russian}

\title[Система программирования Рефал~Плюс]{Новый подход к реализации системы программирования Рефал~Плюс}

\keywords{Рефал, Рефал~Плюс, компиляция, библиотека поддержки периода исполнения, система программирования}

 \author[С.~Абрамов]{Сергей~Михайлович~Абрамов}
     \address{Институт программных систем РАН}
       \email{abram@botik.ru}
          \thanks{Работа выполнена при поддержке Суперкомпьютерной программы
<<СКИФ>> Союзного государства и Российского Фонда Фундаментальных Исследований, проект \No~02\--07\--90126}

 \author[А.~Орлов]{Антон~Юрьевич~Орлов}
   \address{Исследовательский центр мультипроцессорных систем ИПС РАН}
      \email{orlov@mccme.ru}

 \author[Л.~Парменова]{Любовь~Валерьевна~Парменова}
   \address{Исследовательский центр мультипроцессорных систем ИПС РАН}
      \email{luba@blackcat.botik.ru}
      
       \author[С.~Пономарева]{Светлана~Михайловна~Пономарева}
   \address{Институт программных систем РАН}
      \email{psm@kbse.botik.ru}
      
       \author[А.~Слепухин]{Андрей~Феликсович~Слепухин}
   \address{Московский Государственный Университет им. М.~В.~Ломоносова}
      \email{pooh@msu.ru}
      
\begin{abstract}

В работе описывается реализация языка программирования Рефал~Плюс на основе массивного представления объектных выражений и прямой компиляции в~императивные языки. Даны описания разработанных формализмов, структуры библиотеки поддержки периода исполнения (run\-/time support lib\-rary), приведены данные о сравнительном тестировании разработанного ПО и других реализаций языка Рефал~Плюс.
\end{abstract}

\maketitle                   

\section{Введение}
\label{sec:intro}

\sloppy
Язык программирования Рефал был разработан в нашей стране в середине шестидесятых годов прошлого столетия~\cite{bib:Tur66}.
Классическую авторcкую характеристику языка процитируем из работы В.~Ф.~Турчина~\cite{bib:Tur89}: 
\begin{quote}\small
\textbf{РЕФАЛ} (\textbf{РЕ}курсивных \textbf{Ф}ункций \textbf{АЛ}го\-рит\-ми\-чес\-кий язык) \--- это функциональный язык программирования, ориентированный на так называемые <<символьные преобразования>>: обработку символьных строк (например, алгебраические выкладки), перевод с одного языка (искусственного или естественного) на другой, решение проблем, связанных с искусственным интеллектом. Функциональные языки программирования в настоящее время пользуются вполне заслуженной популярностью. Один из старейших членов этого семейства (впервые реализован в 1968 году в России, где широко используется и поныне), РЕФАЛ соединяет в себе математическую простоту с практической ориентацией на написание больших и сложных программ.
\end{quote}

За годы своего существования и развития Рефал, среди прочего, использовался в следующих областях:
\begin{itemize}

	\item \emph{Манипуляции над программами}. На Рефале реализовано большое число различных макрогенераторов, трансляторов, интерпретаторов, систем анализа программ и их преобразования (в том числе средства метавычислений над программами).
{
%\emergencystretch=3pt

}


	\item \emph{Искусственный интеллект}.	Рефал использовался для разработок систем обработки текстов на естественном языке и  доказательства теорем.
	
	\item \emph{Компьютерная алгебра}.  Здесь речь идет и о разработанных на Рефале программах для проведения вычислений с абсолютной точностью (например, вычисления без округлений над целыми числами без ограничения на их длину, рациональными числами и квадратными корнями из них), и о многочисленных системах компьютерной алгебры.
	
	\item \emph{Веб приложения, средства написания сценариев (scripts)}.  Ярким (но не единственным) образцом одного из таких применений Рефала является система, интегрирующая Рефал, PHP и редактор SciTE~\cites{bib:Belous:RefalPHP,bib:Belous:RefalPHPScite}.

\end{itemize}

За время становления и развития языка образовалось несколько диалектов языка Рефал, а реализации языка прошли эволюционный путь от интерпретирующих и полукомпилирующих\footnote{
        Рефал\-/программы преобразуются в так называемый язык сборки, который затем исполняется интерпретатором языка сборки~\cites{bib:BzR77,bib:Rom87a}.
} реализаций до систем, основанных на компиляции.  В настоящее время наиболее популярными реализациями диалектов языка Рефал являются следующие системы:
\begin{itemize}

	\item В системах программирования языка \emph{Рефал\-/5}~\cites{bib:Tur89, bib:Belous:RefalPHP, bib:Belous:RefalPHPScite} используются классическое списковое представление~\cite{bib:BzR77} объектных выражений и полукомпилирующая схема~\cites{bib:BzR77,bib:Rom87a} реализации языка.
	
	\item В системе программирования \emph{Рефал\-/6}~\cites{bib:K03} используется модифицированное списковое представление\footnote{%
	             Отличается от классического~\cite{bib:BzR77} более эффективным (более экономным по памяти) представлением термов, имеющих вид выражений в скобках \--- так называемые <<подвешенные скобки со счетчиками ссылок>>.
} объектных выражений и полукомпилирующая схема реализации языка.

	\item Предыдущая версия реализации \emph{Рефала~Плюс} основана на представлении объектных выражений массивами. В системе использована идея двухпроходной компиляции: рефал\-/программа преобразуется в виртуальный код~\cite{bib:Rom99}, который затем отображается в исполняемый код целевого компьютера.

	\item В системе %программирования 
	\emph{Рефал\-/6/Java}~\cite{bib:KK03} используется представление объектных выражений Java\-/массивами и прямая компиляцию рефал\-/программы в язык Java.
	
\end{itemize}

Данная работа посвящена новому подходу к реализации диалектов Рефала.  При этом, целью являлось создание такой системы программирования, которая обладала бы следующими свойствами:
\begin{itemize}

	\item \emph{Использование представления объектных рефал\-/выражений в виде массивов.}  Массивное представление рефал\-/выражений обладает рядом преимуществ перед другими способами.  В том числе, оно позволяет эффективно в процессе выполнения рефал\-/программ выполнять операции вычисления длины рефал\-/выражения и построения подвыражения по длине и позиции расположения подвыражения в рефал\-/выражении.  Эффективная реализация этих двух операций позволила разработать и использовать в системе \emph{новый подход к эффективной реализации синтаксического отождествления} в языке Рефал~\cites{bib:AbO04}.
	
	\item \emph{Прямая компиляция рефал\-/программ в императивный язык} В системе реализована схема прямой компиляции рефал\-/программ в некий абстрактный императивный язык, который затем, отдельным проходом (\emph{back\-/end} модулем), может быть легко отображен в любую целевую платформу.  В настоящее время полностью реализован \emph{back\-/end} модуль для языка, отображающий результат компиляции в С++, на стадии реализации \--- компиляция в T++.
	
	\item \emph{Открытость, гибкость, продуманная модульность.} Система построена как набор отдельных модулей, с четко описанными интерфейсами между ними.  Модули доступны в исходных текстах.  Компилятор системы написан на Рефале~Плюс, 
варианты библиотек поддержки периода исполнения (run\-/time support lib\-rary, RSL) под различные платформы разрабатывается на языках высокого уровня (C++, Java, C\#, T++).  Среди прочего, такой подход должен обеспечивать \emph{высокий уровень переносимости системы}.

\begin{figure}
%\includegraphics[height=57mm,width=67mm]{gener-shem}
\includegraphics{gener-shem}
\caption{Система программирования Рефал~Плюс}
\label{fig:shema}
\end{figure}

	\item \emph{Поддержка возможных расширений.} За счет модульной структуры системы авторы старались поддержать легкость изменения ее функциональности, без необходимости модификации большей части кода и системы в~целом.  Речь идет о возможностях (см. рис.~\ref{fig:shema}):
			\begin{itemize}
				\item Добавления различных (в том числе оптимизирующих) преобразований рефал\-/программ в формате абстрактного синтаксиса (<<AS2AS>>\-/преобразователи).
				\item Добавления различных (в том числе оптимизирующих) преобразований результата компиляции в формате абстрактного императивного языка (<<Optim>>).
				\item Реализации в рамках системы поддержки разнообразных рефал\-/диалектов, как существующих (Рефал\-/2, -5. -6), так и будущих, за счет возможности добавления различных \emph{front\-/end} (<<Lexer~\&~Par\-ser>>) модулей.
				\item Реализации в рамках системы поддержки разнообразных целевых архитектур и платформ.  Речь идет о возможности реализации разных версий \emph{back\-/end} модулей и соответствующих библиотек периода исполнения (RSL) и за счет этого реализации системы как на базе привычных императивных языков (C++, Java, C\#), так и на базе языков, поддерживающих параллельное исполнение программ в мультипроцессорных системах (T++, OpenTS)~\cite{bib:AAP99}.
			\end{itemize}
			
\end{itemize}

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

\section{Архитектура системы}
\label{sec:comp-shema}	

На рис.~\ref{fig:shema} на стр.~\pageref{fig:shema} показана общая архитектура системы программирования Рефал~Плюс. В~данной схеме сплошные линии отображают реализованные или находящиеся в стадии реализации модули системы, пунктир \--- то, что предполагается реализовать в перспективе.

Предложенная многопроходная схема реализации системы обеспечивает относительно простое расширение как набора входных языков другими диалектами Рефала, так и множества выходных императивных языков. Для реализации этого подхода в процессе компиляции рефал\-/программ выделены четыре основные этапа:
\begin{itemize}

	\item 
	Выполняемое блоком Lexer~\&~Parcer преобразование рефал\-/программы в~текст на промежуточном рефал\-/ориентированном абстрактном языке, называемом \emph{Абстрактный синтаксис} (AS\-/code).  Абстрактный синтаксис включает элементы, адекватно отображающие особенности всех диалектов Рефала, и подробно рассмотрен в разделе~\ref{sec:as}. 
	
	\item 
	Преобразование AS\-/кода в~программу на \emph{Абстрактном императивном 
	языке} (AIL\-/code) с помощью модуля Compiler. Описание синтаксиса абстрактного  императивного языка дано в разделе~\ref{sec:asail}. 
	
	\item
  Генерация модулем Сonverter выходного текста на императивном языке. Правила конвертирования, использованные для С++, сформулированы в разделе \ref{sec:convert}. 
  
  \item
  Генерация исполняемого модуля на основе %соответствующей 
  библиотеки поддержки периода исполнения, структура RSL для C++ описана в разделе~\ref{sec:RSL}.
	
\end{itemize}

 Рассмотрим более подробно основные этапы компиляции.

\section{Этап компиляции <<Рефал~Плюс \--- Абстрактный синтаксис>>}
\label{sec:as}	

При разработке \emph{Абстрактного синтаксиса} (далее AS) главной была задача обеспечить возможность отображения в его конструкциях всех особенностей существующих диалектов Рефала, нивелируя различия, связанные с несовпадением семантики одних и тех же символов, которое наблюдается при сравнении, например, Рефала~Плюс и Рефала\-/6. В результате было разработано  следующее <<рефальское>> описание AS\-/языка: 
\medskip
    
\begin{syntax}
t.Syntax          ::= t.Module | t.Interface
t.Module          ::= (MODULE t.ModName e.ModBody)
t.Interface       ::= (INTERFACE t.InterfaceName
                  e.InterfaceBody)
t.ModName         ::= t.Name
t.InterfaceName   ::= t.Name
e.ModBody         ::= t.Item | e.ModuleBody t.Item 
t.Item            ::= t.Function | t.Object | t.Const
                  | t.Initializer | t.PragmaTrace     
t.Function        ::= (s.IntLinkage s.FunctionTag 
                  t.Pragma t.FunctionName t.InputParam 
                  t.OutputParam e.Sentence) 
                  | (s.ExtLinkage s.FunctionTag 
                  t.Pragma t.FunctionName t.InputParam 
                  t.OutputParam)
s.Linkage         ::= s.IntLinkage | s.ExtLinkage
s.IntLinkage      ::= EXPORT | LOCAL
s.ExtLinkage      ::= IMPORT
s.FunctionTag     ::= FUNC | FUNC?
t.FunctionName    ::= t.Name
t.InputParam      ::= (e.ListParam)
t.OutputParam     ::= (e.ListParam)
e.ListParam       ::= /*Empty*/ | e.ListParam t.Param
t.Param           ::= (SVAR) | (EVAR) | (TVAR) 
                  | (VVAR) | (PAREN e.ListParam)
e.Sentence        ::= /*Empty*/
                  | t.Statement e.Sentence
t.Statement       ::= t.Action | t.Operator | t.Branch 
                  | t.ComplexOperator | t.Pragma 
                  | t.Format
t.Format          ::= (FORMAT t.Pragma e.HardExpr)
e.HardExpr        ::= e.HardTerms
                  | e.HardTerms t.EVar e.HardTerms 
                  | e.HardTerms t.VVar e.HardTerms
e.HardTerms       ::= /*Empty*/ 
                  | t.HardTerm e.HardTerms
t.HardTerm        ::= t.Symbol | (PAREN e.HardExpr) 
                  | t.SVar | t.TVar
t.Operator        ::= (CUT t.Pragma) | (ERROR t.Pragma) 
                  | (STAKE t.Pragma) | NOFAIL  
                  | (FAIL t.Pragma) | (CUTALL t.Pragma)
t.ComplexOperator ::= (NOT t.Branch) 
                  | (ITER t.IterBody t.IterVars 
                  t.IterCond)
                  | (TRY t.TrySentence 
                  e.Nofail t.CatchSentence)
t.IterBody        ::= t.branch
t.IterVars        ::= t.Format
t.IterCond        ::= t.branch
t.TrySentence     ::= t.branch
t.CatchSentence   ::= t.block | t.branch
t.Action          ::= t.Pattern | t.Result | t.Format 
                  | t.Block
t.Block           ::= (BLOCK t.Pragma e.Branches)
                  | (BLOCK? t.Pragma e.Branches)
e.Branches        ::= /*Empty*/ | t.Branch e.Branches
t.Branch          ::= (BRANCH t.Pragma e.Sentence) 
t.Pattern         ::= (LEFT t.Pragma e.PatternExpr) 
                  | (RIGHT t.Pragma e.PatternExpr)
e.PatternExpr     ::= /*Empty*/ 
                  | t.PatternTerm  e.PatternExpr
t.PatternTerm     ::= t.Symbol | (PAREN e.PatternExpr) 
                  | t.Variable
t.Variable        ::= t.EVar | t.VVar | t.TVar | t.Svar
t.EVar            ::= (EVAR t.Pragma t.Name)
t.VVar            ::= (VVAR t.Pragma t.Name)
t.TVar            ::= (TVAR t.Pragma t.Name)
t.SVar            ::= (SVAR t.Pragma t.Name)
t.Name            ::= (e.QualifiedName)
e.QualifiedName   ::= s.Word | e.QualifiedName  s.Word
t.Result          ::= (RESULT t.Pragma e.ResultExpr) 
e.ResultExpr      ::= /*Empty*/ 
                  | t.ResultTerm e.ResultExpr
t.ResultTerm      ::= t.Symbol | t.Variable | t.block 
                  | (PAREN e.ResultExpr)
                  | (CALL t.Pragma t.FunctionName 
                  e.ResultExpr)
t.Object          ::= (s.Linkage s.ObjectType t.Pragma 
                  t.ObjectName)
s.ObjectType      ::= TABLE | BOX | STRING | VECTOR 
                  | CHANNEL
t.ObjectName      ::= t.Name
t.Initializer     ::= (EXEC e.ResultExpr)
t.Pragma          ::= 
                  (PRAGMA t.PragmaFile t.PragmaLine)
t.PragmaFile      ::= (FILE e.FileName)
e.FileName        ::= s.Char | s.Char e.FileName
t.PragmaLine      ::= (LINE s.Line s.Column)
s.Line            ::= s.Number
s.Column          ::= s.Number
t.PragmaTrace     ::= (TRACE e.TraceNames) 
e.TraceNames      ::= /*Empty*/ 
                  | t.TraceName e.TraceNames
t.TraceName       ::= t.Name
t.Const           ::= (s.IntLinkage CONST t.Pragma 
                  t.ConstName e.ConstExpr)
                  | (s.ExtLinkage CONST t.Pragma 
                  t.ConstName)
t.ConstName       ::= t.Name
e.ConstExpr       ::= /*Empty*/ 
                  | t.ConstTerm e.ConstExpr
t.ConstTerm       ::= t.Symbol | (PAREN e.ConstExpr) 
t.Symbol          ::= s.StaticSymbol | (REF t.Name)
s.StaticSymbol    ::= s.Char | s.Word | s.Number
s.Char            ::= символ-литера (в смысле Рефал+)
s.Word            ::= символ-слово (в смысле Рефал+)
s.Number          ::= символ-число (в смысле Рефал+)
\end{syntax}

\section {Этап компиляции <<Абстрактный синтаксис \--- Абстрактный императивный язык>>} 
\label{sec:asail}

Как говорилось выше, одна из важных особенностей данной реализации \---использование на этапе компиляции в модуле Compiler преимуществ массивного представления данных для эффективной реализации синтаксического отождествления~\cites{bib:AbO04}. При этом в коде на императивном языке наиболее часто используются операции вычисления длины рефал\-/выражения и построения подвыражения по длине и позиции расположения подвыражения в рефал\-/выражении, т.е. действия, связанные с двумя типами данных \--- целыми (обозначаемые int) и классом Expr, реализующим рефал\-/выражения. Как следствие этого был сформирован набор конструкций \emph{Абстрактного императивного языка} (AIL), который включает наряду с общими элементами императивных языков (вызов функций с параметрами, цикл, условный оператор, операторы перехода, арифметические операции и др.) набор методов класса Expr, обращение к которым  обусловлено особенностями алгоритма компиляции.

Ниже приводится описание синтаксиса \emph{Абстрактного императивного языка}, где в качестве комментариев даны пояснения некоторых конструкций AIL.
 
\begin{syntax}
e.ASAIL      ::= /*empty*/ | t.Func e.ASAIL
t.Func       ::= (FUNC t.QualifName (e.param)
                  (e.param) e.body)
// Определение  функции: t.QualifName - имя функции,
// e.param - входные и выходные параметры, e.body -
// тело функции.
t.QualifName ::= (e.name)
e.name       ::= /*empty*/ | s.numb e.name
             | s.word e.name
e.param      ::= /*empty*/ | t.var-ref e.param
e.body       ::= /*empty*/ | t.statement e.body
t.statement  ::= t.call | t.tailcall | t.assign 
             | t.if | t.for | t.continue | t.break
             |t.lsplit | t.rsplit | t.catch
             | t.try | t.drop | t.expr-obj | t.deref
             | t.subexpr | t.constexpr | t.blok-label
             | t.decl | t.decl-int | t.decl-func 
             | t.decl-const | t.decl-obj | t.obj
             | t.error 
             | RETURN
// Оператор успешного выхода из функции.
             | FATAL
// Оператор аварии, вырабатывающий исключение
// вида Unexpected fail.
             | RETFAIL
// Оператор неуспешного выхода из функции (fail).
t.call       ::= (CALL t.QualifName (e.args) (e.args))
// Вызов функции, где t.QualifName - имя функции,
// e.args - входные и выходные фактические
// параметры, передаваемые по значению.
e.args       :: = /*empty*/ | t.arg e.args
t.arg        ::= t.var | (e.expr)
t.var        ::=  t.var-ref | t.var-int
e.expr       ::=  e.expr-ref | e.expr-int
t.tailcall   ::= (TAILCALL t.QualifName (e.arg)(e.arg))
// <<Хвостовой>> вызов функции,
// где t.QualifName - имя функции,
// e.arg - входные и выходные фактические параметры,
// передаваемые по значению.
t.assign     ::= (ASSIGN t.var e.expr)
// Оператор присваивания, где t.var - имя переменной,
// e.expr - присваиваемое значение.
t.decl       ::= (DECL s.type t.var)
// Объявление переменной t.var типа s.type.
// Предполагается поддержка двух базовых типов:
// int (целые числа) и Expr (Рефал-выражения).
s.type       ::= "Expr" | "int"
t.decl-int   ::= (INT t.var e.expr-int)
// Объявление переменной t.var типа int
// и инициализация ее значением e.expr-int.
t.if         ::= (IF (e.cond) e.body)
// Условный оператор, где e.cond - условие,
// e.body - последовательность действий, выполняемых
// в случае его истинности.
e.cond       ::= /*empty*/ | t.cond-term e.cond
// Операнды t.cond-term, входящие в условие e.cond,
// соединяются AND.
t.cond-term  ::= t.call
             | (SYMBOL? e.expr-ref (e.pos))
// Проверка структуры элемента, занимающего в
// выражении e.expr-ref позицию e.pos;
// условие истинно, если этот элемент - символ.
             | (EQ e.expr-ref1 (e.expr-ref2) (e.pos))
// Проверка равенства выпажения e.expr-ref1
// подвыражению выражения e.expr-ref2, начинающемуся
// с позиции e.pos.
             | (TERM-EQ e.expr-ref1 (e.expr-ref2)
             (e.pos))
// Проверка равенства первого терма выражения
// e.expr-ref1 терму выражения e.expr-ref2,
// занимающему позицию e.pos.
             | (NOT e.cond)
// Логическое отрицание условия e.cond.
             | (CHECK-ITER e.expr-ref)
// Проверка успешности очередного шага итерации.
             | (INFIX s.op-bool e.args-log)
             | (INFIX s.op-eq e.args-int)
e.args-log   ::= /*empty*/ | (e.expr-log) e.args-log
e.pos        ::=e.expr-int
e.len        ::= e.expr-int
e.expr-log   ::= /*empty*/
             | t.cond-term e.expr-log
             | t.int-term e.expr-log
s.op-bool    ::= "&&" | "||"
s.op-eq      ::= "<" | ">" | "<=" | ">=" | "==" | "!="
t.for        ::= (FOR (e.cont-lab) (e.break-lab)
             (e.cond) (e.step) e.body)
// Цикл  FOR: e.cont-lab - empty или метка цикла
// (для использования в операторе CONTINUE),
// e.break-lab - empty или метка для оператора BREAK,
// e.cond - условие выполнения цикла, 
// e.step  - оператор итерации, e.body - тело цикла.
e.cont-lab      ::= t.label | /*empty*/
e.break-lab  ::= t.label | /*empty*/
t.label      ::= t.QualifName
e.step       ::= (INC-ITER e.expr-ref)
             | (DEC-ITER e.expr-ref)
// Шаг цикла FOR - инкремент/декремент итератора
// переменной e.expr-ref, созданного ранее
// соответствующей функцией lsplit() или rsplit().
t.continue   ::= (CONTINUE t.label)
// Оператор перехода к следующей итерации цикла FOR,
// t.label - метка цикла.
t.break      ::= (BREAK t.label)
// Оператор выхода из цикла FOR,
// t.label - метка блока, содержащего цикл.
t.lsplit     ::= (LSPLIT e.expr-ref (e.min) t.l t.r)
t.rsplit     ::= (RSPLIT e.expr-ref (e.min) t.l t.r)
// Функции отщепления фрагментов Рефал-выражения
// (соответственно, слева и справа);
// e.expr-ref - исходное выражение;
// e.min - минимальная длина отщепляемого участка;
// t.l и t.r, соответственно, левая и правая части,
// на которые разделяется выражение.
t.l          ::= t.var-ref
t.r          ::= t.var-ref
e.min        ::= e.expr-int
t.try        ::= (TRY e.body)
// try-блок, где e.body - тело блока. Исключения из 
// него перехватываются в соответствующем catch-блоке.
t.error      ::= (ERROR e.expr-ref)
// Оператор генерации исключения e.expr-ref.
t.catch      ::= (CATCH-ERROR e.body)
// Блок перехвата исключений, вырабатываемых
// try-блоком. Для любого try-блока существует только
// один catch-блок, условие которого всегда  истинно
@// (вида Expr const@&@ err), анализ  и обработка@
// исключения проводится в теле блока e.body.
t.drop       ::= (DROP t.var-ref)
// Блок, сигнализирующий о возможности освобождения
// памяти, занимаемой объектом  t.var-ref,
// т.к. она далее не используется.
t.expr-obj   ::= (EXPR t.var-ref e.expr-ref)
// Конструктор объекта t.var-ref класса Expr
// со значением e.expr-ref.
t.deref      ::= (DEREF t.var-expr e.expr-ref (e.pos))
// Конструктор объекта t.var-ref класса Expr,
// значение которого - содержимое скобочного терма,
// занимающего в выражении e.expr-ref позицию e.pos.
t.subexpr    ::= (SUBEXPR t.var-ref e.expr-ref
             (e.pos) (e.len))
// Конструктор объекта t.var-ref класса Expr,
// который выделяет в выражении e.expr-ref,
// начиная с элемента e.pos, подвыражение длиной e.len.
e.pos        ::= e.expr-int
e.len        ::= e.expr-int
t.constexpr  ::= (CONSTEXPR s.linkage t.const-name
             (e.comment) e.const-expr)
// Конструктор константного объекта класса Expr.
s.linkage    ::= EXPORT | LOCAL
e.comment    ::= выражение (в смысле Рефал Плюс)
// e.comment - выражение в том виде, в котором оно
// встретилось в Рефал-программе.
t.const-name ::= t.QualifName | (STATIC t.QualifName)
e.const-expr ::= e.comp-expr | e.const-subexpr
e.comp-expr  ::= [empty] | t.const-term e.const-expr
// Термы, входящие в e.comp-expr, конкатенируются.
t.const-term ::= s.symbol | (PAREN e.const-expr)
             | (REF t.QualifName)
             | (STATIC t.QualifName)
e.const-subexpr ::= (SUBEXPR t.const-name s.const-pos
             s.const-len)
e.const-pos  ::= s.numb
s.const-len  ::= s.numb
t.decl-obj   ::= 
             (DECL-OBJ s.linkage s.tag t.QualifName)
// Объявление объектов, s.tag - тип объекта.
s.tag        ::= "Box" | "Table" | "Vector"
             | "Channel" | "String"
t.obj        ::= (OBJ s.linkage s.tag t.name)
// Конструктор произвольного объекта.
t.blok-label ::= (LABEL (e.maybe-empty) e.body)
// Блок: e.body - тело блока,
// e.maybe-empty - метка или empty.
t.decl-func  ::= (DECL-FUNC  t.QualifName)
// Объявление функции с именем t.QualifName.
e.expr-ref   ::= /*empty*/ | t.term-ref e.expr-ref
// Термы в Рефал-выражении объединяются конкатенацией.
t.term-ref   :: = s.symbol | t.var-ref
             | (PAREN e.expr-ref)
// Оператор <<навешивания скобок>> для выражения
// e.expr-ref; результат типа Expr.
             | (DEREF e.expr-ref (e.pos))
// Извлечение содержимого скобочного терма,
// находящегося в e.expr-ref в позиции e.pos,
// результат типа Expr.
             | (SUBEXPR e.expr-ref (e.pos) (e.len))
// Выделение в выражении e.expr-ref подвыражения,
// начинающегося в e.pos и имеющего длину e.len;
// результат типа Expr.
e.expr-int   ::= /*empty*/ | t.int-term e.expr-int
// Термы в целочисленном выражении e.expr-int
// соединяются + (сложение); результат типа int.
t.int-term   ::= s.numb | t.var-int
             | (LENGTH e.expr-ref)
// Вычисление длины выражения e.expr-ref;
// результат типа int.
             | (MIN e.args-int) | (MAX e.args-int)
// Вычисление минимума (максимума) для аргументов типа
// int; результат типа int.
             | (INFIX s.op-int e.args-int)
// Арифметические операции (левоассоциативные) для
// аргументов типа int.
e.args-int   ::= /*empty*/ | (e.expr-int) e.args-int
s.op-int     ::= "+" | "-" | "*" | "/" | "%"
t.var-ref    ::= (STATIC (s.numb) )|(VAR t.QualifName)
             | (TVAR t.QualifName) |(VVAR t.QualifName)
             | (EVAR t.QualifName) |(SVAR t.QualifName)
t.var-int    ::= (VAR t.QualifName)
s.numb       ::= символ-число (в смысле Рефал Плюс)
s.word       ::= символ-слово (в смысле Рефал Плюс)
\end{syntax}


\section {Этап компиляции <<Абстрактный императивный язык \--- Си++>>} 
\label{sec:convert}

\subsection {Правила конвертирования} 

Основной тип объекта, над которым выполняются действия \---это рефал\-/выражение,
для его описания в С++\-/реализации определен класс Expr, методы работы которого позволяют эффективно выполнять действия, на которые ориентирован алгоритм, рассмотренный в~\cites{bib:AbO04}: оценка длины выражения, выбор терма и подвыражения, снятие скобок с выражения и т.д.

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

Рассмотрим использованные в модуле C++\-/Converter правила соответствия конструкций \emph{Абстрактного императивного языка} выходному С++\-/коду. Этот набор правил отражает схему конвертирования, которая не требует существенных изменений при необходимости компиляции в  другие объектно\-/ориентированные языки. 

Будем преобразование AIL\-/выражения \textbf{X} обозначать конструкцией \convert{\textbf{X}} и отделять от результата знаком $\Longrightarrow$.     

\subsubsection{Генерация операторов и блоков} 

\newenvironment{CompRule}{\begin{slshape}\begin{tabbing}****\=******\=******\=******\=******\=******\=******\=\kill}{\end{tabbing}\end{slshape}}

\begin{itemize}

\item
Определение  функции
\begin{CompRule}
\>\convert{(FUNC t.name (e.arg) (e.res) e.body)} $\Longrightarrow$\\ 
\>         \>RF\_FUNC \>   \>(  \>\convert{t.name},\\
\>         \>         \>   \>   \>(RF\_ARG \convert{e.arg}),\\
\>         \>         \>   \>   \>(RF\_RES \convert{e.res})\\
\>         \>         \>   \>) \\
\>         \>         \>   \>\convert{e.body} \\
\>         \>RF\_END
\end{CompRule}

	\item
Вызовы функции
\begin{CompRule}
\>\convert{(CALL t.name (e.arg${}_{in}$) (e.arg${}_{out}$))} $\Longrightarrow$ \\
\> \> RF\_CALL (\convert{t.name}, \\
\> \> \> (\convert{e.arg${}_{in}$}), (\convert{e.arg${}_{out}$}))
\end{CompRule}
\begin{CompRule}
\>\convert{(TAILCALL t.name (e.arg${}_{in}$) (e.arg${}_{out}$))} $\Longrightarrow$ \\
\> \> RF\_TAILCALL (\convert{t.name}, \\
\> \> \> (\convert{e.arg${}_{in}$}), (\convert{e.arg${}_{out}$}))
\end{CompRule}

	\item
Оператор присваивания 
\begin{CompRule}
\> \convert{(ASSIGN t.var e.expr)} $\Longrightarrow$ \\
\> \> \convert{t.var} = \convert{e.expr};
\end{CompRule}

	\item
Объявление переменной
\begin{CompRule}
\> \convert{(DECL s.type t.var)}  $\Longrightarrow$  \\
\> \> \convert{s.type}~~\convert{t.var};
\end{CompRule}

	\item
Условный оператор 
\begin{CompRule}
\> \convert{(IF (e.cond) e.body)} $\Longrightarrow$  \\
\> \> if (\convert{e.cond}) \\
\> \> \{  \\
\> \> \> \convert{e.body} \\
\> \> \}
\end{CompRule}
	
	\item
Генерация помеченного блока 
\begin{CompRule}
\> \convert{(LABEL (e.label) e.body )} $\Longrightarrow$\\
\> \> \{ \\
\> \> \> \convert{e.body} \\
\> \> \} \\ 
\> \> \convert {e.label}: \{~\}
\end{CompRule}

	\item
Цикл  FOR
\begin{CompRule}
\> \convertL(FOR (e.c-lab) (e.b-lab) (e.cond)\\
\> \> (INC-ITER t.var) e.body)\convertR $\Longrightarrow$ \\
\> \> \> for ( ; \convert{e.cond}; iter(\convert{t.var})++)\\
\> \> \> \{  \\
\> \> \> \> \convert{e.body} \\
\> \> \> \> \convert{e.c-lab} : \{~\} \\
\> \> \> \}\\
\> \> \> \convert{ e.b-lab}: \{~\}
\end{CompRule}

	\item
Оператор перехода к следующей итерации цикла for
\begin{CompRule}
\> \convert{(CONTINUE t.label)} $\Longrightarrow$  \\
\> \> goto \convert{t.label} ;
\end{CompRule}

	\item
Оператор выхода из цикла
\begin{CompRule}
\> \convert{(BREAK t.label)} $\Longrightarrow$  \\
\> \> goto \convert{t.label} ;
\end{CompRule}
где t.label \--- метка блока, содержащего цикл.
  
	\item
Функция отщепления слева фрагмента рефал\-/выражения
\begin{CompRule}
\>\convert{(LSPLIT e.expr (e.min) t.l t.r)} $\Longrightarrow$ \\
\>  \> lsplit( \>\convert{e.expr}, \convert{e.min}, \convert{t.l},\\
\>  \>         \>\convert{t.r}~); 
\end{CompRule}

	\item
Функция отщепления справа фрагмента рефал\-/выражения
\begin{CompRule}
\> \convert{(RSPLIT e.expr (e.min) t.l t.r)} $\Longrightarrow$\\
\> \> rsplit( \>\convert{e.expr},\convert{e.min}, \convert{t.l},\\
\> \>         \>\convert{t.r}); 
\end{CompRule}
 
	\item
Оператор генерации исключения
\begin{CompRule}
\> \convert{(ERROR e.expr)} $\Longrightarrow$ \\
\> \> error  (\convert{e.expr});
\end{CompRule}

	\item
try\-/блок
\begin{CompRule}
\> \convert{(TRY e.body )} $\Longrightarrow$ \\
\> \> trap \\
\> \> \{ \\
\> \> \> \convert{e.body} \\
\> \> \}
\end{CompRule}

	\item
Блок перехвата исключений
\begin{CompRule}
\> \convert{(CATCH-ERROR e.body)} $\Longrightarrow$ \\
\> \> with \\
\> \> \{  \\
\> \> \> \convert{e.body} \\
\> \> \}
\end{CompRule}

	\item
Вызов метода освобождения памяти, занимаемой объектом t.var
\begin{CompRule}
\> \convert{(DROP t.var)}  $\Longrightarrow$ \\
\> \> \convert{t.var}.drop\,();
\end{CompRule}

	\item
Оператор успешного выхода из функции
\begin{CompRule}
\> \convert{RETURN} $\Longrightarrow$  \\
\> \> return true;
\end{CompRule}

	\item
Оператор неуспешного выхода из функции
\begin{CompRule}
\> \convert{RETFAIL} $\Longrightarrow$ \\
\> \> retfail;
\end{CompRule}

	\item
Оператор неуспешного выхода из функции
\begin{CompRule}
\> \convert{FATAL} $\Longrightarrow$ \\
\> \> error (''Unexpected fail'');
\end{CompRule}
 
	\item
Конструктор объекта типа Int
\begin{CompRule}
\> \convert{(INT  t.var e.expr )} $\Longrightarrow$ \\
\> \> uintptr\_t \convert{t.var}\ = \convert{e.expr};
\end{CompRule}

	\item
Конструктор объекта класса Expr
\begin{CompRule}
\> \convert{(EXPR  t.var e.expr )} $\Longrightarrow$ \\
\> \> Expr \convert{t.var}\,(\convert{e.expr});
\end{CompRule}
  
	\item
Конструктор объекта класса Expr, значение которого  \---содержимое  скобочного терма, занимающего в e.expr позицию e.pos
\begin{CompRule}
\> \convert{(DEREF t.var e.expr  (e.pos))} $\Longrightarrow$ \\
\> \> Expr \convert{t.var}\,(\convert{e.expr}, \convert{e.pos});
\end{CompRule}
 
	\item
Конструктор объекта класса Expr, который является 
подвыражением выражения e.expr, 
начиная с элемента e.pos, длиной e.len
\begin{CompRule}
\> \convert{(SUBEXPR t.v e.exp (e.pos) (e.len))} $\Longrightarrow$ \\
\> \> Expr \convert{t.v}\,( \convert{e.exp}, \\
\> \>                   \> \> \> \convert{e.pos}, \convert{e.len});
\end{CompRule}

	\item  
Конструктор константного объекта класса Expr (термы, входящие в e.expr, объединены операцией конкатенации)
\begin{CompRule}
\> \convert{(CONSTEXPR s.link t.name (e.comment)\\
\> \> e.expr )} $\Longrightarrow$ \\
\> \> \> \convert{s.link} const Expr \convert{t.name} =\\
\> \> \>   \> \convert{e.expr};
\end{CompRule}

	\item
Объявление функции
\begin{CompRule}
\> \convert{(DECL-FUNC t.name)} $\Longrightarrow$ \\
\> \> RF\_DECL (\convert{t.name});
\end{CompRule}
  
\item
Объявление объекта типа Box, String, Vector, Table, Channel
\begin{CompRule}
\> \convert{(DECL-OBJ t.name)} $\Longrightarrow$  \\
\> \> extern const Expr \convert{t.name};
\end{CompRule}

\item
Конструктор объекта типа Box, String, Vector, Table, Channel
\begin{CompRule}
\> \convert{(OBJ s.linkage s.tag t.name)} $\Longrightarrow$ \\
\> \> \convert{s.linkage} const Expr \convert{t.name} = \\
\>  \> \>  new rftype::\convert{s.tag}();
\end{CompRule}

\end{itemize}

\subsubsection {Генерация логических функций, результат которых 
 \---true или false }

\begin{itemize}

	\item 
Условие истинно, если элемент, занимающий в выражении e.expr позицию e.pos, является символом (в смысле Рефала Плюс)
\begin{CompRule}
\>  \convert{(SYMBOL? e.expr (e.pos))} $\Longrightarrow$  \\
\> \> \convert{e.expr}.symbol\_at(\convert{e.pos})
\end{CompRule}

	\item
Условие истинно, если выражение e.1 равно подвыражению выражения e.2, начинающегося с позиции e.pos
\begin{CompRule}
\> \convert{(EQ e.1 (e.2) (e.pos))} $\Longrightarrow$ \\
\> \> \convert{e.1}.eq (\convert{e.expr2}, \convert{e.pos})
\end{CompRule}

 	\item 
Условие истинно, если первый терм выражения e.1 равен терму выражения e.2, который занимает позицию e.pos
\begin{CompRule}
\> \convert{(TERM-EQ e.1 (e.2) (e.pos))} $\Longrightarrow$  \\
\> \> \convert{e.1}.term\_eq (\convert{e.2}, \convert{e.pos})\end{CompRule}
 
	\item
Логическое отрицание
\begin{CompRule}
\> \convert{(NOT e.cond)} $\Longrightarrow$ \\
\> \> ! \convert{e.cond}
\end{CompRule}

	\item
Логическая операция (левоассоциативная)
\begin{CompRule}
\> \convert{(INFIX  s.op (t.log${}_1$ \ldots\ t.log${}_n$))} $\Longrightarrow$  \\
\> \> (\convert{t.log${}_1$}~s.op~\ldots~s.op~\convert{t.log${}_n$})
\end{CompRule}
 
\end{itemize}


\subsubsection{Генерация методов работы с объектами класса Expr, их результат \---объект класса Expr}
   
\begin{itemize}
	
	\item    
Операция <<навешивания скобок>>
\begin{CompRule}
\> \convert{(PAREN e.expr)} $\Longrightarrow$ \\
\> \> \convert{e.expr} ()
\end{CompRule}

	\item
Извлечение содержимого скобочного терма, занимающего в выражении e.expr позицию e.pos
\begin{CompRule}
\> \convert{(DEREF e.expr (e.pos)) } $\Longrightarrow$  \\
\> \> Expr (\convert{e.expr}, \convert{e.pos})
\end{CompRule}

	\item
Выделение в выражении e.expr подвыражения, начинающегося  в e.pos и  имеющего длину e.len
\begin{CompRule}
\> \convert{(SUBEXPR e.expr (e.pos)(e.len))} $\Longrightarrow$  \\
\> \> Expr (\convert{e.expr}, \convert{e.pos}, \convert{e.len})
\end{CompRule}

\end{itemize}

\subsubsection {Генерация целочисленных операций}
   
\begin{itemize}

	\item 
Вычисление длины выражения
\begin{CompRule}
\> \convert{(LENGTH e.expr)} $\Longrightarrow$  \\
\> \> (int) \convert{e.expr}.get\_len()
\end{CompRule}

	\item
Вычисление минимума целых аргументов
\begin{CompRule}
\> \convert{(MIN e.args)} $\Longrightarrow$ \\
\> \> pxx\_min (\convert{e.args})
\end{CompRule}

	\item
Вычисление максимума целых аргументов
\begin{CompRule}
\> \convert{(MAX e.args)} $\Longrightarrow$  \\
\> \> pxx\_max (\convert{e.args})
\end{CompRule}
 
 	\item
Арифметическая операция (левоассоциативная)
\begin{CompRule}
\> \convert{(INFIX  s.op (t.log${}_1$ \ldots\ t.log${}_n$))} $\Longrightarrow$  \\
\> \> (\convert{t.log${}_1$}~s.op~\ldots~s.op~\convert{t.log${}_n$})
\end{CompRule}

\end{itemize}


\subsection{Пример компиляции <<Рефал Плюс\---С++>>}

В качестве иллюстрации к вышесказанному, рассмотрим результаты конвертирования Рефал~Плюс\-/программы в С++\-/код. 

\smallskip
\textit{Входной текст на языке Рефал~Плюс: } 

\begin{refal}

$use StdIO;  
Main = <PrintLN 'Hello!'>; 

\end{refal}

\textit{Выходной С++\-/текст: }

\smallskip

\begin{myC++}
#include <rf_core.hh> 
#include <refal/StdIO.hh> 
namespace refal 
{ 
using namespace rfrt; 
namespace hello 
{
 static const Expr _c_0 = Char::create_expr('Hello!'); 
 RF_FUNC (Main, (), (RF_RES _v_res1)) 
   RF_CALL (StdIO::PrintLN, (_c_0), ()); 
   _v_res1 = empty; 
 RF_END 
} 
rfrt::Entry rf_entry (hello::Main); 
} 
\end{myC++}

\section{С++\-/библиотека поддержки периода исполнения (RSL)}
\label{sec:RSL}

\subsection{Архитектура run\-/time support library}


На рис.~\ref{fig:RSL-shema} изображена схема С++\-/библиотеки поддержки периода исполнения. 

\begin{figure}[loc=b]
\begin{center}
\includegraphics{RSL}
\end{center}
\caption{Структура RSL}
\label{fig:RSL-shema}
\end{figure}

Библиотека разделена на три каталога:

\begin{itemize}

\item
Директория \texttt{library} включает набор поддиректорий, содержащих модули реализации библиотечных функций стандарта языка Рефал~Плюс. Основная задача этих функций \---организация на достаточно общем уровне набора действий по переходу от <<рефальских>> вызовов, сгенерированных конвертером, к низкоуровневым функциям работы с С++\-/объектами. Имена файлов соответствуют названиям библиотечных рефал\-/функций. Поддиректория include содержит каталог \texttt{refal}, где находятся заголовочные файлы для организации вызова функций.  

\item
Каталог \texttt{libp++} содержит модули описания абстрактных классов наиболее общих механизмов С++\-/реализации, обеспечивающих распределение памяти, буферизацию, работу с некоторыми видами объектов (строками, векторами), обработку ошибок. Имена файлов этой директории имеют префикс \texttt{pxx\_}.
{
%\emergencystretch=3pt

}


\item
В директорию \texttt{runtime} включены файлы с описаниями классов С++\-/объектов, таких как \texttt{Expr}, а также файлы реализации <<низкоуровневых>> функций поддержки для стандартных библиотечных функций из каталога \texttt{library}. Здесь имена файлов отличаются префиксом \texttt{rf\_}.  

\end{itemize} 
 

\subsection{Описание класса \texttt{Expr}}
\label{ssec:Expr}

Основной класс для представления рефал\-/выражений \---класс \texttt{Expr}. Рассмотрим его структуру и интерфейс, который используется в итоговом C++\-/коде: 

\begin{myC++}

class Expr
{
private:

  // указатель на первый терм 
  Term* first;

  // указатель на следующий за последним термом
  Term* last;

  // указатель на область памяти, в которой находятся
  // термы выражения
  MemoryChunk* mem_chunk;

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

public:
  // конструктор пустого выражения
  inline Expr () ;

  // конструктор, создающий выражение из содержимого скобок,
  // находящихся в выражении _expr в позиции _index
  inline Expr (Expr const& _expr, uintptr_t _index) ;

  // конструктор подвыражения
  inline Expr 
    (Expr const& _expr, uintptr_t _index, uintptr_t _length) ;

  // конструктор копии
  inline Expr (Expr const& _expr) ;

  // конструктор, создающий выражение из одного терма -
  // ссылки на передаваемый объект
  inline Expr (Object* _obj) ;

  // деструктор
  inline ~Expr () ;

  // оператор присваивания
  inline Expr& operator = (Expr const& _expr) ;

  // конкатенация выражений
  INLINE Expr operator + (Expr const& _expr) const ;

  // оператор взятия выражения в скобки
  inline Expr operator () () const ;

  // оператор, снимающий скобки с выражения, состоящего из одного
  // скобочного терма
  inline Expr operator * () const ;

  // проверка, является ли терм по указанному индексу символом 
  inline bool symbol_at (uintptr_t _index) const ;

  // проверка, является ли выражение плоским
  inline bool is_flat () const ;

  // проверка, является ли выражение пустым
  inline bool is_empty () const ;

  // вычисление длины выражения
  inline uintptr_t get_len () const ;

  // сравнение с подвыражением, начинающимся в позиции _index
  // выражения _expr;
  inline bool eq (Expr const& _expr, uintptr_t _index) ;

  // сравнение первого терма с каким-либо термом другого выражения
  inline bool term_eq 
    (Expr const& _expr, uintptr_t _index) const ;

  // проверка равенства выражений
  inline bool operator == (Expr& _expr) ;

  // проверка неравенства выражений
  inline bool operator != (Expr& _expr) ;

  // удаление выражения; используется в деструкторе и операторе
  // присваивания
  inline void drop () ;
};

\end{myC++}

\section{Результаты сравнительного тестирования}
\label{sec:tests}

В качестве тестов эффективности работы разработанного программного обеспечения использовались четыре рефал\-/программы решения следующей задачи: заданa конечная последовательность конечных непустых множеств $S_1, S_2, \ldots S_N$ литер, необходимо построить последовательность элементов:
\[Select(S_1, S_2, \ldots S_N) = (x_1, x_2, \ldots x_N)\]
такую, что $x_i \in S_i$ для любого $i=1,\ldots N$, и
$x_i \neq x_j$ при всех $j \ne i$.

При решении задачи на Рефале будем представлять последовательности и множества литер строками из этих литер.  Тем самым, требуется реализовать функцию \texttt{Select} со следующим форматом:
\begin{refal}
   <Select ( ) (e.Set1) (e.Set2) ... (e.SetN)> ==> s.1 s.2 ... s.N
\end{refal}
где \texttt{e.SetK} \--- непустые строки литер, \texttt{s.К} \--- литеры, отобранные (без повторов) по одной из \texttt{e.SetK}.  Если невозможно отобрать \texttt{s.1 s.2 ... s.N} указанным способом, то функция \texttt{Select} возвращает \texttt{'*'}.

Для тестовых прогонов функция \texttt{Select} вызывалась на следующем аргументе:
\begin{refal}
   <Select ( ) ('1234567890abc') ('1234567890ab') ... ('12') ('1')>
          ==> 'cba0987654321'
\end{refal}
Такой вид начального вызова формировался с помощью вспомогательных функций:
\begin{refal}
Main = <MkArg '1234567890abc'> :: e.Prefixes,
  <PrintLN e.Prefixes>,
  <Select () e.Prefixes> :: eXs-or-sFail,
  <PrintLN eXs-or-sFail> ;

MkArg e.String =  /* e.Prefixes */
  e.String : {  
    e.String-- s = (e.String) <MkArg e.String-->;
    /* empty */  = ;
  };
\end{refal}

Функция \texttt{Select} была реализована четырьмя различными способами:
\begin{itemize}
	\item \texttt{Select.rf} \--- предикат \texttt{OneOf} реализован в стиле языка Рефал\-/5 (возвращает либо \texttt{'T'}, либо \texttt{'F'}).
\begin{refal}
Select (e.Xs) e.Sets = /* (eXs) или '*' */
  e.Sets : {
    /*empty*/ = (e.Xs);
    (e.Set) e.Sets--,
      e.Set : e sX e, 
      <OneOf (e.Xs) sX> : F, 
      <Select (e.Xs sX) e.Sets--> : (e.Xs-) = (e.Xs-);
    e = '+';
  };

OneOf (e.Xs) s.X = /* 'T' или 'F' */
  e.Xs : {
    e sX e = T;
    e      = F;
  };
\end{refal}  

	\item \texttt{Select1.rf} \--- предикат \texttt{OneOf} реализован в стиле языка Рефал Плюс \--- как откатная функция.
\begin{refal}
Select (e.Xs) e.Sets = /* (eXs) или '*' */
  e.Sets : {
    /*empty*/ = (e.Xs);
    (e.Set) e.Sets--,
      e.Set : e sX e, 
      #<OneOf (e.Xs) sX>, 
      <Select (e.Xs sX) e.Sets--> : (e.Xs-) = (e.Xs-);
    e = '*';
   };

OneOf (e.Xs) s.X = /* пусто или $fail */
   e.Xs : e s.X e;
\end{refal}

	\item \texttt{Select2.rf} \--- еще более в стиле языка Рефал~Плюс: функция \texttt{Select} реализована как откатная фукция \texttt{Sel}, а тело предиката \texttt{OneOf} подставлено в единственную точку вызова.

\begin{refal}
Select (e.Xs) e.Sets = /* (eXs) или '*' */
  {
    <Sel (e.Xs) e.Sets>;
    '*';
  };

Sel (e.Xs) e.Sets = /* (eXs) или $fail; */
  e.Sets : \{
    /*empty*/ = (e.Xs);
    (e.Set) e.Sets--,
      e.Set : e sX e, 
      # \{ e.Xs : e s.X e; },
      <Sel (e.Xs sX) e.Sets-->;
  };
\end{refal}  

	\item \texttt{Select3.rf} \--- отличается от \texttt{Select2.rf} тем, что первый аргумент \texttt{Sel} представлен не в виде строки литер (например, \texttt{'cba09'}), а в виде выражения\-/стека \\
(\texttt{'c' ('b' ('a' ('0' ('9'))))}), \\
с замыслом сэкономить на времени выполнения операций конкатенаций.
\begin{refal}
Select (e.Xs) e.Sets = /* (eXs) или '*' */
  {
    <Sel () e.Sets> :: (e.Xs) = (<Stack2Exp e.Xs>);
    '*';
  };

Sel (e.Xs) e.Sets =  /* (eXs) или $fail; */
  e.Sets : \{
    /*empty*/ = (e.Xs);
    (e.Set) e.Sets--,
      e.Set : e sX e, 
      #<InStack e.Xs s.X>,
      <Sel (s.X (e.Xs)) e.Sets-->;
  };

InStack e.Xs s.X =  /* пусто или $fail; */
  e.Xs : s.Y (e.Xs--),
  \{
    s.Y : s.X;
    <InStack e.Xs-- s.X>;
  };
 
Stack2Exp e.Xs =    /* e.ExpXs */
  e.Xs : {
    /*empty*/ = /*empty*/;
    s.Y (e.Xs--) = <Stack2Exp e.Xs--> s.Y;
  };
\end{refal}
	
\end{itemize}

В таблице~\ref{tab:tests} приведены временные характеристики выполнения этих программ для трех реализаций языка Рефал~Плюс: v~1.8.00.8b, v~1.8.7 и обсуждаемой программной системы v~2.0, работающей под Linux. Тестирование проводилось на компьютере Pentium~4 2,0 GHz.  Как и ожидалось, новые принципы реализации языка позволили получить на задаче \texttt{Select} ускорение (от 1,3 до 5,3 раз) счета.  Аналогичные значения коэффициентов ускорения были получены и для других тестов.  

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

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}     \hline
             &\multicolumn{4}{c|}{Тесты}\\ \cline{2-5}                   
 Версии Рефала~Плюс             & select   & select1 & select2 & select3 \\ \hline
refal-plus 1.8.00.8b (DOS)  & 252,5c   & 232,9с  & 225,3с  & 170,1с  \\ \hline
refal-plus 1.8.7 (Linux)    & 45,5с    & 41,5с   & 39,3с   & 33,65с   \\ \hline
refal-plus 2.0 (Linux)    & 17,9с    & 11,2с   & 7,45с   & 25,54с   \\ \hline
ускорение (2.0 vs. 1.8.7) & 2,54     & 3,71    & 5,28    & 1,32     \\ \hline
\end {tabular}
\end{center}

\caption{Результаты тестирования}
\label{tab:tests}
\end{table}

\section{Состояние разработки и ближайшие планы развития}

Сегодня в~основном завершена разработка всей <<магистральной>> линии системы, обеспечивающей реализацию языка Рефал~Плюс на базе системы программирования C++:
\begin{itemize}
	\item входной (front\-/end) модуль для языка Рефал~Плюс;
	\item компилятор;
	\item базовый оптимизатор AIL\-/кода;
	\item выходной (back\-/end) модуль для языка C++;
	\item библиотека периода исполнения на базе языка C++.
\end{itemize}

Дистрибутив распространяется как архив формата <<tar.gz>>, предназначенный для ОС Linux:
\begin{center}
\mbox{\url{http://skif.pereslavl.ru/refal}} .
\end{center}
%
Ближайшие планы разработчиков:
%
\begin{itemize}

	\item Реализация дистрибутива системы <<Рефал~Плюс/C++>> для ОС Windows.

	\item Реализация в системе эффективных и удобных средств отладки рефал\-/программ.

	\item Разработка и реализация в системе элементов поддержки (back\-/end и RSL) целевых языков C\# (платформа .NET) и Т++ (платформа OpenTS, поддерживающая автоматическое динамическое распаралелливание программ пользователя~\cites{bib:AAP99}).

	\item Разработка и реализация в системе элементов поддержки (front\-/end)  существующих диалектов языка Рефал (Рефал\-/2, -5 и -6) в качестве входных языков.

\end{itemize}

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

\subsection*{Благодарности}
\label{sec:tnx}
Авторы благодарны всему рефал\-/сообществу за содержательные и полезные обсуждения во время выполнения данного проекта.

\begin{bibsection}
\begin{biblist}

\bib{bib:AbR88}{misc}{
        author={Абрамов, С. М.},
        author={Романенко, С. А.},
        title={Представление объектных выражений массивами при реализации языка Рефал},
        series={186},
        type={Препринт},
        publisher={ИПМ им. М.В.Келдыша},
        pages={27},
        place={М.},
        date={1988},
}
\bib{bib:AbO04}{inproceedings}{
        author={Абрамов, С. М.},
        author={Орлов, А. Ю.},
        title={Компиляция в~императивные языки синтаксического отождествления языка Рефал},
        publisher={Физматлит},
        conference={Международная конференция <<Программные системы: теория и приложения>>},
        place={Переславль\-/Залесский},
        date={2004},
}
\bib{bib:AAP99}{misc}{
        author={Абрамов, С. М.},
        author={Адамович, А. И.},
        author={Позлевич, Р. В.},      
        title={Т\-/система \---среда программирования с поддержкой автоматического динамического          распараллеливания программ},
        type={Сборник},
        publisher={Физматлит},
        booktitle={Программные системы: Теоретические основы и приложения},
        place={M.},
        date={1999},
}
\bib{bib:BzR77}{book}{
        title={Базисный Рефал и его реализация на вычислительных машинах},
        publisher={ЦНИИПИАС},
        place={М.},
        date={1977},
        pages={258},
}
\bib{bib:GurR91}{book}{
        author={Гурин, Р. Ф.},
        author={Романенко, С. А.},
        title={Язык программирования Рефал Плюс},
        pages={183},
        publisher={Интертех},
        place={М.},
        date={1991},
}
\bib{bib:KlR86}{misc}{
        author={Климов, Ан. В.},
        author={Романенко, С. А.},
        title={Система программирования Рефал\-/2 для ЕС ЭВМ. Описание библиотеки функций},
        series={200},
        type={Препринт},
        publisher={ИПМ им. М.В.Келдыша},
        place={М.},
        date={1986},
        pages={38},
}
\bib{bib:KlR87}{misc}{
        author={Климов, Ан. В.},
        author={Романенко, С. А.},
        title={Система программирования Рефал\-/2 для ЕС ЭВМ. Описание входного языка},
        type={Препринт},
        publisher={ИПМ им. М.В.Келдыша},
        place={М.},
        date={1987},
        pages={52},
}
\bib{bib:KRT72}{misc}{
        author={Климов, Ан. В.},
        author={Романенко, С. А.},
        author={Турчин, В. Ф.},
        title={Компилятор с языка Рефал},
        publisher={ИПМ им. М.В.Келдыша},
        place={М.},
        date={1972},
        pages={74},
}
\bib{bib:Rom87a}{book}{
        author={Романенко, С. А.},
        title={Реализация Рефала\-/2},
        publisher={ИПМ им. М.В.Келдыша},
        place={М.},
        date={1987},
        pages={191},
}
\bib{bib:Rom87b}{misc}{
        author={Романенко, С. А.},
        title={Рефал\-/4 \---расширение Рефала\-/2, обеспечивающее выразимость результатов                прогонки},
        publisher={ИПМ им. М.В.Келдыша},
        type={Препринт},
        series={147},
        place={М.},
        date={1987},
        pages={27},
}
\bib{bib:Rom87c}{misc}{
        author={Романенко, С. А.},
        title={Прогонка для программ на Рефале\-/4},
        publisher={ИПМ им.~М.В.~Кел\-ды\-ша АН~СССР},
        type={Препринт},
        series={211},
        place={М.},
        date={1987},
        pages={19},
}
\bib{bib:Rom99}{misc}{
        author={Романенко, С. А.},
        title={Компиляция Рефал\-/программ в виртуальный код},
        date={1999},
        note={\\\mbox{\url{http://shade.msu.ru/refal.msu.ru/docs/rbvcomp.ps.gz}}},
}

\bib{bib:Tur66}{incollection}{
        author={Турчин В.Ф.},
        title={Метаязык для формального описания алгоритмических языков},
        institution={ИПМ им. М.В.Келдыша},
        type={Сборник},
        booktitle={Цифровая вычислительная техника и программирование},
        publisher={Сов. Радио},
        pages={116\--124},
        place={М.},
        date={1966},
}
\bib{bib:Tur71}{misc}{
        author={Турчин В.Ф.},
        title={Программирование на языке Рефал},
        publisher={ИПМ им. М.В.Келдыша},
        type={Препринт},
        series={41, 43, 44, 48, 49},
        place={М.},
        date={1971},
}
\bib{bib:K03}{misc}{
        author={Klimov, A. V.},
        title={Refal\-/6},
        date={2003}, 
        note={\mbox{\url{http://www.refal.org/\~arklimov/refal6}}},
}
\bib{bib:KK03}{misc}{
        author={Klimov, A. V.},
        author={Klimov, An. V.},
        title={REFAL \---JAVA. The prog\-ram\-ming language Refal implemented on top of the
        Java2 Platform},
        note={\\\mbox{\url{http://www.refal.org/\~arklimov/refal6/refal-j.htm}}},
        date={2003}, 
}
\bib{bib:Tur89}{book}{
        author={Turchin, V. F.},
        title={Refal\-/5},
        type={Programming Guide and Reference Manual},
        publisher={New England Publishing Co.},
        place={Holyoke},
        note={\mbox{\url{http://shura.botik.ru/refal/book/html/}}, на русском языке:
        \mbox{\url{http://www.refal.ru/rf5_frm.htm}}},
        date={1989},
}
\bib{bib:Belous:RefalPHP}{inproceedings}{
        author={Белоус, Леонид Ф.},
        title={Refal\-/PHP: Универсальный инструмент Интернет\-/технологий},
        conference={Всероссийская научная конференция <<Научный сервис в сети Интернет>>,               г.~Новороссийск, 23\--28~сентября 2002~г.},
        publisher={изд-во. МГУ},
        place={М.},
        date={2002},
        pages={44\--47},
}

\bib{bib:Belous:RefalPHPScite}{misc}{
        author={Белоус, Леонид Ф.},
        title={REFAL\-/SCITE: Интегрированная оболочка для разработки программ в интранет\-/среде},
        type={Электронный ресурс},
        date={2003-06-10},
        note={\\\mbox{\url{http://www.refal.net/~belous/refscite.htm}}},
}

\end{biblist}
\end{bibsection}

\end{document}               
