Forth, Рефал-5λ и первая проекция
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый день всем!
В этом послании я кратко расскажу про язык программирования Forth (его вариант), напишу простой интерпретатор Forth’а на Рефале-5λ и покажу, что новые возможности оптимизации компилятора Рефала-5λ позволяют осуществить первую проекцию Футамуры. Письмо длинное, чтобы проще было читать его по диагонали, опорные слова я выделил жирным шрифтом.
Примечание. Рассматриваемый стековый язык отличается синтаксисом от классического Форта, поэтому, строго говоря, его Фортом называть не следует. Целью этого письма является демонстрация возможностей оптимизации Рефала-5λ, для чего был выбран язык, для которого сравнительно легко написать интерпретатор.
Хочу поблагодарить своих выпускников Кирилла Ситникова и Дарью Сухомлинову, которые в своих дипломах как раз реализовали, соответственно, оптимизации встраивания/прогонки и специализации функций. Оба дипломника есть в копии письма, желательно, при ответе на письмо их там сохранять.
Язык Forth
Forth (далее я буду его называть Форт) — стековый язык программирования. Данными Форта являются числа, лежащие на стеке. Программа — последовательность команд (слов), которые этот стек модифицируют. Помимо стека интерпретатор Форта содержит словарь — хранилище определённых в программе функций. Далее мы рассмотрим основные команды Форта, которые будут использоваться в последующих примерах.
Стек Форта обычно изображает растущим слева-направо. Мы будем использовать запись вида
... x y z
для изображения стека, у которого нам интересны только три верхних элемента.
Действие команд будем изображать так:
команда: стек-до → стек-после
Простейшей командой является литерал числа. Если в программе встретилось число, то оно просто кладётся на стек:
число: ... → ... число
Поэтому, если записано несколько чисел подряд, то они кладутся на стек в том порядке, в каком перечислены. Например, программа
10 20 30
поменяет стек так:
... → ... 10 20 30
Двуместные арифметические команды снимают со стека два операнда, выполняют соответствующую операцию и кладут на стек результат:
+: ... x y → ... x+y
−: ... x y → ... x−y
*: ... x y → ... x*y
/: ... x y → ... x/y
MOD: ... x y → ... x%y
Команды манипуляции со стеком: DUP дублирует вершину стека, DROP отбрасывает вершину стека, SWAP меняет местами вершину и подвершину, OVER берёт подвершину и кладёт её на стек:
DUP: ... x → ... x x
DROP: ... x → ...
SWAP: ... x y → ... y x
OVER: ... x y → ... x y x
Команды сравнения сравнивают вершину и подвершину и кладут на стек 0, если результат ложен, и 1, если истинен. В примерах нам потребуется только сравнение на равенство:
=: ... x y → ... 1, x = y
=: ... x y → ... 0, x ≠ y
Ветвление выполняет первую ветку, если на вершине стека не ноль, вторую, если ноль. Последующая запись будет напоминать денотационную семантику:
if (on-true) else (on-false): stack x → stack′, x ≠ 0
if (on-true) else (on-false): stack 0 → stack″
---------------------------------------------------------
on-true: stack → stack′
on-false: stack → stack″
Здесь on-true и on-false некоторые последовательности команд. В классическом стеке скобок нет, вместо них пишется IF … ENDIF или IF … ELSE … ENDIF, здесь для удобства разбора мы ввели скобки.
Печать вершины стека осуществляет команда «точка». Она эквивалентна команде DROP, снимаемое число при этом выводится на экран:
.: ... x → ...
Определение функции стек не меняет, функция добавляется в словарь:
define FuncName (body): ... → ...
Здесь FuncName — слово, body — последовательность команд. В классическом стеке определение функции тоже записывается без скобок, начинается с двоеточия и заканчивается точкой с запятой:
: FuncName … ;
Вызов функции. Если очередное слово не является числом или встроенной командой Форта, то в словаре ищется функция с заданным именем:
FuncName: stack → stack′
---------------------------
body: stack → stack′
Запись означает, что эффект применения FuncName эквивалентен эффекту применения команд тела этой функции.
Пример. Вычислим факториал наибольшего общего делителя 30 и 48:
\ Fact: ... n → ... n!
define Fact (
DUP 0 = if (
DROP 1
) else (
DUP 1 − Fact *
)
)
\ Gcd: ... x y → ... gcd
define Gcd (
OVER 0 = if (
SWAP DROP
) else (
OVER MOD SWAP Gcd
)
)
30 48 Gcd Fact .
Рассмотрим функцию факториала. Если на вершине стека лежит ноль, то он снимается со стека и вместо него кладётся 1. Иначе число на стеке удваивается, из вершины вычитается 1, рекурсивно вызывается факториал, число и факториал предыдущего числа перемножаются.
DUP 0 = копирует вершину стека и сравнивает её с нулём. Вместо неё, конечно, можно было записать просто DUP и поменять местами ветки if и else, но я решил для наглядности выделить сравнение.
Функция наибольшего общего делителя немного сложнее. Если подвершина стека равна нулю, то результатом функции является содержимое вершины стека. Для этого нужно поменять вершину с подвершиной местами (SWAP) и бывшую подвершину стереть (DROP). Иначе, мы заменяем вершину стека на её остаток деления на подвершину, меняем местами аргументы и рекурсивно вычисляем наибольший общий делитель.
Интерпретатор на Рефале
Очевидно, для такого языка несложно написать интерпретатор на Рефале. Вот его полная реализация на Рефале-5λ:
$ENTRY Go {
= <Forth
define Fact (
DUP (0) '=' if (
DROP (1)
) else (
DUP (1) '-' Fact '*'
)
)
define Gcd (
OVER (0) '=' if (
SWAP DROP
) else (
OVER MOD SWAP Gcd
)
)
(6) Fact '.'
(30) (48) Gcd '.'
(30) (48) Gcd Fact '.'
>
}
$INLINE Forth;
Forth {
e.Program = <Loop /* пустой стек */ (e.Program) (/* пустой словарь */)>;
}
$SPEC Loop e.stack (e.CODE) (e.DICT);
Loop {
e.Stack (e.Code_) (e.Dict)
, e.Code_
: {
/* empty */ = e.Stack;
DUP e.Code
= e.Stack : e.Stack^ t.Top
= <Loop e.Stack t.Top t.Top (e.Code) (e.Dict)>;
DROP e.Code
= e.Stack : e.Stack^ t.Top
= <Loop e.Stack (e.Code) (e.Dict)>;
SWAP e.Code
= e.Stack : e.Stack^ (e.X) (e.Y)
= <Loop e.Stack (e.Y) (e.X) (e.Code) (e.Dict)>;
OVER e.Code
= e.Stack : e.Stack^ (e.X) (e.Y)
= <Loop e.Stack (e.X) (e.Y) (e.X) (e.Code) (e.Dict)>;
'-' e.Code
= e.Stack : e.Stack^ (e.X) (e.Y)
= <Loop e.Stack (<Sub (e.X) e.Y>) (e.Code) (e.Dict)>;
'*' e.Code
= e.Stack : e.Stack^ (e.X) (e.Y)
= <Loop e.Stack (<Mul (e.X) e.Y>) (e.Code) (e.Dict)>;
MOD e.Code
= e.Stack : e.Stack^ (e.X) (e.Y)
= <Loop e.Stack (<Mod (e.X) e.Y>) (e.Code) (e.Dict)>;
(e.Const) e.Code = <Loop e.Stack (e.Const) (e.Code) (e.Dict)>;
'.' e.Code
= e.Stack : e.Stack^ (e.Top)
= <Prout e.Top>
<Loop e.Stack (e.Code) (e.Dict)>;
'=' e.Code
= e.Stack
: {
e.Stack^ (s.Eq) (s.Eq) = e.Stack (1);
e.Stack^ (s.X) (s.Y) = e.Stack (0);
}
: e.Stack^
= <Loop e.Stack (e.Code) (e.Dict)>;
if (e.True) else (e.False) e.Code
, e.Stack
: {
e.Stack^ (0)
= <Loop
<Loop e.Stack (e.False) (e.Dict)>
(e.Code) (e.Dict)
>;
e.Stack^ (e.NotZero)
= <Loop
<Loop e.Stack (e.True) (e.Dict)>
(e.Code) (e.Dict)
>;
};
define e.Code
= <TransferBodyToDict e.Code (e.Dict)> : e.Code^ (e.Dict^)
/* Функция TransferBodyToDict нужна, чтобы избежать зацикливания */
= <Loop e.Stack (e.Code) (e.Dict)>;
s.Callee e.Code
= <Loop
<Loop e.Stack (<Lookup s.Callee e.Dict>) (e.Dict)>
(e.Code) (e.Dict)
>;
};
}
$INLINE TransferBodyToDict, Lookup;
TransferBodyToDict {
s.FuncName (e.Body) e.Code (e.Dict) = e.Code ((s.FuncName e.Body) e.Dict);
}
Lookup {
s.Func (s.Func e.Code) e.Dict = e.Code;
s.Func (s.OtherFunc e.Code) e.Dict = <Lookup s.Func e.Dict>;
}
Напомню, что символ ^ означает объявление новой переменной, скрывающей предыдущую одноимённую переменную. Запись
… e.X …, e.X Foo : e.X^, (e.X e.X) : e.X^ = … e.X …
означает примерно это
… e.X …, e.X Foo : e.X¹, (e.X¹ e.X¹) : e.X² = … e.X² …
Конструкция = R : P называется «присваивание» и отличается от условия , R : P тем, что сопоставление с образцом обязано выполняться. Если сопоставление невозможно, то программа вылетает с ошибкой. Например:
DUP e.Code
= e.Stack : e.Stack^ t.Top
= <Loop e.Stack t.Top t.Top (e.Code) (e.Dict)>;
означает, что на вершине стека должен быть как минимум один элемент. Если стек пустой — программа упадёт. Вообще, в интерпретаторе никакого внимания обработке ошибок не уделяется, в частности, если вызывается неопределённая функция, Lookup упадёт. Если в предложении с DUP присваивание заменить на условие, то для пустого стека будут выполняться последующие предложения.
В случае пустого стека интерпретатор просто возвращает стек. Команды DUP, DROP, SWAP, OVER и арифметические команды реализованы довольно очевидно. Оператор if-else рекурсивно вызывает интерпретатор для обработки ветвей. Также рекурсивно вызывается интерпретатор в последнем предложении для пользовательской функции. Числа для удобства разбора написаны как выражения в скобках. Во-первых, чтобы их можно было отличать от команд простым сопоставлением с образцом, во-вторых, числа в Рефале-5(λ) могут представляться как цепочки макроцифр. Если цифры отличать от других команд по типу (функция Type), то программа оптимизироваться не сможет, поскольку для оптимизатора функция Type — просто неизвестная внешняя функция.
Обработку define хотелось бы написать так:
define s.FuncName (e.Body) e.Code
= <Loop e.Stack (e.Code) ((s.FuncName e.Body) e.Dict)>;
но при этом оптимизатор-специализатор зацикливается, далее объясню, почему.
Первая проекция Футамуры
Директива $INLINE помечает встраиваемые функции — функции, которые должны заменяться результатом своего вычисления, если этот результат однозначен при любых значениях переменных аргумента вызова. В частности, оптимизатор заменит в функции Go вызов <Forth …> на вызов <Loop …>.
Директива $SPEC описывает шаблон специализации (инстанцирования) функции Loop. Переменные в шаблоне, записанные с большой буквы, являются статическими, с маленькой буквы динамическими. Для каждого вызова специализируемой функции (здесь это Loop) компилятор будет создавать новую функцию, которая учитывает вид статических параметров аргумента. Статическими параметрами функции Loop являются код программы и содержимое словаря. Поэтому для всех возможных значений этих параметров компилятор построит специализированные версии этих функций.
Во-первых, будет построен специализированный вариант функции Loop, вызываемой в Go (после встраивания вызова Forth) и все последующие вызовы. Во-вторых, сама функция Loop тоже будет оптимизирована — рекурсивные вызовы в ней также будут подвергаться специализации. В третьих будет специализирован вызов Loop в функции Forth — создан новый экземпляр, который учитывает первый вызов с пустым словарём. Нас будет интересовать только вызов из функции Go.
Вернёмся к define. Если бы мы написали его обработку как в примере выше, то компилятор построил бы специализированный вариант, учитывающий, что словарь имеет вид (s.F e.B) e.D. В новой специализируемой функции опять встретилось бы это предложение и в нём был бы построен специализированный экземпляр для словаря вида (s.F1 e.B1) (s.F e.B) e.D. На следующей итерации — (s.F2 e.B2) (s.F1 e.B1) (s.F e.B) e.D и так далее. Компилятор по умолчанию делает 100 итераций, а значит, было бы построено 100 функций со специализированными вариантами словаря. Это глупо, поэтому приходится делать обходной манёвр, чтобы статический параметр e.DICT получал переменную общего вида. Некрасиво, но таковы ограничения текущей версии.
На первый взгляд, программа написана очень коряво. Куда естественнее было бы написать её на Рефале вот так:
Loop {
e.Stack (/* пусто */) (e.Dict) = e.Stack;
e.Stack t.Top (DUP e.Code) (e.Dict)
= <Loop e.Stack t.Top t.Top (e.Code) (e.Dict)>;
e.Stack t.Top (DROP e.Code) (e.Dict)
= <Loop e.Stack (e.Code) (e.Dict)>;
e.Stack (e.X) (e.Y) (SWAP e.Code) (e.Dict)
= <Loop e.Stack (e.Y) (e.X) (e.Code) (e.Dict)>;
...
}
Так и есть, программа написана коряво. Ограничение связано с возможностями оптимизатора.
Во-первых, статические параметры в шаблоне специализации (инстанцирования) функции должны соответствовать переменным того же типа в каждом предложении. Поэтому статический параметр e.CODE не может в предложении отображаться в DUP e.Code. Ради этого функция Loop состоит из единственного предложения с образцом, соответствующим шаблону, e.Code_ разбирается уже в блоке.
Во-вторых, как я уже писал выше, контроль ошибок. Образец вида
e.Stack t.Top (DUP e.Code) (e.Dict)
может не сопоставиться как из-за того, что код не начинается с команды DUP, так и из-за пустого стека. Поэтому отдельно уточняем e.Code_ : DUP e.Code и отдельно в присваивании содержимое стека.
В-третьих, ради прогонки. Поговорим о прогонке подробнее.
Есть две разновидности встраивания функций, которые умеет Рефал-5λ: слабый инлайнинг (inline) и сильная прогонка (drive). Инлайнинг допускает замену вызова функции её результатом, если этот вызов однозначен, не зависит от значений переменных в аргументе функции. Функции, подлежащие инлайнингу, помечаются ключевым словом $INLINE (пример выше). Прогонка позволяет заменить вызов функции на результат даже если этот результат зависит от значений переменных в аргументе функции. При встраивании предложение с вызовом размножается и различные ограничения на аргументы прогоняемого вызова учитываются в левых частях новых предложений. Прогоняемые функции помечаются ключевым словом $DRIVE.
Для присваиваний и блоков Рефал-5λ неявно создаёт вспомогательные функции, и эти функции неявно являются прогоняемыми. Т.е. блок в функции Loop будет прогоняться оптимизатором. На самом деле, если заглянуть в лог компилятора, функция Loop после оптимизации примет вид
Loop {
e.Stack#1 () (e.Dict#1) = e.Stack#1;
e.0#0 t.#0 (DUP e.#0) (e.Dict#1)
= <Loop e.0#0 t.#0 t.#0 (e.#0) (e.Dict#1)>;
e.Stack#1 (DUP e.#0) (e.Dict#1)
= <Loop:1$2=1*1 (e.#0) (e.Dict#1) e.Stack#1>;
e.0#0 t.#0 (DROP e.#0) (e.Dict#1) = <Loop e.0#0 (e.#0) (e.Dict#1)>;
e.Stack#1 (DROP e.#0) (e.Dict#1)
= <Loop:1$3=1*1 (e.#0) (e.Dict#1) e.Stack#1>;
e.2#0 (e.3#0) (e.1#0) (SWAP e.#0) (e.Dict#1)
= <Loop e.2#0 (e.1#0) (e.3#0) (e.#0) (e.Dict#1)>;
e.Stack#1 (SWAP e.#0) (e.Dict#1)
= <Loop:1$4=1*1 (e.#0) (e.Dict#1) e.Stack#1>;
...
}
Функции Loop:1$2=1*1 пустые, при их вызове программа падает. Компилятор их добавляет для сохранения семантики — оптимизированная программа будет точно также падать, как и не оптимизированная, если функция Loop вызывается с пустым стеком и очередной командой DUP.
Но нам более интересен вызов из функции Go. В нём текст программы на Форте и словарь известны статически, следовательно следующая ветка выполнится однозначно. В данном случае это define. Функция TransferBodyToDict будет вызываться со статическим константным аргументом, а значит, она встроится. Последующий рекурсивный вызов будет содержать в словаре определение функции Fact, а программа (e.CODE) будет начинаться с define Gcd. Для этого вызова снова будет построена (инстанцирована) новая версия Loop, в ней однозначно выберется ветка с define, в словарь будет помещена функция Gcd. Следующие шаги положат на стек два числа и будет сделан рекурсивный вызов для Fact.
Заметим, на каждом вызове статические параметры константны, т.е. не содержат переменных, поэтому экземпляры (instance) функции Loop будут зависеть только от динамического параметра — стека. Код интерпретатора и текст интерпретируемой программы при оптимизации исчезнут, останутся лишь непосредственные операции со стеком. Т.е. интерпретатор растворится, компилятор осуществит первую проекцию Футамуры(-Турчина).
Вот код построенной программы из лога компилятора. Я удалил те функции, которые не вызываются из Go, также удалил предложения, вызывающие пустые функции (вроде Loop:1$3=1*1, см. выше):
$ENTRY Go { /* empty */ = <Loop@1>; }
Loop@1 { e.Stack#1 = <Loop@4 e.Stack#1>; }
Loop@4 { e.Stack#1 = <Loop@5 e.Stack#1>; }
Loop@5 { e.Stack#1 = <Loop@6 e.Stack#1 (6)>; }
Loop@6 { e.Stack#1 = <Loop@8 <Loop@7 e.Stack#1>>; }
Loop@7 { e.#0 t.#0 = <Loop@9 e.#0 t.#0 t.#0>; }
Loop@8 { e.#0 (e.0#0) = <Prout e.0#0> <Loop@10 e.#0>; }
Loop@9 { e.Stack#1 = <Loop@11 e.Stack#1 (0)>; }
Loop@10 { e.Stack#1 = <Loop@12 e.Stack#1 (30)>; }
Loop@11 {
e.1#0 (s.Eq#3) (s.Eq#3) = <Loop@14 e.1#0 (1)>;
e.1#0 (s.X#3) (s.Y#3) = <Loop@14 e.1#0 (0)>;
}
Loop@12 { e.Stack#1 = <Loop@13 e.Stack#1 (48)>; }
Loop@13 { e.Stack#1 = <Loop@16 <Loop@15 e.Stack#1>>; }
Loop@14 {
e.#0 (0) = <Loop@19 <Loop@17 e.#0>>;
e.#0 (e.0#0) = <Loop@19 <Loop@18 e.#0>>;
}
Loop@15 { e.1#0 (e.2#0) (e.0#0) = <Loop@20 e.1#0 (e.2#0) (e.0#0) (e.2#0)>; }
Loop@16 { e.#0 (e.0#0) = <Prout e.0#0> <Loop@21 e.#0>; }
Loop@17 { e.#0 t.#0 = <Loop@22 e.#0 t.#0 t.#0>; }
Loop@18 { e.#0 t.#0 = <Loop@23 e.#0>; }
Loop@19 { e.Stack#1 = e.Stack#1; }
Loop@20 { e.Stack#1 = <Loop@24 e.Stack#1 (0)>; }
Loop@21 { e.Stack#1 = <Loop@25 e.Stack#1 (30)>; }
Loop@22 { e.Stack#1 = <Loop@26 e.Stack#1 (1)>; }
Loop@23 { e.Stack#1 = <Loop@19 e.Stack#1 (1)>; }
Loop@24 {
e.1#0 (s.Eq#3) (s.Eq#3) = <Loop@28 e.1#0 (1)>;
e.1#0 (s.X#3) (s.Y#3) = <Loop@28 e.1#0 (0)>;
}
Loop@25 { e.Stack#1 = <Loop@27 e.Stack#1 (48)>; }
Loop@26 { e.1#0 (e.2#0) (e.0#0) = <Loop@29 e.1#0 (<Sub (e.2#0) e.0#0>)>; }
Loop@27 { e.Stack#1 = <Loop@30 <Loop@15 e.Stack#1>>; }
Loop@28 {
e.#0 (0) = <Loop@19 <Loop@31 e.#0>>;
e.#0 (e.0#0) = <Loop@19 <Loop@32 e.#0>>;
}
Loop@29 { e.Stack#1 = <Loop@35 <Loop@7 e.Stack#1>>; }
Loop@30 { e.Stack#1 = <Loop@36 <Loop@7 e.Stack#1>>; }
Loop@31 { e.1#0 (e.2#0) (e.0#0) = <Loop@33 e.1#0 (e.2#0) (e.0#0) (e.2#0)>; }
Loop@32 { e.1#0 (e.2#0) (e.0#0) = <Loop@34 e.1#0 (e.0#0) (e.2#0)>; }
Loop@33 { e.1#0 (e.2#0) (e.0#0) = <Loop@37 e.1#0 (<Mod (e.2#0) e.0#0>)>; }
Loop@34 { e.#0 t.#0 = <Loop@19 e.#0>; }
Loop@35 { e.1#0 (e.2#0) (e.0#0) = <Loop@19 e.1#0 (<Mul (e.2#0) e.0#0>)>; }
Loop@36 { e.#0 (e.0#0) = <Prout e.0#0> <Loop@19 e.#0>; }
Loop@37 { e.1#0 (e.2#0) (e.0#0) = <Loop@38 e.1#0 (e.0#0) (e.2#0)>; }
Loop@38 { e.Stack#1 = <Loop@19 <Loop@15 e.Stack#1>>; }
Следов интерпретатора и интерпретируемой программы в программе нет. Для каждого шага вычислений компилятор построил специализированную функцию Loop. Единственный аргумент этих функций — стек.
Виден и недостаток текущей версии. Многие из этих функций можно было бы прогнать и даже встроить (в смысле, inline). Но, поскольку они создаются компилятором автоматически, приписать к ним $DRIVE или $INLINE пользователь не может. Одной из дальнейших задач будет автоматическая разметка прогоняемых функций, которая позволит упрощать такие программы.
Во вложении находится расширенный пример интерпретатора. Он также содержит бенчмарк, запускающий функцию
GcdFact {
s.X s.Y
= <Forth
define Fact (
DUP (0) '=' if (
DROP (1)
) else (
DUP (1) '-' Fact '*'
)
)
define Gcd (
OVER (0) '=' if (
SWAP DROP
) else (
OVER MOD SWAP Gcd
)
)
(s.X) (s.Y) Gcd Fact
>
}
сто тысяч раз и выводящий время её выполнения. На моей машине версия без оптимизации выполняется 64,625 секунды, оптимизированная (с ключами -ODS) — 24,469 секунды. Флаг D включает встраивание и прогонку, флаг S — специализацию (инстанцирование).
Внимательные читатели заметят, что функцию Benchmark можно описать как
$SPEC Benchmark e.number s.FUNC;
но это будет нечестно. Меряется не производительность бенчмарка, а вызываемой функции. Но я не думаю, что, если добавить этот $SPEC, результат поменяется статистически значимо.
Если хотите повторить эксперимент, нужно будет скачать актуальную версию Рефала-5λ
https://github.com/bmstu-iu9/refal-5-lambda/releases/tag/2.4
установить согласно приложенной инструкции.
Для компиляции приложенного к письму файла без оптимизации введите
srefc forth-rec.ref --log=log-forth.txt
При этом в папке должны появиться forth-rec.rasl (нужно удалить), forth-rec.exe и log-forth.txt. В логе ничего особо интересного нет. Можно, разве что, увидеть, как присваивания и блоки преобразуются во вспомогательные функции.
Для компиляции с оптимизацией:
srefc forth-rec.ref --log=log-forth.txt -ODS
В логе можно пронаблюдать процесс оптимизации, как на каждом проходе оптимизируются очередные вызовы функций, строятся новые экземпляры функций, которые тоже можно оптимизировать. Для полной оптимизации этого примера компилятору потребовалось 33 прохода (100−67). К сожалению, текущая версия оставляет в программе функции, которые нигде не вызываются, в дальнейших планах предполагается чистить программу от этого мусора.
Про эти оптимизации можно подробнее прочитать в записках к дипломам:
https://github.com/bmstu-iu9/refal-5-lambda/blob/2.4/doc/Презентация_Ситников_Прогонка.pdf
https://github.com/bmstu-iu9/refal-5-lambda/blob/2.4/doc/РПЗ_Ситников_Прогонка_2019.pdf
https://github.com/bmstu-iu9/refal-5-lambda/blob/2.4/doc/Презентация_Сухомлинова_Специализация_функций_2019.pdf
https://github.com/bmstu-iu9/refal-5-lambda/blob/2.4/doc/РПЗ_Сухомлинова_Специализация_функций_2019.pdf
Буду рад ответить на любые вопросы
Спасибо тем, кто это письмо дочитал,
Александр Коновалов
Sergei M. Abramov abram_AT_botik.ru
Александр, Кирилл и Дарья -- замечательный результат! Я бы этот текст
где-то выложил (или он и так в архиве переписки? киньте безрукому
ссылку?) и послал бы И.Р.Агамирзяну. Уверен, он порадуется.
С уважением,
Абрамов С.М.
ab...@botik.ru
мобильный: +7(903)2928308
Александр Коновалов a.v.konovalov87_AT_mail.ru
https://groups.google.com/d/msg/refal/Jz32ptpuVvE/WXMOBAIHFQAJ
А вот второй архив исходное письмо почему-то не сохранил (есть только Ваш ответ).
Позже (вечером или завтра) я напишу комментарии по синтаксису Рефала-5λ и сущности используемых оптимизаций, с ними первоначальный текст будет прозрачнее. Понятное дело, письмо подошьётся к архиву переписки, доступному по ссылке выше.
А кто такой И.Р.Агамирзян?
С уважением,
Александр Коновалов
Sergei M. Abramov abram_AT_botik.ru
Интересный человек. Игорь Рубенович Агамирзян, АГА. Как-то жизнь нас
(меня, рефальцев) многократно пересекала, всегда позитивно и со
взаимным уважением:
1. 1980..1991 -- сотрудник ЛИИАН СССР (ныне СПИИРАН), главный
конструктор программного обеспечения суперкомпьтера ЕС 2704.
А до того и тогда известный в стране энтузиаст Форта, которыей много
сделал для различных реализаций и продвижения языка в стране. До сих
пор ФОРТ для него -- любимое слово.
Я тода был в НИЦЭВТе (куратор всех проектов ЕС 27?? и единственный
разработчик/ программист системы сопряжения ЕС 2704 со стандартными ЕС
ЭВМ через блокмультиплексый канал) и потом в ИПС АН СССР
(со-исполниутель у АГА по созданию ПО для ЕС2704).
Проект ЕС 2704 был интересный, а машинка во многом несла черты
функ.программирования. Из этого опыта потом в нашем институте вырос
проект Т-системы (автоматическое динамическое распараллеливание
программ на базе функциональной парадигме)
Где-то в это годы (?) АГА познакомился и со всей рефал-командой.
2. 1995..2007 АГА в Майкрософте. К концу он был просто вторым
человеком в Майкрософт Рус. Приэтом не продавцом, а организатором R&D
проектов.
Именно он возил рефал-команду в Майкросовт Рисерч Кэмбридж и пытался
что-то тут заварить (в конце концов заварился специализатор для MSIE),
а потом именно он заварил два контракта нашего Института с
Майкрософтом вокруг Т-системы.
В эти же годы он независимо познакомился с В.Ф.Турчиным в Америке и
бывал у него в гостях, знает, любит и ценит...
3. 2007-2009 После ухода из Майкрософта (Гейтс не поддержал его
инициативу создать Майкрософт рисерч в России и поручить это ему) он
(по сути в отместку) ровно это и сделал -- создал в Питере успешное
R&D подраздление ЕМС. Сделал то, что не поддержал Гейтс. EMC немного
скромнее Майкрософта, но не сильно.
4. 2009—2016 гг. — Генеральный директор и председатель правления АО
"Российская венчурная компания". Ну... это как "Роснанао", только
серьезнее, а руководитель -- статус федерального министра.
Жестко перестроил (даже правил устав) РВК и в те годы РВК сделала
много разумного, доброго и вечного. Держал партнерство с
рефал-сообществом. Ушел по ... по некоторым существенным причинам
(примерно, как было с Гейтцем: руководство хотело не того, что АГА
считал верным)
5. С 2016 г. Вице-президент Национального исследовательского
университета Высшая школа экономики. Отвечает за правильное
АйТи-образование в вышке (конечно, не мгновенно все удается). Держит
партнерство с рефал-сообществом.
https://ru.wikipedia.org/wiki --> Агамирзян Игорь Рубенович
Главное, интересный, содержательный, умный и порядочный. А слова
ФОРТ, Рефал, Метавычисления и Турчин -- для него значимые. Поэтому я
и среагировал...
Спасибо за ссылку. Я ему отпишу ссылку. жду ссылку на вторую часть
;-)
PS. Александр, начал править опечатки в "рыжих книшках", которые Вы
нашли в 2018 году. Книшки будут переиздаваться. Если еще что-то
нашли, то скажите -- буду благодарен.
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый день всем!
Прошу прощения за столь поздний ответ. На первое письмо мне в личку практически сразу ответил Андрей Климов и попросил дать пояснения по синтаксису Рефала-5λ.
Предыдущее письмо я написал с целью продемонстрировать, что возможности оптимизации Рефала-5λ позволяют осуществить первую проекцию Футамуры. Для программы на Рефале с интерпретатором языка стековой машины компилятор построил синтаксическое дерево, в котором уже нет текста интерпретируемой программы. Код интерпретатора, модифицирующего стек в зависимости от очередной команды, превратился в набор взаимно-рекурсивных функций, которые передают друг другу только один стек.
Цели показать и объяснить Рефал-5λ не было, я предполагал, что код на нём и псевдокод синтаксического дерева будут более-менее понятны читателям, знакомым с Рефалом-5, -6 или Плюс.
В этом письме я подробнее остановлюсь на синтаксических средствах Рефала-5λ и подробнее напишу о сущности оптимизаций прогонки и специализации. В дальнейшем изложении я буду предполагать, что читателям знаком Рефал-5, чтобы на нём подробно не останавливаться. (Прошу прощения у пользователей Рефала-2, но по Рефалу-5 есть много хорошей литературы и я не хочу её лишний раз пересказывать.)
Рефал-5λ расширяет Рефал-5, наиболее существенное расширение — вложенные функции. Внутри результатного выражения можно записать набор предложений в фигурных скобках. Во время выполнения программы в это место будет помещён особый символ (значение, сопоставляемое с s-переменной). Этот символ — замыкание — представляет собой экземпляр безымянной функции, в котором зафиксированы значения связанных переменных в момент его создания. Если его поместить после левой угловой скобки, то эта функция вызовется (Рефал-5λ в отличие от Рефала-5 допускает запись <s.Func e.Arg>). Пример:
/*
<Map s.Func e.Items> == e.Res
вызывает s.Func для каждого терма из e.Items
*/
Map {
s.Func t.Next e.Rest = <s.Func t.Next> <Map s.Func e.Rest>;
s.Func /* пусто */ = /* пусто */;
}
/*
Декартово произведение двух последовательностей
<CartProd (A B) (1 2 3)> == (A 1) (A 2) (A 3) (B 1) (B 2) (B 3)
*/
CartProd {
(e.As) (e.Bs)
= <Map
{
t.A = <Map { t.B = (t.A t.B) } e.Bs>
}
e.As
>
}
Многие синтаксические конструкции Рефала-5λ выражаются через вложенные функции, являются синтаксическим сахаром. Без этого сложно будет понять, почему интерпретатор растворяется при оптимизации. Но обо всё по порядку.
От Рефала-5 Рефал-5λ унаследовал блок:
F {
…
Pat, Res : { Pat1 = Res1; Pat2 = Res2; … };
…
}
После успешного сопоставления аргумента функции F с образцом Pat, вычисляется значение результатного выражения Res и последовательно сопоставляется с образцами Pat1, Pat2, … Результат Resk в блоке становится результатом вычисления всей функции F. В Рефале-5λ блок является синтаксическим сахаром — довольно очевидно выражается через вложенную функцию. Следующий код в точности эквивалентен предыдущему:
F {
…
Pat = <{ Pat1 = Res1; Pat2 = Res2; … } Res>;
…
}
Как видите, вложенная функция с предложениями из блока вызывается с аргументом Res.
Новшеством Рефала-5λ по сравнению с Рефалом-5 являются присваивания — своего рода безоткатные условия:
F {
…
Pat = Res′ : Pat′ = Res″ : Pat″ = Res;
…
}
Семантика следующая. Если аргумент успешно сопоставился с образцом Pat, вычисляется значение Res′ и сопоставляется с образцом Pat′. Если сопоставление неуспешно, программа падает с ошибкой. Иначе продолжается вычисление предложения.
В выражении Res′ могут использоваться только переменные из Pat (что логично), в Pat′ — как переменные из Pat, так и новые переменные. Если в Pat′ используется переменная из Pat, то она считается связанной и повторной, должна иметь то же значение, что и в Pat. Т.е. присваивание присваивает новым переменным в Pat′ значения из результата вычисления Res′ (это отличает их от присваиваний Рефала Плюс). Аналогично выполняется второе присваивание = Res″ : Pat″ — вычисляется Res″ и сопоставляется с Pat″. Выражение Res может содержать переменные из всех предшествующих образцов и оно является результатом вызова функции F.
Присваивания тоже являются синтаксическим сахаром и выражаются через блоки:
F {
…
Pat = Res′ : { Pat′ = Res″ : { Pat″ = Res; }; };
…
}
А те выражаются уже через вложенные безымянные функции:
F {
…
Pat = <{ Pat′ = <{ Pat″ = Res; } Res″>; } Res′>
…
}
(Именно так это и реализовано — сначала присваивания в блоки, потом блоки во вложенные функции.)
Третья синтаксическая конструкция, используемая в примере — сокрытие (или переопределение) переменной. Часто бывает, что в блоке или в цепочке присваиваний несколько раз модифицируется некоторое значение. По смыслу оно одно и то же, но на каждом шаге вычислений оно обновляется и поэтому оно различно. Поэтому одной и той же сущности приходится присваивать различные имена (иначе переменная будет считаться повторной). Например:
((e.Pattern) e.Conditions (e.Result) (e.Blocks))
= <RemoveAssigns-Conditions e.Conditions> : e.Conditions1
= <RemoveAssigns-WindBlocks (e.Result) e.Blocks> : (e.Result1)
= <RemoveAssigns-Result e.Result1> : e.Result2
= ((e.Pattern) e.Conditions1 (e.Result2));
Это слегка изменённый фрагмент кода из компилятора. В нём отдельными шагами удаляются присваивания из условий, на результатное выражение «наматываются» блоки (их может быть несколько подряд) и удаляются присваивания из вложенных функций в результатном выражении. Т.е. один раз изменяются условия (e.Conditions), два раза модифицируется результатное выражение (e.Result). Для каждого этапа преобразований пришлось ввести новую переменную (e.Conditions1, e.Result1, e.Result2), здесь путём приписывания циферки. При этом в результатном выражении предложения исходные e.Result и e.Conditions не используются, поскольку используется модифицированный в присваиваниях результат.
Приписывание циферок — чисто механическая процедура, а значит, её можно автоматизировать, переложить на компилятор. Если мы хотим ввести новую переменную с тем же именем, что была связана ранее, мы можем приписать к ней знак ^. Такая переменная в образце уже будет считаться свободной и не повторной, она может быть связана с новым значением. И это новое связывание действует до конца предложения (если затем не перекроется новой переменной с крышкой). Код в примере выше на самом деле записан в компиляторе так:
((e.Pattern) e.Conditions (e.Result) (e.Blocks))
= <RemoveAssigns-Conditions e.Conditions> : e.Conditions^
= <RemoveAssigns-WindBlocks (e.Result) e.Blocks> : (e.Result^)
= <RemoveAssigns-Result e.Result> : e.Result^
= ((e.Pattern) e.Conditions (e.Result));
Вместо «пронумерованных» переменных используются те же самые имена e.Conditions и e.Result, но они связываются уже с новыми значениями. Переменная e.Result переопределяется дважды.
Теперь рассмотрим оптимизации, которым были посвящены две выпускные квалификационные работы бакалавра. Каждая из оптимизаций по отдельности не особо интересна (особенно, специализация), максимальная выгода происходит при их совместном применении.
Кирилл Ситников делал оптимизацию прогонки (driving) и встраивания (inlining). Под прогонкой здесь подразумевается оптимизация, описанная Турчиным в работах «Эквивалентные преобразования …» 197? года (Турчин 1972, Турчин 1974), а под встраиванием — ограниченная разновидность прогонки.
Прогонка пытается выполнить шаги рефал-машины во время компиляции, спекулятивно вычислить вызовы функций в результатных выражениях. Сложность тут в том, что вызов функции в тексте программы может содержать переменные, а результат вычисления функции может зависеть от их конкретных значений. А может и не зависеть. Если результат конкретного вызова функции не зависит от значений переменных в аргументе, то компилятор просто заменяет этот вызов на результат. Этот процесс в Рефале-5λ называется встраиванием.
Если результат вызова функции зависит от значений переменных, то тут интереснее. Для некоторого подмножества Рефала (т.н. «ограниченный Рефал», см. работы Турчина) можно описать непересекающиеся множества значений переменных в виде подстановок и для каждого из этих множеств записать свой результат вычисления функции. Для каждого набора ограничений на переменные создаётся экземпляр предложения с вызовом, в нём применяются эти подстановки для переменных, а вызов функции заменяется на результат.
Пример:
Back {
e.Front t.Back = Ok t.Back;
/* пусто */ = Error;
}
F {
e.A t.B '*' = <Back e.A t.B>;
e.X t.Y ((e.Z)) = e.Z <Back t.Y e.X>;
(e.100) e.500 = <Back e.100 e.500>;
…
}
Функция Back либо возвращает Ok и последний терм аргумента, либо, если аргумент пустой, возвращает Error. Здесь у нас есть три вызова функции Back и мы хотим их оптимизировать.
В первом предложении результат функции Back не зависит от значений переменных e.A и t.B — её вызов сразу можно заменить на Ok t.B. В этом случае мы говорим о том, что функция Back встроилась. Предложение заменится на
e.A t.B '*' = Ok t.B;
Во втором предложении результат вызова зависит от значения переменной e.X. Если e.X пустой (подстановка e.X → ε), то функция вернёт Ok t.Y. Если не пустой и имеет вид e.X → e.X′ t.X″, то вызов <Back t.Y e.X> заменится на Ok t.X″. Компилятор запишет второе предложение дважды, к каждому из них применит подстановку для e.X и заменит вызов на соответствующий результат:
/* пусто */ t.Y ((e.Z)) = e.Z Ok t.Y;
e.X′ t.X″ t.Y ((e.Z)) = e.Z Ok t.X″;
В третьем предложении результат вычисления зависит от значений e.100 и e.500. Подстановки и результаты будут, соответственно, e.100 → ε, e.500 → ε, результат Error; e.100 → e.1 t.2, e.500 → ε, результат Ok t.2; e.100 — любое, e.500 → e.3 t.4, результат Ok t.4. Получится три предложения:
(/* пусто */) /* пусто */ = Error;
(e.1 t.2) /* пусто */ = Ok t.2;
(e.100) e.3 t.4 = Ok t.4;
Функция F целиком после преобразований примет вид
F {
e.A t.B '*' = Ok t.B;
/* пусто */ t.Y ((e.Z)) = e.Z Ok t.Y;
e.X′ t.X″ t.Y ((e.Z)) = e.Z Ok t.X″;
(/* пусто */) /* пусто */ = Error;
(e.1 t.2) /* пусто */ = Ok t.2;
(e.100) e.3 t.4 = Ok t.4;
…
}
Прогонка хорошо работает только для ограниченного класса как вызывающих, так и вызываемых функций. Чтобы можно было прогнать вызов, образец вызывающего предложения должен быть L-выражением (не содержать открытых e-переменных и повторных t- и e-переменных), вызываемая функция должна быть функцией ограниченного Рефала (базисный Рефал + образцы должны быть L-выражениями). Встраивать функции можно в предложении любого вида.
Далее под встраиванием будем понимать частный случай прогонки без сужений на переменные из вызова, а под прогонкой — общий случай, допускающий сужения.
Пытаться прогонять все вызовы в программе бессмысленно, поскольку на рекурсивных функциях компилятор будет зависать. Поэтому выбирать оптимизируемые функции должен пользователь. Для того, чтобы пометить функции, пригодные для оптимизации, используется следующий синтаксис:
$DRIVE Foo, Bar, Baz;
или
$INLINE Foo, Bar, Baz;
Для примера выше можно записать:
$DRIVE Back;
Ключевое слово $DRIVE помечает функции, которые компилятор будет пытаться прогнать. Функции, помеченные $INLINE, разрешается только встраивать. Если функцию Back описать как встраиваемую, то оптимизируется вызов только в первом предложении функции F.
Зачем потребовалось различать $DRIVE и $INLINE? Потому что есть функции, вызовы которых можно оптимизировать, но прогонка приведёт к зацикливанию. Например, пусть мы хотим писать арифметические выражения в инфиксной нотации. Напишем для этого простую функцию интерпретации:
$INLINE Eval;
Eval {
(t.X '+' t.Y) = <Add <Eval t.X> <Eval t.Y>>;
(t.X '*' t.Y) = <Mul <Eval t.X> <Eval t.Y>>;
s.Number = s.Number;
}
SqDist {
s.X s.Y = <Eval ((s.X '*' s.X) '+' (s.Y '*' s.Y))>;
}
В функции SqDist правая часть полностью вычислится на стадии компиляции:
SqDist {
s.X s.Y = <Add <Mul s.X s.X> <Mul s.Y s.Y>>;
}
А теперь заменим s-переменные на t-переменные:
SqDist {
t.X t.Y = <Eval ((t.X '*' t.X) '+' (t.Y '*' t.Y))>;
}
Поскольку они теперь термы, они сами могут содержать выражения, пригодные для вычисления при помощи Eval. Например, функцию можно вызвать так: <SqDist (s.A '+' s.B) (1 '+' s.Z)> и она вычислится правильно. После встраивания Eval получится такой код:
SqDist {
t.X t.Y = <Add <Mul <Eval t.X> <Eval t.X>> <Mul <Eval t.Y> <Eval t.Y>>>;
}
Да, тут дважды вычисляется <Eval t.X> и <Eval t.Y>, но не будем на это обращать внимание. Тут интересно другое. Допустим, функция Eval была бы объявлена как $DRIVE:
$DRIVE Eval;
Что тогда? Тогда в новой версии SqDist вызовы <Eval t.X> и <Eval t.Y> стали бы прогоняться. Были бы рассмотрены случаи, когда t.X имеет вид (t.1 '+' t.2), (t.1 '*' t.2) и s.1, после подстановок появились бы вызовы <Eval t.1> и <Eval t.2>, которые стали бы прогоняться точно также… Прогонка зациклится, а встраивание — нет.
Надо понимать, что компилятор не требует, чтобы оптимизируемые функции принадлежали ограниченному Рефалу. Дело в том, что компилятор может очень ограниченно выходить за рамки ограниченного Рефала, либо такие функции могут оптимизироваться частично — до первого предложения не-ограниченного Рефала (с образцом общего вида либо с условием). В дальнейшем планируется расширить класс функций и класс контекстов вызова, которые компилятор сможет оптимизировать. В любом случае, пометки $DRIVE и $INLINE — это не приказ, а совет компилятору попробовать оптимизировать их вызовы. Если оптимизация невозможна — это не ошибка, вызов остаётся как есть.
Теперь вернёмся к началу нашего письма и вспомним про вложенные функции. Нужно знать, что вложенные функции всегда прогоняются. У них всегда есть неявная метка $DRIVE. Они безымянные, поэтому не могут вызываться рекурсивно (?), а значит, к ним такую пометку давать не только можно, но и нужно.
Есть ограничения текущей реализации: аргументы оптимизируемых вызовов должны быть пассивными, вызовы в предложениях с условиями не оптимизируются, не поддерживается синтаксис $DRIVE F { … }, который планировался изначально. К сожалению, бакалаврам на диплом дают всего месяц (раньше инженерам давали полгода).
Дарья Сухомлинова реализовала оптимизацию специализации, которую правильнее называть инстанцированием (термин предложен Аркадием Климовым). Этот механизм позволяет строить для вызовов помеченных функций новые функции, адаптированные к условиям их запуска. Например, если в вызове некоторые параметры функции являются константами, то вызов заменяется на вызов экземпляра (instance) специализированной функции, где эти параметры даже не передаются, а соответствующие константы включены сразу в тело новой функции.
Рассмотрим пример:
Replace {
(e.From) (e.To) e.Text-B e.From e.Text-E
= e.Text-B e.To <Replace (e.From) (e.To) e.Text-E>;
(e.From) (e.To) e.Text = e.Text;
}
F {
e.Text = <Replace ('AB') ('CD') e.Text>;
}
Функция Replace выполняет замену в тексте. Получает три аргумента: что заменять, на что заменять и сам текст. В функции F вызов Replace заменяет подстроку AB на подстроку CD. Функция будет вызывать себя рекурсивно и с одними и теми же аргументами.
Очевидно, для данного вызова можно написать более компактную и эффективную функцию для такой замены:
F {
e.Text = <Replace′ e.Text>;
}
Replace′ {
e.Text-B 'AB' e.Text-E
= e.Text-B 'CD' <Replace′ e.Text-E>;
e.Text = e.Text;
}
Функцию Replace′ можно получить из Replace вычёркиванием из обоих предложений первых двух скобочных термов и подстановки вместо e.From и e.To их фактических значений ('AB' и 'CD'), а также коррекцией рекурсивного вызова.
Собственно, оптимизация специализации примерно это и делает. Пользователь помечает функции, которые, по его мнению, имеет смысл специализировать, компилятор для вызовов этих функций создаёт специализированные экземпляры, где вместо известных параметров подставляется фактическое значение из вызова.
«…некоторые параметры функции являются константами…», «…известных параметров подставляется фактическое значение из вызова» — следовательно (а) у специализируемых функций должны быть параметры и (б) они должны легко замещаться на фактические значения.
У функций на Рефале-5(λ) только один аргумент по определению. Поэтому для специализируемых функций приходится явно описывать их входной формат, примерно, как в Рефале Плюс. А чтобы можно было легко осуществлять подстановку фактических значений при порождении экземпляров (instances), заменяемые параметры должны в образцах отождествляться в переменные того же типа.
Специализируемая функция описывается так:
$SPEC ИмяФункции Шаблон;
где Шаблон — жёсткое выражение. Индексы переменных в шаблоне роли не играют, за исключением первого знака. Если это буква верхнего регистра, значит параметр является статическим и по нему будет проходить специализация. Если это цифра или буква нижнего регистра — параметр динамический. Образцы функции должны быть уточнениями этого шаблона, причём статические параметры могут уточняться только в переменные того же типа, динамические могут уточняться во что угодно.
Для функции Replace шаблон можно описать так:
$SPEC Replace (e.FROM) (e.TO) e.text;
Для большей наглядности имена статических параметров написаны целиком большими буквами, имя динамического — целиком строчными. Хотя достаточно только первой буквы.
Надо отметить, что специализация не требует ограниченного Рефала. Так например, в функции Replace есть и открытые, и повторные e-переменные.
Реализована следующая семантика. Допустим, компилятор нашёл вызов специализируемой функции, дальнейшие шаги:
· Если аргумент вызова не соответствует шаблону — вызов не оптимизируется.
· Если соответствует шаблону, то есть подстановка переменных в шаблон, переводящая его в аргумент. Значения динамических параметров никак не анализируются, компилятору интересны только статические параметры.
· Если статические параметры содержат активные выражения, то вызов не оптимизируется (ограничение текущей версии).
· Выписываются переменные (без повторов) из статических параметров, после чего выписываются динамические параметры. Вокруг e-переменных и вокруг значений динамических e-параметров добавляются круглые скобки, кроме одной. Потому что для разделения N e-значений достаточно N−1 круглых скобок.
· Значения статических параметров с точностью до переименования образуют сигнатуру. Сигнатура для рассматриваемого вызова ищется среди известных сигнатур. Если сигнатура известна — подставляется имя экземпляра функции и на этом обработка заканчивается. Иначе (сигнатура новая) идём дальше.
· В образцах предложений удаляются статические параметры, в начало каждого предложения добавляются переменные из фактических значений статических параметров. Значения динамических e-параметров и e-переменные из фактических значений фактических окружаются круглыми скобками, тоже все кроме одной. Тут ещё есть возня с переименованиями переменных, не буду о ней писать подробно.
· В выражениях для динамических параметров и в остатках предложений (т.е. условия с правой частью) вместо переменных статических параметров подставляются их фактические значения.
· Генерируется новое имя функции. Имена, которые генерирует компилятор, имеют вид FuncName@N, где N — десятичное число. В исходном тексте знак @ недопустим в идентификаторах, поэтому конфликтов имён с пользовательским кодом быть не может. Имена вроде FuncName@N могут наблюдаться, например, в отладочном дампе оптимизированной программы, либо в отладочном логе компилятора.
· Из предложений пред-предыдущего этапа строится новая функция с этим именем. Это же имя подставляется в вызов.
· Запоминается связь между новым именем и сигнатурой.
Новая функция, которая получилась в результате этой процедуры, подвергается дальнейшим оптимизациям: встраивания/прогонки и специализации вызовов.
Рассмотрим на примере функций F и Replace. Вызов <Replace ('AB') ('CD') e.Text> шаблону соответствует. Сигнатура вызова: 'AB' ← e.FROM, 'CD' ← e.TO комплятору ещё не известна. Он выбирает новое имя Replace@1, исключает из вызова статические параметры и получает новый вызов в функции F:
F {
e.Text = <Replace@1 e.Text>;
}
Затем строится новое тело Replace@1. В предложениях функции исключаются статические параметры, в динамических параметрах и в правой части статические параметры заменяются на их фактические значения:
Replace@1 {
e.Text-B 'AB' e.Text-E = e.Text-B 'CD' <Replace ('AB') ('CD') e.Text-E>;
e.Text = e.Text;
}
Новая функция подвергается оптимизации. В ней нечего прогонять и встраивать, но есть вызов Replace, который можно проспециализировать. Сигнатура вызова 'AB' ← e.FROM, 'CD' ← e.TO компилятору известна, ей соответствует функция Replace@1. Компилятор просто заменяет вызов:
Replace@1 {
e.Text-B 'AB' e.Text-E = e.Text-B 'CD' <Replace@1 e.Text-E>;
e.Text = e.Text;
}
Рассмотрим такую функцию G:
G {
(s.A e.B s.C) e.Text = <Replace (s.A e.B) (e.B s.C) e.Text>;
}
Нетрудно убедиться, что результат оптимизации будет примерно таким:
G {
(s.A e.B s.C) e.Text = <Replace@2 s.A e.B s.C (e.Text)>;
}
Replace@2 {
s.A e.B s.C (e.Text-B s.A e.B e.Text-E)
= e.Text-B e.B s.C <Replace@2 s.A e.B s.C (e.Text-E)>;
s.A e.B s.C (e.Text) = e.Text;
}
Вернёмся к декартову произведению:
Map {
s.Func t.Next e.Rest = <s.Func t.Next> <Map s.Func e.Rest>;
s.Func /* пусто */ = /* пусто */;
}
$SPEC Map s.FUNC e.items;
CartProd {
(e.As) (e.Bs)
= <Map
{
t.A = <Map { t.B = (t.A t.B) } e.Bs>
}
e.As
>
}
Функция Map объявлена специализируемой. Первый аргумент функции Map — замыкание, которое захватывает переменную e.Bs. При специализации это замыкание попадёт в статический параметр, поэтому (а) будет удалено из вызова функции, (б) будет добавлена переменная e.Bs, от которой зависит объект замыкания. Само замыкание будет создаваться внутри нового экземпляра Map@1:
CartProd {
(e.As) (e.Bs) = <Map@1 e.Bs (e.As)>;
}
Map@1 {
e.Bs (t.Next e.Rest)
= <
{
t.A = <Map { t.B = (t.A t.B) } e.Bs>
}
t.Next
>
<Map
{
t.A = <Map { t.B = (t.A t.B) } e.Bs>
}
e.Rest
>
e.Bs (/* пусто */) = /* пусто */;
}
Безымянная функция по умолчанию прогоняемая, поэтому первый вызов компилятор упростит. Второй вызов будет иметь ту же сигнатуру, что и исходный вызов Map в CartProd:
Map@1 {
e.Bs (t.Next e.Rest)
= <Map { t.B = (t.Next t.B) } e.Bs>
<Map@1 e.Bs (e.Rest)>;
e.Bs (/* пусто */) = /* пусто */;
}
Первый вызов Map будет проспециализирован. Замыкание захватывает переменную t.Next, поэтому в функцию Map@2 будет передаваться t.Next.
Map@1 {
e.Bs (t.Next e.Rest) = <Map@2 t.Next e.Bs> <Map@1 e.Bs (e.Rest)>;
e.Bs (/* пусто */) = /* пусто */;
}
Map@2 {
t.Next1 t.Next e.Rest
= <{ t.B = (t.Next1 t.B) } t.Next>
<Map { t.B = (t.Next1 t.B) } e.Rest>;
t.Next /* пусто */ = /* пусто */;
}
Первый вызов в новой функции встраивается, второй специализируется:
Map@2 {
t.Next1 t.Next e.Rest = (t.Next1 t.Next) <Map@2 t.Next1 e.Rest>;
t.Next /* пусто */ = /* пусто */;
}
Остаточная программа:
CartProd {
(e.As) (e.Bs) = <Map@1 e.Bs (e.As)>;
}
Map@1 {
e.Bs (t.Next e.Rest) = <Map@2 t.Next e.Bs> <Map@1 e.Bs (e.Rest)>;
e.Bs (/* пусто */) = /* пусто */;
}
Map@2 {
t.Next1 t.Next e.Rest = (t.Next1 t.Next) <Map@2 t.Next1 e.Rest>;
t.Next /* пусто */ = /* пусто */;
}
По-моему, если бы программист решил написать декартово произведение без функций высших порядков, то он написал примерно так, как в коде выше. Ну, с точностью до имён и форматов функций и без транзитного вызова CartProd → Map@1.
Пометка функций специализируемыми в некотором смысле соответствует базисным конфигурациям в суперкомпиляции. Пометка $SPEC имеет смысл для рекурсивных функций, у которых статические параметры в точности воспроизводятся на рекурсивных вызовах. Поэтому новый экземпляр функции на следующих проходах оптимизации рано или поздно вызовет функцию с известной сигнатурой, а значит, зациклится. В примере с функцией Loop интерпретатора стекового языка статические параметры воспроизводятся через несколько итераций, поэтому получается система взаимно-рекурсивных экземпляров функции Loop.
Термины «специализация», «статический параметр» и «динамический параметр» не очень точны, это обсуждалось ещё в МГТУ имени Баумана в июне. Но на семинаре мы так и не подобрали подходящей альтернативы. Может быть, коллективным разумом рассылки мы придумаем более подходящую терминологию.
Вывод. Два сравнительно простых преобразования программ позволяют осуществить достаточно глубокую оптимизацию программ на Рефале-5λ при условии их совместной работы. Специализация строит новые экземпляры функций, в которые захардкожены статически известные значения статических параметров. Дальнейший проход оптимизации прогонки учитывает эти известные значения и дальше упрощает программу. Если программист понимает принципы прогонки и специализации, то может написать такие программы, которые после оптимизации существенно упрощаются, например с полным растворением интерпретатора (первая проекция Футамуры-Турчина).
Если это письмо вызовет интерес, дальше я могу подробнее разобрать интерпретатор стековой машины из первого письма, почему для оптимизации он написан был именно так, а не иначе. Почему, например, if/else использует рекурсию (вызов Loop, вложенный в вызов Loop), зачем нужна корявая функция TransferBodyToDict и т.д. Всё это я кратко затрагивал в первом письме, но эти моменты достойны более подробного обсуждения.
Да и по текущему письму, я надеюсь, найдётся, что обсудить.
Жду ваших вопросов.
С уважением,
Александр Коновалов