Continuation-Passing style in Go

Go is a versatile language and generally does not try to enforce a certain style of programming on its users. As such, it’s perfectly possible to write in a functional style using Go. One style of programming that is possible in functional languages is known as the “Continuation-Passing style (CPS)” of programming.

The main difference with how we’d usually structure code, is that control flow is achieved by passing new functions up the stack. In practice this means that any function takes another function (a continuation) as its argument. Wikipedia does a good job at explaining this, far better than I could: https://en.wikipedia.org/wiki/Continuation-passing_style. However, the article is missing a Go implementation. And with good reason, Go is not the typical language where you’d expect this kind of programming.

There’s one main requirement for a language to support CPS, and that is to have first-class functions, which Go has. However, in an ideal world, a second requirement would be to have Tail-Call optimization. Without this, you’re going to cripple performance when writing recursive CPS functions. Sadly, Go does not have this as of 1.13. This does not mean you’d never use Recursion in Go — but you’d tend to be more mindful about where you want to use it.

Anyway, onwards to some actual code we Go!

Our goal is to write a factorial function, the factorial(n) being defined as the product of all positive integer less than or equal to n. Hence factorial(5) = 5 * 4 * 3 * 2 * 1 = 120.

As mentioned, our function will have at least one other function as an argument. In addition to this, we want to know our ’n’ value.

func factorial(n int, f func(int)) 

We’re dealing with recursion, so we’ll want to set-up a base case to end recursion. Our base case would be n == 1 at which point we’ll want to go up the call stack with f(1) . In case we’ve not yet reached 1, we’ll want to recursively call our factorial function and add a multiplication function call. Notice I mention ‘multiplication function call’, we won’t yet perform the multiplication.

The body of our function thus becomes:

func factorial(n int, f func(int)) {
   if n == 1 {
       f(1) // base-case
   } else {
       factorial(n - 1, func(y int) { f(n * y) })
   }
}

Notice how we don’t just recursively call factorial with a multiplication, instead we pass on a function to the next factorial call in which we’ll multiply the current n with y . Our y won’t hold a value just yet, but it will deeper down the stack. This function is a ‘closure’, as we’re using the outer-scope n value.

We could call this function like so:

factorial(5, func(i int) { fmt.Printf("result: %v", i})

Which would return result: 120 . The function we pass to the factorial function first is the last function to get executed. Because with each step in the recursion we ‘go deeper’ and add layers of functions on top of each other. When we reach our base case, we’re resolving each function is reverse-calling order.

Go is a pretty fun language for exactly this reason, you can write code (pretty much) the way you want. It might not be a great idea to do so, but at least it’s possible. 😅

If you enjoyed this topic, consider buying my book “Functional Programming in Go”, which explores this topic and many more: https://www.amazon.ca/Functional-Programming-functional-testability-readability/dp/1801811164