¿Cómo hacer una CAF no una CAF en Haskell?

ghc compiler-optimization

Question

¿Cómo puedo hacer un Formulario de solicitud constante en, bueno, no un Formulario de solicitud constante, para evitar que se conserve durante la vigencia del programa?

He intentado este enfoque:

-- | Dummy parameter to avoid creating a CAF
twoTrues :: () -> [[[Bool]]]
twoTrues _ = map (++ (True : repeat False)) . trueBlock <$> [1..]

pero no parece funcionar: el perfil muestra que todavía se conserva y todavía lo marca como CAF.

Encontré un resultado relevante de Google sobre esto, una respuesta de Simon Peyton-Jones a Neil Mitchell, quien hizo precisamente esta pregunta, pero esa respuesta se refiere a un enlace muerto, desafortunadamente.

Answer 1

Con la introducción de un parámetro ficticio, también debe hacer que parezca que el resultado realmente depende del parámetro. De lo contrario, la inteligencia de GHC podría convertirlo nuevamente en CAF.

Sugiero lo siguiente:

twoTrues u = map (++ (True : repeat False)) . trueBlock <$> [(u `seq` 1)..]

Answer 2

La solución más simple posible podría ser decirle al compilador que lo alinee. (Nota: esta respuesta no se ha probado. Si no funciona, coméntela a continuación).

Incluso si (hipotéticamente) el compilador se niega a alinearlo por alguna razón, puede usar cpp lugar, al #definirlo:

#define twoTrues (map (++ (True : repeat False)) . trueBlock <$> [1..])

(aunque con ese enfoque, por supuesto, no aparecerá en la interfaz del módulo , por lo que solo puede usarlo dentro de ese módulo).

La opción -cpp le dice a GHC que preprocesa el archivo de entrada con cpp.

Inlinear significa duplicar el código n veces si se refiere a twoTrues en n> 1 lugares. Sin embargo, aunque eso es teóricamente indeseable, probablemente no sea un problema significativo en la práctica.

Answer 3

Necesita ocultar el hecho de que el rhs es un CAF del optimizador. Algo como esto debería hacerlo.

twoTrues :: () -> [[[Bool]]]
twoTrues u = map (++ (True : repeat (false u))) . trueBlock <$> [1..]
{-# NOINLINE false #-}
false :: () -> Bool
false _ = False

Answer 4

Parece ser un problema de larga data http://hackage.haskell.org/trac/ghc/ticket/917 . Y en mi opinión uno crítico.

Answer 5

Siempre que use () como parámetro, lo que va a decir es en realidad

Aunque he declarado un parámetro aquí, no soy interesante en lo que es y no voy a hacer nada con su valor.

No eres interesante en eso, porque () no tiene nada interesante en absoluto; no vas a hacer nada con eso, porque no puedes hacer nada con () .

El problema es que el compilador tiene derecho a optimizarlo ya que solo hay un valor posible para aprobar, por lo que su uso siempre es predecible y, por lo tanto, ¿por qué no asumirlo? Pero lo vuelve a mover a CAF y hace que la idea no funcione.

Afortunadamente, hay otra manera de hacerlo. Mira la siguiente modificación de dos twoTrues :

twoTrues :: a -> [[[Bool]]]
twoTrues _ = map (++ (True : repeat False)) . trueBlock <$> [1..]

Ahora puedes usar dos twoTrues como esta:

map concat $ twoTrues()

Como a es un parámetro de tipo no utilizado, el que llama puede pasar cualquier cosa. Y porque no sabes lo que sería, entonces no tienes idea de lo que puedes hacer con eso. En realidad, esto te obliga a ignorar su valor. Entonces, básicamente, se está declarando la misma declaración que mencioné antes.

Por causa, ahora puede pasar cualquier cosa (incluso undefined ) a esa función. Pero no importa y, de hecho, es esta posibilidad la que hace viable este truco, ya que el compilador ya no puede predecir cómo se usa esta función. Cuando el usuario humano vea esta función, ellos deberían saber lo que van a decir aquí y concluir que pasar () es lo más fácil, pero incluso si no lo hacen y pasando algo más, no rompería nada y dado que Haskell es perezoso, el parámetro nunca podría ser evaluado en absoluto.

Entonces, ¿qué ocurre si () se usa como resultado? Esto es aún peor. Dado que regresar () significa que su función no hace nada en absoluto (en Haskell, todos los efectos de una función se representarán en su valor de retorno), el compilador tiene el derecho de concluir que su función no es necesaria.

La conclusión es que () como un tipo no aparecerá en las firmas de tipo a menos que se use con algún otro tipo (es decir, en IO () ).

EDITAR

Ahora uno puede preguntarse, si hay una sola forma de implementar a -> String desde una String , por qué el compilador no puede concluir que son iguales. La respuesta es que realmente tiene dos formas de implementar esto.

usual :: a -> String
usual _ = "Hello World!"
unusual :: a -> String
unusual a = seq a "Hello World!"

Para casi todas las entradas, el usual value = unusual value , pero lo usual undefined es "Hello World!" mientras que unusual undefined está undefined .

Desde el punto de vista humano, lo unusual es bastante inusual, porque obliga a evaluar un valor no relacionado con el resultado final. Si en algún caso necesitas algo así, simplemente llamar a seq sería más fácil. Además, dado que Haskell es por defecto perezoso, si desea definir una función que sea estricta, será mejor que documente este comportamiento. Entonces, si ve una firma de este tipo sin documentación adicional, tiene derecho a asumir que se implementa de la manera usual .

Answer 6

Generalizar. Si tiene un valor constante, ¿puede generalizarlo a una función de alguna variable? El nombre de mi función en la pregunta, dos twoTrues , sugiere de inmediato que esta constante es la tercera en una secuencia zeroTrues , oneTrue , twoTrues , threeTrues , etc., y de hecho lo es. Así que generalizar dos twoTrues en una función nTrues que toma un parámetro n y elimina dos twoTrues , eliminaría un CAF del programa.

En este caso, solo consideré los casos zeroTrues , oneTrue y twoTrues para mi programa porque eso era todo lo que necesitaba, pero mi programa podría extenderse naturalmente para tratar con nTrues para n > 2, así que generalizar a nTrues sería significa que tendría sentido "generalizar todo el camino" para los usuarios de zeroTrues , oneTrue , etc. Ese no sería siempre el caso.

Nota: es posible que haya otros CAF para tratar, ya sea en el código o producidos por las "optimizaciones" de GHC (que en realidad no son optimizaciones en estos casos patológicos).

Sin embargo, esta respuesta puede implicar más trabajo del programador de lo estrictamente necesario. En realidad no es necesario generalizar, como muestra la respuesta de Don.

Por otro lado, en algunos casos, generalizar una constante puede dejar más claro lo que se está haciendo en realidad y ayudar a la reutilización. Incluso puede revelar maneras de calcular una serie de valores de una manera mejor y más sistemática, y / o de manera más eficiente.

Una nota sobre este caso particular (que puede ignorarse): en este caso particular, no me gustaría convertir nTrues en una lista infinita (¡lo que sería una CAF nuevamente, reintroduciendo el problema original!) En lugar de una función. Una razón es que aunque twoTrues podría ser útil en la forma de una lista infinita, no veo cómo sería útil (en mi aplicación, de todos modos) que nTrues tenga la forma de una lista infinita.

Answer 7

Un ejemplo completo

Aquí hay un pequeño ejemplo que muestra la situación:

module A where
big :: () -> [Int]
big _ = [1..10^7]

Parece una función, ¿verdad? Pero, ¿qué hace GHC? ¡Flota la enumeración al nivel superior!

A.big1 :: [Int]
[ Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
ConLike=False, Cheap=False, Expandable=False,
Guidance=IF_ARGS [] 7 0}]
A.big1 =
case A.$wf1 10 A.big2 of ww_sDD { __DEFAULT ->
eftInt 1 ww_sDD
}
A.big :: () -> [Int]
[Arity=1,
Unf=Unf{Src=InlineStable, TopLvl=True, Arity=1, Value=True,
ConLike=True, Cheap=True, Expandable=True,
Guidance=ALWAYS_IF(unsat_ok=True,boring_ok=True)
Tmpl= / _ -> A.big1}]
A.big = / _ -> A.big1

Ooops!

Entonces, ¿qué podemos hacer?

Desactivar optimizaciones

Eso funciona, -Onot , pero no es deseable:

A.big :: () -> [Int]
[GblId, Arity=1]
A.big =
/ _ ->
enumFromTo
@ Int
$fEnumInt
(I# 1)
(^
@ Int
@ Type.Integer
$fNumInt
$fIntegralInteger
(I# 10)
(smallInteger 7))

No en línea, y más funciones

Haga que todo funcione, incluido el enumFromTo , canalizando el parámetro a través de los trabajadores:

big :: () -> [Int]
big u = myEnumFromTo u 1 (10^7)
{-# NOINLINE big #-}
myEnumFromTo :: () -> Int -> Int -> [Int]
myEnumFromTo _ n m = enumFromTo n m
{-# NOINLINE myEnumFromTo #-}

¡Ahora finalmente estamos libres de CAF! Incluso con -O2

A.myEnumFromTo [InlPrag=NOINLINE]
:: () -> Int -> Int -> [Int]
A.myEnumFromTo =
/ _ (n_afx :: Int) (m_afy :: Int) ->
$fEnumInt_$cenumFromTo n_afx m_afy
A.big [InlPrag=NOINLINE] :: () -> [Int]
A.big = / (u_abx :: ()) -> A.myEnumFromTo u_abx A.$s^2 lvl3_rEe

Hurra.

¿Qué no funciona?

Desactivar-pereza-completa

La transformación de holgazanería llena las definiciones hacia afuera. Está -O1 por defecto con -O1 o superior. Intentemos apagarlo con -fno-full-laziness . Sin embargo, no funciona.