Добрый день всем! Аннотация. В сообщении ниже я пишу про метод дефорестации и размышляю над его применимостью к Рефалу.
Почти тридцать лет назад Филип Вадлер предложил метод оптимизации программ на функциональных языках программирования - дефорестацию: Wadler, Philip (1990). <Deforestation: transforming programs to eliminate trees>. Theoretical Computer Science. 73 (2): 231-248. doi:10.1016/0304-3975(90)90147-A. http://homepages.inf.ed.ac.uk/wadler/papers/deforest/deforest.ps (файл формата 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' <FabL e.X>; s.1 e.X = s.1 <FabL e.X>; = ; } FabR { e.X 'A' = <FabR e.X> 'B'; e.X s.1 = <FabR e.X> s.1; = ; } FbcR { e.X 'B' = <FbcR e.X> 'C'; e.X s.1 = <FbcR e.X> s.1; = ; } Тогда выражение <FbcR <FabR e.X>> может быть преобразовано в бездревесную функцию. А <FbcR <FabL e.X>> - нет, поскольку функции FbcR и FabL разного направления. Сделаем формальные преобразования вызова <FbcR <FabR e.X>>, похожие на предложенные Филипом Вадлером: F { e.X = <FbcR <FabR e.X>>; } F { e.X , <FabR e.X> : { e.X1 'B' = <FbcR e.X1> 'C'; e.X1 s.1 = <FbcR e.X1> s.1; = ; } } F { e.X , e.X : { e.X2 'A' = <FabR e.X2> 'B'; e.X2 s.2 = <FabR e.X2> s.2; = ; } : { /* Да, не Рефал-5. Но вы поняли, что имеется ввиду. */ e.X1 'B' = <FbcR e.X1> 'C'; e.X1 s.1 = <FbcR e.X1> s.1; = ; }; } F { e.X , e.X : { e.X2 'A' , <FabR e.X2> 'B' : { e.X1 'B' = <FbcR e.X1> 'C'; e.X1 s.1 = <FbcR e.X1> s.1; = ; }; e.X2 s.2 , <FabR e.X2> s.2: { e.X1 'B' = <FbcR e.X1> 'C'; e.X1 s.1 = <FbcR e.X1> s.1; = ; }; , : { e.X1 'B' = <FbcR e.X1> 'C'; e.X1 s.1 = <FbcR e.X1> s.1; = ; }; }; } F { e.X , e.X : { e.X2 'A' = <FbcR <FabR e.X2>> 'C'; e.X2 s.2 , s.2 : { 'B' = <FbcR <FabR e.X2>> 'C'; s.1 = <FbcR <FabR e.X2>> s.1; }; = ; }; } Видно, что вызов <FbcR <FabR e.X2>> повторяет исходный вызов с точностью до имени переменной. Можно заменить на вызов функции F: F { e.X , e.X : { e.X2 'A' = <F e.X2> 'C'; e.X2 s.2 , s.2 : { 'B' = <F e.X2> 'C'; s.1 = <F e.X2> s.1; }; = ; }; } После упрощения получаем F { e.X2 'A' = <F e.X2> 'C'; e.X2 'B' = <F e.X2> 'C'; e.X2 s.1 = <F e.X2> s.1; = ; } Бездревесные функции компилятор может определять автоматически, хоть и не просто. Конечно, определить L-выражения слева и линейные правые части с простыми (<F var>) вызовами функций справа легко. А вот оценить направление функции уже поинтереснее, но тоже реализуемо. Оптимизация малополезна для Рефалов со списковой реализацией (вроде Рефала-5, Рефала-6), но довольно интересна для диалектов с массивовой реализацией (вроде Рефала Плюс). А для векторно-спискового представления Скоробогатова - так вообще идеальна. Филип Вадлер также рассматривает расширение бездревесных функций на встроенные арифметические действия и let-конструкцию (blazed treeless form), думаю, их тоже можно перенести на Рефал. Гилл Эндрю, Джон Лончбери и Саймон Пейтон Джонс предложили сокращённую дефорестацию (short cut deforestation), она работает только с лисповскими списками и на Рефал не натягивается никак. Готов ответить на все ваши вопросы по теме. С уважением, Александр Коновалов
