hm

package module
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Sep 17, 2017 License: MIT Imports: 5 Imported by: 39

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.

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)! 

package main

import (
	"fmt"
	"log"
	"strings"

	"github.com/pkg/errors"
)

const digits = "0123456789"

type TyperExpression interface {
	Expression
	Typer
}

type λ struct {
	name string
	body Expression
}

func (n λ) Name() string     { return n.name }
func (n λ) Body() Expression { return n.body }
func (n λ) IsLambda() bool   { return true }

type lit string

func (n lit) Name() string     { return string(n) }
func (n lit) Body() Expression { return n }
func (n lit) Type() Type {
	switch {
	case strings.ContainsAny(digits, string(n)) && strings.ContainsAny(digits, string(n[0])):
		return Float
	case string(n) == "true" || string(n) == "false":
		return Bool
	default:
		return nil
	}
}
func (n lit) IsLit() bool    { return true }
func (n lit) IsLambda() bool { return true }

type app struct {
	f   Expression
	arg Expression
}

func (n app) Fn() Expression   { return n.f }
func (n app) Body() Expression { return n.arg }
func (n app) Arg() Expression  { return n.arg }

type let struct {
	name string
	def  Expression
	in   Expression
}

func (n let) Name() string     { return n.name }
func (n let) Def() Expression  { return n.def }
func (n let) Body() Expression { return n.in }

type letrec struct {
	name string
	def  Expression
	in   Expression
}

func (n letrec) Name() string           { return n.name }
func (n letrec) Def() Expression        { return n.def }
func (n letrec) Body() Expression       { return n.in }
func (n letrec) Children() []Expression { return []Expression{n.def, n.in} }
func (n letrec) IsRecursive() bool      { return true }

type prim byte

const (
	Float prim = iota
	Bool
)

// implement Type
func (t prim) Name() string                                   { return t.String() }
func (t prim) Apply(Subs) Substitutable                       { return t }
func (t prim) FreeTypeVar() TypeVarSet                        { return nil }
func (t prim) Normalize(TypeVarSet, TypeVarSet) (Type, error) { return t, nil }
func (t prim) Types() Types                                   { return nil }
func (t prim) Eq(other Type) bool {
	if ot, ok := other.(prim); ok {
		return ot == t
	}
	return false
}

func (t prim) Format(s fmt.State, c rune) { fmt.Fprintf(s, t.String()) }
func (t prim) String() string {
	switch t {
	case Float:
		return "Float"
	case Bool:
		return "Bool"
	}
	return "HELP"
}

// 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)!
func main() {
	// haskell envy in a greenspun's tenth law example function!
	//
	// We'll assume the following is the "input" code
	// 		let fac n = if n == 0 then 1 else n * fac (n - 1) in fac 5
	// and what we have is the AST

	fac := letrec{
		"fac",
		λ{
			"n",
			app{
				app{
					app{
						lit("if"),
						app{
							lit("isZero"),
							lit("n"),
						},
					},
					lit("1"),
				},
				app{
					app{lit("mul"), lit("n")},
					app{lit("fac"), app{lit("--"), lit("n")}},
				},
			},
		},
		app{lit("fac"), lit("5")},
	}

	// but first, let's start with something simple:
	// let x = 3 in x+5
	simple := let{
		"x",
		lit("3"),
		app{
			app{
				lit("+"),
				lit("5"),
			},
			lit("x"),
		},
	}

	env := SimpleEnv{
		"--":     &Scheme{tvs: TypeVarSet{'a'}, t: NewFnType(TypeVariable('a'), TypeVariable('a'))},
		"if":     &Scheme{tvs: TypeVarSet{'a'}, t: NewFnType(Bool, TypeVariable('a'), TypeVariable('a'), TypeVariable('a'))},
		"isZero": &Scheme{t: NewFnType(Float, Bool)},
		"mul":    &Scheme{t: NewFnType(Float, Float, Float)},
		"+":      &Scheme{tvs: TypeVarSet{'a'}, t: NewFnType(TypeVariable('a'), TypeVariable('a'), TypeVariable('a'))},
	}

	var scheme *Scheme
	var err error
	scheme, err = Infer(env, simple)
	if err != nil {
		log.Printf("%+v", errors.Cause(err))
	}
	simpleType, ok := scheme.Type()
	fmt.Printf("simple Type: %v | isMonoType: %v | err: %v\n", simpleType, ok, err)

	scheme, err = Infer(env, fac)
	if err != nil {
		log.Printf("%+v", errors.Cause(err))
	}

	facType, ok := scheme.Type()
	fmt.Printf("fac Type: %v | isMonoType: %v | err: %v", facType, ok, err)

}

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

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.