Tail recursion with trampoline in Go

July 06, 2019 3 minutes reading time Development go fp

The Go compiler is another example for missing support for proper tail call optimization. It’s a deliberate choice: reusing and thereby overwriting the current stack frame with the next one deletes all information needed to provide a meaningful stacktrace in the case of an error. This is one of the reasons that Go does not support it. See my previous post on the topic of using the trampoline device in JavaScript for a more general discussion.

The following example shows you how to use the trampoline device in Go. We will implement the famous Fibonacci numbers this way.

The Go type system

Since Go is a statically typed language, every function, parameter, variable, etc. has to have a type at compile time. Go has no generics either, which makes it more verbose, because generics allow you to abstract the same algorithm over multiple data types. That’s why you cannot write a trampoline device in Go that is applicable for all function signatures like in JavaScript. Well, maybe you could by using reflection, but that is not considered idiomatic for the language.

The solution

We’ll walk backwards: the call to the function should look like this: fib(10). We expect the result 55. So the type of this function is func(int) int, a function that expects an int-argument and returns a int. It follows, that this is the type of the return value of the trampoline function.

We know that we have to call the trampoline function with the thunking version of the function that produces the Fibonacci numbers.

The signature of this thunking version is simple. We have to supply all the parameters and aggregator values and expect either a result of type int or a function with no parameters at all, that returns either the result or another function with no parameters. Let’s call this last recursive function type thunkType and define it: type thunkType func() (int, thunkType). So the return type of the thunkFib function is a tuple: (int, thunkType). The parameters are n int for the argument proper, and the two aggregators prev and curr (starting with 0 and 1).

The last thing we need is a function inside of thunkFib that wraps all the parameters in a function with no arguments and returns a tuple - either the final result or another thunkType. Let’s define its own type: type fnType func(int, int, int) (int, thunkType).

Now we’re ready to write this wrapper function thunk and use it inside our thunkFib function.

package main

import (
	"fmt"
)

// parameters are n, prev, and current
// return either the result (int) or a thunkType if not done
type fnType func(int, int, int) (int, thunkType)

// return either the result (int) or another thunk
type thunkType func() (int, thunkType)

func thunk(fn fnType, n int, prev int, curr int) thunkType {
	return func() (int, thunkType) {
		return fn(n, prev, curr)
	}
}

func thunkFib(n int, prev int, curr int) (int, thunkType) {
	if n == 0 {
		return prev, nil
	}
	if n == 1 {
		return curr, nil
	}
	// since we return another thunk, the int result does not matter
	return 0 /* unused */, thunk(thunkFib, n-1, curr, curr+prev)
}

func trampoline(fn fnType) func(int) int {
	return func(n int) int {
		result, f := fn(n, 0, 1) // initial values for aggregators
		for {
			if f == nil {
				break
			}
			result, f = f()
		}
		return result
	}
}

func main() {
	n := 10 // fib(10) == 55
	fib := trampoline(thunkFib)
	fmt.Printf("Fibonacci(%d) = %d\n", n, fib(n))
}