Pregunta Haskell: ¿por qué la convención de nombrar una función auxiliar "ir"?


Ya veo go mucho al leer el material o la fuente de Haskell, pero nunca me he sentido realmente cómodo al respecto (supongo que tiene la connotación negativa de "goto" en mi mente). Empecé a aprender Haskell con LYAH, y ahí es donde recogí la tendencia a usar acc y step al escribir pliegues. ¿De dónde viene la convención para escribir go ¿viene de?

Lo más importante, ¿cuál es exactamente el nombre go se supone que implica?


73
2018-04-30 21:16


origen


Respuestas:


Hmm! Algo de arqueología!

Desde alrededor de 2004 he usado go como el nombre genérico para bucles de trabajador recursivo de cola, al realizar una transformación worker / wrapper de una función recursiva. Empecé a usarlo ampliamente en bytestring, p.ej.

foldr :: (Word8 -> a -> a) -> a -> ByteString -> a
foldr k v (PS x s l) = inlinePerformIO $ withForeignPtr x $ \ptr ->
        go v (ptr `plusPtr` (s+l-1)) (ptr `plusPtr` (s-1))
    where
        STRICT3(go)
        go z p q | p == q    = return z
                 | otherwise = do c  <- peek p
                                  go (c `k` z) (p `plusPtr` (-1)) q -- tail recursive
{-# INLINE foldr #-}

era de bytestring en agosto de 2005.

Esto se escribió en RWH, y probablemente fue popularizado desde allí. También, en la fusión de la secuencia biblioteca, Duncan Coutts y yo comenzamos a hacerlo mucho.

De las fuentes de GHC

La expresión se remonta más lejos sin embargo. foldr en GHC.Base se da como:

foldr k z = go
      where
         go []     = z
         go (y:ys) = y `k` go ys

que es probablemente donde recogí el truco (pensé que era de la tesis de Andy Gill, pero no puedo encontrar ningún uso de go ahí). Eso no es dado en esta forma en Gofer, así que creo que esto apareció por primera vez en la base de código de GHC.

En 2001, Simon Marlow estaba usando go en algunos de los códigos de nivel de sistemas, por lo que podríamos culpar a alguien en GHC, y esta pista nos lleva a la fuente de GHC, dónde go es ampliamente utilizado en las funciones de los trabajadores:

myCollectBinders expr
  = go [] expr
  where
    go bs (Lam b e)          = go (b:bs) e
    go bs e@(Note (SCC _) _) = (reverse bs, e)
    go bs (Cast e _)         = go bs e
    go bs (Note _ e)         = go bs e
    go bs e                  = (reverse bs, e)

GHC 3.02 y Glasgow

Desenterrando versiones antiguas de GHC, vemos que en GHC 0.29 este modismo no aparece, pero por GHC 3.02 series (1998), el go idioma aparece en todas partes. Un ejemplo, en Numeric.lhs, en la definición de showInt, fechado en 1996-1997:

showInt n r
  | n < 0     = error "Numeric.showInt: can't show negative numbers"
  | otherwise = go n r
    where
     go n r =
      case quotRem n 10 of                 { (n', d) ->
      case chr (ord_0 + fromIntegral d) of { C# c# -> -- stricter than necessary
      let
    r' = C# c# : r
      in
      if n' == 0 then r' else go n' r'
      }}

esta es una implementación diferente a la dado en el informe H98. Profundizando en la implementación de "Numeric.lhs"Sin embargo, encontramos que no es lo mismo que la versión que se agregó a GHC 2.06 en 1997, y aparece un parche muy interesante de Sigbjorne Finne, en abril de 1998, agregando un go loop a Numeric.lhs.

Esto dice que al menos en 1998, Sigbjorne estaba agregando go pasa a la biblioteca "std" de GHC, mientras que simultáneamente, muchos módulos en el núcleo del compilador GHC tenido go bucles. Excavar aún más, esto un compromiso muy interesante de Will Partain en julio de 1996 agrega un ciclo de "ir" a GHC


126
2018-04-30 21:52



Obviamente, la respuesta de Don es la correcta. Permítanme agregar un pequeño detalle (ya que parece ser mi escritura a la que se refiere directamente): ir es bueno porque son solo dos letras.

Ah, y la razón por la que el libro de Yesod dedica tanto contenido al paquete del enumerador es porque ya había escrito el tutorial en tres partes del enumerador como una publicación de blog, así que decidí incluirlo en el libro. El paquete del enumerador se usa en varios lugares a lo largo de Yesod, por lo que es relevante.


17
2018-05-01 02:58



Esperaría que este modismo fuera aplicable no solo a las estructuras lineales (y, por lo tanto, a los "bucles"), sino también a las estructuras de ramificación (tipo árbol).

Me pregunto con qué frecuencia go patrón corresponde a los parámetros de acumulación y, más en general, con las estrategias de codificación de continuación que Mitch Wand exploró en el documento Estrategias de Transformación de Programas Basados ​​en la Continuación (uno de mis papeles favoritos de todos los tiempos). En estos casos, el go función tiene un significado particular, que luego se puede utilizar para derivar el código eficiente de una especificación elegante.


11
2018-04-30 23:42