Может ли GHC действительно никогда не использовать inline map, scanl, foldr и т. Д.? - PullRequest
Новая
       34

Может ли GHC действительно никогда не использовать inline map, scanl, foldr и т. Д.?

27 голосов
/ 12 марта 2012

Я заметил, что в руководстве GHC сказано "для саморекурсивной функции прерыватель цикла может быть только самой функцией, поэтому прагма INLINE всегда игнорируется".

Разве это не говорит о том, что каждое приложение обычных рекурсивных функциональных конструкций, таких как map, zip, scan*, fold*, sum и т. Д., Не может быть встроено?

Вы всегда можете переписать все эти функции, когда используете их, добавляя соответствующие теги строгости, или, возможно, применяете причудливые приемы, такие как рекомендуемое «слияние потоков» здесь .

ЕщеРазве все это не ограничивает нашу способность писать код, который является одновременно быстрым и элегантным?

Ответы [ 3 ]

51 голосов
/ 12 марта 2012

Действительно, GHC в настоящее время не может использовать встроенные рекурсивные функции. Тем не менее:

  • GHC по-прежнему специализирует рекурсивные функции. Например, учитывая 

    fac :: (Eq a, Num a) => a -> a
fac 0 = 1
fac n = n * fac (n-1)

f :: Int -> Int
f x = 1 + fac x

    GHC обнаружит, что fac используется для типа Int -> Int, и сгенерирует специализированную версию fac для этого типа, которая использует быструю целочисленную арифметику.

    Эта специализация происходит автоматически внутри модуля (например, если fac и f определены в одном и том же модуле). Для кросс-модульной специализации (например, если f и fac определены в разных модулях), пометьте специализированную функцию с помощью INLINABLE pragma : 

    {-# INLINABLE fac #-}
fac :: (Eq a, Num a) => a -> a
...

  • Существуют ручные преобразования, которые делают функции нерекурсивными. Метод наименьшей мощности - это статическое преобразование аргумента , которое применяется к рекурсивным функциям с аргументами, которые не изменяются при рекурсивных вызовах (например, многие функции более высокого порядка, такие как map, filter, fold*). Это превращение превращается 

    map f []     = []
map f (x:xs) = f x : map f xs

    в 

    map f xs0 = go xs0
  where
    go []     = []
    go (x:xs) = f x : go xs

    так, что вызов, такой как 

     g :: [Int] -> [Int]
 g xs = map (2*) xs

    будет иметь map встроенный и станет 

     g [] = []
 g (x:xs) = 2*x : g xs

    Это преобразование было применено к функциям Prelude, таким как foldr и foldl.

  • Методы Fusion также делают многие функции нерекурсивными и более мощными, чем статическое преобразование аргументов. Основным подходом для списков, встроенным в Prelude, является сочетание клавиш . Основной подход заключается в написании как можно большего количества функций, чем нерекурсивных функций, использующих foldr и / или build; затем вся рекурсия фиксируется в foldr, и существуют специальные ПРАВИЛА для работы с foldr.

    Использовать преимущества этого объединения в принципе легко: избегайте ручной рекурсии, предпочитая библиотечные функции, такие как foldr, map, filter и любые функции в этом списке . В частности, написание кода в этом стиле создает код, который является «одновременно быстрым и элегантным».

  • Современные библиотеки, такие как text и vector используют stream fusion за сценой. Дон Стюарт написал пару постов в блоге ( 1 , 2 ), демонстрирующих это в действии в устаревшей библиотеке uvector , но те же принципы применяются к тексту и вектор.

    Как и в случае сочетания клавиш, объединение потоков в текст и вектор в принципе является простым: избегайте ручной рекурсии, предпочитая функции библиотеки, помеченные как «подлежащие объединению».

  • Продолжается работа по улучшению GHC для поддержки встраивания рекурсивных функций. Это подпадает под общий заголовок суперкомпиляция , и последние работы над этим, похоже, были проведены Макс Болингброк и Нил Митчелл .

8 голосов
/ 12 марта 2012

Короче, не так часто, как вы думаете. Причина в том, что при внедрении библиотек используются «причудливые методы», такие как слияние потоков, и пользователям библиотеки не нужно о них беспокоиться.

Рассмотрим Data.List.map. Базовый пакет определяет map как 

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

Это map является саморекурсивным, поэтому GHC не сможет его встроить.

Однако base также определяет следующие правила перезаписи: 

{-# RULES
"map"       [~1] forall f xs.   map f xs                = build (\c n -> foldr (mapFB c f) n xs)
"mapList"   [1]  forall f.      foldr (mapFB (:) f) []  = map f
"mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g) 
  #-}

Это заменяет использование map через foldr / build fusion , затем, если функция не может быть объединена, заменяет его на исходное map. Поскольку слияние происходит автоматически, оно не зависит от того, знает ли пользователь об этом.

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

proc1 = sum . take 10 . map (+1) . map (*2)

eval1 = proc1 [1..5]
eval2 = proc1 [1..]

при компиляции с -O2 GHC объединяет все proc1 в единую рекурсивную форму (как видно на выходе ядра с -ddump-simpl).

Конечно, существуют пределы того, что эти методы могут выполнить. Например, наивная средняя функция, mean xs = sum xs / length xs, легко преобразуется вручную в одну единицу, и существуют платформы, которые могут делать это автоматически , однако в настоящее время нет известного способа автоматического перевода между стандартными функциями и рамки фьюжн. Поэтому в этом случае пользователь должен знать об ограничениях кода, созданного компилятором.

Так что во многих случаях компиляторы достаточно продвинуты для создания быстрого и элегантного кода. Знание того, когда они это сделают, и когда компилятор может выйти из строя, ИМХО - большая часть обучения тому, как писать эффективный код на Haskell.

2 голосов
/ 12 марта 2012

для саморекурсивной функции прерыватель цикла может быть только самой функцией, поэтому прагма INLINE всегда игнорируется.

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

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

Однако существуют определенные методы, которые могут делать рекурсивные вызовы намного, намного быстрее, чем их обычная ситуация. Например, оптимизация хвостового вызова SO Wiki

...