search

bmstu-iu9 / refal-5-lambda

Компилятор Рефала-5λ
https://bmstu-iu9.github.io/refal-5-lambda
Other
78 stars 35 forks source link

Оптимизация дефорестации #165

Open Mazdaywik opened 6 years ago

Mazdaywik commented 6 years ago

Есть предложение реализовать в Рефале-5λ оптимизацию дефорестации. Применимость дефорестации к Рефалу я описывал в письме в рассылку refal@botik.ru, поэтому сначала его просто процитирую.

«Лесоочистка в Рефале» (письмо в рассылку)

Доступно в архивах https://www.mail-archive.com/refal@botik.ru/msg00271.html https://groups.google.com/forum/#!topic/refal/6u7oADDvK5o

Для удобства чтения я отформатировал его в Markdown

Добрый день всем!

Дальше поток сознания — первая попытка перенести дефорестацию на Рефал Аннотация. В сообщении ниже я пишу про метод дефорестации и размышляю над его применимостью к Рефалу. Почти тридцать лет назад Филип Вадлер предложил метод оптимизации программ на функциональных языках программирования — дефорестацию: Wadler, Philip (1990). «Deforestation: transforming programs to eliminate trees». Theoretical Computer Science. 73 (2): 231-248. doi:10.1016/0304-3975(90)90147-A. (файл формата PostScript, на Windows нужно ставить GSView) Подозреваю, что многие подписчики не знают, что такое «дефорестация», поэтому кратко расскажу о ней. Дефорестация — способ преобразования программ на функциональных языках, который позволяет избежать построения промежуточных структур данных, которые затем всё равно деструктурируются. Например, в вызове `sum (map square (upto 1 n))` функция `upto` порождает список чисел от 1 до `n`, функция `map` разбирает этот список, `но` при этом порождает новый список — список квадратов. Функция `sum` разбирает список и возвращает число. Метод дефорестации позволяет для этого выражения построить функцию, которая принимает `n` и возвращает сумму квадратов от 1 до `n`, не строя при этом промежуточных списков. Поскольку в большинстве функциональных языков структуры данных являются деревьями (те же cons-ячейки — бинарное дерево), а метод позволяет от них избавиться, его так и назвали — дефорестация (deforestation) — лесоочистка, вырубка леса. Кстати, автор продолжает в статье свою метафору, вводя термины «бездревесные» функции (treeless functions) и зарубки на деревьях (blaze). Метод дефорестации формулируется для статически типизируемого функционального языка программирования (вроде ML). Модельный язык, на котором иллюстрируется метод, имеет функции фиксированной местности, данные языка могут представлять собой либо примитивы (числа), либо конструкторы тоже фиксированной местности (например, `Nil`, `Cons a b`, `Leaf n`, `Branch t1 t2`). Тело функции представляет собой терм, который может быть конструктором, вызовом функции или оператором `case`, например ``` flatten xss = case xss of Nil : Nil Cons xs xss : append xs (flatten xss) flip zt = case zt of Leaf z : Leaf z Branch xt yt : Branch (flip yt) (flip xt) ``` Дефорестация применима только к бездревесным (treeless) функциям — функциям, в термах которых аргументами функций и выражениями под `case of` могут быть только переменные, а также правые части должны быть линейными (отсутствуют повторные переменные в смысле Рефала). Вызываемые функции тоже могут быть только бездревесными. Например, функция `flip` бездревесная, функция `flatten` — нет (аргументом функции `append` является вызов функции `flatten`). Утверждается, что для любой композиции бездревесных функций можно построить эквивалентную функцию, которая будет бездревесной. И приводится набор несложных правил, осуществляющих такое преобразование. Он простой (можно посмотреть по ссылке), но тратить бумагу электронного письма я на него не хочу. К чему я клоню. Алгоритм дефорестации внешне похож на процесс суперкомпиляции. Только в отличие от последнего, в нём нет ни вложения, ни обобщения — а только точное совпадение с видом одного из предыдущих термов. И формулируется он как синтаксические преобразования. Но вот можно ли его применить к Рефалу? Рефал — динамически типизируемый язык без жёстких конструкторов, одно и то же выражение может быть построено разными правыми частями и наоборот разобрано разными образцами. Поэтому напрямую применить вадлеровскую дефорестацию невозможно. Но адаптировать метод, как мне кажется, можно. Во-первых, что следует считать бездревесными функциями? «Физический смысл» вадлеровских бездревесных функций в том, что в них никогда не строится значение, которое затем может быть деструктурировано. Функция может разбирать свой аргумент при помощи `case of`, поэтому аргумент функции не должен создаваться конструктором и другой функцией. По той же причине не может находиться конструктор или вызов функции внутри выражения `case of`. Линейность термов предотвращает избыточные вычисления после преобразования дефорестации. Тогда бездревесные функции на Рефале должны удовлетворять следующим требованиям: * Правые части — «линейные» (без повторных t- и e-переменных), в них аргументами функций могут быть только переменные. Либо, если используются форматы функций Рефала Плюс — аргумент функции в точности соответствует формату. * Левые части функций должны быть L-выражениями (потому что только для них пока есть нормальный матаппарат прогонки). * И такое специфическое требование — семейство бездревесных функций должно формировать и потреблять значения в одном направлении: либо справа налево, либо слева направо. Иначе ничего не получится. Тогда любое выражение на Рефале, содержащее вызовы бездревесных функций одного направления, может быть преобразовано в функцию (или несколько функций) с бездревесным определением. Доказательства у меня нет, но интуитивно мне это кажется верным. Рассмотрим пример. Пусть мы имеем набор ``` FabL { 'A' e.X = 'B' ; s.1 e.X = s.1 ; = ; } FabR { e.X 'A' = 'B'; e.X s.1 = s.1; = ; } FbcR { e.X 'B' = 'C'; e.X s.1 = s.1; = ; } ``` Тогда выражение `>` может быть преобразовано в бездревесную функцию. А `>` — нет, поскольку функции `FbcR` и `FabL` разного направления. Сделаем формальные преобразования вызова `>`, похожие на предложенные Филипом Вадлером: ``` F { e.X = >; } F { e.X , : { e.X1 'B' = 'C'; e.X1 s.1 = s.1; = ; } } ``` ``` F { e.X , e.X : { e.X2 'A' = 'B'; e.X2 s.2 = s.2; = ; } : { /* Да, не Рефал-5. Но вы поняли, что имеется ввиду. */ e.X1 'B' = 'C'; e.X1 s.1 = s.1; = ; }; } ``` ``` F { e.X , e.X : { e.X2 'A' , 'B' : { e.X1 'B' = 'C'; e.X1 s.1 = s.1; = ; }; e.X2 s.2 , s.2: { e.X1 'B' = 'C'; e.X1 s.1 = s.1; = ; }; , : { e.X1 'B' = 'C'; e.X1 s.1 = s.1; = ; }; }; } ``` ``` F { e.X , e.X : { e.X2 'A' = > 'C'; e.X2 s.2 , s.2 : { 'B' = > 'C'; s.1 = > s.1; }; = ; }; } ``` Видно, что вызов `>` повторяет исходный вызов с точностью до имени переменной. Можно заменить на вызов функции `F`: ``` F { e.X , e.X : { e.X2 'A' = 'C'; e.X2 s.2 , s.2 : { 'B' = 'C'; s.1 = s.1; }; = ; }; } ``` После упрощения получаем ``` F { e.X2 'A' = 'C'; e.X2 'B' = 'C'; e.X2 s.1 = s.1; = ; } ``` Бездревесные функции компилятор может определять автоматически, хоть и не просто. Конечно, определить L-выражения слева и линейные правые части с простыми (``) вызовами функций справа легко. А вот оценить направление функции уже поинтереснее, но тоже реализуемо. Оптимизация малополезна для Рефалов со списковой реализацией (вроде Рефала-5, Рефала-6), но довольно интересна для диалектов с массивовой реализацией (вроде Рефала Плюс). А для векторно-спискового представления Скоробогатова — так вообще идеальна. Филип Вадлер также рассматривает расширение бездревесных функций на встроенные арифметические действия и let-конструкцию (blazed treeless form), думаю, их тоже можно перенести на Рефал. Гилл Эндрю, Джон Лончбери и Саймон Пейтон Джонс [предложили](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/deforestation-short-cut.pdf?from=http%3A%2F%2Fresearch.microsoft.com%2Fen-us%2Fum%2Fpeople%2Fsimonpj%2Fpapers%2Fdeforestation-short-cut.pdf) сокращённую дефорестацию (short cut deforestation), она работает только с лисповскими списками и на Рефал не натягивается никак.

Готов ответить на все ваши вопросы по теме.

С уважением, Александр Коновалов

Дефорестация в Рефале-5λ

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

Дефорестация сама по себе в компиляторе не интересна, поскольку, на мой взгляд, не часто в исходниках встречаются композиции безлесых функций в чистом виде. Однако, могу предположить, что после проходов прогонки (#122) и специализации (#126) такие ситуации будут всплывать чаще, а значит, дефорестация станет оправдана к остаточным программам.

Mazdaywik commented 6 years ago

Дальнейшее обсуждение в рассылке привело к таким выводам:

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

Mazdaywik commented 5 years ago

4 апреля 2019 года я читал в ИПМ РАН имени Келдыша доклад, посвящённый дефорестации Рефала. Верить ему, а не тому, что написано выше:

Mazdaywik commented 5 years ago

На самом деле бездревесная форма проще, чем описано в презентации.

Для Рефала первого порядка (без указателей на функцию и Mu). Если в правой части предложения есть рекурсивный (взаимно-рекурсивный) вызов, то

  1. он не может быть аргументом какой-либо другой функции,
  2. все аргументы этого вызова должны быть переменными того же типа или иметь «меньший» тип.

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

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

Т.е. если функция F имеет формат <F s.X (e.Y) t.Z>, то допустимым вызовом будет <F s.1 (e.2) t.3> (все переменные того же типа) или <F A () s.4> (аргументы «меньше»). «Меньше» определено следующими неравенствами: e > ε и e > t > s > X. Проще говоря, значениями аргументов могут быть только значения, длина записи которых не больше 1. Например, в e-параметр нельзя передать t.X e.Z, в t-параметр — (any-expr).

Если рекурсивный вызов не удовлетворяет этим ограничениям, то в конфигурацию добавляются функции CutE и CutT. Добавляются по следующим правилам:

  1. Если (взаимно) рекурсивный вызов является аргументом другой функции, то сам вызов оборачивается в CutE.
  2. Если e- или t-аргументы функции «велики» (длина их записи в токенах больше единицы) — они оборачиваются в CutE или CutT соответственно.

Функция CutS не нужна, поскольку любой аргумент s-параметра будет иметь или тот же тип, или будет меньше.

Если бы полноценно рассматривались выходные форматы, то аргументами s-параметров могли бы быть и функции, которые оборачивались бы в CutS.

Семантика cut-функций. Это тождественные функции

CutE { e.X = e.X }
CutT { t.X = t.X }

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

Другая оговорка по поводу линейности — она не нужна. Достаточно только не распространять информацию. Либо, можно разрешить распространение информации «меньшего» типа.

По поводу зарубок направления отождествления. Описанный в презентации подход разворачивает одну итерацию. Можно итерацию не разворачивать. Если гроздь прогонки для вершины стека содержит рекурсию неприемлемого направления, то обобщаются не рекурсивные вызовы в грозди, а отсекается сама вершина стека. Глубина оптимизации будет меньше, однако у оптимизатора тогда будет больше неподвижных точек (будут ли они всегда — мне пока не очевидно).

Ограничение на L-выражения не существенно, ибо существуют ad hoc расширения. Если прогонка не определена, то вершина стека просто обобщается и падает как есть в остаточную программу.

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

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

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

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

Mazdaywik commented 4 years ago

Вот рассмотрим такую замечательную функцию:

MapAccum {
  t.Fn t.Acc e.Items = <DoMapAccum t.Fn t.Acc () e.Items>;
}

DoMapAccum {
  t.Fn t.Acc (e.Scanned) t.Next e.Unscanned
    = <Apply t.Fn t.Acc t.Next> : t.NewAcc e.New
    = <DoMapAccum t.Fn t.NewAcc (e.Scanned e.New) e.Unscanned>;

  t.Fn t.Acc (e.Scanned) /* пусто */ = t.Fn t.Acc e.Scanned;
}

Функция DoMapAccum рассахарится в следующую пару функций:

DoMapAccum {
  t.Fn t.Acc (e.Scanned) t.Next e.Unscanned
    = <DoMapAccum=1 t.Fn (e.Scanned) (e.Unscanned) <Apply t.Fn t.Acc t.Next>>;

  t.Fn t.Acc (e.Scanned) /* пусто */ = t.Fn t.Acc e.Scanned;
}

DoMapAccum=1 {
  t.Fn (e.Scanned) (e.Unscanned) t.NewAcc e.New
    = <DoMapAccum t.Fn t.NewAcc (e.Scanned e.New) e.Unscanned>;
}

Здесь мы имеем две взаимно рекурсивные функции. Если вычислить форматы как ГСО образцов, получим

<DoMapAccum t.1 t.2 (e.3) e.4> == …
<DoMapAccum=1 t.5 (e.6) (e.7) t.8 e.9> == …

Рекурсивный вызов в DoMapAccum=1 проблем не создаёт, в нём естественным образом вставится вызов CutE:

<DoMapAccum t.Fn t.NewAcc (<CutE e.Scanned e.New>) e.Unscanned>

А вот с рекурсивным вызовом в DoMapAccum проблема. Вызов не соответствует формату: ведь поверх t.8 e.9 падает вызов <Apply …>. Согласно описанному в комментарии выше, вызов, не соответствующий формату должен быть забракован как не подлежащий оптимизации. Следовательно, он оптимизирован не будет.

Что делать? Выводить свой формат для каждого вызова. Формат будет выводиться как ГСО от предложений вызываемой функции и аргумента самой функции. В таком случае любой вызов всегда будет соответствовать формату. Нечто похожее предлагалось в https://github.com/bmstu-iu9/refal-5-lambda/issues/251#issuecomment-622069428.

Для примера выше выведется формат t.10 (e.11) (e.12) e.13, благодаря чему вставится CutE вокруг <Apply …>:

<DoMapAccum=1 t.Fn (e.Scanned) (e.Unscanned) <CutE <Apply t.Fn t.Acc t.Next>>>

Да, это может быть переобобщением, но это не страшно. Ведь цель форматов и вставок CutE/CutT в том, чтобы избежать накопления данных в аккумуляторах. А если мы случайно сотрём и сами аккумуляторы, то они восстановятся при сопоставлении «размазанной» переменной с образцами и таким образом по определению будут самыми общими.

Mazdaywik commented 4 years ago

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

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

https://github.com/bmstu-iu9/refal-5-lambda/issues/165#issuecomment-544966560:

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

Дефорестация может заменить «базовую» специализацию. При «базовой» специализации (т.е. без #251 и #253) статические параметры проецируются в левых частях на переменные. Если функция рекурсивная, то программист должен обеспечить, чтобы рекурсивный вызов получит в точности такое же значение статического параметра. Далее слово базовый будем писать без кавычек.

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

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

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

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

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

Заметим, что шаблон специализации должен обобщать все образцы функции, формат для рекурсивной функции выводится как ГСО образцов + аргумента. Таким образом, если обобщене однозначное, выведенный формат будет не шире шаблона специализации, а статические параметры в нём будут переменными (т.к. они переменные в каждом из образцов). Если обобщение неоднозначное, то, по-видимому, не повезло.

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

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

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

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

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

Также специализатор опережает дефорестатор, когда рекурсивные вызовы намеренно вызываются с новыми статическими аргументами. Дефорестатор такие вызовы будет рассматривать как обычные рекурсивные, при этом статические аргументы будет обобщать. А значит, интересные примеры вроде специализации интерпретатора стекового языка (см. #251) специализатор возьмёт, а дефорестатор (на первом проходе) нет. Если проходов выполняется несколько, то рекурсивные вызовы того же интерпретатора уже будут проспециализированы дефорестатором.

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

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

Mazdaywik commented 4 years ago