ли мы хотим узнать сколько правил сработало в данном прогоне программы). За именем правила пишут
уравнение. В одной прагме может быть несколько уравнений. Правила разделяются точкой с запятой или
переходом на другу строку. Все свободные переменные правила перечисляются в окружении forall (… )
. ~. Компилятор доверяет нам абсолютно. Производится только проверка типов. Никаких других проверок не
проводится. Выполняется ли на самом деле это свойство, будет ли вычисление правой части действительно
проще программы вычисления левой – известно только нам.
Отметим то, что прагма RULES применяется до тех пор пока есть возможность её применять, при этом мы
можем войти в бесконечный цикл:
{-# RULES
”infinite”
forall a b. f a b = f b a
#-}
С помощью прагмы RULES можно реализовать очень сложные схемы оптимизации. Так в Prelude реализу-
ется слияние (fusion) списков. За счёт этой оптимизации многие выражения вида свёртка/развёртка не будут
производить промежуточных списков. Этой схеме будет посвящена отдельная глава. Например если список
преобразуется серией функций map, filter и foldr промежуточные списки не строятся.
Посмотрим как работает прагма RULES, попробуем скомпилировать такой код:
module Main where
data List a = Nil | Cons a (List a)
deriving (Show)
foldrL :: (a -> b -> b) -> b -> List a -> b
foldrL cons nil x = case x of
Nil
-> nil
Cons a as
-> cons a (foldrL cons nil as)
Оптимизация программ | 175
mapL :: (a -> b) -> List a -> List b
mapL = undefined
{-# RULES
”mapL”
forall f xs.
mapL f xs = foldrL (Cons . f) Nil xs
#-}
main = print $ mapL (+100) $ Cons 1 $ Cons 2 $ Cons 3 Nil
Функция mapL не определена, вместо этого мы сделали косвенное определение в прагме RULES. Проверим,
для того чтобы RULES заработали, необходимо компилировать с одним из флагов оптимизаций O или O2:
$ ghc —make -O Rules.hs
$ ./Rules
Rules: Prelude.undefined
Что-то не так. Дело в том, что GHC слишком поторопился и заменил простую функцию mapL на её опре-
деление. Функция $ также очень короткая, если бы нам удалось задержать встраивание mapL, тогда $ превра-
тилось бы в обычное применение и наши правила сработали бы.
Фазы компиляции
Для решения этой проблемы в прагмы RULES и INLINE были введены ссылки на фазы компиляции. С по-
мощью них мы можем указать GHC в каком порядке реагировать на эти прагмы. Фазы пишутся в квадратных
скобках:
{-# INLINE [2] someFun #-}
{-# RULES
”fun” [0] forall …
”fun” [1] forall …
”fun” [~1] forall …
#-}
Компиляция выполняется в несколько фаз. Фазы следуют некотрого заданного целого числа, например
трёх, до нуля. Мы можем сослаться на фазу двумя способами: просто номером и номером с тильдой. Ссылка
без тильды говорит: попытайся применить это правило как можно раньше до тех пор пока не наступит данная
фаза, далее не применяй. Ссылка с тильдой говорит: подожди до наступления этой фазы. В нашем примере
мы задержим встраивание для mapL и foldrL так:
{-# INLINE [1] foldrL #-}
foldrL :: (a -> b -> b) -> b -> List a -> b
{-# INLINE [1] mapL #-}
mapL :: (a -> b) -> List a -> List b
Посмотреть какие правила сработали можно с помощью флага ddump—rule—firings. Теперь скомпилиру-
ем:
$ ghc —make -O Rules.hs -ddump-rule-firings
…
Rule fired: SPEC Main.$fShowList [GHC.Integer.Type.Integer]
Rule fired: mapL
Rule fired: Class op show
…
$ ./Rules
Cons 101 (Cons 102 (Cons 103 Nil))
Среди прочих правил, определённых в стандартных библиотеках, сработало и наше. Составим правила,
которые будут проводить оптимизацию слияние для наших списков, они будут заменять последовательное
применение mapL на один mapL c композицией функций, также промежуточный список будет устранён в
связке foldrL/mapL.
176 | Глава 10: Реализация Haskell в GHC
Прагма UNPACK
Наш основной враг на этапе оптимизации программы это лишние объекты кучи. Чем меньше объектов
мы создаём на пути к результату, тем эффективнее наша программа. С помощью прагмы INLINE мы можем
избавиться от многих объектов, связанных с вызовом функции, это объекты типа FUN. Прагма UNPACK позволя-
ет нам бороться с лишними объектами типа CON. В прошлой главе мы говорили о том, что значения в Haskell
содержат дополнительную служебную информацию, которая необходима на этапе вычисления, например
значение сначала было отложенным, потом мы до него добрались и вычислили, возможно оно оказалось не
определённым значением (undefined). Такие значения называются запакованными (boxed). Незапакованное
значение, это примитивное значение, как оно представлено в памяти компьютера. Вспомним определение
целых чисел:
data Int = I# Int#
По традиции все незапакованные значения пишутся с решёткой на конце. Запакованные значения позво-
ляют отклдывать вычисления, пользоваться undefined при определении функции. Но за эту гибкость прихо-
дится платить. Вспомним расход памяти в выражении [Pair 1 2]
nil = []
— глобальный объект (не в счёт)
let x1
= I# 1
— 2 слова
x2
= I# 2
— 2 слова
p
= Pair x1 x2
— 3 слова
val = Cons p nil
— 3 слова
in
val
————
— 10 слов
Получилось десять слов для списка из одного элемента, который фактически хранит два значения. Размер