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 definitionsinterface
type definitionsfunction
type definitionsfunction
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 asFieldC
'sFieldD
.FieldB
must have same type asFieldE
'sFieldF
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 asMethodB
's first return value.MethodA
's second parameter must be a slice of the same type asMethodB
's first argument.MethodB
's second argument must be a slice of the same type asMethodA
'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?