Back to godoc.org
github.com/chewxy/hm

Package hm

v1.0.0
Latest Go to latest
Published: Sep 17, 2017 | License: MIT | Module: github.com/chewxy/hm

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

Code:

package hm

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 Example_greenspun() {
	// 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>

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

Index

Examples

Package Files

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

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

Documentation was rendered with GOOS=linux and GOARCH=amd64.

Jump to identifier

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to identifier