types

package
v0.0.0-...-9296a29 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 9, 2019 License: MIT Imports: 7 Imported by: 0

Documentation

Overview

The following types are supported: 

Unit:           unit/empty type
Var:            type-variable
Const:          type constant
Size:           size constant
App:            type application
Arrow:          function type
Method:         type-class method type
Record:         record type
Variant:        tagged (ad-hoc) variant-type
RowExtend:      row extension
RowEmpty:       empty row
RecursiveLink:  recursive link to a type

Index

Constants

View Source 
const (
	TopLevel        = 0
	GenericVarLevel = 1 << 31
	LinkVarLevel    = 1 << 30
	// Type-variables within mutable reference-types are weakly-polymorphic and may not be generalized
	WeakVarLevel = 1 << 29

	// Restricted levels (0x01...0x1f) << 24:
	SizeVarLevel  = 1 << 24
	ConstVarLevel = 2 << 24

	RestrictedVarLevelsMask = 0x1f << 24
)

Special binding-levels for type-variables

Variables

View Source 
var EmptyTypeList = TypeList{emptyList}
View Source 
var EmptyTypeMap = TypeMap{emptyMap}
View Source 
var RecordEmptyPointer = &RowExtend{Row: RowEmptyPointer}
View Source 
var RefType = &Const{"ref"}

Mutable references are applications of RefType (a mutable reference-type) with a single referenced type-parameter.

View Source 
var RowEmptyPointer = (*RowEmpty)(nil)

Pointer to the empty row type

Functions

func FlattenRowType 

func FlattenRowType(t Type) (labels TypeMap, rest Type, err error)

Flatten row extensions into a single row.

func IsRefType 

func IsRefType(app *App) bool

Check if a type application is a mutable reference-type.

func TypeName 

func TypeName(t Type) string

func TypeString 

func TypeString(t Type) string

TypeString returns a string representation of a Type.

Types

type App 

type App struct {
	// Const should be a type constant (constructor name) or type-variable
	Const Type
	// Type parameters
	Params []Type
	// Aliased type (optional)
	Underlying Type
	// Source which this type was instantiated from, or nil
	Source *App
	Flags  TypeFlags
}

Type application: `list[int]`

func NewRef 

func NewRef(deref Type) *App

Create an application of RefType (a mutable reference-type) with a single referenced type-parameter.

func (*App) HasRefs 

func (t *App) HasRefs() bool

Check if t contains mutable reference-types.

func (*App) IsGeneric 

func (t *App) IsGeneric() bool

Check if t contains generic types.

func (*App) TypeName 

func (t *App) TypeName() string

"App"

type Arrow 

type Arrow struct {
	Args   []Type
	Return Type
	// Method which the function instantiates, or nil
	Method *Method
	// Source which this type was instantiated from, or nil
	Source *Arrow
	Flags  TypeFlags
}

Function type: `(int, int) -> int`

func (*Arrow) HasRefs 

func (t *Arrow) HasRefs() bool

Check if t contains mutable reference-types.

func (*Arrow) IsGeneric 

func (t *Arrow) IsGeneric() bool

Check if t contains generic types.

func (*Arrow) TypeName 

func (t *Arrow) TypeName() string

"Arrow"

type Const 

type Const struct {
	Name string
}

Type constant: `int`, `bool`, etc

func (*Const) HasRefs 

func (t *Const) HasRefs() bool

Const never contains mutable reference-types.

func (*Const) IsGeneric 

func (t *Const) IsGeneric() bool

Const is never generic.

func (*Const) TypeName 

func (t *Const) TypeName() string

Name of the type-constant

type Instance 

type Instance struct {
	TypeClass *TypeClass
	Param     Type
	Methods   MethodSet
	// Strict disables type-variable unification during instance matching.
	Strict bool
	// MethodNames maps method names to names of their implementations within the type-environment.
	MethodNames map[string]string
}

Instance of a parameterized type-class

func (*Instance) SetStrict 

func (inst *Instance) SetStrict(strict bool)

type InstanceConstraint 

type InstanceConstraint struct {
	TypeClass *TypeClass
}

InstanceConstraint constrains a type-variable to types which implement a type-class.

type Method 

type Method struct {
	TypeClass *TypeClass
	Name      string
	Flags     TypeFlags
}

Type-class method type: `('a, int) -> 'a`

func (*Method) HasRefs 

func (t *Method) HasRefs() bool

Check if t contains mutable reference-types.

func (*Method) IsGeneric 

func (t *Method) IsGeneric() bool

Check if t contains generic types.

func (*Method) TypeName 

func (t *Method) TypeName() string

"Method"

type MethodSet 

type MethodSet map[string]*Arrow

MethodSet is a set of named function-types declared for a type-class or instance.

type Record 

type Record struct {
	// Row extension, empty row, or type-variable
	Row Type
	// Source which this type was instantiated from, or nil
	Source *Record
	Flags  TypeFlags
}

Record type: `{a : int}`

func (*Record) HasRefs 

func (t *Record) HasRefs() bool

Check if t contains mutable reference-types.

func (*Record) IsGeneric 

func (t *Record) IsGeneric() bool

Check if t contains generic types.

func (*Record) TypeName 

func (t *Record) TypeName() string

"Record"

type Recursive 

type Recursive struct {
	// Source is a recursive type which this type instantiates, or nil.
	Source *Recursive
	// Params are type-variables used by the recursive type(s).
	Params []*Var
	// Types is an indexed slice containing one or more aliased types.
	// Each aliased type should contain recursive links which point back to this recursive group.
	Types   []*App
	Names   []string
	Indexes map[string]int
	// Bind types to an instance of this recursive. The new instance may have
	// different type-parameters set before binding, if any of the existing
	// parameters require instantiation.
	Bind  func(instance *Recursive)
	Flags TypeFlags
}

Recursive is a recursive type or a group of mutually-recursive types.

See https://www.cs.cmu.edu/~rwh/papers/datatypes/tr.pdf

Recursive types are separated into their own subcategory, ranged over by δ. A recursive type δ has the form μi(α1,...,αn).(τ1,...,τn), where 1 ≤ i ≤ n and each αj is a type variable that may appear free in any or all of τ1,...,τn. 

δ ::= μi(α1,...,αn).(τ1,...,τn)

Intuitively, this type is the ith in a system of n mutually recursive types. As such, it is isomorphic to τi with each αj replaced by the jth component of the recursive bundle.

Formally, it is isomorphic to the following type: 

τi[μ1(α1,...,αn).(τ1,...,τn), ..., μn(α1,...,αn).(τ1,...,τn) / τ1,...,τn]

where we denote by τ[σ1,...,σn/α1,...,αn] the simultaneous capture-avoiding substitution of σ1,...,σn for α1,...,αn in τ.

func (*Recursive) AddType 

func (r *Recursive) AddType(name string, aliased *App) int

Add a type to the recursive type-group. The index of the type will be returned.

Each type in the recursive type-group must be assigned a unique name, which may be used for looking up the type's index within the group. The name is not printed or included with the type.

func (*Recursive) GetType 

func (r *Recursive) GetType(name string) *App

Lookup a type within the recursive type-group by its unique name.

func (*Recursive) HasRefs 

func (r *Recursive) HasRefs() bool

Check if any type parameters for r contain mutable reference-types.

func (*Recursive) IsGeneric 

func (r *Recursive) IsGeneric() bool

Check if any type parameters for r contain generic types.

func (*Recursive) IsInstanceOf 

func (r *Recursive) IsInstanceOf(source *Recursive) bool

Check if r is declared as an instance of source.

func (*Recursive) Matches 

func (r *Recursive) Matches(other *Recursive) bool

Check if r and other are instantiated from the same root.

func (*Recursive) NeedsGeneralization 

func (r *Recursive) NeedsGeneralization() bool

Check if r needs to be generalized.

func (*Recursive) WithParams 

func (r *Recursive) WithParams(env TypeEnv, params ...Type) *Recursive

Create an instance of r with params bound as its type parameters. 

type RecursiveLink struct {
	Recursive *Recursive
	Index     int
	// Source which this type was instantiated from, or nil
	Source *RecursiveLink
}

Recursive link to a type.

func (*RecursiveLink) HasRefs 

func (t *RecursiveLink) HasRefs() bool

Check if t contains mutable reference-types.

func (*RecursiveLink) IsGeneric 

func (t *RecursiveLink) IsGeneric() bool

Check if t contains generic types. 

func (t *RecursiveLink) Link() Type

Expand the recursively-linked type for t.

func (*RecursiveLink) TypeName 

func (t *RecursiveLink) TypeName() string

"Recursive"

type RowEmpty 

type RowEmpty struct{}

Empty row: `<>`

func (*RowEmpty) HasRefs 

func (t *RowEmpty) HasRefs() bool

RowEmpty never contains mutable reference-types.

func (*RowEmpty) IsGeneric 

func (t *RowEmpty) IsGeneric() bool

RowEmpty is never generic.

func (*RowEmpty) TypeName 

func (t *RowEmpty) TypeName() string

"RowEmpty"

type RowExtend 

type RowExtend struct {
	// Row extension, empty row, or type-variable
	Row    Type
	Labels TypeMap
	// Source which this type was instantiated from, or nil
	Source *RowExtend
	Flags  TypeFlags
}

Row extension: `<a : _ , b : _ | ...>`

func (*RowExtend) HasRefs 

func (t *RowExtend) HasRefs() bool

Check if t contains mutable reference-types.

func (*RowExtend) IsGeneric 

func (t *RowExtend) IsGeneric() bool

Check if t contains generic types.

func (*RowExtend) TypeName 

func (t *RowExtend) TypeName() string

"RowExtend"

type Size 

type Size int

Size constant: `array[int, 8]`

func (Size) HasRefs 

func (t Size) HasRefs() bool

Size never contains mutable reference-types.

func (Size) IsGeneric 

func (t Size) IsGeneric() bool

Size is never generic.

func (Size) TypeName 

func (t Size) TypeName() string

"Size"

type Type 

type Type interface {
	TypeName() string
	// Check if a type is a generic type-variable or contains generic type-variables.
	IsGeneric() bool
	// Check if a type is a mutable reference-type or contains mutable reference-types.
	HasRefs() bool
}

Type is the base for all types.

The following types are supported: 

Unit:           unit/empty type
Var:            type-variable
Const:          type constant
Size:           size constant
App:            type application
Arrow:          function type
Method:         type-class method type
Record:         record type
Variant:        tagged (ad-hoc) variant-type
RowExtend:      row extension
RowEmpty:       empty row
RecursiveLink:  recursive link to a type

func RealType 

func RealType(t Type) Type

Get the underlying type for a chain of linked type-variables, when applicable.

type TypeClass 

type TypeClass struct {
	// Id should uniquely identify the type-class
	Id uint
	// Name should uniquely identify the type-class
	Name      string
	Param     Type
	Methods   MethodSet
	Super     map[uint]*TypeClass
	Sub       map[uint]*TypeClass
	Instances []*Instance
	// Union type-classes may be cast to a tagged (ad-hoc) variant from their labelled instances
	Union        map[string]*Instance
	UnionVariant *Variant
	// contains filtered or unexported fields
}

Parameterized type-class

func NewTypeClass 

func NewTypeClass(id uint, name string, param Type, methods MethodSet) *TypeClass

Create a new named/parameterized type-class with a set of method declarations.

func (*TypeClass) AddInstance 

func (tc *TypeClass) AddInstance(param Type, methods MethodSet, methodNames map[string]string) *Instance

Add an instance to the type-class with param as the type-parameter.

methodNames must map from method names to names of their implementations within the type-environment.

func (*TypeClass) AddSubClass 

func (super *TypeClass) AddSubClass(sub *TypeClass)

Add a sub-class to the type-class.

func (*TypeClass) AddSuperClass 

func (sub *TypeClass) AddSuperClass(super *TypeClass)

Add a super-class to the type-class. This is an alias for `super.AddSubClass(sub)`.

func (*TypeClass) FindInstance 

func (tc *TypeClass) FindInstance(found func(*Instance) bool) bool

Visit all instances for the type-class and all sub-classes. Sub-classes will be visited first.

func (*TypeClass) FindInstanceFromRoots 

func (tc *TypeClass) FindInstanceFromRoots(found func(*Instance) bool) bool

Visit all instances for each of the type-class's top-most parents and all their (transitive) sub-classes. Sub-classes will be visited first.

func (*TypeClass) HasSuperClass 

func (tc *TypeClass) HasSuperClass(super *TypeClass) bool

Check if a type-class is declared as a sub-class of another type-class.

func (*TypeClass) MatchInstance 

func (tc *TypeClass) MatchInstance(param Type, found func(*Instance) bool) (matched bool)

Visit all instances for the type-class and all sub-classes, filtered by a type-parameter. Sub-classes will be visited first.

The type-parameter may reduce the number of instances visited in some cases, filtering out obvious non-matches.

type TypeEnv 

type TypeEnv interface {
	// Lookup the type for an identifier in the environment or its parent environment(s).
	Lookup(name string) Type
	// Declare a type for an identifier within the type environment.
	Assign(name string, t Type)
	// Remove the assigned type for an identifier within the type environment. Parent environment(s) will not be affected,
	// and the identifier's type will still be visible if defined in a parent environment.
	Remove(name string)
	// Create a new type-variable at a given binding-level.
	NewVar(level uint) *Var
}

TypeEnv is a type-enviroment containing mappings from identifiers to declared types.

type TypeFlags 

type TypeFlags uint

TypeFlags contains flags for composite types. 

const (
	// TypeFlags for a type which is a generic type-variable or contains generic type-variables
	ContainsGenericVars TypeFlags = 1
	// TypeFlags for a type which is a mutable reference-type or contains mutable reference-types
	ContainsRefs TypeFlags = 2
	// TypeFlags for a recursive type which is neither being generalized nor already generalized (to break cycles).
	NeedsGeneralization = 4
)

Flags for composite types

type TypeList 

type TypeList struct {
	// contains filtered or unexported fields
}

TypeList contains an immutable list of types.

func NewTypeList 

func NewTypeList() TypeList

func SingletonTypeList 

func SingletonTypeList(t Type) TypeList

Create a TypeList with a single type.

func (TypeList) Builder 

func (l TypeList) Builder() TypeListBuilder

func (TypeList) Get 

func (l TypeList) Get(i int) Type

func (TypeList) Len 

func (l TypeList) Len() int

func (TypeList) Range 

func (l TypeList) Range(f func(int, Type) bool)

Iterate over entries in the list. If f returns false, iteration will be stopped.

func (TypeList) Slice 

func (l TypeList) Slice(start, end int) TypeList

type TypeListBuilder 

type TypeListBuilder struct {
	// contains filtered or unexported fields
}

func NewTypeListBuilder 

func NewTypeListBuilder() TypeListBuilder

func (TypeListBuilder) Append 

func (b TypeListBuilder) Append(t Type)

func (TypeListBuilder) Build 

func (b TypeListBuilder) Build() TypeList

func (*TypeListBuilder) EnsureInitialized 

func (b *TypeListBuilder) EnsureInitialized()

func (TypeListBuilder) Len 

func (b TypeListBuilder) Len() int

func (TypeListBuilder) Set 

func (b TypeListBuilder) Set(i int, t Type)

type TypeMap 

type TypeMap struct {
	// contains filtered or unexported fields
}

TypeMap contains immutable mappings from labels to immutable lists of types.

func NewFlatTypeMap 

func NewFlatTypeMap(m map[string]Type) TypeMap

Create a TypeMap with unscoped labels.

func NewTypeMap 

func NewTypeMap() TypeMap

func SingletonTypeMap 

func SingletonTypeMap(label string, t Type) TypeMap

Create a TypeMap with a single entry.

func (TypeMap) Builder 

func (m TypeMap) Builder() TypeMapBuilder

Convert the map to a builder for modification, without mutating the existing map.

func (TypeMap) First 

func (m TypeMap) First() (string, TypeList)

Get the first entry in the map. Entries are sorted by label.

func (TypeMap) Get 

func (m TypeMap) Get(label string) (TypeList, bool)

Get the list of types for a label.

func (TypeMap) Iterator 

func (m TypeMap) Iterator() TypeMapIterator

Get an iterator which may be used to read entries in the map, in sequential order.

func (TypeMap) Len 

func (m TypeMap) Len() int

Get the number of entries in the map.

func (TypeMap) Range 

func (m TypeMap) Range(f func(string, TypeList) bool)

Iterate over entries in the map. If f returns false, iteration will be stopped.

type TypeMapBuilder 

type TypeMapBuilder struct {
	// contains filtered or unexported fields
}

TypeMapBuilder enables in-place updates of a map before finalization.

func NewTypeMapBuilder 

func NewTypeMapBuilder() TypeMapBuilder

func (TypeMapBuilder) Build 

func (b TypeMapBuilder) Build() TypeMap

Finalize the builder into an immutable map.

func (TypeMapBuilder) Delete 

func (b TypeMapBuilder) Delete(label string) TypeMapBuilder

Delete the given label and corresponding type list from the builder.

func (*TypeMapBuilder) EnsureInitialized 

func (b *TypeMapBuilder) EnsureInitialized()

func (TypeMapBuilder) Len 

func (b TypeMapBuilder) Len() int

Get the number of entries in the builder.

func (TypeMapBuilder) Merge 

func (a TypeMapBuilder) Merge(b TypeMap) TypeMapBuilder

Merge entries into the builder.

func (TypeMapBuilder) Set 

func (b TypeMapBuilder) Set(label string, ts TypeList) TypeMapBuilder

Set the type list for the given label in the builder.

type TypeMapIterator 

type TypeMapIterator struct {
	// contains filtered or unexported fields
}

TypeMapIterator reads entries in a map, in sequential order.

func (TypeMapIterator) Done 

func (i TypeMapIterator) Done() bool

Done returns true if the iterator has reached the end a map.

func (TypeMapIterator) Next 

func (i TypeMapIterator) Next() (string, TypeList)

Next advances the iterator and returns the next entry from a map.

func (TypeMapIterator) Peek 

func (i TypeMapIterator) Peek() (string, TypeList)

Peek returns the next entry from a map without advancing the iterator.

type Unit 

type Unit struct {
}

Unit/empty type: `()` 

var UnitPointer *Unit = &Unit{}

Pointer to the unit type

func NewUnit 

func NewUnit() *Unit

Get a pointer to the unit type.

func (*Unit) HasRefs 

func (t *Unit) HasRefs() bool

Unit never contains mutable reference-types.

func (*Unit) IsGeneric 

func (t *Unit) IsGeneric() bool

Unit is never generic.

func (*Unit) TypeName 

func (t *Unit) TypeName() string

"Unit"

type Var 

type Var struct {
	// contains filtered or unexported fields
}

Type-variable

func NewGenericVar 

func NewGenericVar(id uint) *Var

Create a new generic type-variable.

func NewVar 

func NewVar(id, level uint) *Var

Create a new type-variable with the given id and binding-level.

func (*Var) AddConstraint 

func (tv *Var) AddConstraint(constraint InstanceConstraint)

Constrain the type-variable to types which implement a type-class.

func (*Var) Constraints 

func (tv *Var) Constraints() []InstanceConstraint

Constraints returns the set of type-classes which the type-variable must implement.

func (*Var) Flatten 

func (tv *Var) Flatten()

Flatten a chain of linked type-variables. Predicates for type-variables with qualified types will not be checked during flattening.

func (*Var) HasRefs 

func (t *Var) HasRefs() bool

Check if t is linked to a type containing mutable reference-types.

func (*Var) Id 

func (tv *Var) Id() uint

Id returns the unique identifier of the type-variable.

func (*Var) IsConstVar 

func (tv *Var) IsConstVar() bool

func (*Var) IsGeneric 

func (t *Var) IsGeneric() bool

Check if t is a generic type-variable.

func (*Var) IsGenericVar 

func (tv *Var) IsGenericVar() bool

func (*Var) IsLinkVar 

func (tv *Var) IsLinkVar() bool

func (*Var) IsRestrictedVar 

func (tv *Var) IsRestrictedVar() bool

func (*Var) IsSizeVar 

func (tv *Var) IsSizeVar() bool

func (*Var) IsUnboundVar 

func (tv *Var) IsUnboundVar() bool

func (*Var) IsWeakVar 

func (tv *Var) IsWeakVar() bool

func (*Var) Level 

func (tv *Var) Level() uint

Level returns the adjusted binding-level of the type-variable, with flag levels included.

func (*Var) LevelNum 

func (tv *Var) LevelNum() uint

Level returns the adjusted binding-level of the type-variable, with flag levels excluded. 

func (tv *Var) Link() Type

Link returns the type which the type-variable is bound to, if the type-variable is bound.

func (*Var) Restrict 

func (tv *Var) Restrict(restrictedLevel uint)

Restrict t as a constructor/constant type-variable. Constructor/constant type-variables may only unify with type constants.

func (*Var) RestrictConstVar 

func (tv *Var) RestrictConstVar()

Restrict t as a constructor/constant type-variable. Constructor/constant type-variables may only unify with type constants.

func (*Var) RestrictSizeVar 

func (tv *Var) RestrictSizeVar()

Restrict t as a size type-variable. Size type-variables may only unify with size types.

func (*Var) RestrictedLevel 

func (tv *Var) RestrictedLevel() uint

Level returns the masked level of tv, with only the restricted level included (if any).

func (*Var) SetConstraints 

func (tv *Var) SetConstraints(constraints []InstanceConstraint)

Constrain the type-variable to types which implement a set of type-classes.

func (*Var) SetGeneric 

func (tv *Var) SetGeneric()

Set the binding-level of the type-variable to the generic level.

func (*Var) SetId 

func (tv *Var) SetId(id uint)

Set the unique identifier of the type-variable.

func (*Var) SetLevelNum 

func (tv *Var) SetLevelNum(level uint)

Set the adjusted binding-level of the type-variable, with existing flags retained. 

func (tv *Var) SetLink(t Type)

Set the type which the type-variable is bound to.

func (*Var) SetWeak 

func (tv *Var) SetWeak()

Set the binding-level of the type-variable to the weak level. Weak type-variables may not be generalized.

func (*Var) TypeName 

func (t *Var) TypeName() string

"Var" 

func (tv *Var) UnsafeUnsetLink()

Unset the type which the type-variable is bound to.

type Variant 

type Variant struct {
	// Row extension, empty row, or type-variable
	Row Type
	// Source which this type was instantiated from, or nil
	Source *Variant
	Flags  TypeFlags
}

Tagged (ad-hoc) variant-type: `[i : int, s : string]`

func (*Variant) HasRefs 

func (t *Variant) HasRefs() bool

Check if t contains mutable reference-types.

func (*Variant) IsGeneric 

func (t *Variant) IsGeneric() bool

Check if t contains generic types.

func (*Variant) TypeName 

func (t *Variant) TypeName() string

"Variant"

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.