The power of single-method interfaces in Go

The tree search example using SMIs

The previous post demonstrated a Go solution using higher-order functions for the tree search problem described earlier. I encourage you to review the earlier posts to get the most out of this one.

Let's now see how the same task can be accomplished using SMIs instead of HOFs; the full code is on GitHub. Starting with the types:

type State int
type States []State

// GoalDetector is an interface that wraps a single IsGoal method. IsGoal
// takes a state and determines whether it's a goal state.
type GoalDetector interface {
  IsGoal(s State) bool
}

// SuccessorGenerator is an interface that wraps a single Successors method.
// Successors returns the successors of a state.
type SuccessorGenerator interface {
  Successors(s State) States
}

// Combiner is an interface that wraps a single Combine method. Combine
// determines the search strategy by combining successors of the current state
// with all the other states into a single list of states.
type Combiner interface {
  Combine(succ States, others States) States
}

These are the equivalent SMIs to the GoalP, Successors and Combiner function types we've seen before; the names are slightly modified to be more suitable for interfaces and their methods.

The tree search itself - using these interfaces - is almost identical to the previous version:

func treeSearch(states States, gd GoalDetector, sg SuccessorGenerator, combiner Combiner) State {
  if len(states) == 0 {
    return -1
  }

  first := states[0]
  if gd.IsGoal(first) {
    return first
  } else {
    return treeSearch(combiner.Combine(sg.Successors(first), states[1:]), gd, sg, combiner)
  }
}

To implement BFS, we reuse prependOthers from the previous post (it remains identical):

And again, appendOthers and implementing DFS:

func bfsTreeSearch(start State, gd GoalDetector, sg SuccessorGenerator) State {
  return treeSearch(States{start}, gd, sg, CombineFunc(prependOthers))
}

What is CombineFunc? Since prependOthers is a function - while treeSearch takes interfaces - we need an adapter type:

type CombineFunc func(States, States) States

func (f CombineFunc) Combine(succ States, others States) States {
  return f(succ, others)
}

If you have a bit of Go experience already, this may seem familiar. It's exactly the same breed of adapter as http.HandlerFunc. Unfortunately, at this time a Go function cannot be assigned to a SMI with a compatible method signature, so these adapters are required (see the Appendix for more details).

The rest of the code is also very similar, with an adapter thrown in here and there. Feel free to read the rest of it and compare to the HOF version.

Since a SMI wraps a method, it can do whatever a function type can do. We can pass SMIs to functions; we can return SMIs from functions. There are tons of examples of this across the Go standard library, and in almost any non-trivial Go project.

So is this it? Are SMIs just a cumbersome variation on higher-order functions? No, not at all. The code sample used in this blog post is unfair to SMIs because it was originally written and designed for HOFs. What's important to take from here is that it's also possible to accomplish the same goal with SMIs. This is the basis of the power of SMIs - they can serve the same role as higher-order functions; but they have additional features that HOFs lack.

SMIs are more general than function types

In examining the generality of SMIs, the topic of state immediately comes up. I will only discuss it briefly, because it's a known red herring. One could claim that SMIs are more general because they can represent objects with built-in state (for example, a struct value where the struct type implements a SMI). Functions can represent state too, however, by means of closures. In fact, our sample code clearly shows this in functions like stateIs and costDiffTarget.

The real reasons for why SMIs are more general are:

1. SMIs naturally extend to multi-method interfaces
2. Go values can implement more than one interface

Let's discuss these in detail.

Single-method interfaces; it's in the name! Interfaces with a single method to implement, like the ubiquitous io.Reader:

type Reader interface {
  Read(p []byte) (n int, err error)
}

But just as easily, Go has multi-method interfaces, like io.ReadWriter [1]:

type ReadWriter interface {
  Read(p []byte) (n int, err error)
  Write(p []byte) (n int, err error)
}

There are many other useful multi-method interfaces in the standard library: net/http.ResponseWriter, context.Context, fs.File and so on. While the extension from a SMI to a multi-method interface in Go is trivial, this is difficult and unnatural to achieve with function types [2].

Next, a single Go value can implement multiple interfaces. Implicit interface implementation is one of the banner features of Go - a type does not have to declare that it implements an interface; it does so implicitly if it has the right method. There are many good examples of this in the Go standard library; for example the encoding.BinaryMarshaler interface:

type BinaryMarshaler interface {
  MarshalBinary() (data []byte, err error)
}

And the encoding/json.Marshaler interface:

type Marshaler interface {
  MarshalJSON() ([]byte, error)
}

A type like time.Time implements both, and can thus be encoded into a binary format and JSON.

Another interesting example is the fmt.Stringer interface:

type Stringer interface {
  String() string
}

Many Go types implement this interface along with other interfaces (time.Time does too, of course); overall it's not uncommon to see large, sophisticated types implementing 5 or more interfaces.

Both of the capabilities presented here (multi-method interfaces and a single value implementing multiple SMIs) are very hard to achieve with function types and first-class functions.

Conclusion

The goal of this post was to discuss the prevalence and power of single-method interfaces (SMIs) in Go. It started by showing how SMIs can do whatever higher-order functions (HOFs) can do (albeit somewhat more verbosely, given that the task at hand was tailored for HOFs in previous posts).

Then, we discussed additional capabilities of SMIs that make them unique and aren't achievable with HOFs in a reasonable way.

In functional languages, HOFs are heavily used to implement sophisticated and useful abstractions. In Go, you can use HOFs as well but most Go code prefers to use SMIs for this purpose, because of the added generality.

So which approach should you use? The best tool for the job at hand, of course. While SMIs are more general and powerful, they are also more verbose for the simple cases. When all you need is a function - use a function! Otherwise, interfaces are a powerful and versatile tool Go programmers employ for many tasks.

Appendix: adapter types for converting functions to SMIs

There is some work in the Go developer community to reduce the toil required to convert between a plain function and a SMI. Here's one proposal that was discussed fairly recently and is currently at an advanced stage - waiting for a prototype before decision. In our example with the Combiner interface, this would enable writing:

Combiner(prependOthers).Combine

Instead of having to define the CombineFunc adapter. While it's still not as terse as passing prependOthers where a Combiner is expected, it's an appreciable reduction in boilerplate. For the more ambitious notion of assignability, there's an older, farther-reaching proposal.