101

I see go a lot when reading Haskell material or source, but I've never been really comfortable about it - (I guess it has the negative connotation of "goto" in my mind). I started learning Haskell with LYAH, and that's where I picked up the tendency to use acc and step when writing folds. Where does the convention for writing go come from?

Most importantly, what exactly is the name go supposed to imply?

Dan Burton
  • 53,238
  • 27
  • 117
  • 198
  • 4
    I usually call my function `loop` instead. – augustss Apr 30 '11 at 21:23
  • 2
    Never seen `go` in any Haskell material that I read. Can you give an example/reference? – Ionuț G. Stan Apr 30 '11 at 21:41
  • @Ionuț For example, the [Yesod book's explanation of the Enumerator package](http://www.yesodweb.com/book/enumerator). (Why the Yesod book dedicates so much material to the topic I don't know, but that's beside the point) – Dan Burton Apr 30 '11 at 21:46
  • For what it's worth, I've seen many C/C++ programmers who also name their helper functions "go" when they can't think of a better name. – ShreevatsaR May 01 '11 at 04:39
  • 2
    FWIW, explicit tail recursion _is_ the functional version of goto in a lot of ways, including the potential for obfuscation. Static typing and scoping rules help keep the confusion to a minimum, though. And as for choice of the name, I like @Michael Snoyman's answer below about length and suitability. Also, when there's just one helper function its name seems largely irrelevant, so I generally just pick either 'go' or 'loop' because I have to pick _something_ and those both make sense. I tend to prefer 'go' for lazy loops and "loop" for strict ones. – mokus May 03 '11 at 14:21

3 Answers3

152

Hmm! Some archaeology!

Since around 2004 I've used go as the generic name for tail-recursive worker loops, when doing a worker/wrapper transformation of a recursive function. I started using it widely in bytestring, e.g.

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

was from bytestring in August 2005.

This got written up in RWH, and probably was popularized from there. Also, in the stream fusion library, Duncan Coutts and I started doing it a lot.

From the GHC sources

The idiom goes back further though. foldr in GHC.Base is given as:

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

which is probably where I picked up the trick (I'd thought this was from Andy Gill's thesis, but can't find any use of go there). It isn't given in this form in Gofer, so I think this first appeared in the GHC code base.

By 2001, Simon Marlow was using go in some of the systems-level code, so we might place the blame somewhere in GHC, and this clue leads us to the GHC source, where go is widely used in worker functions:

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

Digging up old versions of GHC, we see that in GHC 0.29 this idiom does not appear, but by GHC 3.02 series (1998), the go idiom appears everywhere. An example, in Numeric.lhs, in the definition of showInt, dated to 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'
      }}

this is a different implementation to the one given in the H98 report. Digging into the implementation of "Numeric.lhs", however, we find that it isn't the same as the version that was added to GHC 2.06 in 1997, and a very interesting patch from Sigbjorne Finne appears, in April 1998, adding a go loop to Numeric.lhs.

This says that at least by 1998, Sigbjorne was adding go loops to the GHC "std" library, while simultaneously, many modules in the GHC compiler core had go loops. Digging further, this very interesting commit from Will Partain in July 1996 adds a "go" loop into GHC -- the code comes from Simon PJ though!

So I'm going to call this as a Glasgow idiom invented by people at Glasgow who worked on GHC in the mid 90s, such as Simon Marlow, Sigbjorn Finne, Will Partain and Simon Peyton Jones.

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
  • 6
    +1 for "the generic name for tail-recursive worker loops" which seems to be generally true for most uses I've seen. For a function `f`, I personally will usually use `f'` as the name for this sort of a thing, though using `go` as a sort of near-keyword idiom is something I might try to pick up. Interesting to note that `showInt` uses the idiom to avoid assessing the same guard multiple times. – Dan Burton Apr 30 '11 at 22:02
  • 1
    BTW, for "what exactly is the name go supposed to imply?" I would say it hints at `goto`, and at handing over control to a helper function. – Don Stewart May 01 '11 at 00:15
  • 29
    My vague recollection is that this is a Simon PJ-ism. I tend to use `loop` unless I'm modifying code that already uses the `go` convention. I always thought it was intended to mean literally "go", as in "go around the loop". – Simon Marlow May 01 '11 at 06:25
  • 6
    I always thought of "go" as a command to the worker function to begin its dirty recursive labor. In any case, personally, I picked it up from one of the stream fusion slides because adding ticks to the function name always had the problem that I would forget the tick. – Heinrich Apfelmus May 01 '11 at 06:27
  • 5
    I believe it has origins predating Haskell. go is a popular name for named lets in scheme (http://google.com/codesearch?as_q=%5C%28let%5C+go%5C+&as_lang=scheme , http://www.google.com/search?q=scheme+%22let+go%22+-let's+car+cdr) – Etienne Laurin May 01 '11 at 06:39
20

Obviously Don's answer is the correct one. Let me just add in a small detail (since it seems to be my writing that you're directly referring to): go is nice because it's only two letters.

Oh, and the reason the Yesod book devotes so much content to the enumerator package is because I'd already written up the three-part tutorial of enumerator as a blog post series, so decided I may as well include it in the book. The enumerator package is used in a number of places throughout Yesod, so it is relevant.

Michael Snoyman
  • 31,100
  • 3
  • 48
  • 77
  • 6
    +1 "go" being only 2 letters (and still meaningful) is a fact that is easy to under-appreciate. While I commented about the Yesod book's use of "go" (which was an excellent name choice for those examples, imho), I was actually reading [a StackOverflow answer](http://stackoverflow.com/questions/5841577/performance-problem-with-euler-problem-and-recursion-on-int64-types/5843344#5843344) that used "go" when I felt I should ask the question. I immediately remembered the Yesod book example, though, because it was memorable. Good stuff! – Dan Burton May 01 '11 at 06:52
11

I'd expect this idiom to be applicable not just to linear structures (and hence "loops"), but also to branching (tree-like) structures.

I wonder how often the go pattern corresponds to accumulation parameters and, more generally, with the continuation-encoding strategites that Mitch Wand explored in the paper Continuation-Based Program Transformation Strategies (one of my all-time favorite papers). In these cases, the go function has a particular meaning, which can then be used to derive efficient code from an elegant specification.

Conal
  • 18,517
  • 2
  • 37
  • 40
  • 1
    I think it bears mentioning that it is often hard to come up with good names for these functions for the simple reason that they typically refer to variables in an enclosing scope and therefore are not really complete. A descriptive name would likely look silly: something like `add_x` or `consOnto_xs`. – dfeuer Jul 27 '14 at 04:50