Fudging generics in Go with AST rewriting

By: on October 30, 2013

One possible workaround for a lack of generics is code generation. Let’s look at Go’s AST manipulation to make a Maybe Int out of a Maybe a.

The Maybe monad is a nice simple structure, representing a computation that may complete successfully (returning a Just containing the result) or fail (returning Nothing). Writing the no-it’s-not-using-generics implementation in Go is easy enough:

package maybe

type Value interface{}

type Maybe interface {
        Bind(func(v Value) Maybe) Maybe

type Nothing struct{}

func (n Nothing) Bind(f func(v Value) Maybe) Maybe {
        return n

type Just struct {
        Value Value

func (j Just) Bind(f func(v Value) Maybe) Maybe {
        return f(j.Value)

(The implementation is deliberately bare-boned. We’d really want a whole bunch of additional helpers, like the function Maybe(m Maybe, default interface{}) interface{}, but for our purposes let’s just keep things simple.)

First, what should the output look like? Clearly, the Value type serves as a placeholder for what we really want – int, complex128, whatever. That means removing the Value type declaration entirely, and replacing references to this type with our target type. Let’s also adjust the package name, so we’ll convert monad Foo’s package from foo to foo_int. That will let us keep our packages nice and small.

The first step is getting the AST, which is trivial:

fset := token.NewFileSet()
f, err := parser.ParseFile(fset, "maybe.go", nil, 0)
if err != nil {
        fmt.Println("Oops! Can't parse the source: %vn", err)

Rewriting the AST happens through the Walk(v Visitor, node Node) function, which we’ve seen before:

v := rewrite.MonadRewriter{"int"}
ast.Walk(v, f)


type MonadRewriter struct {
        TypeName string

Why a string? It just means that the rewriter doesn’t need to import any types. And so on to the meat, rewriting the AST. Go gives us a very neat way of switching on type, so we’ll use that as our find-all-the-things:

func (v MonadRewriter) Visit(node ast.Node) ast.Visitor {
        switch n := node.(type) {
        case *ast.File:
                        // Change the package name
                        n.Name.Name = n.Name.Name + "_int"

                        // Find the Value type declaration...
                        valueIndex := -1
                        for i, m := range n.Decls {
                                d, ok := m.(*ast.GenDecl)
                                if ok {
                                        for _, k := range d.Specs {
                                                t, ok := k.(*ast.TypeSpec)
                                                if ok {
                                                        if t.Name.Name == "Value" {
                                                                valueIndex = i

                        // and remove it by rebuilding the slice.
                        if valueIndex >= 0 {
                                n.Decls = append(n.Decls[:valueIndex], n.Decls[valueIndex+1:]...)
        case *ast.Field:
                        if f, ok := n.Type.(*ast.Ident); ok {
                                if f.Name == "Value" {
                                        f.Name = v.TypeName
        return v

We have eight levels of indentation there, in the *ast.File match. Not ideal! In production code we’d Extract Method all over this, but that would detract from the code clarity in this presentation.

There is one thing missing from the above: if we wanted to make a Maybe for some arbitrary type, we’d need an extra parameter to import the package that contained that type’s declaration.

In summary, we’ve seen that altering an abstract syntax tree in Go is pretty simple, by making in-place changes to the tree during a Walk. Having access to the AST means that we can easily write a code generator to produce type-specific monads/containers.


Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>