sirve - listas en haskell

Generación de código GHC para llamadas de función de clase de tipo

Question

En Haskell para definir una instancia de una clase de tipo, debe proporcionar un diccionario de funciones requeridas por la clase de tipo. Es decir, para definir una instancia de Bounded , debe proporcionar una definición para minBound y maxBound .

Para el propósito de esta pregunta, llamemos vtbl este diccionario para la instancia de clase de tipo. Déjame saber si esto es mala analogía.

Mi pregunta se centra en qué tipo de generación de código puedo esperar de GHC cuando invoco una función de clase de tipo. En tales casos veo tres posibilidades:

1. La búsqueda de vtbl para encontrar la función de implementación está inactiva en el tiempo de ejecución
2. la búsqueda vtbl se realiza en tiempo de compilación y se emite una llamada directa a la función de implementación en el código generado
3. la búsqueda de vtbl se realiza en tiempo de compilación y la función de implementación está en línea en el sitio de la llamada

Me gustaría entender cuándo ocurren cada uno de estos, o si hay otras posibilidades.

Además, ¿importa si la clase de tipo se definió en un módulo compilado por separado en lugar de ser parte de la unidad de compilación "principal"?

En un programa ejecutable, parece que Haskell conoce los tipos de todas las funciones y expresiones en el programa. Por lo tanto, cuando invoco una función de clase de tipo, el compilador debería saber qué es vtbl y exactamente a qué función de implementación llamar. Espero que el compilador genere al menos una llamada directa a la función de implementación. ¿Es esto cierto?

(Digo "programa ejecutable" aquí para distinguirlo de compilar un módulo que no ejecutas.)

Answer 1

Como con todas las buenas preguntas, la respuesta es "depende". La regla de oro es que hay un costo de tiempo de ejecución para cualquier código de clase-polimórfico. Sin embargo, los autores de bibliotecas tienen mucha flexibilidad para eliminar este costo con las reglas de reescritura de GHC, y en particular hay un pragma {-# SPECIALIZE #-} que puede crear automáticamente versiones monomórficas de funciones polimórficas y usarlas siempre que la función polimórfica pueda ser Se infiere para ser utilizado en el tipo monomórfico. (El precio para hacer esto es la biblioteca y el tamaño del ejecutable, creo.)

Puede responder a su pregunta para cualquier segmento de código en particular usando la marca -ddump-simpl de -ddump-simpl . Por ejemplo, aquí hay un breve archivo de Haskell:

vDouble :: Double
vDouble = 3
vInt = length [2..5]
main = print (vDouble + realToFrac vInt)

Sin optimizaciones, puede ver que GHC realiza la búsqueda del diccionario en tiempo de ejecución:

Main.main :: GHC.Types.IO ()
[GblId]
Main.main =
  System.IO.print
    @ GHC.Types.Double
    GHC.Float.$fShowDouble
    (GHC.Num.+
       @ GHC.Types.Double
       GHC.Float.$fNumDouble
       (GHC.Types.D# 3.0)
       (GHC.Real.realToFrac
          @ GHC.Types.Int
          @ GHC.Types.Double
          GHC.Real.$fRealInt
          GHC.Float.$fFractionalDouble
          (GHC.List.length
             @ GHC.Integer.Type.Integer
             (GHC.Enum.enumFromTo
                @ GHC.Integer.Type.Integer
                GHC.Enum.$fEnumInteger
                (__integer 2)
                (__integer 5)))))

... el bit relevante es realToFrac @Int @Double . En -O2 , por otro lado, puede ver que el diccionario realizó una búsqueda estática e incorporó la implementación, con el resultado de una sola llamada a int2Double# :

Main.main2 =
  case GHC.List.$wlen @ GHC.Integer.Type.Integer Main.main3 0
  of ww_a1Oq { __DEFAULT ->
  GHC.Float.$w$sshowSignedFloat
    GHC.Float.$fShowDouble_$sshowFloat
    GHC.Show.shows26
    (GHC.Prim.+## 3.0 (GHC.Prim.int2Double# ww_a1Oq))
    (GHC.Types.[] @ GHC.Types.Char)
  }

También es posible que un autor de biblioteca elija reescribir la función polimórfica a una llamada a una función monomórfica pero no en línea la implementación de la función monomórfica; esto significa que todas las posibilidades que propusiste (y más) son posibles.

Answer 2

Como otras respuestas describen, cualquiera de estos puede suceder en diferentes situaciones. Para cualquier llamada de función específica, la única manera de estar seguro es mirar el núcleo generado. Dicho esto, hay algunos casos en los que puedes tener una buena idea de lo que sucederá.

Usando un método de clase de tipo en un tipo monomórfico.

Cuando se llama a un método de clase de tipo en una situación en la que el tipo se conoce completamente en tiempo de compilación, GHC realizará la búsqueda en tiempo de compilación. Por ejemplo

isFive :: Int -> Bool
isFive i = i == 5

Aquí el compilador sabe que necesita el diccionario de ecuaciones de Int , por lo que emite código para llamar a la función de forma estática. El hecho de que esa llamada esté o no incorporada depende de las reglas de alineación habituales de GHC, y si un pragma INLINE aplica o no a la definición del método de clase.

Exponer una función polimórfica.

Si se expone una función polimórfica desde un módulo compilado, entonces el caso base es que la búsqueda debe realizarse en tiempo de ejecución.

module Foo (isFiveP) where

isFiveP :: (Eq a, Num a) => a -> Bool
isFiveP i = i == 5

Lo que realmente hace GHC es transformar esto en una función de la forma (más o menos)

isFiveP_ eqDict numDict i = (eq_op eqDict) i (fromIntegral_fn numDict 5)

por lo tanto, las búsquedas de funciones deberían realizarse en tiempo de ejecución.

Ese es el caso base, de todos modos. Lo que realmente sucede es que GHC puede ser bastante agresivo con respecto a la incorporación de módulos cruzados. isFiveP es lo suficientemente pequeño como para isFiveP en el sitio de la llamada. Si el tipo se puede determinar en el sitio de la llamada, entonces las búsquedas en el diccionario se realizarán en tiempo de compilación. Incluso si una función polimórfica no está directamente incorporada en el sitio de la llamada, las búsquedas en el diccionario aún se pueden realizar en tiempo de compilación debido a las transformaciones habituales de la función de GHC, si el código llega a un formulario donde la función (con parámetros de diccionario de clase) puede Se aplicará a un diccionario estáticamente conocido.

Answer 3

Si el compilador puede "indicar", en tiempo de compilación, qué tipo real está usando, entonces la búsqueda del método ocurre en tiempo de compilación. De lo contrario, sucede en tiempo de ejecución. Si la búsqueda se realiza en tiempo de compilación, el código del método puede estar en línea, según el tamaño del método. (Esto también se aplica a las funciones normales: si el compilador sabe a qué función está llamando, la integrará si esa función es "lo suficientemente pequeña").

Considere, por ejemplo, (sum [1 .. 10]) :: Integer . Aquí el compilador sabe estáticamente que la lista es una lista de tomas de Integer , por lo que puede alinear la función + para Integer . Por otro lado, si haces algo como

foo :: Num x => [x] -> x
foo xs = sum xs - head x

luego, cuando llama a sum , el compilador no sabe qué tipo está usando. (Depende de qué tipo se le da a foo ), por lo que no puede hacer ninguna búsqueda en tiempo de compilación.

Por otro lado, utilizando el pragma {-# SPECIALIZE #-} , puedes hacer algo como

{-# SPECIALIZE foo:: [Int] -> Int #-}

Lo que esto hace es decirle al compilador que compile una versión especial de foo donde la entrada es una lista de valores Int . Obviamente, esto significa que para esa versión , el compilador puede hacer todas las búsquedas de métodos en tiempo de compilación (y casi con seguridad en línea). Ahora hay dos versiones de foo : una que funciona para cualquier tipo y realiza búsquedas de tipo en tiempo de ejecución, y otra que solo funciona para Int , pero es [probablemente] mucho más rápida.

Cuando llamas a la función foo , el compilador tiene que decidir a qué versión llamar. Si el compilador puede "indicar", en tiempo de compilación, que desea la versión Int , lo hará. Si no puede "decir" qué tipo de letra va a usar, usará la versión más lenta de cualquier tipo.

Tenga en cuenta que puede tener múltiples especializaciones de una sola función. Por ejemplo, podrías hacer

{-# SPECIALIZE foo :: [Int] -> Int #-}
{-# SPECIALIZE foo :: [Double] -> Double #-}
{-# SPECIALIZE foo :: [Complex Double] -> Complex Double #-}

Ahora, cada vez que el compilador puede decir que estás usando uno de estos tipos, usará la versión codificada para ese tipo. Pero si el compilador no puede saber qué tipo está usando, nunca usará las versiones especializadas, y siempre la polimórfica. (Eso podría significar que necesita especializar las funciones que llaman a foo , por ejemplo).

Si se arrastra alrededor de la salida Core del compilador, probablemente pueda averiguar exactamente lo que hizo en cualquier circunstancia particular. Probablemente te volverás completamente loco, aunque ...