Type Systems

Abstract

This is not an introduction to type system theory but a technical specification around an abstract concept which I call Type System – hence the capitals.

This specification aims to be a first step towards a more flexible type-system in the Go programming language. It has clean-cut limitations that make it sane to implement and it is provably closed under the operations it introduces.

All features proposed here should be implementable through templating. That is, a preprocessor that generates Go code.

What is a Type System?

A set of types with relations defined between them that are part of the definition of another, named type.

Applies to…

• struct type definitions
• interface type definitions
• function type definitions
• function signatures

Limitations

These limitations are defined on purpose, targeting simplicity.

• No subtyping, implying:

  • Only expressable relation between types is equality.
  • No way to express greater-than or less-than (sub/super type of) relations.
  • No co/contravariance.
  • No type constraints/bounded type parameters.

• Type parameters definable only on named types.

  • New syntax contained to named type definitions.
  • No inline type parameter mess.

Case: struct type definition

No special syntax is in use here, just color emphasis on type names.

type TypeA struct {
    FieldA TypeX,
    FieldB TypeY,
    FieldC struct {
        FieldD TypeX,
    },
    FieldE struct {
        FieldF []TypeY,
        FieldG TypeZ,
    },
}

Constraints on TypeA

• FieldA must have same type as FieldC's FieldD.
• FieldB must have same type as FieldE's FieldF is a slice of.

What is a TypeA?

Any struct type that has the same amount of fields with the same field names in the same order and the types of said fields conforms to the constraints listed above.

Case: interface type definition

No special syntax is in use here, just color emphasis on type names.

type TypeB interface {
    MethodA(TypeX, []TypeY) TypeZ
    MethodB(TypeY, []TypeZ) (TypeX, error)
}

Constraints on TypeB

• MethodA's first parameter must be of same type as MethodB's first return value.
• MethodA's second parameter must be a slice of the same type as MethodB's first argument.
• MethodB's second argument must be a slice of the same type as MethodA's only return parameter.

What is a TypeB?

Any type that has a method set containing all method names listed in the interface definition and whose signatures conform to the constraints expressed above.

Case: function type definition

No special syntax is in use here, just color emphasis on type names.

type TypeC func(TypeX, []TypeY) ([]TypeX, map[TypeY]TypeZ)

Constraints on TypeC

• Type of first return value is slice of same type as first parameter.
• Type of second return value is map with key type equal to what second parameter is a slice of.

What is a TypeC?

Any function type that takes the same number of arguments and returns the same number of values as TypeC's definition expresses and whose combined types conform to the above constraints.

Case: function signature

No special syntax is in use here, just color emphasis on type names.

func FuncA (TypeX, map[TypeX]TypeY) []TypeY

Constraints on FuncA

• Type of return value is slice of same type as second parameter's elements.
• Type of second parameter's keys is same as first parameter.

What is FuncA?

A function that accepts any combination of parameters that conforms to the above constraints.

Syntax constraints

This document does not propose any new syntax. However, some constraints need be defined upon potential syntax candidates.

References to parameterized types

Just as with the existing "generic" kinds (map, slices, channels, etc), parameterized types cannot be expressed without all of their composing types. For instance:

type Foo struct {
    Bar map[string]int // not just "map" or "map[string]"
    Baz []string       // not just "[]"
    Zap chan int       // not just "chan"
}

Therefore, a syntax that implements this must mention all of a parameterized type's argument names.

Pseudo-syntax used below. I would have preferred not using any new syntax in this document but it proved difficult so please bear with me.

For example, defining a type with 2 parameters:

type Map <k, v> interface {
    Del(k)
    Set(k, v)
    Get(k) (v, bool)
}

Whenever the type Map is referenced, so must be its parameters. Not necessarily with the same names as in Map's definition. For instance in a function signature:

func DoTheBoogie(m Map <x, y>) y {
    // ...
}

Insufficient type parameters

Sometimes a function will require more type parameters than what its arguments provide. For example a constructor for a parametric type:

func NewParametricType() ParametricType<x> // x?

Without introducing new syntax; how can a caller tell NewParametricType what x should be?

Simple: parameterize an empty struct type and use that as a dummy:

type TypeRef <t> struct {}

func NewParametricType(TypeRef <x>) ParametricType <x>

Now NewParametricType's body can refer to x.

Integration with existing parametric types

This specification should extend nicely to the already existing parametric types.

The only difference between the inbuilt generic structures and user-defined parametric types would be that the former are referenced through syntactic sugar while the later are not.

Use-Cases

Pseudo-syntax used below. I would have preferred not using any new syntax in this document but it proved difficult so please bear with me.

Mostly taken from here and outgoing links.

Map, Type-safe containers and Type-agnostic algorithms

3 top requested features are actually tighly related.

type Iterable <t> interface {
    HasNext() bool
    Next()    t
    Reset()
}

type TypeRef <t> struct {}

// *SliceCollection implements Iterable
type SliceCollection <e> struct {
    coll []e
    iter int
}

func NewSliceCollection(t TypeRef<e>) *SliceCollection <e> {
    return &SliceCollection{make([]e, 0), 0}
}

func (c *SliceCollection<e>) HasNext() bool {
    return c.iter < len(c.coll)
}

func (c *SliceCollection<e>) Next() e {
    v := c.coll[c.iter]
    c.iter++
    return v
}

func (c *SliceCollection<e>) Reset() {
    c.iter = 0
}

type Functor <a, b> func(a) b

func Map (i Iterable <a>, f Functor <a, b>) Iterable <b> {
    c := NewSliceCollection(TypeRef<b>{})
    for i.HasNext() {
        c.Add(f(i.Next()))
    }
    return c
}

Map in this case always returns a *SliceCollection in an Iterable interface. This is a limitation of map's definition, not of this implementation.

Classes of numbers

Everything about being complex or quaternion, independent of base type, so as to allow Gaussian integers or complex reals via the same specializable code.

A truly good implementation of this idea depends on multiple dispatch being available to the user. Since this is not the case, the next-best solution are interfaces, which we already have. Therefore this specification brings nothing new to the table in this regard.

Open questions

Should there be a way to express inequality between types?

Would it make sense to provide a syntax that expresses a constraint whereby two types in one Type System cannot be equal?

An arbitrary example would be a function type whose only parameter cannot be of the same type as its single return value.

Should unnamed composite types be able to be parameterized?

When we define an unnamed function, struct or interface (without the type-keyword), should type-parameters be allowed?