Row Polymorphism In Go?!

posted 29 Sep 2019

Note: I tried to make the code snippets readable on mobile phones, but it turned out to be harder than I anticipated – especially at the end of this post. If it’s too hard to read them, feel free to have a look later on your computer or tablet.

My favourite comp.sci. textbook has to be Purely Functional Data Structures by Chris Okasaki. The book shows you how to implement state-of-the-art purely functional data structures in a type-safe manner… or at least almost:

Unfortunately, we usually cannot implement structural decomposition directly in Standard ML. Although the definition of non-uniform recursive datatypes, the type system disallows most of the interesting functions on such types. […]

There are also several pragmatic reasons to prefer the non-uniform definition of 'a Seq over the uniform one:

  • First, it is more concise; […]
  • Second, depending on the language implementation, it may be more efficient […]
  • Third, and most importantly, it allows the type system to catch many more programmer errors. […]

OCaml – Standard ML’s “successor” – supports non-uniform recursive datatypes, so we can implement these data structures the “right” way there. What would happen if it wasn’t supported, though?

This will depend on the language, the use case and the community around the language. I suspect most people will instinctively shoehorn their problem into the type system. If not, one may attempt to bypass it, but will get discouraged by people saying – usually with reasonable arguments – that it’s not idiomatic. That in and of itself is not necessarily bad, but it can feel demoralising: You know there’s a better solution out there, but this type system doesn’t support it.

It’s therefore not surprising that the suggestion to add generics to Go makes a lot of people excited, myself included. Considering Go’s reach, I’d argue it is the biggest language change proposal with serious considerations and big impact for many developers.

As a big fan of data structures, Go’s support for general-purpose data structures is clunky and unsafe with the lack of generics. Having it in the language means I can reuse data structures I’ve needed in the past without feeling I’m “cheating” the type system.

But… generic types are not all roses. First, when it comes out, it will be this shiny new hammer developers will attempt to use for everything. But more importantly, it means developers may future proof designs, making things generic before the need arises. How to solve that is more of a people problem than anything else, one I don’t know the answer for.

For most people aware of Go, these arguments for and against generics is neither new or uncommon to hear about: The Internet has been discussing them since before Go 1.0 came out. But one issue that doesn’t typically reach outside the Go community is how to use (or not use) the context package.

The context.Context type is effectively used for two things: Managing timeouts/cancellation of long-running tasks, and for storing and retrieving contextual values. The package documentation, along with a blog post from Google on how they have used it internally, describes the recommended ways to use it.

Since there are a lot of things that people may want to cancel, a lot of packages now uses context pervasively. Of course, that is bound to create some discussion on how to use and not use it. As context objects may pass objects that bypass the type system, the discussion mostly resides around what values to put into a context, and some even argue that passing any kind of value with context is bad because it is not type-safe.

Not that I would expect it, but few people that have asked the question “what would it take to make it type-safe?”. There is one good blog post out there that takes Lisp’s dynamic variables and adds them to the Go language as a thought experiment. That seems to be it, though.

Middleware Woes

What isn’t often present in these context value discussions is the reusability aspect of middleware functions. I have seen one blog post that discusses this in detail, and ends up with the answer “it depends on your use case”.

Most people argue to pass databases to middleware functions explicitly, instead of via context. From Peter Bourgon’s Context post:

// Don't do this.
func MyMiddleware(next http.Handler) http.Handler {
    return http.HandlerFunc(func (w http.ResponseWriter, r *http.Request) {
        db := r.Context().Value(DatabaseContextKey).(Database)
        // Use db somehow
        next.ServeHTTP(w, r)
    })
}

// Do this instead.
func MyMiddleware(db Database, next http.Handler) http.Handler {
    return http.HandlerFunc(func (w http.ResponseWriter, r *http.Request) {
        // Use db here.
        next.ServeHTTP(w, r)
    })
}

This seems reasonable when you have such an abstract example, but you’ll notice certain issues with this approach when you try to apply it. Let’s consider a web page where we want to check if a user is an admin before they enter a route because we have a lot of “admin only” routes:

func VerifyIsAdmin(db *DB, next http.Handler) http.Handler {
  return http.HandlerFunc(func (w http.ResponseWriter, r *http.Request) {
    tok, err := GetToken(r)
    // handle err
    var u *User
    err = inTransaction(db, func(tx *Tx) error {
      u, err = users.GetByID(tx, tok.Username)
      return err
    })
    // handle err
    if !u.IsAdmin {
      http.Error(w, tok.Username + " is not an admin",
        http.StatusForbidden)
      return
    }
    next.ServeHTTP(w, r)
  }
}

func DoAdminThing(db *DB) http.Handler {
  return http.HandlerFunc(func (w http.ResponseWriter, r *http.Request) {
    tok, err := GetToken(r)
    // handle err
    err = inTransaction(db, func(tx *Tx) error {
      u, err := users.GetByID(tx, tok.Username)
      // handle err

      // do admin thing with user here
    })
    // handle err

    // write response
  }
}

inTransaction can be considered a utility function that ensures that we always commit/rollback a transaction correctly.

As you’ll notice, the recommended way of passing in database connections uses two transactions for a single successful request. Because we’re told to not rely on context for input data, we also “need” to duplicate a bit of code to fetch the user.

We can make the VerifyIsAdmin function into a function each admin HTTP handler calls, but as Jon Calhoun explains:

That is an awful lot of code to repeat across multiple handlers, and it is also very bug prone. Improper access controls shows up time and again on on lists like the OWASP Top 10, and in this case we appear to be making those mistakes even easier to make. All it takes is for a single developer to forget to verify that a user is an admin in a single handler, and we suddenly had an admin-only page being exposed to regular users. We certainly don’t want that to happen.

Row Polymorphism

If we go back to the question “what would it take to make context.Context type-safe?”, one possible answer would be row polymorphism.

Row polymorphism gives you the possibility to take an arbitrary record (struct), and then depend on specific fields and/or add additional fields to it. Here is an example where that would be beneficial:

Say you have a blog platform which contains users, blog posts, and comments. A user can author both blog posts and comments, and so our User struct contains a slice of blog posts and a slice of comments that they have created.

This is all well and fine, until we suddenly see a big spike of new users and posts on our platform (perhaps Medium’s popups got too annoying). With the new load and data sizes, it isn’t possible to always populate the blog posts and comments on a user all the time. And so we don’t, and our problems are gone for a little while.

But then, problems start to arise: We pass in a user with uninitialised blog posts to a function that uses those blog posts. Sometimes these even end up in production because our test coverage isn’t that great, as we have deadlines looming over us all the time.

Finally, one day we decide that enough is enough. We create 4 structs, depending on the use case: User, UserWithPosts, UserWithComments and UserWithPostsAndComments. To make the whole ordeal a bit easier for ourselves, we take in interfaces instead of user structs to support UserWithPostsAndComments in cases where we only need the blog posts/comments.

This is fine, albeit a bit cludgy. And it works, but you will feel the sense of foreboding for how we have to manage future fields. We know we need to add another field to the User struct at some point, and combinatorial explosion will make this more and more painful.

Row polymorphism will make this less painful. With it, you can say things like

I need a record R which contains the fields A and B

but you can go even further, and say

If you give me this record R with at least the fields A, B and C, then I can give you a record R with the same fields along with field D

Extending the Generics Draft

While rows polymorphism is great in certain cases, the language syntax needs to support it. So, how would that look like in Go?

Let’s assume that the Go 2 generics proposal goes through and that the proposed generics design is implemented. In that case, we can implement linked lists like this:

type List(type T) struct {
	elem T
	next *List(T)
}

func (l *List(T)) First() *T {
  // ...
}

Interestingly enough, the proposal does not discuss whether these forms are valid or not:

type WithInt(type T) struct {
	T
	Val int64
}

type GetInter(type T) interface {
	T
	GetInt() int64
}

Let’s assume that they are not, and that we extend the type system so that they mean the following:

// A struct that contains the value Val, and embeds
// any type T, along with all (exported and non-exported)
// methods of T.
type WithInt(type T) struct {
	T
	Val int64
}

// An interface that implements GetInt(), and all
// (exported and non-exported) methods of T.
type GetInter(type T) interface {
	T
	GetInt() int64
}

The rules of Go and generics are still the same, which means this Go code will build successfully:

type WithInt(type T) struct {
	T
	Val int64
}

func (wi WithInt) GetInt() int64 {
    return wi.Val
}

type WithFloat(type T) struct {
	T
	Val float64
}


func (wf WithFloat) GetFloat() float64 {
    return wf.Val
}

type FloatAndInt interface {
    GetFloat() float64
    GetInt() int64
}

// This typechecks...
var _ FloatAndInt = WithFloat{
  T: WithInt{
    T: nil,
    Val: 100,
  },
  Val: 1.0,
}

// order does not matter, so this does too
var _ FloatAndInt = WithInt{
  T: WithFloat{
    T: nil,
    Val: 1.0,
  },
  Val: 100,
}

This is pretty neat for a couple of reasons:

With this addition, we’re not able to support row polymorphism on struct fields, but we have managed to do it on interfaces: We can make functions that say

If you give me any interface type T, then I can give you back a new interface type U, which is the union of T and some other interface.

When used right, this can be very powerful.

Typed Middleware

To use row polymorphism in our HTTP middleware, we need to be able to tell exactly what kind of context type is stored inside http.Request. This can be done as follows:

type Request(type T context.Context) struct {
  // tons of fields
  ctx T
}

type Handler(type T) interface {
  ServeHTTP(ResponseWriter, *Request(T))
}

The (type T context.Context) part here means that T must implement context.Context. As long as that requirement is satisfied, we can store anything in there.

The generic proposal does not allow methods to contain generic types, so let’s assume the http package has a new function with this signature:

func WithContext(type T, U)(*Request(T), U) *Request(U)

This works identical to the WithContext method on *http.Request, except that it’s using the new typesafe context type.

With those changes available to us, we can create middleware functions in a type-safe manner. Let’s begin by attaching an access token to the context:

type WithToken(type T) struct{
  T
  token *Token
}

func (wt *WithToken) GetToken() *Token {
  return wt.token
}

func AttachToken(type T context.Context)(next http.Handler(*WithToken(T))) http.Handler(T) {
  return http.HandlerFunc(func (w http.ResponseWriter, r *http.Request(T)) {
    tok, err := GetTokenFromRequest(r)
    // handle error
    ctx := &WithToken{T: r.Context(), token: tok}
    r2 := http.WithContext(r, ctx)
    next.ServeHTTP(w, r2)
  })
}

For a Go developer, this function signature probably feels… very strange. To simplify a bit, we can consider http.Handler a function call (it effectively is). If we do that, we see that the function we pass in is not something that contains *WithToken(T), but expects one when called. And what we return is a function that expects a T, and does not yet have one1.

With the access token available through the GetToken method, we can depend on it in other middleware functions. Typically you’d like to look up the user, so the next middleware does just that. It also assumes that a database is provided.

type WithUser(type T) struct {
  T
  user *User
}

func (wu *WithUser) GetUser() *User {
  return wu.user
}

type GetTokenDBer interface {
  GetToken() *Token
  GetDB()    *DB
}

func AttachUser(type T GetTokenDBer)(next http.Handler(*WithUser(T))) http.Handler(T) {
  return http.HandlerFunc(func (w http.ResponseWriter, r *http.Request(T)) {
    rctx := r.Context()
    tok := rctx.GetToken()
    var u *User
    err = inTransaction(rctx.GetDB(), func(tx *Tx) error {
      u, err = users.GetByID(tx, tok.Username)
      return err
    })
    // handle error
    ctx := WithUser{T: rctx, user: u}
    r2 := http.WithContext(r, ctx)
    next.ServeHTTP(w, r2)
  })
}

This, in turn, can be used to make yet another middleware function: One that verifies that a user is an admin before allowing them access.

type GetUserer interface {
  GetUser() *User
}

func VerifyIsAdmin(type T GetUserer) (next http.Handler(T)) http.Handler(T) {
  return http.HandlerFunc(func (w http.ResponseWriter, r *http.Request(T)) {
    u := r.Context().GetUser()
    if !u.IsAdmin {
      http.Error(w, u.Username + " is not an admin",
        http.StatusForbidden)
      return
    }
    next.ServeHTTP(w, r)
  })
}

The final result is that we have composable middlewares with proper type safety:

func main() {
  var db *DB
  AttachToken(AttachDB(db, AttachUser(VerifyIsAdmin(DoAdminThing))))
  AttachDB(db, AttachToken(AttachUser(VerifyIsAdmin(DoAdminThing))))
}

This example isn’t perfect though. One thing is to avoid redundant work, but I also talked about reusing transactions as well. The example here doesn’t do that, but it’s possible with a bit of thought 2.

An Idea Within an Idea

Adding row polymorphism is an idea that bases itself off another unimplemented idea: Generics for Go. While Generics have been proposed and seriously considered, both generics and row polymorphism are things that go against the minimalism Go tries to achieve.

But row polymorphism is on a different level compared to generics: It’s hard to grasp the subtleities for a newcomer, error messages are likely indecipherable, and the implementation itself will be hard to get efficient if it follows the semantics covered here. And if we wanted to do row polymorphism “right”, we also need to consider the absence of fields/properties. That, in turn, will make both the implementation and the syntax even more complex.

So while row polymorphism is a nice idea which could shut down the context debate once and for all, I think it will be too complex to realistically get into the Go language and runtime.

But if you like the idea of row polymorphism and want to test it out yourself, don’t fret! I don’t know that many industrial strength programming languages with support for row polymorphism, but it is possible to cover both your frontend and the backend needs: Both PureScript and OCaml3 support row polymorphism, and Haskell has libraries as well as a proposal to get row polymorphism into the language itself.

  1. If you’re eager to understand how this works in general and want to dip your toes into Haskell while you’re at it, then I recommend having a look at Understanding contravariance. Be warned though: If you’re not already familiar with Haskell, then this may make you even more confused. 

  2. The main issue is how one would handle errors when committing a transaction. My recommended solution would be to change the HTTP handler interface to separate domain logic, and serialisation and socket concerns, but that’s another blog post entirely. 

  3. And, by extension, presumably also Reason.