Unknown - haskell-notes

Посмотрим как работает прагма RULES, попробуем скомпилировать такой код:

module Main where

data Lista = Nil | Consa ( Lista)

deriving( Show)

foldrL ::(a ->b ->b) ->b -> Lista ->b

foldrL cons nil x = casex of

Nil

->nil

Consa as

->cons a (foldrL cons nil as)

Оптимизация программ | 175

mapL ::(a ->b) -> Lista -> Listb

mapL =undefined

{-# RULES

”mapL”

forall f xs.

mapL f xs = foldrL (Cons . f) Nil xs

#-}

main =print $mapL ( +100) $ Cons1 $ Cons2 $ Cons3 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 -> Lista ->b

{-# INLINE [1] mapL #-}

mapL ::(a ->b) -> Lista -> Listb

Посмотреть какие правила сработали можно с помощью флага 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 при определении функции. Но за эту гибкость прихо-

дится платить. Вспомним расход памяти в выражении [ Pair1 2]

nil = []

-- глобальный объект (не в счёт)

letx1

= I#1

-- 2 слова

x2

= I#2

-- 2 слова

p

= Pairx1 x2

-- 3 слова

val = Consp nil

-- 3 слова

in

val

------------

-- 10 слов

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

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