Платформа Haskell: вложенные функции и оптимизация - PullRequest
Новая
       1

Платформа Haskell: вложенные функции и оптимизация

19 голосов
/ 18 марта 2012

Существует очень распространенная модель реализации многих функций на платформе haskell, которая беспокоит меня, но я не смог найти объяснения.Речь идет об использовании вложенных функций для оптимизации.

Причина вложенных функций в предложениях where, когда они нацелены на создание хвостовой рекурсии, мне очень понятна (как в length ), но чтоцель, когда внутренняя функция имеет точно такой же тип, как и функция верхнего уровня?Например, это происходит во многих функциях Data.Set модуля , например, следующего: 

-- | /O(log n)/. Is the element in the set?
member :: Ord a => a -> Set a -> Bool
member = go
  where
    STRICT_1_OF_2(go)
    go _ Tip = False
    go x (Bin _ y l r) = case compare x y of
          LT -> go x l
          GT -> go x r
          EQ -> True
#if __GLASGOW_HASKELL__ >= 700
{-# INLINABLE member #-}
#else
{-# INLINE member #-}
#endif

Я подозреваю, что это может иметь какое-то отношение к запоминанию, но яЯ не уверен.

edit : Поскольку dave4420 предполагает строгость, вот определение для макроса STRICT_1_OF_2, который можно найти в том же модуле: 

-- Use macros to define strictness of functions.
-- STRICT_x_OF_y denotes an y-ary function strict in the x-th parameter.
-- We do not use BangPatterns, because they are not in any standard and we
-- want the compilers to be compiled by as many compilers as possible.
#define STRICT_1_OF_2(fn) fn arg _ | arg `seq` False = undefined

Я понимаю, как работает этот макросОднако я до сих пор не понимаю, почему go вместе с STRICT_1_OF_2(go) не следует перемещать на верхний уровень вместо member.

Возможно, это не из-за оптимизации, а просто из-застилистический выбор?

edit 2 : Я добавил INLINABLE и INLINE часть из модуля установки.Я не думал, что они могут иметь какое-то отношение к этому на первый взгляд.

Ответы [ 2 ]

16 голосов
/ 18 марта 2012

Одним из непосредственных преимуществ наличия обертки INLINABLE (или INLINE) вокруг местного работника является специализация. Способ определения member на сайте вызова с фиксированным типом элемента, словарь Ord может быть отброшен, а соответствующая функция compare встроена или, по крайней мере, передана как статический аргумент.

При прямом рекурсивном определении member становится прерывателем цикла и не является встроенным, поэтому специализация сайта вызовов не завершена - это была, по крайней мере, история до прагмы INLINABLE.

При использовании прагмы INLINABLE специализация сайта вызовов происходит, словарь исключается, но в нескольких попытках мне не удалось написать рекурсивную member, которая столь же эффективна, как и текущая. Но с прагмой INLINE закон остается в силе, прерыватель цикла не встроен; для member это означает, что никакая специализация call-сайта для исключения словаря невозможна.

Так что, возможно, больше не нужно писать функции в этом стиле, но это было, чтобы получить специализацию call-сайта.

13 голосов
/ 18 марта 2012

GHC не может встроить рекурсивные функции. Способ member определен, рекурсия ограничена go, а member не является рекурсивным и может быть встроенным.

Из руководства пользователя GHC:

GHC гарантирует, что встраивание не может продолжаться вечно: каждый взаимно-рекурсивная группа разрезается одним или несколькими прерывателями цикла, никогда не указывается (см. Секреты вкладыша GHC, JFP 12 (4) июль 2002 г.). GHC пытается не выбирать функцию с прагмой INLINE в качестве цикла выключатель, но когда нет выбора, даже функция INLINE может быть выбран, и в этом случае прагма INLINE игнорируется. Например, для саморекурсивная функция, прерыватель цикла может быть только функцией сама по себе, поэтому прагма INLINE всегда игнорируется.

...