optimization - resueltos - Plataforma Haskell: funciones anidadas y optimización.

función anidadas en excel

Question

Hay un patrón muy común en la implementación de muchas funciones en la plataforma de haskell que me molesta, pero no pude encontrar una explicación. Se trata del uso de funciones anidadas para la optimización.

El motivo de las funciones anidadas en las cláusulas donde intentan hacer la recursión de la cola es muy claro para mí (como en length ), pero ¿cuál es el propósito cuando la función interna tiene exactamente el mismo tipo que la de nivel superior? Sucede, por ejemplo, en muchas funciones del módulo Data.Set , como la siguiente:

-- | /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

Sospecho que puede tener algo que ver con la memoria, pero no estoy seguro.

edición : dado que dave4420 sugiere rigor, aquí está la definición de la macro STRICT_1_OF_2 que se puede encontrar en el mismo módulo:

-- 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

Entiendo cómo funciona esta macro, sin embargo, todavía no veo por qué go junto con STRICT_1_OF_2(go) no se debe mover al nivel superior en lugar de member .

¿Quizás no sea por una optimización, sino simplemente por una elección estilística?

Edición 2 : agregué la parte INLINABLE e INLINE del módulo de configuración. No pensé que pudieran tener algo que ver con eso a primera vista.

Answer 1

GHC no puede en línea funciones recursivas. La forma en que se define el member , la recursión se limita a go y el member sí no es recursivo y se puede alinear.

De la guía de usuario de GHC:

GHC garantiza que la alineación no puede durar para siempre: cada grupo recursivo se corta con uno o más interruptores de bucle que nunca están alineados (consulte Secrets of the GHC inliner, JFP 12 (4) July 2002). GHC intenta no seleccionar una función con un pragma INLINE como interruptor de bucle, pero cuando no hay otra opción, incluso se puede seleccionar una función INLINE, en cuyo caso se ignora el pragma INLINE. Por ejemplo, para una función auto-recursiva, el interruptor de bucle solo puede ser la función en sí, por lo que un pragma INLINE siempre se ignora.

Answer 2

Un beneficio inmediato de tener un INLINABLE (o INLINE ) alrededor del trabajador local es la especialización. La forma en que se define ese member , en el sitio de la llamada, con un tipo de elemento fijo, el diccionario Ord se puede descartar y la función de compare apropiada se puede incluir o al menos pasar como un argumento estático.

Con una definición recursiva directa, el member convierte en un factor de ruptura de bucle y no está en línea, por lo que no se realiza la especialización de sitio de llamada; al menos, esa era la historia antes del pragma INLINABLE .

Con un pragma INLINABLE , se realiza la especialización del sitio de llamadas, se elimina el diccionario, pero en algunos intentos no he logrado escribir un member directamente recursivo que sea tan eficiente como el actual. Pero con un pragma INLINE , la ley sigue vigente, un interruptor automático no está en línea; para el member que significa que no es posible una especialización de sitio de llamada para eliminar el diccionario.

Por lo tanto, puede que ya no sea necesario escribir las funciones con ese estilo, pero sí lo fue para obtener la especialización del sitio de llamada.