%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% <<СА: 21.11.2000 12:00 Зачаточное описание алгоритма компиляции фрагмента RefalResExp : RefalPattern, ... и далее ... =========================================== Терминология и введение: ======================== T1. Элементарные куски образца ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Для кусочков RefalPattern будем использовать такие термины и обозначения (местами отличные от принятых в классических публикациях): -1- zI константные (непустые ;-) подвыражения максиамльной длины /* длина L_zI известна даже в compile time */; z :: Const_Symbol | z1 ... zN | (z) Слова максимальной длины надо понимать так, что при разборе образца на кусочки, куски вида zI набираются максимально длинными. Образец вида: A B C e1 это кусок (z1=A B C) с длинной 3 и кусок e1. -2- (RefalPattern') (краткое обозначение: bI) термы вида (RefalPattern') /* длина = 1 */; -3- sI, tI (общее обозначение: yI) новые s/t-переменныe /* длина = 1 */; -3- sOld_I, tOld_I (общее обозначение: yOld_I) старые (повторные) s/t-переменныe /* длина = 1 */; Понятие новая/старая s/t-переменная для рассматриваемого алгоритма то же самое, что было в предыдущих алгоритмах (для e/v- переменных это не так). -4- еOld_I, vOld_I (общее обозначение: xOld_I) Новый термин: совсем старые e/v-переменных, то есть, е/v-переменные, которые уже "к подходу" к компилируемому фрагменту имели значения /* длина L_Old_I известна в run-time уже к подходу к образцу */. Пояснение: в новой терминологии в образце еSrc : e1 e1, либо обе переменные е1 "совсем старые": еSrc : eOld_1 eOld_1, либо они обе не "совсем старые" еSrc : e1 e1, Tогда можно говорить, что первая--открытая, вторая--повторная, но обе они не "совсем старая". И более того, более правильно именно для данного образца их называть псевдо-закрытые переменные---их длина вычисляется прямым вычислением за счет решения простенького уравнения (если оно имеет решение, конечно). -5- еI, vI (общее обозначение: xI) не совсем старые e/v-переменные; Их длина "вычисляется" (либо в итерации--для открытых переменных, либо прямым вычислением--для закрытых переменных, либо за счет решения простенького уравнения--для псевдо-закрытых переменных: е.Src : A e1 B e1 C e1 D ==> if ((L_Src-4) % 3) goto <>; L_x1 = (L_Src-4) / 3; В любом случае, их длина подчиняется закону (если нарушен ==> goto <>): L_xI >= minI, где minI = 0, в случае e-переменной eI, minI = 1, в случае v-переменной vI. T.2 Более крупные куски образца и образец в целом ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ В этих терминах, каждый образец на верхнем уровне скобочной структуры имеет вид: * фрагмент с заведомоизвестной (known) длиной L_kI: kI = { zI | pI | sI | tI | eOldI | vOldI }* * образец в целом: RefalPattern :: k1 | k0 x1 kI x2 ... xN kN Первый случай можно назвать "жесткий по длине образец" (длина образца вычисляется к моменту "подхода" к компилируемой перестройки). Второй случай: "образец с вычисляемыми (подбираемыми) длинами e/v-переменных". T.3 Правая часть ~~~~~~~~~~~~~~~~~ При компиляции фрагмента RefalResExp : RefalPattern, ... и далее ... будем считать, что: * значение левой части посчитано в eSrc, длина значения посчитана в L_Src. * текущая метка, куда надо перейти в случае неудачи: <>; Алгоритм компиляции =================== ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ А1. "Жесткий" по длине образец (не путать с жестким образцом) Безвариантное отождествление ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ То есть, все компоненты в образце (на верхнем скобочном уровне) имеют предопределенные длины, то есть образец (на верхнем уровне) выглядит как: RefPattern :: k1 .... kN где kI имеет вид kI :: zI | (RefalPattern'I) | sI | tI | sOld_I | tOld_I | eOld_I | vOld_I Длина L_I каждого куска и индекс i_I его первого терма в значении eSrc может быть посчитана к моменту подхода к компиляции конструкции: RefalResExp : RefalPattern, ... и далее ... по следущим правилам: Если kI имеет вид ==> то ------------------------------------------------ zI ==> int L_I = константа, i_I = i_(I-1) + L_(I-1); (RefalPattern'I) ==> int L_I = 1, i_I = i_(I-1) + L_(I-1); sI, tI, sOld_I, tOld_I==> int L_I = 1, i_I = i_(I-1) + L_(I-1); eOld_I, vOld_I==> int L_I = length(kI),i_I = i_(I-1) + L_(I-1); ------------------------------------------------ /* Здесь, L_(-1) = i_(-1) = 0; */ Общая длина образца ==> int L_Pat = i_N+L_N; Компилируем вот такой код: ////////////////////////////////////////////////////////////// << заведение и подсчет всех int L_I = ..., i_I = ..., L_Pat = ...; описано выше >> if (L_Src != L_Pat) goto <>; << N-фрагментов кода вида: откусывание и доп. проверка для k_I >> << Компилируем все запомненные под-перестройки, если они есть --- см. чуть ниже, отмечено !!!, затем компилируем фрагмент "...и далее..." >> \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ где откусывание и доп. проверка для k_I -- это такой код: -------------------:--------------------------------------------------- k_I имеет вид : Код -------------------:--------------------------------------------------- zI, sOld_I, tOld_I,: if (!(is_equal_exp( k_I, subexp(eSrc, i_I, L_I)))) eOld_I, vOld_I : goto <>; -------------------:--------------------------------------------------- tI : rterm tI = subexp(eSrc, i_I, L_I); -------------------:--------------------------------------------------- sI : rterm sI = subexp(eSrc, i_I, L_I); : if (!(is_symbol(sI))) : goto <>; -------------------:--------------------------------------------------- (RefalPattern'I) : rterm tTmp = subexp(eSrc, i_I, L_I); : if (is_symbol(sI)) : goto <>; : rexpr eSrcTmp_I = unBracket(tTmp); !!! : << действие в компиляторе: запоминаем, что надо !!! : еще будет компилировать под-перестройку: !!! : eSrcTmp_I : RefalPattern'I; !!! : >> -------------------:--------------------------------------------------- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ А2. Образец начинается и/или заканчивается непустыми фрагмнетами известной длины Порождение безвариантных отождествлений ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Tо есть образец (на верхнем уровне) выглядит как: RefPattern :: k1 .... kN RefPattern' k'1 .... k'M и N+M > 0. Как это описано выше, подсчитываем для k1 .... kN и для k'1 .... k'M их длины L_N, L_M. Компилируем вот такой код: ////////////////////////////////////////////////////////////// /* проверка длины */ if (L_Src < (L_N+L_M+ <> )) goto <>; rexp eSrc_Left = subexp(eSrc, 0, L_N); rexp eSrc_Middle = subexp(eSrc, L_N, (L_Src-L_M-LN)); rexp eSrc_Right = subexp(eSrc, (L_Src-L_M-1), L_M); !!!<< действие в компиляторе: запоминаем, что надо !!! еще будет компилировать под-перестройки: !!! eSrc_Left : k1 .... kN, !!! eSrc_Middle : RefPattern', !!! eSrc_Right : k'1 .... k'M !!!>> << Компилируем все запомненные под-перестройки, если они есть, затем компилируем фрагмент "...и далее..." >> \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ Примечание: как в компиляторе выписывается минимально допустимая длина образца <> --будет описано далее. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (А3.) Образец начинается с не совсем старой e/v-переменной, заканчивается не совсем старой e/v-переменной: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ RefalResExp : x1 RefalPattern xN Разбирая верхний уровень правой части, мы можем записать слагаемые длин правой части: RefalResExp : x1 k1 x2 k2 ... kn x(n+1) длина?: ? L1 ? L2 ....Ln ? Обозначим слагаемые длин: ------------------------- Lxi -- для e/v-переменных, которые >>не совсем старые<< -- то есть не известны до начала работы данной перестройки; Ci -- кратность, с которой xi входит в образец; Lj -- длины фрагментов kJ, которые >>известны<< до начала работы данной перестройки. Тогда мы получим простое (диафантово? ;-) уравнение на длины x1 ... xK всех не совсем старых е/v-переменных: C1*Lx1 + C2*Lx2 + C3*Lx3 + ... + CK*LxK = L где L = L_Src - L1 - ... Ln с доп. ограничениями: LxI >= minI где minI = 0, в случае e-переменной eI; minI = 1, в случае v-переменной vI. Обратите внимание: >>вхождений<< не совсем старых переменных--N, но это могут быть повторные вхождения... Число K >>разных<< не совсем старых переменных может и меньше чем N (K <= N) за счет повторных вхождений (Ci>1). Ну, и теперь пытаемся компилировать (для разных случаев): ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (А3.1) Случай К=1. Образец начинается с не совсем старой e/v-переменной, заканчивается не совсем старой e/v-переменной, но в образце есть (на верхнем уровне скобочной структуры) ровно одна не совсем старая переменная x1 входящая возможно многократно (C1 >=1). Это случай закрытой (одна переменная) или квази-закрытой (многократные вхождения одной и той же переменной) e/v-переменной. Безвариантное отождествление ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Компиляция фрагмента RefalResExp : x1 k1 x1 k2 x1 ... x1 kn x1 ...и далее... при условии K=1 (как считается K -- см выше). Полагаем, L -- int-переменная с вычисленным (L_Src - L1 - ... Ln), min1 = 0, в случае e-переменной e1; min1 = 1, в случае v-переменной v1. Система уравнений/неравенств на длины у нас имеет вид: C1*Lx1 = L; Lx1 >= minI Компилируем вот такой код: ////////////////////////////////////////////////////////////// rexp x1; /* e/v-переменная */ int Lx1; /* ee длина */ rexp eSrcTail; ? if (L%C1) /* если не делится на C1 */ ? goto <>; ? Lx1 = L / C1; ? if (Lx1>; x1 = subexp(eSrc,0,L_x1); eSrcTail = subexp(eSrc, L_x1, (L_Src-L_x1)); !!!<< действие в компиляторе: запоминаем, что надо !!! еще будет компилировать под-перестройку: !!! !!! eSrcTail : k1 x1 k2 x1 ... x1 kn x1, !!! !!! при этом x1 -- уже старая переменная с длиной Lx1 >> << Компилируем все запомненные под-перестройки, если они есть, затем компилируем фрагмент "...и далее..." >> \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ Примечания к реализации: Если мы не доверяем оптимизирующим свойствам gcc, то строки, помеченные "?" надо >>особо<< генерировать для случая C1==1 (не генерировать 1..2, упростить 3) и min1=0 (не генерировать 4..5). ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (А3.2) Случай: К>1 Итерационное (многовариантное) отождествление. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Компиляция фрагмента, RefalResExp : x1 RefalPattern xN, ...и далее... при условии K>1 (как считается K -- см выше). Полагаем, что L -- int-переменная с вычисленным (L_Src - L1 - ... Ln), minI = 0, в случае e-переменной eI, minI = 1, в случае v-переменной vI, I=1,...,K. Система уравнений/неравенств на длины имеет вид: C1*Lx1 + C2*Lx2 + C3*Lx3 + ... + CK*LxK = L LxI >= minI (I=1,...K) Первое уравнение можно переписать так: C1*Lx1 = L - (C2*Lx2 + C3*Lx3 + ... + CK*LxK) Посему, длина максимальная для x1 будет: L_ / C1, где L_ = L - (C2*min2 + C3*min3 + ... + CK*minK) длина минимальная -- min1. Компилируем вот такой код: ////////////////////////////////////////////////////////////// rexp x1; /* e/v-переменная */ int L_x1, L_ = L - (C2*min2 + C3*min3 + ... + CK*minK), /* круглые скобки есть константа, считаемая в compile-time */ L_min_x1 = min1, ? L_max_x1 = L_ / C1; << Действие в компиляторе: Push(current_label_if_fail, "increment_x1"); >> for(L_x1 = min1; L_x1 <= L_max_x1; L_x1++) { x1 = subexp(eSrc,0,L_x1); eSrcTail = subexp(eSrc, L_x1, (L_Src-L_x1)); !!! << действие в компиляторе: запоминаем, что надо !!! еще будет компилировать под-перестройку: !!! !!! eSrcTail : RefalPattern xN, !!! !!! при этом x1 -- старая переменная с длиной L_x1 !!! >> << Компилируем все запомненные под-перестройки, если они есть, затем компилируем фрагмент "...и далее..." >> increment_x1: /* метка перехода в случае fail */; }; << Действие в компиляторе: Pop(current_label_if_fail); >> /* не смогли подобрать длину! */ goto <>; \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ Примечания к реализации: Если мы не доверяем оптимизирующим свойствам gcc, то строку, помеченную "?" надо особо генерировать (упростить) для случая C1==1. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (A.4) Реализация действия <<Компилируем все запомненные под-перестройки, если они есть>> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Как видно выше, при компиляции перестройки могут возникать "под- перестройки", которые надо компилировать... Они при этом куда-то заносятся (в хранилище) при помощи: !!! << действие в компиляторе: запоминаем, что надо !!! еще будет компилировать под-перестройку: !!! .... !!! >> Для корректной реализации открытых переменных (чем вхождение правее, тем переменная короче) это место (хранилище) должно обладать порядком (слева-направо). И для первой, не вполне эффективной реализации, наверноее, и следует всегда выбирать самую левую подперестройку и ее сыновей-под-перестройки, записывать в ее позицию... Однако, как мне кажется, КООРЕКТНО (проверьте меня!) и более эффективности с этим хранилищем под-перестроек действовать вот так: при реализации действия <<Компилируем все запомненные под-перестройки, если они есть>>: ==> Выбор из хранилища, кого дальше будем компилировать? ---------------------------------------------------- о Если есть под-перестройка с безвариантным отождествлением (все случаи, кроме А3.2), то именно ее выбираем на компиляцию (наплевать на порядок), но запоминаем позицию, откуда ее выбрали. о Если все подперестройки вида А3.2 (итерационное, многовариантное отождествление) -- выбираем самую левую под-перестройку, и запоминаем позицию, откуда ее выбрали. ==> Запись в хранилище порожденных под-перестроек --------------------------------------------- Сыновей-под-перестройки следует записывать в позицию, откуда выбиралась под-перестройка-прародитель. ==> Тип под-перестройки ------------------- При >>каждом<< выборе "кого дальше будем компилировать" тип (A1..A3.2) надо пересчитывать, так как бывшие ранее "не совсем старые e/v-переменные" при каждом новом обращении к хранилищу под-перестроек могут вполне стать совсем старыми... Пример: e.Src : e0 e1 e2 (A e1 B e1 C e1 D) ==> eSrc : eSrc1 (eSrc2), /* А2, жесткая длина справа */ еSrc2 : A e1 B e1 C e1 D, /* A3.1 квази-закрытая, безвариантная */ /* for Le0=0 to (L_Src1-L_e1) */ еSrc1 : e0 eSrc11, /* A3.2 вариантная, но верхний предел цикла ужат */ eSrc11: e1/*Old!*/ eSrc12,/* А2, жесткая длина слева */ eSrc12: e2, /* A3.1 закрытая, безвариантная */ /* end for */ Заключительное замечание ======================== Не уверен, что все написано удачно, но надеюсь, что что-то новое я сказал (как минимум: квазизакрытый случай, как обобщение закрытого случая и выписан подсчет верхнего/нижнего пределе цикла по длине открытых переменных). Не уверен, что выбранная классификация (А1..А3.2) удачна для реализации и/или изложения. Не удивлюсь, что самый оптимальный случай, это: =1= реализация эффективной стратегии с хранилищем под-перестроек (см. выше) плюс =2= иная классификация, например такая: (А0) RefPattern == /* пусто */ (A1) RefPattern == k1 RefPattern' (A2) RefPattern == RefPattern' k1 (A3) -- как описано здесь... Но сил выписать иное, чем уже выписано--не осталось... Задача для других участников ;-) СА: 21.11.2000 12:00>> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%