Автоматическая разметка оптимизируемых функций

[Mazdaywik]

Мотивация

В своём недавнем письме в рассылку я привёл пример того, как в Рефале-5λ можно осуществить первую проекцию Футамуры. В письме приведён пример интерпретатора стекового языка программирования и оптимизированная программа в псевдокоде. Программа содержит более трёх десятков специализированных функций, большинство из которых транзитные и могут быть встроены (inline).

Встроить их компилятор не может, поскольку они не помечены как встраиваемые. Пользователь не может задать атрибут $INLINE, поскольку функции создаются компилятором. Таким образом, при оптимизации могут создаваться функции, которые можно снова оптимизировать.

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

Может показаться, что пример с первой проекцией искусственный. Но есть и «естественные» примеры. Например, функцию DoMapAccum-Aux@N во многих случаях можно встроить. Рассмотрим пример: функцию отделяющую овец от козлов:

$INCLUDE "LibraryEx";

/**
  <Separate t.Animal*> == (t.Sheep*) t.Goat*

  t.Animal ::= (Sheep t.Sheep) | (Goat t.Goat)
*/
$ENTRY Separate {
  e.Animals
    = <MapAccum
        {
          (e.Sheeps) (Sheep t.Sheep) = (e.Sheeps t.Sheep);

          (e.Sheeps) (Goat t.Goat) = (e.Sheeps) t.Goat;
        }
        (/* sheeps */) e.Animals
      >;
}

Преобразованная программа будет иметь вид:

$ENTRY Separate {
  e.Animals#1 = <MapAccum@1 () e.Animals#1>;
}

MapAccum@1 {
  t.Acc#1 e.Tail#1 = <DoMapAccum@1 t.Acc#1 e.Tail#1 ()>;
}

DoMapAccum@1 {
  (e.#0) (Sheep t.0#0) e.Tail#1 (e.Scanned#1)
    = <DoMapAccum-Aux@1 e.Tail#1 (e.Scanned#1) ((e.#0 t.0#0))>;

  (e.#0) (Goat t.0#0) e.Tail#1 (e.Scanned#1)
    = <DoMapAccum-Aux@1 e.Tail#1 (e.Scanned#1) ((e.#0) t.0#0)>;

  t.Acc#1 t.Next#1 e.Tail#1 (e.Scanned#1)
    = <DoMapAccum-Aux@1
        e.Tail#1 (e.Scanned#1) (<Separate\1*2 t.Acc#1 t.Next#1>)
      >;

  t.Acc#1 (e.Scanned#1) = t.Acc#1 e.Scanned#1;
}

Separate\1*2 {
}

DoMapAccum-Aux@1 {
  e.Tail#1 (e.Scanned#1) (t.Acc#1 e.StepScanned#1)
    = <DoMapAccum@1 t.Acc#1 e.Tail#1 (e.Scanned#1 e.StepScanned#1)>;
}

Очевидно, в первых двух предложениях DoMapAccum@1 вызов DoMapAccum-Aux@1 можно встроить.

Кроме того, компилятор может транслировать программы, в которых в принципе нет разметки для оптимизации (например, SCP4 или MSCP-A). Но функции, пригодные для оптимизации, в них могут быть.

Задача

Задача состоит в том, чтобы добавить в оптимизатор автоматическую разметку оптимизируемых функций и дополнительный внешний цикл оптимизации. На данный момент цикл только один: выполнять проходы Simple, Drive и Spec до неподвижной точки или до исчерпания счётчика. Предлагается добавить внешний цикл, который до неподвижной точки или исчерпания счётчика добавляет разметку функций, чистит программу от мусора (#228) и выполняет внутренний цикл. Причём счётчик должен быть сквозным.

Самое интересное здесь — по каким критериям будет выполняться разметка. Разметка должна быть:

• безопасной — помеченная функция не должна приводить, например, к бесконечной прогонке, оптимизация должна терминироваться;
• сравнительно простой и эффективной — алгоритмы не должны быть запредельно сложными.

Понятно, что точная разметка представляет собой алгоритмически неразрешимую задачу, поэтому здесь нужны эвристики — критерии, хорошо работающие на практике,

Добавление меток $DRIVE

Это, как мне кажется, одно из самых простых и очевидных.

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

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

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

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

Наверное, можно подобрать и другие простые признаки прогоняемых функций. Но этих, как мне кажется, на практике достаточно.

Добавление меток $INLINE

Встраивание слабее прогонки, и поэтому, как ни парадоксально, признаки встраиваемых функций сложнее признаков прогоняемых.

Вообще, каким функциям стоит вешать метку $INLINE? Во-первых, тем функциям, чьи вызовы могут быть вычислены во время компиляции. Во-вторых, тем функциям, которым нельзя приписать метку $DRIVE. Ведь если функцию можно прогонять, зачем себя ограничивать встраиванием?

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

Eval {
  s.Num = s.Num;
  (t.X '+' t.Y) = <Add <Eval t.X> <Eval t.Y>>;
  (t.X '*' t.Y) = <Mul <Eval t.X> <Eval t.Y>>;
}

Apply {
  s.Func e.Arg = <s.Func e.Arg>;
  (t.Func e.Bound) e.Arg = <Apply t.Func e.Bound e.Arg>;
}

Eval принимает единственный терм (её формат можно описать как <Eval t.Expr>) и вызывает себя рекурсивно с частями этого терма. Apply вызывает себя рекурсивно с частью первого терма аргумента.

Соответственно, метку $INLINE нужно давать рекурсивным функциям, которые в один из своих аргументов передают часть этого же аргумента. Для этого нужен механизм вывода входного формата функции и дальнейшая проверка, как функция распоряжается аргументами. Вывод типов можно организовать простейший: ГСО от образцов.

Что делать со взаимно-рекурсивными функциями, пока не понятно (upd: см. про $SPEC ниже). Можно ограничиться только непосредственной рекурсией.

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

Заметим, что если будет реализована разметка неразменных аргументов (#231), то аргументы, значение которых уменьшается на каждом шаге рекурсии должны быть помечены как неразменные.

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

Добавление меток и шаблонов $SPEC

Когда функцию разумно объявлять специализируемой? Когда она рекурсивна и один или несколько аргументов на рекурсивных вызовах не меняются. При этом желательно, чтобы фактическое значение константного аргумента было чем-то интересно и при его фиксации в теле функции можно было выполнить дополнительные преобразования. Но это уже неочевидная семантика. А неизменность аргумента на рекурсивном вызове — критерий синтаксический.

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

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

Предложенный алгоритм не будет работать со взаимно-рекурсивными функциями, поэтому пару DoMapAccum + DoMapAccum-Aux он не распознает. Возможно, стоит продумать расширение на такой случай.

Для взаимно-рекурсивных функций можно строить что-то вроде дерева процессов. В корень поместить одну из функций, для каждого рекурсивного вызова построить рёбра, спускаться вниз, пока не встретим функцию из корня. В ней анализировать свойства аргументов. Если аргумент не изменил своего значения на всём пути — он статический для специализации. Если в аргумент дошла только часть его же самого — он неразменный для встраивания.

В корень по идее можно помещать всё, что угодно. Но разумнее помещать точку входа компоненты сильной связанности — функцию, которая вызывается извне. Если таковых несколько — одну из. Чисто из эстетических соображений.

Нюанс: функция встраиваемая и специализируемая одновременно

Алгоритм выше может пометить функцию и как встраиваемую, и как специализируемую одновременно. За примером далеко ходить не надо:

* <Map t.Func e.Items> == e.Res
Map {
  t.Func t.Next e.Rest = <Apply t.Func t.Next> <Map t.Func e.Rest>;
  t.Func /* empty */ = /* empty */;
}

Первый аргумент константен, по нему можно специализировать. Второй аргумент уменьшается, по нему можно встраивать. (Действительно, почему бы не встроить этот вызов?

<Map { t.X = (t.X) } A B C>

Он тогда сможет полностью просчитаться во время компиляции в (A) (B) (C).)

Что делать в случае такой разметки? Пытаться встроить, пока функция встраивается. Если не встраивается — пытаться проспециализировать. К слову, ответ на один из вопросов в #229.

Выводы

Детали, конечно, нужно уточнять. Но фронт работ нарисован довольно чётко.

[Mazdaywik]

Прекрасная задача для исследования в рамках образовательного процесса!

В рамках курсовой работы нужно будет научиться распознавать рекурсивные, взаимно-рекурсивные и нерекурсивные функции и на основе этого развешивать метки $DRIVE.

На ВКР можно будет вынести всё остальное.

Почему так? Потому что все три разметки ($DRIVE, $INLINE и $SPEC) требуют знания «рекурсивности» функций. Но при этом только расстановка меток $DRIVE делается непосредственно на основе графа вызовов. Остальные требуют дополнительного анализа.

Поэтому построение графа вызовов (или иной способ определения «рекурсивности») и непосредственно из него следующую разметку $DRIVE логично выделить в первый этап. Остальное (выделение форматов функций и анализ свойств аргументов) — во второй.

[Mazdaywik]

Задача не была выбрана в качестве курсовой.

[Mazdaywik]

Некоторые важные соображения и уточнения

Уточним определения.

• Разметка является корректной, если она не нарушает инвариантов. В данном случае инварианты следующие:
  • метки (Inline …), (Drive …), (Spec …), добавляемые в синтаксическое дерево, должны ссылаться на существующие функции;
  • шаблон в (Spec …) должен согласовываться с определением функции — все образцы предложений являются его уточнениями, статические параметры в них отображаются на переменные того же типа;
  • метки (Spec …) нельзя назначать функциям с суффиксами — актуальная версия специализатора такого не поддерживает.
• Разметка оптимизируемых функций является безопасной, если она не приводит к зацикливанию оптимизатора.
• Разметка является избыточной, если она помечает функции, которые прогонщик или специализатор оптимизировать не могут. Например, метка $DRIVE для функции с не-L-образцами..

Цель работы: реализовать корректную и безопасную разметку, при этом избыточность допустима.

С некорректной разметкой компилятор просто будет неработоспособен.

С небезопасной — будет зацикливаться. На самом деле, оптимизатор всегда делает конечное число проходов — максимальное их количество задаётся параметром --opt-tree-cycles=N и по умолчанию равно 100. Но, если разметка будет неправильной (небезопасной), то все эти 100 итераций будут выполняться совершенно бессмысленные оптимизации. И если компилятор в норме останавливается после десятка-двух проходов, то здесь он выполнит все 100 проходов, которые ничего содержательного не дадут.

Избыточная приведёт лишь к бесполезным попыткам оптимизировать те вызовы, которые оптимизировать нельзя. Неизбыточная расстановка не возможна, поскольку проблема остановки алгоритмически неразрешима. Поэтому можно лишь эту избыточность снижать (в рамках ВКР этого не требуется в принципе).

Как написано в предыдущих комментариях — расстановка меток $DRIVE выполняется в первую очередь и является обязательной, меток $SPEC и $INLINE — во вторую очередь. Причина — расстановка меток $DRIVE требует поиска сильно связанных компонент в графе вызовов и зависит только от них. Расстановка других меток требует тех же сильно связанных компонент и дополнительной логики.

Метки $DRIVE: подводные камни косвенных вызовов

Расстановка меток $DRIVE была определена так:

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

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

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

Самое интересное выделено курсивом — эту фразу нужно будет уточнить. И вот пример:

$ENTRY Test {
  e.X = <Rec &Rec e.X>;
}

Rec {
  s.Rec /* пусто */ = /* пусто */;
  s.Rec s.L e.R = <s.Rec s.Rec e.R> s.L;
}

Функция Rec на первый взгляд не является рекурсивной — в её теле нет непосредственного вызова себя. Однако, назначать ей метку $DRIVE нельзя ни в коем случае. Если в эту программу добавить $DRIVE Rec;, то оптимизатор зациклится. С числом итераций по умолчанию (100) у меня компилятор работал две минуты и построил дамп размером ≈8 Мбайт. С --opt-tree-cycles=5 он построил вот такую остаточную программу:

Функция Test в логе

$ENTRY Test {
  /* empty */ = /* empty */;
  
  s.L#1 = s.L#1;
  
  s.L#1 s.L0#1 = s.L0#1 s.L#1;
  
  s.L#1 s.L0#1 s.L1#1 = s.L1#1 s.L0#1 s.L#1;
  
  s.L#1 s.L0#1 s.L1#1 s.L2#1 e.0#0
    = <Rec &Rec e.0#0> s.L2#1 s.L1#1 s.L0#1 s.L#1;
  
  s.L#1 s.L0#1 s.L1#1 e.#0 = <* &Rec*2 &Rec e.#0*> s.L1#1 s.L0#1 s.L#1;
  
  s.L#1 s.L0#1 e.0#0 = <* &Rec*2 &Rec e.0#0*> s.L0#1 s.L#1;
  
  s.L#1 e.#0 = <* &Rec*2 &Rec e.#0*> s.L#1;
  
  e.X#1 = <* &Rec*2 &Rec e.X#1*>;
}

В чём проблема? Откуда зацикливание?

Функция Rec вызывает функцию косвенно — по указателю. А этот указатель может быть каким угодно, в том числе и на саму функцию Rec (что мы и имеем в функции Test).

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

Что делать?

Можно считать, что функция, которая осуществляет косвенный вызов, может вызывать любую функцию, но это решение построит менее точный граф. Правильнее считать, что функции, содержащие косвенный вызов, могут вызывать любую функцию, на которую в дереве берётся указатель.

Как это реализовать при построении графа? Можно ввести псевдофункцию, назвать её indirect (символом-словом, сами функции в программе представляются последовательностью литер, конфликта не будет). При обходе дерева и построении графа для каждого указателя на функцию делать стрелку от indirect к данной функции. При каждом косвенном вызове делать стрелку от вызывающей функции к indirect.

Для примера выше граф будет иметь следующие рёбра:

• 'Test' → 'Rec' (непосредственный вызов Rec из Test).
• indirect → 'Rec' (взятие указателя в функции Test).
• 'Rec' → indirect (косвенный вызов в Rec).

Таким образом, функция Rec будет взаимно-рекурсивной с indirect, а значит, не будет подлежать встраиванию.

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

Также нужно уточнить второй признак прогоняемой функции:

• она вызывается в программе ровно один раз, причём из другой функции (т.е. не является непосредственно рекурсивной), и эта функция — не псевдофункция indirect и не метатаблица (см. далее).

Смысл этого признака в том, что если функция вызывается ровно один раз, то её в точке вызова можно прогнать. А indirect — не функция, а фиктивная вершина в графе, чтобы обнаруживать неявную рекурсию.

Метафункции

Метафункции вроде Mu реализуются при помощи функций-метатаблиц (#254 — прочитать обязательно!), и функций-реализаций (__Meta-Mu), которые принимают метатаблицу, находят в ней функцию по имени и вызывают её.

Поэтому, если мы кого-то вызываем, передавая ей метатаблицу, то вызываемая функция будет из метатаблицы кого-то вызывать. Поэтому функция, содержащая указатель на метатаблицу, косвенно вызывает все функции, которые в этой метатаблице содержатся. Так что эвристика, предписывающая ставить стрелку от функции с указателем к указываемой функции не вредна в общем случае и необходима в контексте метатаблиц.

Для самих функций-метатаблиц нужно в графе строить стрелку от метатаблицы ко всем функциям внутри неё.

Как различать в дереве прямые вызовы и косвенные

• Указатель на функцию в дереве представляется как (Symbol Name e.Name).

• Вызов функции как (CallBrackets …), причём внутри скобок может быть всё, что угодно.

• Замыкание (ClosureBrackets …), первым термом всегда является указатель на функцию. В псевдокоде (выводе в лог) замыкание обозначается как {{ &Func контекст }}.

• Прямой вызов <Func …> в дереве будет виден как (CallBrackets (Symbol Name e.Name) e.Arg).

• Прямой вызов замыкания — разновидность прямого вызова функции: <{{ &Func контекст }} аргумент>.
  В дереве: (CallBrackets (ClosureBrackets (Symbol Name e.Name) e.Context) e.Arg).
  Для прямого вызова замыкания строится та же стрелка в графе, что и для обычного прямого вызова.

• Косвенный вызов < … > — содержимое (CallBrackets …) не начинается с имени функции. Для него рисуется стрелка в indirect.

• Указатель на функцию — или символ (Symbol Name e.Name) не в позиции вызова, или замыкание не в позиции вызова. В обоих случаях рисуется стрелка рисуется и из вызывающей функции, и из indirect.

Метки $SPEC: упрощение, если повезёт

Базовый вариант

В тексте заявки предлагается хитрый алгоритм для расстановки меток $SPEC и $INLINE:

• выбрать компоненту сильной связности,
• вычислить у них входные форматы, например, построив ГСО,
• выбрать одну из функций — назовём её корневой,
• начать её спекулятивное вычисление с отслеживанием трансформаций входных параметров,
• ветвь спекулятивного вычисления останавливается, когда снова вызывается корневая и срабатывает «свисток» (см. далее), либо когда вызов взаимно-рекурсивной функции не соответствует формату.

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

Детали реализации

В результате работы этого алгоритма метка ($SPEC или $INLINE) назначается только корневой функции. Для назначения меток остальным функциям компоненты сильной связности нужно либо повторить алгоритм (последние три шага) каждой из них, либо дополнительно усложнить (мне пока не очевидно как), чтобы делать всё это за один проход.

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

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

Для каждой функции мы вычислили формат.

Образец предложения является уточнением формата, т.е. для каждого параметра формата можно выделить подвыражение образца — сужение параметра. Сужение параметра может быть тривиальным — неповторной переменной того же типа, либо может быть образцом, в общем случае с переменными.

Правая часть в общем случае содержит вызовы (взаимно-)рекурсивных функций, их аргументы тоже должны соответствовать формату, иначе функции компоненты сильной связности не подлежат оптимизации. А значит можно для каждого параметра формата выделить подаргумент функции. Подаргумент может быть тривиальным — переменной того же типа, либо быть некоторым выражением.

При спекулятивном выполнении аргументы вызовов функций и значения переменных могут иметь три вида меток:

• точный стартовый параметр номер N,
• часть стартового параметра номер N,
• синтезированное значение.

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

Сопоставление выполняется так:

• Если аргумент синтезированный — то все переменные сужения становятся синтезированными.
• Если аргумент — точный стартовый параметр и сужение тривиальное, то значением переменной является точный стартовый параметр.
• Иначе — значения всех переменных — часть соответствующего стартового параметра.

Если в образце есть повторная переменная, которая получила разные значения, то ей присваивается метка синтезированного значения. 

Аргументы вызова строятся так:

• Если аргумент вызова тривиален, то он получает метку соответствующей переменной.
• Если аргумент вызова является выражением, то он получает метку синтезированного значения.

Спекулятивное вычисление начинается с вызова корневой функции, каждый параметр которой получает значение «точный стартовый параметр N», где N — его порядковый номер.

«Свисток» срабатывает, когда в ветке вычислений обнаруживается вызов функции с теми же аргументами, что и выше по дереву. Поскольку число функций конечно, число значений их аргументов тоже конечно (2×N+1 — N точных, N частей и синтезированный), то при движении по ветке рано или поздно встретим повторение.

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

• Если во всех вызовах i-м аргументом является точное значение i-го стартового параметра, то функция специализируемая ($SPEC), а i-й параметр является статическим.
• Если во всех вызовах i-м аргументом является часть i-го стартового параметра, то эта функция встраиваемая ($INLINE) [и этот параметр является разменным].

Упрощение, если повезёт

Точнее, если @koshelevandrey нас не подведёт. Актуальный алгоритм специализации может зависать — существуют рекурсивные функции, для которых он построит специализированный вариант, а в ней будет вызов, для которого будет построен ещё один специализированный вариант, и так до бесконечности.

Но в задаче #253 (над которой работает @koshelevandrey) требуется обеспечить безопасность специализации, так что специализация любой функции обязательно прервётся.

В упрощённом варианте действуем так:

• перебираем все рекурсивные функции — входящей в сильно связанные компоненты,
• вычисляем для них формат как ГСО для образцов — он будет шаблоном специализации,
• если в каждом предложении параметр формата сужается в неповторную переменную того же типа, то этот параметр статический.

Такая разметка будет избыточной, но в силу безопасности специализации (#253), она будет безопасной.

UPD 11.05.2020

Специализировать можно не только рекурсивные, но и вообще все функции, нерекурсивные тоже. Более того, специализация нерекурсивных функций безопасна: на них по определению оптимизатор не может зациклиться.

И более того, она полезна: будет способствовать распространению информации (см. #160).

Ещё интересный пример:

$EXTERN H;

F {
  s.FnTrue s.FnFalse e.Arg (e._ True e._) = <s.FnTrue e.Arg>;
  s.FnTrue s.FnFalse e.Arg (e._) = <s.FnFalse e.Arg>;
}

G {
  e.Arg = <F &Begin &End e.Arg (<H e.Arg>)>
}

Begin { t.Begin e._ = t.Begin }
End { e._ t.End = t.End }

Очевидно, функции Begin и End получат метку $DRIVE, т.к. нерекурсивные. Функция F тоже. Но её вызов прогнать нельзя: невозможно применить сужение к вызову функции. А вот специализировать вызов можно.

Для функции вычислится шаблон

$SPEC F s.S1 s.S2 e.S3 (e.d4);

Параметры s.S1, s.S2, e.S3 во всех предложениях соответствуют переменным того же типа, поэтому статические. Параметр e.d4 в первом предложении соответствует выражению — динамический.

Специализация вызова даст

G {
  e.Arg = <F@1 e.Arg (<H e.Arg>)>
}

F@1 {
  e.Arg (e._ True e._) = <Begin e.Arg>;
  e.Arg (e._) = <End e.Arg>;
}

А тут уже функции Begin и End вызываются. Их можно прогнать:

F@1 {
  t.1 e._ (e._ True e._) = t.1;
  e._ t.2 (e._) = t.2;
}

(В примерах для наглядности я опускал аварийные предложения. Если этот пример запустить в компиляторе, то оптимизированная программа будет несколько сложнее.)

Поэтому нужно

• (а) назначать метки $SPEC всем функциям, для которых допустима прогонка,
• (б) когда @koshelevandrey реализует остановку рекурсивной специализации, можно будет назначать метки $SPEC всем непустым функциям программы.

План такой

• Делаем разметку для прогонки и специализации функций, для которых безопасна прогонка.
• Если к этому моменту будет работать остановка специализации (Останавливать специализацию по отношению Хигмана-Крускала #253), хотя бы в неполном варианте (без обобщений), то делаем разметку для специализации всех функций.
• Если не будет работать остановка специализации, то смотрим по обстоятельствам — скорее всего, ограничиваемся одной прогонкой.