Changeset 1374


Ignore:
Timestamp:
Mar 15, 2004, 2:55:44 AM (17 years ago)
Author:
orlov
Message:
  • Final version
File:
1 edited

Legend:

Unmodified
Added
Removed
  • to-imperative/trunk/docs/pm.tex

    r1372 r1374  
    221221
    222222В статье предполагается, что в реализации Рефала используется такое представление объектных выражений, что операции вычисления длины (\length{e_x}) выражения и конструирования подвыражения (\(\subexpr{e_x}{i}{L}\))\footnote{
    223                 В конструкции \(e_y = \subexpr{e_x}{i}{L}\) фрагменты $i$ и $L$ могут быть выражениями, вырабатывающие неотрицательные целые значения \--- номер терма в $e_x$, с которого будет начинаться подвыражение $e_y$ и длину подвыражения $e_y$, соответственно.  Термы нумеруются слева направо начиная с 0, номер последнего терма \--- $(\length{e_x}-1)$.
     223                В конструкции \(e_y = \subexpr{e_x}{i}{L}\) фрагменты $i$ и $L$ могут быть выражениями, вырабатывающими неотрицательные целые значения \--- номер терма в $e_x$, с которого будет начинаться подвыражение $e_y$, и длину подвыражения $e_y$, соответственно.  Термы нумеруются слева направо начиная с 0, номер последнего терма \--- $(\length{e_x}-1)$.
    224224        } выполняются за константное (не зависящее от выражения) время.  Это предположение выполнено для большинства современных реализаций диалектов языка Рефал~\cites{bib:vector-exps,bib:Refal+,bib:Web:New-Refal+,bib:KK03}.
    225225
     
    244244\end{quote}
    245245%
    246 Во второй строке данного описания стоит \emph{перестройка} $e_x : e_1\,e_1\,e_1$
     246Во второй строке данного описания стоит \emph{перестройка} $e_x : e_1\,e_1\,e_1,$
    247247выполняющая следующую проверку: <<верно ли, что аргумент функции $e_x$
    248248может быть представлен как конкатенация трех копий
     
    273273реализациях диалектов Рефала вычисление такой несложной
    274274функции (всего один шаг <<проверка\--замена>>) даже на современных ПЭВМ
    275 занимает достаточно длительное время (см. таблицу~\ref{tab:IsTripletTime}).
    276 Причиной этого является неэффективная схема (см. рис.~\ref{pic:isTripletOld})
     275занимает достаточно длительное время (см. Таблицу~\ref{tab:IsTripletTime}).
     276Причиной этого является неэффективная схема (см. Рис.~\ref{pic:isTripletOld})
    277277реализации перестройки $e_x : e_1\,e_1\,e_1$ в функции \Verb"IsTriplet": при
    278 такой схеме реализации, сложность вычисления функции составляет $O({A_x}^2)$, где
     278такой схеме реализации сложность вычисления функции составляет $O({A_x}^2)$, где
    279279${A_x = \length{e_x}}$ \--- длина входных данных.
    280280
     
    363363вариантов для значения переменной} $e_1$ рассматриваются \emph{все возможные
    364364префиксы} длины $X_1$, префиксы рассматриваются поочередно, в следующем
    365 порядке $X_1\!= 0,\ldots,A_x$ и для каждого значения $e_1$ делается проверка,
     365порядке: $X_1\!= 0,\ldots,A_x$. Для каждого значения $e_1$ делается проверка,
    366366не совпадает ли $e_x$ с конкатенацией $e_1\,e_1\,e_1$ трех копий $e_1$.
    367367
    368368Корни неэффективности в том, что в качестве возможных значений для неизвестной
    369369$e_1$ перебираются \emph{все} префиксы $e_x$.  А этого можно избежать.
    370 Действительно, предположим нам удалось подобрать такое значение $e_1$
     370Действительно, предположим, нам удалось подобрать такое значение $e_1$
    371371некоторой длинны $X_1$, что $e_x$ совпадает с конкатенацией $e_1\,e_1\,e_1$
    372372трех копий $e_1$.  Тогда мы можем утверждать, что:
     
    377377\end{itemize}
    378378Тем самым найден новый эффективный способ вычисления функции \Verb|IsTriplet|
    379 (см. рис.~\ref{pic:isTripletNew}).  Способ имеет вычислительную сложность не
     379(см. Рис.~\ref{pic:isTripletNew}).  Способ имеет вычислительную сложность не
    380380$O({A_x}^2)$, a $O(A_x)$.  В нем не рассматривается (отсекается) множество вариантов
    381381значений для $e_1$, которые не имеют никаких шансов быть решением
     
    384384\Verb|IsTriplet| обеспечивает \emph{ускорение примерно в $8\,500$ раз}\footnote{
    385385        Отношение числа сравнений символов: $17\,000 \cdot 17\,001 / (2 \cdot 17\,000) =  8\,500.5$.
    386 } вычислений, упомянутых в таблице~\ref{tab:IsTripletTime}.
     386} вычислений, упомянутых в Таблице~\ref{tab:IsTripletTime}.
    387387
    388388\subsubsection{Пример на тему <<учет ограничений на длины>>}
     
    401401выполняется по следующей схеме:
    402402\begin{itemize}
    403         \item В цикле поочередно рассматриваются все префиксы $e_1$ выражения $e_x$, с длинами от $0$ до $A_x = \length{e_x}$.
    404         \item Проверяется, верно ли, что за префиксом $e_1$ в выражении $e_x$ имеется выражение, равное $e_y$.  Если проверка не успешная, то в качестве $e_1$ рассматривается следующий префикс $e_x$ (удлинение переменной $e_1$).  Если проверка успешная, то функция вычислена, результат \Verb|True|.
    405         \item Если все префиксы $e_1$ выражения $e_x$ рассмотрены и невозможно очередное удлинение переменной $e_1$, то функция вычислена, результат \Verb|False|.
     403        \item в цикле поочередно рассматриваются все префиксы $e_1$ выражения $e_x$, с длинами от $0$ до $A_x = \length{e_x}$;
     404        \item проверяется, верно ли, что за префиксом $e_1$ в выражении $e_x$ имеется выражение, равное $e_y$.  Если проверка не успешная, то в качестве $e_1$ рассматривается следующий префикс $e_x$ (удлинение переменной $e_1$).  Если проверка успешная, то функция вычислена, результат \Verb|True|;
     405        \item если все префиксы $e_1$ выражения $e_x$ рассмотрены и невозможно очередное удлинение переменной $e_1$, то функция вычислена, результат \Verb|False|.
    406406\end{itemize}
    407407
     
    451451        \right.
    452452\]
    453 что позволяет выписать более эффективную (чем описанную выше) схему реализации функции \Verb|IsSubexp| (см. рис.~\ref{pic:IsSubexp}).
     453что позволяет выписать более эффективную (чем описанную выше) схему реализации функции \Verb|IsSubexp| (см. Рис.~\ref{pic:IsSubexp}).
    454454
    455455\subsubsection{Пример на тему <<цепочка перестроек>>}
     
    563563        \label{eq:sysVII}
    564564\end{equation}
    565 После этого легко построить схему вычисления (см. рис.~\ref{pic:AreSymmetric}) функции \Verb|AreSymmetric|.  Отметим, что за счет решения системы уравнений на длины переменных, полученный алгоритм имеет не два вложенных цикла, а один цикл, и работает он в среднем в $\length{e_y}$ раз быстрее, чем это есть для классических способов компиляции данной функции.
     565После этого легко построить схему вычисления (см. Рис.~\ref{pic:AreSymmetric}) функции \Verb|AreSymmetric|.  Отметим, что за счет решения системы уравнений на длины переменных, полученный алгоритм имеет не два вложенных цикла, а один цикл, и работает он в среднем в $\length{e_y}$ раз быстрее, чем это есть для классических способов компиляции данной функции.
    566566
    567567\begin{figure}
     
    664664удовлетворяющие определенному отношению порядка на подстановках.
    665665Существующие диалекты Рефала определяют только два противоположных отношения
    666 порядка, называемых~\cite{bib:Refal+} сопоставлениями \emph{слева направо}, и
     666порядка, называемых~\cite{bib:Refal+} сопоставлениями \emph{слева направо} и
    667667\emph{справа налево}.
    668668
     
    681681причем $\Pe_L$ является \emph{источником}, то есть, $\Pe_L$ является выражением,
    682682содержащим только \emph{старые переменные\footnote{
    683          Старые переменные \--- означенные переменные, переменные чьи значения были
     683         Старые переменные \--- означенные переменные, переменные, чьи значения были
    684684         определены в рефал\-/программе ранее.  Все остальные переменные называются \emph{новыми}.
    685685}} \--- переменные, имеющие значение к моменту вычисления данного выражения.
     
    691691перестройка ${\Pe_L : \Pe_R}$ в момент своего выполнения редуцируется до базового
    692692клэша, и ее выполнение сводится к решению этого базового клэша.  А во время
    693 компиляции, компилятор должен по заданной перестройке ${\Pe_L : \Pe_R}$ выписать
     693компиляции компилятор должен по заданной перестройке ${\Pe_L : \Pe_R}$ выписать
    694694императивный алгоритм для решения любых базовых клэшей, которые могут
    695695получиться из данной перестройки при разных значениях старых переменных.
     
    741741
    742742Компилятор строит код императивной программы, выполняющей заданную цепочку
    743 перестроек $\Scl$.  В процессе выполнения этой цепочки, все больше новых
     743перестроек $\Scl$.  В процессе выполнения этой цепочки все больше новых
    744744переменных, входящих в $\Scl$, получают значения \--- становятся
    745 старыми переменными.  Для того, чтобы хранить информацию о том, какие
     745старыми переменными.  Для того чтобы хранить информацию о том, какие
    746746переменные будут иметь значения после исполнения кода, построенного на данный
    747747момент, компилятор использует список старых переменных $\Old$.
     
    759759        \item
    760760      \INT\-/переменные, значениями которых являются неотрицательные целые числа (длины объектных выражений) и особое значение\footnote{
    761                         Значение $\infty$ будет встречаться только в таком контексте, что результат операций с ним определяется интуитивно понятным, однозначным образом: ${\infty + \infty = \infty}$, ${\infty + x = \infty}$, ${\Min(\infty,x) = x}$ и т.п. (здесь $x$ \--- неотрицательное целое число).
     761                        Значение $\infty$ будет встречаться только в таком контексте, что результат операций с ним определяется интуитивно понятным, однозначным образом: ${\infty + \infty = \infty}$, ${\infty + x = \infty}$, ${\Min(\infty,x) = x}$ и т.~п. (здесь $x$ \--- неотрицательное целое число).
    762762        } $\infty$;
    763763\end{itemize}
    764764        \item выражения двух типов (\EXPR{} и \INT\footnote{
    765765                        Значениями выражений типа \INT{} могут являться любые целые числа, $\infty$ и~$-\infty$.
    766                 }), построенные над этими переменными и константами, при помощи соответствующих наборов операций (см. Рис.~\ref{fig:Syntax});
     766                }), построенные над этими переменными и константами при помощи соответствующих наборов операций (см. Рис.~\ref{fig:Syntax});
    767767        \item логические выражения, используемые в условиях операторов \IF\ и \FOR\ (см. Рис.~\ref{fig:Syntax});
    768768        \item операторы (см. Рис.~\ref{fig:Syntax}).
     
    975975$\Seq^\vartriangle$ уравнений на длины по следующим правилам:
    976976\begin{itemize}
    977         \item Из каждой перестройки ${\Pe_L : \Pe_R}$ получается одно уравнение
     977        \item из каждой перестройки ${\Pe_L : \Pe_R}$ получается одно уравнение
    978978                ${\Sigma_L = \Sigma_R}$, причем $\Sigma_L$ строится в результате анализа верхнего уровня
    979                 выражения $\Pe_L$, а $\Sigma_R$ \--- в результате анализа верхнего уровня выражения $\Pe_R$.
    980   \item Объектный символ $\Os$ заменяется на 1.
    981   \item Выражение в скобках $(\Pe)$ заменяется на 1.
    982   \item Старая переменная $V_j$ заменяется на $A_j=|V_j|$.
    983         \item Новая переменная $V_j[m,m]$ заменяется на $m$.
    984   \item Новая переменная $V_j[m,n]$, где $m \ne n$, заменяется на $X_j$
     979                выражения $\Pe_L$, а $\Sigma_R$ \--- в результате анализа верхнего уровня выражения $\Pe_R$;
     980  \item объектный символ $\Os$ заменяется на 1;
     981  \item выражение в скобках $(\Pe)$ заменяется на 1;
     982  \item старая переменная $V_j$ заменяется на $A_j=|V_j|$;
     983        \item новая переменная $V_j[m,m]$ заменяется на $m$;
     984  \item новая переменная $V_j[m,n]$, где $m \ne n$, заменяется на $X_j$
    985985  (в этом случае, так же мы будем использовать для $X_j$
    986986  обозначение $X_j[m,n]$).
     
    990990приведен в разделе~\ref{sec:IntroExampleSystem}.
    991991
    992 Нас будут интересовать только такие подстановки $\{X_j \to k_j\}$ $(k \in \mathbb{Z})$, решающие систему уравнений на длины, что для всякой переменной $X_j$, соответствующей рефал\-/переменной $V_j[m,n]$, выполнено: $m \leq k_j \leq n$.  Поэтому мы везде далее будем говорить, что система уравнений на длины \emph{совместна}, если множество подстановок, обладающих указанным свойством, непусто.  Иначе, мы будем назвать систему \emph{несовместной}.
     992Нас будут интересовать только такие подстановки $\{X_j \to k_j\}$ $(k \in \mathbb{Z})$, решающие систему уравнений на длины, что для всякой переменной $X_j$, соответствующей рефал\-/переменной $V_j[m,n]$, выполнено: $m \leq k_j \leq n$.  Поэтому мы везде далее будем говорить, что система уравнений на длины \emph{совместна}, если множество подстановок, обладающих указанным свойством, не пусто.  Иначе, мы будем назвать систему \emph{несовместной}.
    993993
    994994\subsection{Основные свойства систем уравнений, соответствующих
     
    10931093        алгоритм~\EqG{}):
    10941094                \begin{itemize}
    1095                         \item Система $\Seq' = G_0 \cup G_1 \cup \cdots \cup G_k$
    1096                         эквивалентна системе $\Seq$.
    1097                         \item Каждое уравнение из $G_0$ не
    1098                                 содержит переменных $X$.
    1099                         \item Каждое уравнение из $G_p$ (где $p>0$) имеет вид
     1095                        \item система $\Seq' = G_0 \cup G_1 \cup \cdots \cup G_k$
     1096                        эквивалентна системе $\Seq$;
     1097                        \item каждое уравнение из $G_0$ не
     1098                                содержит переменных $X$;
     1099                        \item каждое уравнение из $G_p$ (где $p>0$) имеет вид
    11001100                                $c \cdot X = \Sigma$, где $\Sigma$ не содержит переменных из левых
    1101                                 частей уравнений группы $G_p$, и $c \ne 0$.
    1102                         \item Множество переменных, входящих в некоторую группу, не пересекается
     1101                                частей уравнений группы $G_p$, и $c \ne 0$;
     1102                        \item множество переменных, входящих в некоторую группу, не пересекается
    11031103                                с множеством переменных, входящих в любую другую группу.
    11041104%                       \item Если уравнение $c \cdot X = \Sigma$ принадлежит группе
     
    11251125                коде императивной программы линейной последовательности следующих проверок:
    11261126                \begin{enumerate}
    1127                         \item Для каждого уравнения $\Eq$ из группы $G_0$ выписывается проверка
     1127                        \item для каждого уравнения $\Eq$ из группы $G_0$ выписывается проверка
    11281128                                условия, которое $\Eq$ накладывает на параметры $A$
    1129                                 (см.~раздел~\ref{sec:cond-eq}, алгоритм~\ChkEq).
    1130                         \item Для каждого уравнения $c \cdot X[m,n] = \Sigma$ системы
     1129                                (см.~раздел~\ref{sec:cond-eq}, алгоритм~\ChkEq);
     1130                        \item для каждого уравнения $c \cdot X[m,n] = \Sigma$ системы
    11311131                                $\Seq'$, где $\Sigma$ не содержит переменных, выписываются
    11321132                                проверки делимости $\Sigma$ на $c$ нацело и неравенств
    11331133                                ${c \cdot m \leq \Sigma \leq c \cdot n}$
    1134         (см.~раздел~\ref{sec:ChkHard}, алгоритм~\ChkHard).
    1135                         \item Для каждой свободной переменной каждой группы $G_p$, $p>0$,
     1134        (см.~раздел~\ref{sec:ChkHard}, алгоритм~\ChkHard);
     1135                        \item для каждой свободной переменной каждой группы $G_p$, $p>0$,
    11361136                                выписывается\footnote{
    1137                                         При грамотной реализации алгоритма, проверки ограничений на свободные
     1137                                        При грамотной реализации алгоритма проверки ограничений на свободные
    11381138                                        переменные должны выписываться только в том случае, когда нет
    11391139                                        <<дешевого>> способа эти ограничения улучшить.  Например, если,
     
    11481148                                проверка условия,
    11491149                                необходимого, чтобы множество возможных значений этой переменной было
    1150                                 непусто (см.~раздел~\ref{sec:cond-min-max}, алгоритм~\ChkBnd).
     1150                                не пусто (см.~раздел~\ref{sec:cond-min-max}, алгоритм~\ChkBnd).
    11511151                \end{enumerate}
    11521152                Вывод некоторой проверки в код императивной программы блокируется, если эта
     
    12231223                \end{enumerate}
    12241224        \item \label{lst:EQ-make-group}
    1225 %AO: Ниже должно быть "не пуст" или "непуст"?
    12261225                До тех пор, пока список $T$ не пуст, выполняются следующие действия:
    12271226                \begin{enumerate}
     
    12631262                        \item Выполняется рекурсивный переход к шагу~\ref{lst:EQ-make-group}.
    12641263                \end{enumerate}
    1265 %AO: Ниже должно быть "не пуста" или "непуста"?
    12661264        \item Если система $S$ не пуста, то выполняется переход к
    12671265                шагу~\ref{lst:EQ-analyze-first}, иначе алгоритм заканчивает работу, выдавая
     
    15491547вычисления решения цепочки:
    15501548\begin{itemize}
    1551         \item Построение объектного выражения $\Oe_L$, соответствующего левой части
     1549        \item построение объектного выражения $\Oe_L$, соответствующего левой части
    15521550                $\Pe_L$ некоторой перестройки ${\Pe_L : \Pe_R}$ (см.~раздел~\ref{sec:CL-Oe}).
    15531551                Везде далее, в случае, если существует объектное выражение\footnote{
     
    15601558                соответствующее левой части $\Pe_L$
    15611559                некоторой перестройки ${\Pe_L : \Pe_R}$, мы будем говорить, что
    1562                 перестройка имеет вид ${\Oe_L : \Pe_R}$.
    1563         \item Упрощение перестройки ${\Oe_L : \Pe_1 (\Pe_2) \Pe_3}$, в которой длина одного из
    1564                 выражений $\Pe_1$ и $\Pe_3$ может быть вычислена, путем снятия скобок с
     1560                перестройка имеет вид ${\Oe_L : \Pe_R}$;
     1561        \item упрощение перестройки ${\Oe_L : \Pe_1 (\Pe_2) \Pe_3}$, в которой длина одного из
     1562                выражений $\Pe_1$ и $\Pe_3$ может быть вычислена путем снятия скобок с
    15651563                соответствующего терма выражения $\Oe_L$ и создания новой вспомогательной
    1566                 перестройки (см.~раздел~\ref{sec:CL-deref}).
    1567         \item Сравнение на равенство старых переменных и объектных подвыражений,
     1564                перестройки (см.~раздел~\ref{sec:CL-deref});
     1565        \item сравнение на равенство старых переменных и объектных подвыражений,
    15681566                встречающихся в правой части $\Pe_R$ некоторой перестройки ${\Oe_L : \Pe_R}$,
    1569                 соответствующим подвыражениям выражения $\Oe_L$ (см.~раздел~\ref{sec:CL-compare}).
    1570         \item Означивание новых переменных, встречающихся в правой части $\Pe_R$
     1567                соответствующим подвыражениям выражения $\Oe_L$ (см.~раздел~\ref{sec:CL-compare});
     1568        \item означивание новых переменных, встречающихся в правой части $\Pe_R$
    15711569                некоторой перестройки ${\Oe_L : \Pe_R}$, путем взятия соответствующих
    1572                 подвыражений выражения $\Oe_L$ (см.~раздел~\ref{sec:CL-compare}).
    1573         \item Итеративный подбор значения одной из новых переменных (см.~раздел~\ref{sec:CL-cycle}).
     1570                подвыражений выражения $\Oe_L$ (см.~раздел~\ref{sec:CL-compare});
     1571        \item итеративный подбор значения одной из новых переменных (см.~раздел~\ref{sec:CL-cycle}).
    15741572\end{itemize}
    15751573
    15761574Кроме того, как результат анализа, изменяется состояние компилятора
    1577 \((\Scl, \Old, \Fail)\) (см.~раздел~\ref{sec:comp-params}).
     1575\((\Scl, \Old, \Fail)\) (см.~раздел~\ref{sec:comp-params}):
    15781576\begin{itemize}
    1579         \item Цепочка перестроек $\Scl$ упрощается в результате действий, описанных
     1577        \item цепочка перестроек $\Scl$ упрощается в результате действий, описанных
    15801578                в разделах~\ref{sec:CL-new-vars}\--\ref{sec:CL-cycle};
    1581         \item Список старых переменных $\Old$ пополняется за счет означивания новых
     1579        \item список старых переменных $\Old$ пополняется за счет означивания новых
    15821580                переменных и заведения вспомогательных выражений
    15831581                (см. разделы~\ref{sec:CL-Oe}, \ref{sec:CL-new-vars},
    1584                 \ref{sec:CL-compare} и~\ref{sec:CL-cycle}).
    1585         \item Метка $\Fail$, соответствующая следующей попытке удлинения значения
     1582                \ref{sec:CL-compare} и~\ref{sec:CL-cycle});
     1583        \item метка $\Fail$, соответствующая следующей попытке удлинения значения
    15861584                текущей открытой (итерируемой) переменной, изменяется в результате
    15871585                образования цикла подбора значения одной из новых переменных, которая
     
    15921590\((\Scl, \Old, \Fail)\), подается упорядоченная тройка $(\Hard, \Amin, \Amax)$,
    15931591полученная с помощью алгоритма \EqA{} из системы уравнений $\Seq$,
    1594 соответствующей цепочке $\Scl$ (см.~раздел~\ref{sec:EQ-analysis}).
     1592соответствующей цепочке $\Scl$ (см.~раздел~\ref{sec:EQ-analysis}):
    15951593\begin{itemize}
    15961594        \item $\Hard$ \--- список переменных, длина значений которых может быть
     
    15991597                объектных символов $\Os$, выражений в скобках $(\Pe')$ и переменных
    16001598                $V$, принадлежащих списку $\Hard$), то мы будем называть его
    1601                 \emph{жестким} выражением и обозначать $\He$.
     1599                \emph{жестким} выражением и обозначать $\He$;
    16021600        \item $\Amin, \Amax$ \--- выражения, редуцируемые во время исполнения к
    16031601                ограничениям соответственно снизу и сверху на длину первой (слева)
     
    16531651        \item \label{lst:CL-compare}
    16541652                Если в цепочке $\Scl$ есть перестройка вида ${\Oe_L : \He_1 \Pe_2 \He_3}$,
    1655                 где одно из выражений $\He_1$ и $\He_3$ непусто, то в коде императивной
     1653                где одно из выражений $\He_1$ и $\He_3$ не пусто, то в коде императивной
    16561654                программы строятся проверки на равенство старых переменных и объектных
    16571655                подвыражений выражений $\He_1$ и $\He_3$ соответствующим подвыражениям
    16581656                выражения $\Oe_L$.
    16591657                Новые переменные, содержащиеся в выражениях $\He_1$ и $\He_3$, получают
    1660                 значения, и добавляются в список $\Old$.
     1658                значения и добавляются в список $\Old$.
    16611659                Исходная перестройка заменяется на перестройку ${\Oe_L' : \Pe_2}$, где
    16621660                $\Oe_L'$ получается из $\Oe_L$ отбрасыванием слева и справа выражений,
     
    16651663        \item \label{lst:CL-new-val2}
    16661664                Если в цепочке $\Scl$ есть перестройка вида ${\Pe_L : \He_1 \Pe_2 \He_3}$,
    1667                 где одно из выражений $\He_1$ и $\He_3$ непусто, а значения новых переменных
     1665                где одно из выражений $\He_1$ и $\He_3$ не пусто, а значения новых переменных
    16681666                выражения $\Pe_L$ однозначно определяются, исходя из значений старых переменных,
    16691667                то выполняется означивание новых переменных выражения $\Pe_L$
     
    16811679                % DONE: SA: Антон, так и есть? переход к шагу~\ref{lst:CL-catenate}?
    16821680        \item \label{lst:CL-cycle}
    1683 %AO: Ниже должно быть "не пуста" или "непуста"?
    16841681                Если цепочка $\Scl$ не пуста, то выполняется построение
    16851682                % фрагмента кода
     
    17131710        \item Если выражение $\Pe$ имеет вид $(\Pe')$, следует выполнить
    17141711                построение выражения императивного языка $E'$ для выражения
    1715                 $\Pe'$, и взять его в скобки: \((E^\prime)\).
     1712                $\Pe'$ и взять его в скобки: \((E^\prime)\).
    17161713        \item Если выражение $\Pe$ является объектным символом или старой
    17171714                переменной, следует просто вернуть выражение \(\Pe\).
     
    17271724Переменная $V_\diamond$ заносится в список старых переменных $\Old$.
    17281725
    1729 Перестройка ${\Pe_L : \Pe_R}$ заменяется на следующую: ${V_\diamond : \Pe_R}$
     1726Перестройка ${\Pe_L : \Pe_R}$ заменяется на следующую: ${V_\diamond : \Pe_R}$.
    17301727
    17311728\subsubsection{Формирование значений новых переменных, принадлежащих левой
     
    17391736сформировать значения всех новых переменных выражения $\Pe_L$, и в случае, когда
    17401737ответ положительный, для построения фрагмента кода императивной программы,
    1741 вычисляющего значения новых переменных выражения $\Pe_L$.
     1738%вычисляющего значения новых переменных выражения $\Pe_L$.
     1739% Не очень внятно изложен смысл последнего предложения... Как будто не хватает еще чего-то!
     1740вычисляющего эти значения.
     1741%AO: Так лучше?
    17421742
    17431743Следующий рекурсивный алгоритм генерирует фрагмент кода императивной программы,
    1744 осуществляющий построение значения переменной $V$, а также всех объектных
     1744осуществляющий построение значения новой переменной $V$, а также всех объектных
    17451745выражений и значений других новых переменных, необходимых для этого.
    17461746Если, исходя из текущего набора старых переменных $\Old$ и имеющихся
     
    18061806                заканчивается неудачей.
    18071807\end{algo}
    1808 
    1809 Для того, чтобы выражение $\Pe_L$ не содержало новых переменных, достаточно
     1808%Если фраза "`Для того чтобы"' стоит впереди, то перед "`чтобы"' запятая не нужна. Это единый блок.
     1809%AO: Ясно, спасибо! ;-)
     1810Для того чтобы выражение $\Pe_L$ не содержало новых переменных, достаточно
    18101811запустить приведенный алгоритм для всех новых переменных, содержащихся в
    18111812$\Pe_L$.  Если для какой-то из этих переменных работа алгоритма закончится
     
    20202021
    20212022Алгоритм \EqA{} анализа системы уравнений $\Seq$, соответствующей цепочке $\Scl$,
    2022 строит только условия на подстановки $\sigma_i$ \emph{необходимые}, для того,
     2023строит только условия на подстановки $\sigma_i$ \emph{необходимые} для того,
    20232024чтобы $\sigma_i$ принадлежали решению $\Scl$ (см.~теорему~\ref{thm:sys}
    20242025и~алгоритм~\EqA, раздел~\ref{sec:EqA}).
     
    20642065решении цепочки, полученной переносом перестройки ${\Pe_L : \Pe_R}$ в начало.
    20652066
    2066 Значит существуют две такие переменные $V_1$ и $V_2$, что:
     2067Значит, существуют две такие переменные $V_1$ и $V_2$, что:
    20672068\begin{itemize}
    20682069\item $V_1/\sigma_1 < V_1/\sigma_2$,
     
    23462347Проблема в том, что свободные переменные $X_5$ и $X_6$ входят в последнее
    23472348уравнение группы одновременно, однако ограничения на них генерируются
    2348 независимо.  В данном конкретном случае, достаточно было бы после получения на
     2349независимо.  В данном конкретном случае достаточно было бы после получения на
    23492350свободные переменные нетривиальных ограничений снизу, еще раз вычислить
    23502351ограничения на них сверху, исходя из последнего уравнения.
Note: See TracChangeset for help on using the changeset viewer.