A non-orthogonal feature of Golang and how it broke my transpiler

I just ran into a problem that illustrates a couple of strategies for implementing compilers, so let's dig into it and see what we can learn.

I'm working on a Go transpiler, that is, a compiler that transforms Go code into different Go code. One of the properties of this compiler is that we need to reify functions as objects, so function types also need to be translated to interfaces to capture their signatures. For our purposes, let's say we translate:

type IntHasProperty func(int) bool

into:

type IntHasProperty interface {
    Call(int) bool
}

This captures the essential input and output types of the function, and we can imagine extending it with generics if we need to. There is one fundamental problem. Suppose in our source code, we write:

func (p IntHasProperty) IsNot(n int) bool {
    return !p(n)
}

If we try to compile this method, we'd expect to transform the function call site:

func (p IntHasProperty) IsNot(n int) bool {
    return !p.Call(n)
}

But the Go compiler complains:

invalid receiver type MyType (pointer or interface type)

An interface can't be a receiver type, which should be obvious, since it's not a concrete type, but this is in contrast to every other type we can declare in Go. If we relaxed this restriction, an interface would no longer be an interface, which by its nature cannot have defined methods (or else it would be more like a mixin or abstract class). It's also a consequence of the way interface values are laid out in memory in Go. We can sidestep this limitation by instead translating the original type to:

type IntHasProperty struct {
    f interface {
        Call(int) bool
    }
}

This requires that we keep track of the fact that every value of this type is wrapped in a struct so that at usage time, we can dereference it:

func (p IntHasProperty) IsNot(n int) bool {
    return !p.f.Call(n)
}

Furthermore, when we assign to a variable of this type, we need to wrap it. We need to translate:

var isEven IntHasProperty
k := 2
isEven = func(n int) bool {
    return n%k == 0
}

to:

type isEvenFunc struct {
    k int
}

func (f isEvenFunc) Call(n int) bool {
    return n%f.k == 0
}

var isEven IntHasProperty
isEven = IntHasProperty{isEvenFunc{k: 2}}

There's a bunch going on there with the variable capture and implementing the functional interface with a new isEvenFunc type, but the key point is that we need to wrap functional instances of a type.

This whole episode illustrates two general techniques for implementing languages, whether they be with compilers or interpreters:

1. Snarfing is borrowing features from the target system to implement the same feature in your higher level system. For example, if you are compiling down to ARM assembly, you don't need to reinvent integer addition in your compiler. You just snarf the integer addition feature of the chip and use it whenever you need to add something. In my case in this post, we are snarfing a lot of things: types, receiver methods, functions, etc. We tried to snarf receiver methods on function types though, and failed, which leads to:
2. Reifying is making something that is implicit in a system explicit. In our case, we started by reifying a function type as an interface to satisfy other requirements of our language. When that failed, we made a different choice and reified function types as structs of interfaces instead.

These concepts represent a ladder of complexity. As implementers we'd like to borrow (or snarf) as much as possible from a target system, reifying only what we must in order to solve our problems. You might expect that transpiling Go to Go should allow us to snarf a lot, and you'd be right. The wrinkles show up where we want our system to do something different, and expand from there.

Conversely, we can choose to create a higher level system that defines its concepts more similarly to the underlying system, as C did for the PDP-11. Only when we have firm requirements on both the high level and target system sides might we need to implement a lot more translation. Since we want to keep our systems simple, we can use any flexibility we have on either side to build more but write less.