Unknown - haskell-notes

ма часто используется при различных трюках с unsafePerformIO, встраивание функции, которая содержит

неконтролируемые побочные эффекты, может повлиять на её результат.

Прагма RULES

Разработчики GHC хотели, чтобы их компилятор был расширяемым и программист мог бы определять

специфические для его приложения правила оптимизации. Для этого была придумана прагма RULES. За счёт

чистоты функций мы можем в очень простом виде выражать инварианты программы. Инвариант – это неко-

торое свойство значения, которое остаётся постоянным при некоторых преобразованиях. Наиболее распро-

странённые инварианты имеют собственные имена. Например, это коммутативность сложения:

forall a b .a +b =b +a

Здесь мы пишем: для любых a и b изменение порядка следования аргументов у ( +) не влияет на результат.

С ключевым словом forall мы уже когда-то встречались, когда говорили о типе ST. Помните тип функции

runST? Пример свойства функции map:

forall f g .

map f .map g =map (f .g)

174 | Глава 10: Реализация Haskell в GHC

Это свойство принято называть дистрибутивностью. Мы видим, что функция композиции дистрибутив-

на относительно функции map. Инварианты определяют скрытые закономерности значений. За счёт чистоты

функций мы можем безболезненно заменить в любом месте программы левую часть на правую или наобо-

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

эффективнее другой. Так в примере с map выражение справа от знака равно гораздо эффективнее, поскольку

в нём мы не строим промежуточный список. Особенно ярко разница проявляется в энергичной стратегии

вычислений. Или посмотрим на такое совсем простое свойство:

map id =id

Если мы заменим левую часть на правую, то число сэкономленных усилий будет пропорционально длине

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

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

Можно представить, что эти правила являются дополнительными уравнениями в определении функции:

map f []

= []

map f (x :xs)

=f x :map f xs

map id a

=a

map f (map g x) =map (f .g) x

Словно теперь мы можем проводить сопоставление с образцом не только по конструкторам, но и по выра-

жениям самого языка и функция map стала конструктором. Что интересно, зависимости могут быть какими

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

тельных уравнениях мы подставляем аргументы так же как и в обычных, если где-нибудь в коде программы

находится соответствие с левой частью уравнения, мы заменяем её на правую. При этом мы пишем правила

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

Такие дополнительные правила пишутся в специальной прагме RULES:

{-# RULES

”map/compose”

forall f g x.

map f (map g x)

= map (f . g) x

”map/id”

map id

= id

#-}

Первым в кавычках идёт имя правила. Оно используется только для подсчёта статистики (например ес-

ли мы хотим узнать сколько правил сработало в данном прогоне программы). За именем правила пишут

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

переходом на другу строку. Все свободные переменные правила перечисляются в окружении forall ( ...)

.~. Компилятор доверяет нам абсолютно. Производится только проверка типов. Никаких других проверок не

проводится. Выполняется ли на самом деле это свойство, будет ли вычисление правой части действительно

проще программы вычисления левой – известно только нам.

Отметим то, что прагма RULESприменяется до тех пор пока есть возможность её применять, при этом мы

можем войти в бесконечный цикл:

{-# RULES

”infinite”

forall a b. f a b = f b a

#-}

С помощью прагмы RULESможно реализовать очень сложные схемы оптимизации. Так в Prelude реализу-

ется слияние (fusion) списков. За счёт этой оптимизации многие выражения вида свёртка/развёртка не будут

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

преобразуется серией функций map, filter и foldr промежуточные списки не строятся.