technology from back to front

Fudging generics in Go with AST rewriting

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)
        return
}

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)

where

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

                        // 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.

by
Frank Shearar
on
30/10/13
 
 


4 + = ten

2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us