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

В реализации многих функций на платформе 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

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

изменить: поскольку 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.

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

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


optimization haskell haskell-platform
person Riccardo T.    schedule 18.03.2012    source источник
comment
Я подозреваю, что это как-то связано с анализом строгости: ожидается, что компилятор сделает вывод, что первый аргумент member должен быть оценен, но первый аргумент go всегда уже будет оценен. Но я не уверен.   -  person dave4420    schedule 18.03.2012
comment
@ dave4420: Спасибо за ваше предложение. Я обновил свой вопрос, добавив дополнительную информацию о строгости функции, надеюсь, это поможет.   -  person Riccardo T.    schedule 18.03.2012
comment
Я думаю, что это чисто стилистическая проблема. Но вы могли бы получить небольшую прибыль, позволив x быть свободным в go. Мне не нравится стиль, в котором это написано, так как это, кажется, подразумевает, что x получает seq:ed в каждой итерации. Кроме того, он делает членов строгими в x, когда это не обязательно (но это второстепенно).   -  person augustss    schedule 18.03.2012
comment
Это пример стиля worker wrapper (см. статьи Энди Гилла и Грэма Хаттона), он может помочь анализатору строгости определить, что переменные цикла являются строгими.   -  person stephen tetley    schedule 18.03.2012

Ответы (2)


arrow_upward
17
arrow_downward

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

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

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

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

person Daniel Fischer    schedule 18.03.2012

arrow_upward
13
arrow_downward

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

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

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

person Grzegorz Chrupała    schedule 18.03.2012
comment
Спасибо. С этим я на шаг ближе к пониманию, но до сих пор не понимаю. Какой смысл объявлять его INLINE для начала, если все, что он делает, это вызывает другую не встроенную функцию go? - person Riccardo T.; 18.03.2012
comment
Итак, определяя вложенную функцию, мы каким-то образом разрешаем встраивание даже для рекурсивной функции member, давая GHC возможность выбрать go в качестве прерывателя цикла, я прав? - person Riccardo T.; 18.03.2012
comment
@Riccardo, хороший вопрос. Некоторая связанная информация есть на hackage.haskell.org/trac/ghc/wiki/Inlining Возможно, это немного проясняет ситуацию. - person Grzegorz Chrupała; 18.03.2012
comment
+1, спасибо за ответ и ссылку. Однако я приму ответ Дэниела, поскольку он более прямой и всеобъемлющий. - person Riccardo T.; 18.03.2012