Хаскелл: почему конвенция для обозначения вспомогательной функции "идет"?

Я часто вижу go при чтении материала или источника Haskell, но мне это никогда не нравилось - (на мой взгляд, у меня есть отрицательная коннотация "goto" ). Я начал изучать Haskell с LYAH, и там, где я набирал тенденцию использовать acc и step при написании сгибов. Откуда взялось соглашение для написания go?

Самое главное, что именно подразумевается под именем go?

Ответ 1

Хм! Некоторая археология!

С 2004 года я использовал go как общее имя для хвостовых рекурсивных циклов рабочих, когда выполнял преобразование рабочего/обертки рекурсивной функции. Я начал широко использовать его в bytestring, например.

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

был от bytestring в августе 2005 года.

Это записано в RWH и, вероятно, было популяризировано оттуда. Кроме того, в библиотеке слияния потоков, Duncan Coutts и я начали делать это много.

Из источников GHC

Идиома возвращается еще дальше. foldr в GHC.Base дается как:

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

который, вероятно, там, где я подхватил трюк (я думал, что это было из тезиса Энди Гилла, но не может найти никакого использования go там). Он не указан в этой форме в Gofer, поэтому я думаю, что это впервые появилось в базе кода GHC.

К 2001 году Саймон Марло использовал код go в некотором коде системного уровня, поэтому мы могли бы поместить его в GHC, и этот ключ ведет нас к источник GHC, где go широко используется в рабочих функциях:

myCollectBinders expr
  = go [] expr
  where
    go bs (Lam b e)          = go (b:bs) e
    go bs [email protected](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 и Глазго

Выкапывая старые версии GHC, мы видим, что в GHC 0.29 эта идиома не появляется, но серия GHC 3.02 (1998), идиома go появляется везде. Например, в Numeric.lhs, в определении showInt, датированном 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'
      }}

это другая реализация для приведенная в отчете H98. Однако, копаясь в реализации "Numeric.lhs" , мы обнаруживаем, что это не то же самое, что версия, добавленная в GHC 2.06 в 1997 году, и очень интересный патч от Sigbjorne Finne появляется в апреле 1998 года добавление цикла go к Numeric.lhs.

Это говорит о том, что, по крайней мере, к 1998 году Sigbjorne добавлял циклы go в библиотеку "std" GHC, а одновременно, многие модули в компиляторе GHC ядро имели циклы go. Копаясь дальше, этот очень интересный коммит от Will Partain в июле 1996 года добавляет цикл "go" в GHC - код исходит от Саймона PJ, хотя!

Итак, я собираюсь назвать это идиомой Глазго, изобретенной людьми из Глазго, которые работали в GHC в середине 90-х, например Саймон Марлоу, Sigbjorn Finne, Будет ли Partain и Саймон Пейтон Джонс.

Ответ 2

Очевидно, что ответ Дон правильный. Позвольте мне просто добавить небольшую деталь (поскольку, похоже, это мое письмо, на которое вы прямо ссылаетесь): go хорошо, потому что это всего две буквы.

О, и причина, по которой книга Есода посвящает столько контента пакету перечислителя, состоит в том, что я уже написал учебник из трех частей перечислителя в виде серии сообщений в блоге, поэтому я решил включить его в книга. Пакет перечислителя используется в нескольких местах по всему Yesod, поэтому он имеет значение.

Ответ 3

Я ожидаю, что эта идиома применима не только к линейным структурам (и, следовательно, к "петлям" ), но также к ветвящимся (древовидным) структурам.

Интересно, как часто шаблон go соответствует параметрам накопления и, в более общем плане, стратегиям кодирования продолжения, которые исследовал Митч Ванд в документе Продолжение Стратегии трансформации программ (одна из моих любимых статей за все время). В этих случаях функция go имеет особое значение, которое затем может использоваться для получения эффективного кода из элегантной спецификации.