What is the idiomatic way in Go to create a complex hierarchy of structs?

Question

I am writing an interpreter in Go and I am looking for the idiomatic way to store the AST. I read the Go compiler source code and it seems they used interfaces with an empty method to represent the AST. For example, we have the following hierarchy,

Object
--Immovable
----Building
----Mountain
--Movable
----Car
----Bike

This is how the above hierarchy is implemented in the "empty method" way.

type Object interface {
  object()
}

type Immovable interface {
  Object
  immovable()
}

type Building struct {
  ... 
}

type Mountain struct {
  ... 
}

type Movable interface {
  Object
  movable()
}

type Car struct {
  ...
} 

type Mountain struct {
  ...
} 

func (*Building) object() {}
func (*Mountain) object() {}
func (*Car) object() {}
func (*Bike) object() {}
func (*Building) immovable() {}
func (*Mountain) immovable() {}
func (*Car) movable() {}
func (*Bike) movable() {}    

The above code is a contrived example and this is how the Go compiler implemented the AST with dozens of empty methods. But WHY? Note how many empty methods are defined. It may get very complicated with the increase of the depth of the hierarchy.

It is stated in the comments that the empty methods disallow the assignment of incompatible types. In our example, a *Car can't be assigned to a *Immovable for instance.

This is so easy in other languages like C++ that supports inheritance. I can't think of any other way of representing the AST.

The way how the Go compiler AST is implemented may be idiomatic but isn't it less straight forward?

Answer 1

Go is not (quite) an object oriented language: it does not have classes and it does not have type inheritance; but it supports a similar construct called embedding both on struct level and on interface level, and it does have methods.

Interfaces in Go are just fixed method sets. A type implicitly implements an interface if its method set is a superset of the interface (there is no declaration of the intent).

Empty methods are great if you want to document or state explicitly that your type does implement an interface (because it is not stated explicitly). Official Go FAQ: How can I guarantee my type satisfies an interface?

type Fooer interface {
    Foo()
    ImplementsFooer()
}

If you want a distinction in your type hierarchy (e.g. you don't want to allow an object to be both Movable and Immovable), they must have different method sets (there must be at least 1 method in each of the method sets of Movable and Immovable that is not present in the other's), because if the method sets would contain the same methods, an implementation of one would automatically implement the other too therefore you could assign a Movable object to a variable of type Immovable.

Adding an empty method to the interface with the same name will provide you this distinction, assuming that you will not add such methods to other types.

Reducing the number of empty methods

Personally I have no problem with empty methods whatsoever. There is a way to reduce them though.

If you also create a struct implementation for each type in the hierarchy and each implementation embeds the struct implementation one level higher, the method set of one level higher will automatically come without further ado:

Object

Object interface and ObjectImpl implementation:

type Object interface {
  object()
}
type ObjectImpl struct {}
func (o *ObjectImpl) object() {}

Immovable

Immovable interface and ImmovableImpl implementation:

type Immovable interface {
    Object
    immovable()
}
type ImmovableImpl struct {
    ObjectImpl // Embed ObjectImpl
}
func (o *Immovable) immovable() {}

Note ImmovableImpl only adds immovable() method, object() is "inherited".

Building

Building implementation:

type Building struct {
    ImmovableImpl // Embed ImmovableImpl struct

    // Building-specific other fields may come here
}

Note Building does not add any new methods yet it is automatically an Immovable object.

The advantage of this technic grows greatly if the number of "subtypes" increases or if the interface types have more than just 1 "marker" method (because all methods are "inherited").