hm: github.com/chewxy/hm Index | Examples | Files

package hm

import "github.com/chewxy/hm"

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

}

Index

Examples

Package Files

const.go constraint.go env.go expression.go functionType.go hm.go perf.go release.go scheme.go solver.go substitutables.go substitutions.go type.go typeVarSet.go typeVariable.go

func BorrowMSubs Uses

func BorrowMSubs() mSubs

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

func BorrowSSubs Uses

func BorrowSSubs(size int) *sSubs

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

func ReturnFnType Uses

func ReturnFnType(fnt *FunctionType)

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

func ReturnSubs Uses

func ReturnSubs(sub Subs)

ReturnSubs returns substitutions to the pool. USE WITH CAUTION.

func ReturnTypeVarSet Uses

func ReturnTypeVarSet(ts TypeVarSet)

ReturnTypeVarSet returns the TypeVarSet to pool. USE WITH CAUTION

func ReturnTypes Uses

func ReturnTypes(ts Types)

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

type Apply Uses

type Apply interface {
    Expression
    Fn() Expression
}

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

type Cloner Uses

type Cloner interface {
    Clone() interface{}
}

Cloner is any type that can clone

type Constraint Uses

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 Uses

func (c Constraint) Apply(sub Subs) Substitutable

func (Constraint) Format Uses

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

func (Constraint) FreeTypeVar Uses

func (c Constraint) FreeTypeVar() TypeVarSet

type Constraints Uses

type Constraints []Constraint

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

func (Constraints) Apply Uses

func (cs Constraints) Apply(sub Subs) Substitutable

func (Constraints) Format Uses

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

func (Constraints) FreeTypeVar Uses

func (cs Constraints) FreeTypeVar() TypeVarSet

type Env Uses

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 Uses

type Expression interface {
    Body() Expression
}

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

type Fresher Uses

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 Uses

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

FunctionType is a type constructor that builds function types.

func NewFnType Uses

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 Uses

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

func (*FunctionType) Arg Uses

func (t *FunctionType) Arg() Type

Arg returns the type of the function argument

func (*FunctionType) Clone Uses

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

Clone implements Cloner

func (*FunctionType) Eq Uses

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

func (*FunctionType) FlatTypes Uses

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 Uses

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

func (*FunctionType) FreeTypeVar Uses

func (t *FunctionType) FreeTypeVar() TypeVarSet

func (*FunctionType) Name Uses

func (t *FunctionType) Name() string

func (*FunctionType) Normalize Uses

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

func (*FunctionType) Ret Uses

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 Uses

func (t *FunctionType) String() string

func (*FunctionType) Types Uses

func (t *FunctionType) Types() Types

type Inferer Uses

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

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

type Lambda Uses

type Lambda interface {
    Expression
    Namer
    IsLambda() bool
}

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

type Let Uses

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 Uses

type LetRec interface {
    Let
    IsRecursive() bool
}

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

type Literal Uses

type Literal interface {
    Var
    IsLit() bool
}

Literal is an Expression/AST Node representing a literal

type Namer Uses

type Namer interface {
    Name() string
}

A Namer is anything that knows its own name

type Record Uses

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

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

func NewRecordType Uses

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

NewRecordType creates a new Record Type

func (*Record) Apply Uses

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

func (*Record) Clone Uses

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

Clone implements Cloner

func (*Record) Eq Uses

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

func (*Record) Format Uses

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

func (*Record) FreeTypeVar Uses

func (t *Record) FreeTypeVar() TypeVarSet

func (*Record) Name Uses

func (t *Record) Name() string

func (*Record) Normalize Uses

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

func (*Record) String Uses

func (t *Record) String() string

func (*Record) Types Uses

func (t *Record) Types() Types

type Scheme Uses

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 Uses

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 Uses

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 Uses

func NewScheme(tvs TypeVarSet, t Type) *Scheme

func (*Scheme) Apply Uses

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

func (*Scheme) Clone Uses

func (s *Scheme) Clone() *Scheme

func (*Scheme) Format Uses

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

func (*Scheme) FreeTypeVar Uses

func (s *Scheme) FreeTypeVar() TypeVarSet

func (*Scheme) Normalize Uses

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 Uses

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 Uses

type SimpleEnv map[string]*Scheme

func (SimpleEnv) Add Uses

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

func (SimpleEnv) Apply Uses

func (e SimpleEnv) Apply(sub Subs) Substitutable

func (SimpleEnv) Clone Uses

func (e SimpleEnv) Clone() Env

func (SimpleEnv) FreeTypeVar Uses

func (e SimpleEnv) FreeTypeVar() TypeVarSet

func (SimpleEnv) Remove Uses

func (e SimpleEnv) Remove(name string) Env

func (SimpleEnv) SchemeOf Uses

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

type Subs Uses

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 Uses

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 Uses

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 Uses

type Substitution struct {
    Tv  TypeVariable
    T   Type
}

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

type Type Uses

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 Uses

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 Uses

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 Uses

func (t TypeConst) Apply(Subs) Substitutable

func (TypeConst) Eq Uses

func (t TypeConst) Eq(other Type) bool

func (TypeConst) Format Uses

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

func (TypeConst) FreeTypeVar Uses

func (t TypeConst) FreeTypeVar() TypeVarSet

func (TypeConst) Name Uses

func (t TypeConst) Name() string

func (TypeConst) Normalize Uses

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

func (TypeConst) String Uses

func (t TypeConst) String() string

func (TypeConst) Types Uses

func (t TypeConst) Types() Types

type TypeVarSet Uses

type TypeVarSet []TypeVariable

TypeVarSet is a set of TypeVariable

func BorrowTypeVarSet Uses

func BorrowTypeVarSet(size int) TypeVarSet

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

func (TypeVarSet) Contains Uses

func (s TypeVarSet) Contains(tv TypeVariable) bool

func (TypeVarSet) Difference Uses

func (s TypeVarSet) Difference(other TypeVarSet) TypeVarSet

func (TypeVarSet) Equals Uses

func (s TypeVarSet) Equals(other TypeVarSet) bool

func (TypeVarSet) Index Uses

func (s TypeVarSet) Index(tv TypeVariable) int

func (TypeVarSet) Intersect Uses

func (s TypeVarSet) Intersect(other TypeVarSet) TypeVarSet

func (TypeVarSet) Len Uses

func (s TypeVarSet) Len() int

func (TypeVarSet) Less Uses

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

func (TypeVarSet) Set Uses

func (s TypeVarSet) Set() TypeVarSet

func (TypeVarSet) Swap Uses

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

func (TypeVarSet) Union Uses

func (s TypeVarSet) Union(other TypeVarSet) TypeVarSet

type TypeVariable Uses

type TypeVariable rune

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

func (TypeVariable) Apply Uses

func (t TypeVariable) Apply(sub Subs) Substitutable

func (TypeVariable) Eq Uses

func (t TypeVariable) Eq(other Type) bool

func (TypeVariable) Format Uses

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

func (TypeVariable) FreeTypeVar Uses

func (t TypeVariable) FreeTypeVar() TypeVarSet

func (TypeVariable) Name Uses

func (t TypeVariable) Name() string

func (TypeVariable) Normalize Uses

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

func (TypeVariable) String Uses

func (t TypeVariable) String() string

func (TypeVariable) Types Uses

func (t TypeVariable) Types() Types

type Typer Uses

type Typer interface {
    Type() Type
}

A Typer is an Expression node that knows its own Type

type Types Uses

type Types []Type

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

func BorrowTypes Uses

func BorrowTypes(size int) Types

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

func (Types) Contains Uses

func (ts Types) Contains(t Type) bool

type Var Uses

type Var interface {
    Expression
    Namer
    Typer
}

Var is an expression representing a variable

Package hm imports 5 packages (graph) and is imported by 11 packages. Updated 2018-05-23. Refresh now. Tools for package owners.