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

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

# «Лесоочистка в Рефале» (письмо в рассылку)
> Доступно в архивах
> 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) такие ситуации будут всплывать чаще, а значит, дефорестация станет оправдана к остаточным программам.