The humble sum should nei­ther necessitate indirection nor be unbounded across pack­age bound­aries (#250)

Routinely, I am irked by the effort required in most languages to express al­ge­bra­ic data types — the epitome of in­for­ma­tion itself. An inert datum is too often occluded by hard­ware-inspired lingo forcing one to adapt to rigid reg­is­ter-fitted types. Leastways the C lineage supports bytestrings to­geth­er with their concatenation which, under the previous constraints, are equatable to prod­uct types. Though whilst control flow neatly factors through such a type, the categorical dual consistently re­quires an iffy cast or virtual se­man­tics alltogether: the humble sum is qui­et­ly ignored in favor of its dual in whose hulking shadow it sometimes desintegrates out of existence. A far cry from Haskell’s ef­fort­less type alternative “|”, C at least supports byte-based type superpositioning. Yet although Go inherits “struct”, the fameless yet in no way inferior “union” is — to me unreasonably — absent.

Consequently, when I im­ple­ment­ed miniKanren in Go back in March of 2021⁠¹, I was flabbergasted to find a gaping lan­guage definition hole where I had expected a sum type. Toying with the idea to one-hot en­code S-expressions via

I quickly dismissed it in hopes of a more elegant idiomatic Go ap­proach. What I found was an in­ter­pre­ta­tion of a sum type which conflates ob­ject action, dynamic dispatch, undefined control flow and unbounded sums into a briddle mess of Go lines which can be viewed as indeed im­ple­ment­ing a type coproduct. Needless to say, I am dissatisfied with Go’s negligence in this regard.

-=-

Where­as Haskell’s concise syntax for al­ge­bra­ic data types allows for an S-Expression type to be cleanly defined in two lines, Go’s convoluted interface repurposing re­quires five lines when shrunk:

-- Haskell
data Term = Symbol String
          | Pair Term Term

// Go
type Term interface { isTerm() }

type Symbol struct { Data string }
func (_ Symbol) isTerm() {}

type Pair struct { Car, Cdr Term }
func (_ Pair) isTerm() {}

Go’s support for discriminating the above is likewise a lengthy endeavour:

-- Haskell
flatten :: Term -> [String]
flatten (Symbol sym) = pure sym
flatten (Pair t s)   = flatten t ++ flatten s

// Go
func flatten(t Term) []string {
    switch x := t.(type) {
        case Symbol:
            return []string{x.Data}
        case Pair:
            return append(flatten(x.Car), flatten(x.Cdr)...)
        default:
            panic("unexpected summand")
    }
}

Ignoring the raw line or byte count, Go seems to actively revolt when working a tad more abstractly than with neatly byte-packed data; writ­ing these fundamental type manipulations by hand is not a pleasant ex­pe­ri­ence. Auspiciously, the above is implementable — if at a high cost: Go’s interfaces were built to al­low packages func­tion­al­i­ty exports. Hence appending to or redefining a struct’s receiver methods across pack­age bound­aries is strictly forbidden, yet im­ple­ment­ing an interface actively encouraged. And therein lies the prob­lem: any struct from any source is allowed to im­ple­ment isTerm() as a receiver meth­od and will be seen as supporting the func­tion­al­i­ty required by Term — when viewed as an interface. Com­ing back to the sum type view, this means func flatten(Term) []string can be made to panic by nothing more than injecting another summand, from any pack­age:

// Go
type ExtraPackatorial struct {}
func (_ ExtraPackatorial) isTerm() {}
func panics() { flatten(&ExtraPackatorial{}) }

All this leads me to pro­pose an extension to the Go lan­guage: interface admission clauses. In action they may look like the following:

// wishful Go
type Term interface admits (Symbol; Pair) { isTerm() }

Taylored to al­low bound­ed sum type im­ple­men­ta­tion, admits restricts im­ple­men­ta­tion of an interface such that on­ly the types admitted by said interface may do so. Consequently, ExtraPackatorial’s at­tempt to fake itself into the sum type would be foiled by the com­pil­er which respects Term’s request for an exclusive implementability.

Even though admits should be used rarely to not hinder pack­age’s effectiveness and further support duck typing, it would close the gaping hole described in this post. Clear­ly, not every interface is meant to be freely extended and I think specifying structs by name which are granted permission to im­ple­ment an interface would be a valuable fea­ture, adding cur­rent­ly lacking control to define a universally useful type — the sum type.

• pingback from #284