Подтвердить что ты не робот

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

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

Причина для вложенных функций в тех случаях, когда клаузулы, когда они стремятся сделать хвостовую рекурсию, мне очень понятна (как в 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 из установленного модуля. Я не думал, что с первого взгляда они могут что-то с этим сделать.

4b9b3361

Ответ 1

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

С прямым рекурсивным определением member становится петлевым выключателем и не является встроенным, поэтому специализация сайта не выполняется - это, по крайней мере, история перед праймой INLINABLE.

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

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

Ответ 2

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

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

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