README

hm GoDoc Build Status Coverage Status

Package hm is a simple Hindley-Milner type inference system in Go. It provides the necessary data structures and functions for creating such a system.

Installation

This package is go-gettable: go get -u github.com/chewxy/hm

There are very few dependencies that this package uses. Therefore there isn't a need for vendoring tools. However, package hm DOES provide a Gopkg.toml and Gopkg.lock for any potential users of the dep tool.

Here is a listing of the dependencies of hm:

Package Used For Vitality Notes Licence
errors Error wrapping Can do without, but this is by far the superior error solution out there Stable API for the past 6 months errors licence (MIT/BSD-like)
testify/assert Testing Can do without but will be a massive pain in the ass to test testify licence (MIT/BSD-like)

Usage

TODO: Write this

Notes

This package is used by Gorgonia as part of the graph building process. It is also used by several other internal projects of this author, all sharing a similar theme of requiring a type system, which is why this was abstracted out.

Contributing

This library is developed using Github. Therefore the workflow is very github-centric.

Licence

Package hm is licenced under the MIT licence.

Expand ▾ Collapse ▴

Documentation

Overview

Example (Greenspun)

    Phillip Greenspun's tenth law says:

    "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."
    

    So let's implement a half-arsed lisp (Or rather, an AST that can optionally be executed upon if you write the correct interpreter)!

    Output:
    
    simple Type: Float | isMonoType: true | err: <nil>
    fac Type: Float | isMonoType: true | err: <nil>
    

    Index

    Examples

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    func BorrowMSubs

    func BorrowMSubs() mSubs

      BorrowMSubs gets a map based substitution from a shared pool. USE WITH CAUTION

      func BorrowSSubs

      func BorrowSSubs(size int) *sSubs

        BorrowSSubs gets a slice based substituiton from a shared pool. USE WITH CAUTION

        func ReturnFnType

        func ReturnFnType(fnt *FunctionType)

          ReturnFnType returns a *FunctionType to the pool. NewFnType automatically borrows from the pool. USE WITH CAUTION

          func ReturnSubs

          func ReturnSubs(sub Subs)

            ReturnSubs returns substitutions to the pool. USE WITH CAUTION.

            func ReturnTypeVarSet

            func ReturnTypeVarSet(ts TypeVarSet)

              ReturnTypeVarSet returns the TypeVarSet to pool. USE WITH CAUTION

              func ReturnTypes

              func ReturnTypes(ts Types)

                ReturnTypes returns the slice of types into the pool. USE WITH CAUTION

                Types

                type Apply

                type Apply interface {
                	Expression
                	Fn() Expression
                }

                  Apply is an Expression/AST node that represents a function application

                  type Cloner

                  type Cloner interface {
                  	Clone() interface{}
                  }

                    Cloner is any type that can clone

                    type Constraint

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

                      A Constraint is well.. a constraint that says a must equal to b. It's used mainly in the constraint generation process.

                      func (Constraint) Apply

                      func (c Constraint) Apply(sub Subs) Substitutable

                      func (Constraint) Format

                      func (c Constraint) Format(state fmt.State, r rune)

                      func (Constraint) FreeTypeVar

                      func (c Constraint) FreeTypeVar() TypeVarSet

                      type Constraints

                      type Constraints []Constraint

                        Constraints is a slice of Constraint. Like a Constraint, it is also a Substitutable

                        func (Constraints) Apply

                        func (cs Constraints) Apply(sub Subs) Substitutable

                        func (Constraints) Format

                        func (cs Constraints) Format(state fmt.State, c rune)

                        func (Constraints) FreeTypeVar

                        func (cs Constraints) FreeTypeVar() TypeVarSet

                        type Env

                        type Env interface {
                        	Substitutable
                        	SchemeOf(string) (*Scheme, bool)
                        	Clone() Env
                        
                        	Add(string, *Scheme) Env
                        	Remove(string) Env
                        }

                          An Env is essentially a map of names to schemes

                          type Expression

                          type Expression interface {
                          	Body() Expression
                          }

                            An Expression is basically an AST node. In its simplest form, it's lambda calculus

                            type Fresher

                            type Fresher interface {
                            	Fresh() TypeVariable
                            }

                              Fresher keeps track of all the TypeVariables that has been generated so far. It has one method - Fresh(), which is to create a new TypeVariable

                              type FunctionType

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

                                FunctionType is a type constructor that builds function types.

                                func NewFnType

                                func NewFnType(ts ...Type) *FunctionType

                                  NewFnType creates a new FunctionType. Functions are by default right associative. This:

                                  NewFnType(a, a, a)
                                  

                                  is short hand for this:

                                  NewFnType(a, NewFnType(a, a))
                                  

                                  func (*FunctionType) Apply

                                  func (t *FunctionType) Apply(sub Subs) Substitutable

                                  func (*FunctionType) Arg

                                  func (t *FunctionType) Arg() Type

                                    Arg returns the type of the function argument

                                    func (*FunctionType) Clone

                                    func (t *FunctionType) Clone() interface{}

                                      Clone implements Cloner

                                      func (*FunctionType) Eq

                                      func (t *FunctionType) Eq(other Type) bool

                                      func (*FunctionType) FlatTypes

                                      func (t *FunctionType) FlatTypes() Types

                                        FlatTypes returns the types in FunctionTypes as a flat slice of types. This allows for easier iteration in some applications

                                        func (*FunctionType) Format

                                        func (t *FunctionType) Format(s fmt.State, c rune)

                                        func (*FunctionType) FreeTypeVar

                                        func (t *FunctionType) FreeTypeVar() TypeVarSet

                                        func (*FunctionType) Name

                                        func (t *FunctionType) Name() string

                                        func (*FunctionType) Normalize

                                        func (t *FunctionType) Normalize(k, v TypeVarSet) (Type, error)

                                        func (*FunctionType) Ret

                                        func (t *FunctionType) Ret(recursive bool) Type

                                          Ret returns the return type of a function. If recursive is true, it will get the final return type

                                          func (*FunctionType) String

                                          func (t *FunctionType) String() string

                                          func (*FunctionType) Types

                                          func (t *FunctionType) Types() Types

                                          type Inferer

                                          type Inferer interface {
                                          	Infer(Env, Fresher) (Type, error)
                                          }

                                            An Inferer is an Expression that can infer its own Type given an Env

                                            type Lambda

                                            type Lambda interface {
                                            	Expression
                                            	Namer
                                            	IsLambda() bool
                                            }

                                              Lambda is an Expression/AST node that represents a function definiton

                                              type Let

                                              type Let interface {
                                              	// let name = def in body
                                              	Expression
                                              	Namer
                                              	Def() Expression
                                              }

                                                Let is an Expression/AST node that represents the standard let polymorphism found in functional languages

                                                type LetRec

                                                type LetRec interface {
                                                	Let
                                                	IsRecursive() bool
                                                }

                                                  LetRec is an Expression/AST node that represents a recursive let

                                                  type Literal

                                                  type Literal interface {
                                                  	Var
                                                  	IsLit() bool
                                                  }

                                                    Literal is an Expression/AST Node representing a literal

                                                    type Namer

                                                    type Namer interface {
                                                    	Name() string
                                                    }

                                                      A Namer is anything that knows its own name

                                                      type Record

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

                                                        Record is a basic record/tuple type. It takes an optional name.

                                                        func NewRecordType

                                                        func NewRecordType(name string, ts ...Type) *Record

                                                          NewRecordType creates a new Record Type

                                                          func (*Record) Apply

                                                          func (t *Record) Apply(subs Subs) Substitutable

                                                          func (*Record) Clone

                                                          func (t *Record) Clone() interface{}

                                                            Clone implements Cloner

                                                            func (*Record) Eq

                                                            func (t *Record) Eq(other Type) bool

                                                            func (*Record) Format

                                                            func (t *Record) Format(f fmt.State, c rune)

                                                            func (*Record) FreeTypeVar

                                                            func (t *Record) FreeTypeVar() TypeVarSet

                                                            func (*Record) Name

                                                            func (t *Record) Name() string

                                                            func (*Record) Normalize

                                                            func (t *Record) Normalize(k, v TypeVarSet) (Type, error)

                                                            func (*Record) String

                                                            func (t *Record) String() string

                                                            func (*Record) Types

                                                            func (t *Record) Types() Types

                                                            type Scheme

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

                                                              Scheme represents a polytype. It basically says this:

                                                              ∀TypeVariables.Type.
                                                              

                                                              What this means is for all TypeVariables enclosed in Type, those TypeVariables can be of any Type.

                                                              func Generalize

                                                              func Generalize(env Env, t Type) *Scheme

                                                              Generalize takes an env and a type and creates the most general possible type - which is a polytype

                                                              Generalization

                                                              If ...

                                                                Γ ⊢ e: T1  T1 ∉ free(Γ)
                                                              ---------------------------
                                                                 Γ ⊢ e: ∀ α.T1
                                                              

                                                              func Infer

                                                              func Infer(env Env, expr Expression) (*Scheme, error)

                                                              Infer takes an env, and an expression, and returns a scheme.

                                                              The Infer function is the core of the HM type inference system. This is a reference implementation and is completely servicable, but not quite performant. You should use this as a reference and write your own infer function.

                                                              Very briefly, these rules are implemented:

                                                              Var

                                                              If x is of type T, in a collection of statements Γ, then we can infer that x has type T when we come to a new instance of x

                                                               x: T ∈ Γ
                                                              -----------
                                                               Γ ⊢ x: T
                                                              

                                                              Apply

                                                              If f is a function that takes T1 and returns T2; and if x is of type T1; then we can infer that the result of applying f on x will yield a result has type T2

                                                               Γ ⊢ f: T1→T2  Γ ⊢ x: T1
                                                              -------------------------
                                                                   Γ ⊢ f(x): T2
                                                              

                                                              Lambda Abstraction

                                                              If we assume x has type T1, and because of that we were able to infer e has type T2 then we can infer that the lambda abstraction of e with respect to the variable x, λx.e, will be a function with type T1→T2

                                                                Γ, x: T1 ⊢ e: T2
                                                              -------------------
                                                                Γ ⊢ λx.e: T1→T2
                                                              

                                                              Let

                                                              If we can infer that e1 has type T1 and if we take x to have type T1 such that we could infer that e2 has type T2, then we can infer that the result of letting x = e1 and substituting it into e2 has type T2

                                                                Γ, e1: T1  Γ, x: T1 ⊢ e2: T2
                                                              --------------------------------
                                                                   Γ ⊢ let x = e1 in e2: T2
                                                              

                                                              func NewScheme

                                                              func NewScheme(tvs TypeVarSet, t Type) *Scheme

                                                              func (*Scheme) Apply

                                                              func (s *Scheme) Apply(sub Subs) Substitutable

                                                              func (*Scheme) Clone

                                                              func (s *Scheme) Clone() *Scheme

                                                              func (*Scheme) Format

                                                              func (s *Scheme) Format(state fmt.State, c rune)

                                                              func (*Scheme) FreeTypeVar

                                                              func (s *Scheme) FreeTypeVar() TypeVarSet

                                                              func (*Scheme) Normalize

                                                              func (s *Scheme) Normalize() (err error)

                                                                Normalize normalizes the type variables in a scheme, so all the names will be in alphabetical order

                                                                func (*Scheme) Type

                                                                func (s *Scheme) Type() (t Type, isMonoType bool)

                                                                  Type returns the type of the scheme, as well as a boolean indicating if *Scheme represents a monotype. If it's a polytype, it'll return false

                                                                  type SimpleEnv

                                                                  type SimpleEnv map[string]*Scheme

                                                                  func (SimpleEnv) Add

                                                                  func (e SimpleEnv) Add(name string, s *Scheme) Env

                                                                  func (SimpleEnv) Apply

                                                                  func (e SimpleEnv) Apply(sub Subs) Substitutable

                                                                  func (SimpleEnv) Clone

                                                                  func (e SimpleEnv) Clone() Env

                                                                  func (SimpleEnv) FreeTypeVar

                                                                  func (e SimpleEnv) FreeTypeVar() TypeVarSet

                                                                  func (SimpleEnv) Remove

                                                                  func (e SimpleEnv) Remove(name string) Env

                                                                  func (SimpleEnv) SchemeOf

                                                                  func (e SimpleEnv) SchemeOf(name string) (retVal *Scheme, ok bool)

                                                                  type Subs

                                                                  type Subs interface {
                                                                  	Get(TypeVariable) (Type, bool)
                                                                  	Add(TypeVariable, Type) Subs
                                                                  	Remove(TypeVariable) Subs
                                                                  
                                                                  	// Iter() <-chan Substitution
                                                                  	Iter() []Substitution
                                                                  	Size() int
                                                                  	Clone() Subs
                                                                  }

                                                                    Subs is a list of substitution. Internally there are two very basic substitutions - one backed by map and the other a normal slice

                                                                    func Unify

                                                                    func Unify(a, b Type) (sub Subs, err error)

                                                                    Unify unifies the two types and returns a list of substitutions. These are the rules:

                                                                    Type Constants and Type Constants

                                                                    Type constants (atomic types) have no substitution

                                                                    c ~ c : []
                                                                    

                                                                    Type Variables and Type Variables

                                                                    Type variables have no substitutions if there are no instances:

                                                                    a ~ a : []
                                                                    

                                                                    Default Unification

                                                                    if type variable 'a' is not in 'T', then unification is simple: replace all instances of 'a' with 'T'

                                                                         a ∉ T
                                                                    ---------------
                                                                     a ~ T : [a/T]
                                                                    

                                                                    type Substitutable

                                                                    type Substitutable interface {
                                                                    	Apply(Subs) Substitutable
                                                                    	FreeTypeVar() TypeVarSet
                                                                    }

                                                                      Substitutable is any type that can have a set of substitutions applied on it, as well as being able to know what its free type variables are

                                                                      type Substitution

                                                                      type Substitution struct {
                                                                      	Tv TypeVariable
                                                                      	T  Type
                                                                      }

                                                                        A Substitution is a tuple representing the TypeVariable and the replacement Type

                                                                        type Type

                                                                        type Type interface {
                                                                        	Substitutable
                                                                        	Name() string                                   // Name is the name of the constructor
                                                                        	Normalize(TypeVarSet, TypeVarSet) (Type, error) // Normalize normalizes all the type variable names in the type
                                                                        	Types() Types                                   // If the type is made up of smaller types, then it will return them
                                                                        	Eq(Type) bool                                   // equality operation
                                                                        
                                                                        	fmt.Formatter
                                                                        	fmt.Stringer
                                                                        }

                                                                          Type represents all the possible type constructors.

                                                                          func Instantiate

                                                                          func Instantiate(f Fresher, s *Scheme) Type

                                                                            Instantiate takes a fresh name generator, an a polytype and makes a concrete type out of it.

                                                                            If ...

                                                                              Γ ⊢ e: T1  T1 ⊑ T
                                                                            ----------------------
                                                                                   Γ ⊢ e: T
                                                                            

                                                                            type TypeConst

                                                                            type TypeConst string

                                                                              TypeConst are the default implementation of a constant type. Feel free to implement your own. TypeConsts should be immutable (so no pointer types plz)

                                                                              func (TypeConst) Apply

                                                                              func (t TypeConst) Apply(Subs) Substitutable

                                                                              func (TypeConst) Eq

                                                                              func (t TypeConst) Eq(other Type) bool

                                                                              func (TypeConst) Format

                                                                              func (t TypeConst) Format(s fmt.State, c rune)

                                                                              func (TypeConst) FreeTypeVar

                                                                              func (t TypeConst) FreeTypeVar() TypeVarSet

                                                                              func (TypeConst) Name

                                                                              func (t TypeConst) Name() string

                                                                              func (TypeConst) Normalize

                                                                              func (t TypeConst) Normalize(k, v TypeVarSet) (Type, error)

                                                                              func (TypeConst) String

                                                                              func (t TypeConst) String() string

                                                                              func (TypeConst) Types

                                                                              func (t TypeConst) Types() Types

                                                                              type TypeVarSet

                                                                              type TypeVarSet []TypeVariable

                                                                                TypeVarSet is a set of TypeVariable

                                                                                func BorrowTypeVarSet

                                                                                func BorrowTypeVarSet(size int) TypeVarSet

                                                                                  BorrowTypeVarSet gets a TypeVarSet of size from pool. USE WITH CAUTION

                                                                                  func (TypeVarSet) Contains

                                                                                  func (s TypeVarSet) Contains(tv TypeVariable) bool

                                                                                  func (TypeVarSet) Difference

                                                                                  func (s TypeVarSet) Difference(other TypeVarSet) TypeVarSet

                                                                                  func (TypeVarSet) Equals

                                                                                  func (s TypeVarSet) Equals(other TypeVarSet) bool

                                                                                  func (TypeVarSet) Index

                                                                                  func (s TypeVarSet) Index(tv TypeVariable) int

                                                                                  func (TypeVarSet) Intersect

                                                                                  func (s TypeVarSet) Intersect(other TypeVarSet) TypeVarSet

                                                                                  func (TypeVarSet) Len

                                                                                  func (s TypeVarSet) Len() int

                                                                                  func (TypeVarSet) Less

                                                                                  func (s TypeVarSet) Less(i, j int) bool

                                                                                  func (TypeVarSet) Set

                                                                                  func (s TypeVarSet) Set() TypeVarSet

                                                                                  func (TypeVarSet) Swap

                                                                                  func (s TypeVarSet) Swap(i, j int)

                                                                                  func (TypeVarSet) Union

                                                                                  func (s TypeVarSet) Union(other TypeVarSet) TypeVarSet

                                                                                  type TypeVariable

                                                                                  type TypeVariable rune

                                                                                    TypeVariable is a variable that ranges over the types - that is to say it can take any type.

                                                                                    func (TypeVariable) Apply

                                                                                    func (t TypeVariable) Apply(sub Subs) Substitutable

                                                                                    func (TypeVariable) Eq

                                                                                    func (t TypeVariable) Eq(other Type) bool

                                                                                    func (TypeVariable) Format

                                                                                    func (t TypeVariable) Format(s fmt.State, c rune)

                                                                                    func (TypeVariable) FreeTypeVar

                                                                                    func (t TypeVariable) FreeTypeVar() TypeVarSet

                                                                                    func (TypeVariable) Name

                                                                                    func (t TypeVariable) Name() string

                                                                                    func (TypeVariable) Normalize

                                                                                    func (t TypeVariable) Normalize(k, v TypeVarSet) (Type, error)

                                                                                    func (TypeVariable) String

                                                                                    func (t TypeVariable) String() string

                                                                                    func (TypeVariable) Types

                                                                                    func (t TypeVariable) Types() Types

                                                                                    type Typer

                                                                                    type Typer interface {
                                                                                    	Type() Type
                                                                                    }

                                                                                      A Typer is an Expression node that knows its own Type

                                                                                      type Types

                                                                                      type Types []Type

                                                                                        Types is a slice of Type. Future additions to the methods of this type may be possible

                                                                                        func BorrowTypes

                                                                                        func BorrowTypes(size int) Types

                                                                                          BorrowTypes gets a slice of Types with size. USE WITH CAUTION.

                                                                                          func (Types) Contains

                                                                                          func (ts Types) Contains(t Type) bool

                                                                                          type Var

                                                                                          type Var interface {
                                                                                          	Expression
                                                                                          	Namer
                                                                                          	Typer
                                                                                          }

                                                                                            Var is an expression representing a variable