Учебник по Haskell

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

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

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

Такие дополнительные правила пишутся в специальной прагме 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 промежуточные списки не строятся.

Посмотрим как работает прагма 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

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

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