poly

package module
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: 6 Imported by: 0

README

package poly

import "github.com/wdamron/poly"

poly provides inference for a polymorphic type-system with extensible records and variants.

The type-system is an extension of Hindley-Milner based on Daan Leijen's paper: Extensible Records with Scoped Labels (Microsoft Research).

The core of the implementation is based on an OCaml library by Tom Primozic.

Supported Features

  • Extensible records and variants with scoped labels
  • Generic type classes, constructor classes, and parametric overloading
  • Limited/explicit (type class) subtyping with multiple inheritance
  • Mutually-recursive (generic) function expressions within grouped let bindings
  • Mutually-recursive (generic) data types
  • Transparently aliased (generic) types
  • Control-flow graph expressions
  • Mutable references with the value restriction
  • Size-bound type variables

More Info

Documentation

Overview

poly provides inference for a polymorphic type-system with extensible records and variants.

The type-system is an extension of Hindley-Milner based on Daan Leijen's paper: Extensible Records with Scoped Labels (Microsoft Research).

The implementation is based on an OCaml library by Tom Primozic.

Supported Features:

  • Extensible records and variants with scoped labels
  • Generic type classes, constructor classes, and parametric overloading
  • Limited/explicit (type class) subtyping with multiple inheritance
  • Mutually-recursive (generic) function expressions within grouped let bindings
  • Mutually-recursive (generic) data types
  • Transparently aliased (generic) types
  • Control-flow graph expressions
  • Mutable references with the value restriction
  • Size-bound type variables

Links:

extensible_rows2 (OCaml implementation): https://github.com/tomprimozic/type-systems/tree/master/extensible_rows2

Extensible Records with Scoped Labels (Leijen, 2005): https://www.microsoft.com/en-us/research/publication/extensible-records-with-scoped-labels/

Efficient Generalization with Levels (Oleg Kiselyov): http://okmij.org/ftp/ML/generalization.html#levels

Hindley-Milner type system: https://en.wikipedia.org/wiki/Hindley–Milner_type_system

Value restriction: https://en.wikipedia.org/wiki/Value_restriction

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Generalize 

func Generalize(t types.Type) types.Type

Generalize all unbound type-variables in t, excluding type-variables within mutable reference-types.

func GeneralizeAtLevel 

func GeneralizeAtLevel(level uint, t types.Type) types.Type

Generalize all unbound type-variables in t, excluding type-variables within mutable reference-types.

func GeneralizeRefs 

func GeneralizeRefs(t types.Type) types.Type

Generalize all unbound type-variables in t, including type-variables within mutable reference-types.

func GeneralizeWeak 

func GeneralizeWeak(t types.Type) types.Type

Generalize all unbound type-variables in t, marking each generalized variable as weakly-polymorphic.

func MarkWeak 

func MarkWeak(t types.Type) types.Type

Mark all type-variables in t as weakly-polymorphic. Weakly-polymorphic types will not be generalized during inference.

Types

type InferenceContext 

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

InferenceContext is a reusable context for type inference.

An inference context cannot be used concurrently.

func NewContext 

func NewContext() *InferenceContext

Create a new type-inference context. A context may be reused for inference.

func (*InferenceContext) Annotate 

func (ti *InferenceContext) Annotate(expr ast.Expr, env *TypeEnv) (ast.Expr, error)

Infer the type of expr within env. The type-annotated copy of expr will be returned.

A type-environment cannot be used concurrently for inference; to share a type-environment across threads, create a new type-environment for each thread which inherits from the shared environment.

func (*InferenceContext) AnnotateDirect 

func (ti *InferenceContext) AnnotateDirect(expr ast.Expr, env *TypeEnv) error

Infer the type of expr within env. Type-annotations will be added directly to expr. All sub-expressions of expr must have unique addresses.

A type-environment cannot be used concurrently for inference; to share a type-environment across threads, create a new type-environment for each thread which inherits from the shared environment.

func (*InferenceContext) EnableDeferredInstanceMatching 

func (ti *InferenceContext) EnableDeferredInstanceMatching(enabled bool)

Deferred instance-matching may find matching type-classes when the surrounding context does not initially contain enough information to determine a match. Deferred matching may (or may not) lead to unsound types for previously inferred expressions.

By default, deferred instance-matching is disabled.

func (*InferenceContext) Error 

func (ti *InferenceContext) Error() error

Get the error which caused inference to fail.

func (*InferenceContext) Infer 

func (ti *InferenceContext) Infer(expr ast.Expr, env *TypeEnv) (types.Type, error)

Infer the type of expr within env.

A type-environment cannot be used concurrently for inference; to share a type-environment across threads, create a new type-environment for each thread which inherits from the shared environment.

func (*InferenceContext) InvalidExpr 

func (ti *InferenceContext) InvalidExpr() ast.Expr

Get the expression which caused inference to fail.

func (*InferenceContext) Reset 

func (ti *InferenceContext) Reset()

Reset the state of the context. The context will be reset automatically before inference.

type TypeEnv 

type TypeEnv struct {
	// Mappings from identifiers to declared types in the current type-environment
	Types map[string]types.Type
	// Type-classes declared in the current type-environment
	TypeClasses map[string]*types.TypeClass
	// Predeclared types in the parent of the current type-environment
	Parent *TypeEnv
	// contains filtered or unexported fields
}

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

A type-environment cannot be used concurrently for inference; to share a type-environment across threads, create a new type-environment for each thread which inherits from the shared environment.

func NewTypeEnv 

func NewTypeEnv(parent *TypeEnv) *TypeEnv

Create a type-environment. The new environment will inherit bindings from the parent, if the parent is not nil.

A type-environment cannot be used concurrently for inference; to share a type-environment across threads, create a new type-environment for each thread which inherits from the shared environment.

func (*TypeEnv) Assign 

func (e *TypeEnv) Assign(name string, t types.Type)

Declare a type for an identifier within the type environment.

Type-variables will not be generalized.

Assign is an alias for DeclareInvariant.

func (*TypeEnv) Declare 

func (e *TypeEnv) Declare(name string, t types.Type)

Declare a type for an identifier within the type environment.

Type-variables contained within mutable reference-types will be generalized.

func (*TypeEnv) DeclareInstance 

func (e *TypeEnv) DeclareInstance(tc *types.TypeClass, param types.Type, methodNames map[string]string) (*types.Instance, error)

Declare an instance for a parameterized type-class within the type environment. The instance must implement all methods for the type-class and all parents of the type-class. The instance type must not overlap with (i.e. unify with) any other instances for the type-class.

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

The type-class which the instance implements will be modified to add an instance entry; changes will be visible across all uses of the type-class, and changes must not be made to type-classes concurrently.

func (*TypeEnv) DeclareInvariant 

func (e *TypeEnv) DeclareInvariant(name string, t types.Type)

Declare a type for an identifier within the type environment.

Type-variables will not be generalized.

func (*TypeEnv) DeclareTypeClass 

func (e *TypeEnv) DeclareTypeClass(name string, bind func(*types.Var) types.MethodSet, implements ...*types.TypeClass) (*types.TypeClass, error)

Declare a parameterized type-class within the type environment.

If the type-parameter is not linked within the bind function, an instance constraint will be added to the parameter.

Each super-class which the type-class implements will be modified to add a sub-class entry; changes will be visible across all uses of the super-classes, and changes must not be made to type-classes concurrently.

func (*TypeEnv) DeclareUnionTypeClass 

func (e *TypeEnv) DeclareUnionTypeClass(name string, bind func(*types.Var), instances map[string]types.Type) (*types.TypeClass, error)

Declare a closed union (a.k.a. sum/variant/enum) type-class within the type environment. This is a shortcut for declaring a type-class with an empty method-set and no super-classes then declaring the given instances for the type-class.

Additionally, a helper function will be declared in the type environment with the same name as the type-class, which converts an instance of the type-class to a tagged (ad-hoc) variant-type which may be used in (tag-based) match expressions. The variant-type will be labeled with the name and type of each instance.

If the bind function is nil or the type-parameter is not linked within the bind function, an instance constraint will be added to the parameter.

A union type-class represents a named/closed set of types, whereas tagged (ad-hoc) variant-types are anonymous/open sets of types. Functions may be parameterized over a union type-class; only tagged (ad-hoc) variant-types may be used in (tag-based) match expressions. Match expressions may offer less flexibility compared to (unification-driven) function overloading with instance constraints.

Each super-class which the type-class implements will be modified to add a sub-class entry; changes will be visible across all uses of the super-classes, and changes must not be made to type-classes concurrently.

func (*TypeEnv) DeclareWeak 

func (e *TypeEnv) DeclareWeak(name string, t types.Type)

Declare a weakly-polymorphic type for an identifier within the type environment.

Type-variables contained within mutable reference-types will not be generalized.

func (*TypeEnv) FindMethodInstance 

func (e *TypeEnv) FindMethodInstance(arrow *types.Arrow) *types.Instance

Find the type-class instance which implements a called function's underlying method.

arrow should be the function-type assigned to a Call expression during inference. If the Call expression was not inferred to be a method call, a nil instance will be returned.

func (*TypeEnv) Instantiate 

func (e *TypeEnv) Instantiate(level uint, t types.Type) types.Type

Instantiate a type at a given let-binding level. Instantiation should only occur indirectly during inference.

Literal expressions may need to instantiate types at the level they are being instantiated at.

func (*TypeEnv) Lookup 

func (e *TypeEnv) Lookup(name string) types.Type

Lookup the type for an identifier in the environment or its parent environment(s).

func (*TypeEnv) LookupTypeClass 

func (e *TypeEnv) LookupTypeClass(name string) *types.TypeClass

Lookup a declared type-class in the environment or its parent environment(s).

func (*TypeEnv) NewGenericSize 

func (e *TypeEnv) NewGenericSize() *types.Var

Create a generic size type-variable with a unique id. Size type-variables must link to size types.

func (*TypeEnv) NewGenericVar 

func (e *TypeEnv) NewGenericVar() *types.Var

Create a generic type-variable with a unique id.

func (*TypeEnv) NewQualifiedVar 

func (e *TypeEnv) NewQualifiedVar(constraints ...types.InstanceConstraint) *types.Var

Create a qualified type-variable with a unique id.

func (*TypeEnv) NewRecursive 

func (e *TypeEnv) NewRecursive(params []*types.Var, bind func(recursive *types.Recursive)) *types.Recursive

Create a new recursive type or group of mutually-recursive types.

The bind function should add aliased types with underlying types which are recursively linked to one or more types in the Recursive.

func (*TypeEnv) NewSimpleRecursive 

func (e *TypeEnv) NewSimpleRecursive(params []*types.Var, bindSelf func(*types.Recursive, *types.RecursiveLink)) *types.Recursive

Create a new recursive type.

The bindSelf function should add a single aliased type with an underlying type which is recursively linked to the Recursive.

func (*TypeEnv) NewVar 

func (e *TypeEnv) NewVar(level uint) *types.Var

Create a unbound type-variable with a unique id at a given binding-level.

func (*TypeEnv) NextVarId 

func (e *TypeEnv) NextVarId() uint

Get the id which will be assigned to the next type-variable generated within the type-environment.

func (*TypeEnv) Remove 

func (e *TypeEnv) Remove(name string)

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.

Source Files

View all Source files

Directories

Path Synopsis
The following expressions are supported: Literal: semi-opaque literal value Var: variable Deref: dereference DerefAssign: dereference and assign ControlFlow: control-flow graph Pipe: pipeline Call: function call Func: function abstraction Let: let-binding LetGroup: grouped let-bindings RecordSelect: selecting (scoped) value of label RecordExtend: extending record RecordRestrict: deleting (scoped) label RecordEmpty: empty record Variant: tagged (ad-hoc) variant Match: variant-matching switch
 The following expressions are supported: Literal: semi-opaque literal value Var: variable Deref: dereference DerefAssign: dereference and assign ControlFlow: control-flow graph Pipe: pipeline Call: function call Func: function abstraction Let: let-binding LetGroup: grouped let-bindings RecordSelect: selecting (scoped) value of label RecordExtend: extending record RecordRestrict: deleting (scoped) label RecordEmpty: empty record Variant: tagged (ad-hoc) variant Match: variant-matching switch
internal
astutil
typeutil
util
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
 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

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.