hm

package
v0.0.0-...-44669ab Latest Latest
Warning

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

 Go to latest Published: Feb 27, 2026 License: Apache-2.0 Imports: 6 Imported by: 0

README

Hindley-Milner type inference

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func ReturnSubs 

func ReturnSubs(s Subs)

ReturnSubs is a no-op function for compatibility with object pooling

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() any
}

Cloner is any type that can clone itself

type Coercible 

type Coercible interface {
	AcceptsCoercionFrom(Type) bool
}

Coercible is implemented by types that accept coercion from other types. This is used primarily for custom scalar types that can accept values of built-in types (e.g., a URL scalar accepting a String literal).

type Env 

type Env interface {
	SchemeOf(name string) (*Scheme, bool)
	Clone() Env
	Add(name string, scheme *Scheme) Env
	Remove(name string) Env
	FreeTypeVar() TypeVarSet
	Apply(subs Subs) Substitutable
	GetDynamicScopeType() Type
	SetDynamicScopeType(t Type)
}

Env represents a type environment

type Expression 

type Expression interface {
	Body() Expression
}

Expression is basically an AST node

type Fresher 

type Fresher interface {
	Fresh() TypeVariable
}

Fresher interface for generating fresh type variables

type FunctionType 

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

FunctionType represents a function type

func NewFnType 

func NewFnType(arg, ret Type) *FunctionType

func (*FunctionType) Apply 

func (ft *FunctionType) Apply(subs Subs) Substitutable

func (*FunctionType) Arg 

func (ft *FunctionType) Arg() Type

Arg returns the argument type

func (*FunctionType) Block 

func (ft *FunctionType) Block() *FunctionType

Block returns the optional block argument type

func (*FunctionType) Eq 

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

func (*FunctionType) Format 

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

func (*FunctionType) FreeTypeVar 

func (ft *FunctionType) FreeTypeVar() TypeVarSet

func (*FunctionType) Name 

func (ft *FunctionType) Name() string

func (*FunctionType) Normalize 

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

func (*FunctionType) Ret 

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

Ret returns the return type, with optional recursive parameter for compatibility

func (*FunctionType) ReturnType 

func (ft *FunctionType) ReturnType() Type

Convenience method for getting return type

func (*FunctionType) SetBlock 

func (ft *FunctionType) SetBlock(block *FunctionType)

SetBlock sets the block argument type

func (*FunctionType) String 

func (ft *FunctionType) String() string

func (*FunctionType) Supertypes 

func (ft *FunctionType) Supertypes() []Type

func (*FunctionType) Types 

func (ft *FunctionType) Types() Types

type Inferer 

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

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

type Lambda 

type Lambda interface {
	Expression
	Namer // name of the parameter
}

Lambda is an Expression/AST node that represents a lambda abstraction

type Let 

type Let interface {
	Expression
	Namer            // name of the bound variable
	Def() Expression // definition
}

Let is an Expression/AST node that represents let polymorphism

type LetRec 

type LetRec interface {
	Let
	IsRecursive() bool
}

LetRec is an Expression/AST node that represents 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
}

Namer is anything that knows its own name

type NonNullType 

type NonNullType struct {
	Type Type
}

NonNullType represents a non-nullable type wrapper

func (NonNullType) Apply 

func (t NonNullType) Apply(subs Subs) Substitutable

func (NonNullType) Eq 

func (t NonNullType) Eq(other Type) bool

func (NonNullType) Format 

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

func (NonNullType) FreeTypeVar 

func (t NonNullType) FreeTypeVar() TypeVarSet

func (NonNullType) Name 

func (t NonNullType) Name() string

func (NonNullType) Normalize 

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

func (NonNullType) String 

func (t NonNullType) String() string

func (NonNullType) Supertypes 

func (t NonNullType) Supertypes() []Type

func (NonNullType) Types 

func (t NonNullType) Types() Types

type NullableTypeVariable 

type NullableTypeVariable struct {
	TypeVariable
}

NullableTypeVariable is a type variable that carries a nullability taint. It is produced by null literals. When unified with a NonNullType during binding, it strips the NonNull wrapper, ensuring that null always resolves to a nullable type.

func (NullableTypeVariable) Apply 

func (ntv NullableTypeVariable) Apply(subs Subs) Substitutable

func (NullableTypeVariable) Eq 

func (ntv NullableTypeVariable) Eq(other Type) bool

func (NullableTypeVariable) Format 

func (ntv NullableTypeVariable) Format(s fmt.State, c rune)

func (NullableTypeVariable) String 

func (ntv NullableTypeVariable) String() string

type Scheme 

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

Scheme represents a type scheme for polymorphic types

func Generalize 

func Generalize(env Env, t Type) *Scheme

Generalize creates a type scheme by quantifying over type variables that are free in the type but not free in the environment

func NewScheme 

func NewScheme(tvs []TypeVariable, t Type) *Scheme

NewScheme creates a new type scheme

func (*Scheme) Apply 

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

Apply applies a substitution to a scheme

func (*Scheme) Clone 

func (s *Scheme) Clone() *Scheme

Clone creates a copy of the scheme

func (*Scheme) FreeTypeVar 

func (s *Scheme) FreeTypeVar() TypeVarSet

FreeTypeVar returns the free type variables in the scheme

func (*Scheme) Normalize 

func (s *Scheme) Normalize() error

Normalize normalizes the type variable names in the scheme

func (*Scheme) String 

func (s *Scheme) String() string

String returns a string representation

func (*Scheme) Type 

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

Type returns the underlying type and whether it's monomorphic

func (*Scheme) TypeVars 

func (s *Scheme) TypeVars() []TypeVariable

TypeVars returns the bound type variables

type SimpleEnv 

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

SimpleEnv is a simple implementation of Env

func NewSimpleEnv 

func NewSimpleEnv() *SimpleEnv

NewSimpleEnv creates a new SimpleEnv

func (*SimpleEnv) Add 

func (env *SimpleEnv) Add(name string, scheme *Scheme) Env

Add adds a binding to the environment

func (*SimpleEnv) Apply 

func (env *SimpleEnv) Apply(subs Subs) Substitutable

Apply applies a substitution to the environment

func (*SimpleEnv) Clone 

func (env *SimpleEnv) Clone() Env

Clone creates a copy of the environment

func (*SimpleEnv) FreeTypeVar 

func (env *SimpleEnv) FreeTypeVar() TypeVarSet

FreeTypeVar returns the free type variables in the environment

func (*SimpleEnv) GetDynamicScopeType 

func (env *SimpleEnv) GetDynamicScopeType() Type

GetDynamicScopeType returns the current dynamic scope type

func (*SimpleEnv) Remove 

func (env *SimpleEnv) Remove(name string) Env

Remove removes a binding from the environment

func (*SimpleEnv) SchemeOf 

func (env *SimpleEnv) SchemeOf(name string) (*Scheme, bool)

SchemeOf returns the scheme for a name

func (*SimpleEnv) SetDynamicScopeType 

func (env *SimpleEnv) SetDynamicScopeType(t Type)

SetDynamicScopeType sets the current dynamic scope type

type SimpleFresher 

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

SimpleFresher is a simple implementation of Fresher

func NewSimpleFresher 

func NewSimpleFresher() *SimpleFresher

NewSimpleFresher creates a new SimpleFresher

func (*SimpleFresher) Fresh 

func (f *SimpleFresher) Fresh() TypeVariable

Fresh generates a fresh type variable

type Subs 

type Subs map[TypeVariable]Type

Subs represents a substitution mapping from type variables to types

func Assignable 

func Assignable(have, want Type) (Subs, error)

Assignable attempts to unify two types, returning a substitution or error. If unification fails, it checks subtyping: have can be assigned to want if have is a subtype of want.

func NewSubs 

func NewSubs() Subs

NewSubs creates a new substitution

func (Subs) Add 

func (s Subs) Add(tv TypeVariable, t Type) Subs

Add adds a substitution mapping and returns the updated substitution

func (Subs) Apply 

func (s Subs) Apply(t Type) Type

Apply applies a substitution to a type

func (Subs) Clone 

func (s Subs) Clone() Subs

Clone creates a copy of the substitution

func (Subs) Compose 

func (s Subs) Compose(other Subs) Subs

Compose composes two substitutions

func (Subs) Get 

func (s Subs) Get(tv TypeVariable) (Type, bool)

Get gets a type for a type variable

func (Subs) Iter 

func (s Subs) Iter() []Substitution

Iter iterates over the substitutions

type Substitutable 

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

Substitutable is any type that can have substitutions applied and knows its free type variables

type Substitution 

type Substitution struct {
	Tv TypeVariable
	T  Type
}

Substitution represents a single type variable to type mapping

type Type 

type Type interface {
	Substitutable
	Name() string
	Normalize(TypeVarSet, TypeVarSet) (Type, error)
	Types() Types
	Eq(Type) bool
	// Supertypes returns the direct supertypes of this type.
	// For example, NonNullType{String} returns [String].
	// Module types implementing interfaces return those interfaces.
	// Most types return nil (no supertypes).
	Supertypes() []Type
	// fmt.Formatter
	fmt.Stringer
}

Type represents all possible type constructors with nullability support

func Instantiate 

func Instantiate(fresher Fresher, scheme *Scheme) Type

Instantiate creates a fresh instance of a type scheme

type TypeVarSet 

type TypeVarSet map[TypeVariable]bool

TypeVarSet represents a set of type variables

func NewTypeVarSet 

func NewTypeVarSet(tvs ...TypeVariable) TypeVarSet

NewTypeVarSet creates a new TypeVarSet

func (TypeVarSet) Add 

func (tvs TypeVarSet) Add(tv TypeVariable)

Add adds a type variable to the set

func (TypeVarSet) Contains 

func (tvs TypeVarSet) Contains(tv TypeVariable) bool

Contains checks if a type variable is in the set

func (TypeVarSet) Remove 

func (tvs TypeVarSet) Remove(tv TypeVariable)

Remove removes a type variable from the set

func (TypeVarSet) ToSlice 

func (tvs TypeVarSet) ToSlice() []TypeVariable

ToSlice converts the set to a slice

func (TypeVarSet) Union 

func (tvs TypeVarSet) Union(other TypeVarSet) TypeVarSet

Union returns the union of two TypeVarSets

type TypeVariable 

type TypeVariable rune

TypeVariable represents a type variable

func (TypeVariable) Apply 

func (tv TypeVariable) Apply(subs Subs) Substitutable

func (TypeVariable) Eq 

func (tv TypeVariable) Eq(other Type) bool

func (TypeVariable) Format 

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

func (TypeVariable) FreeTypeVar 

func (tv TypeVariable) FreeTypeVar() TypeVarSet

func (TypeVariable) Name 

func (tv TypeVariable) Name() string

func (TypeVariable) Normalize 

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

func (TypeVariable) String 

func (tv TypeVariable) String() string

func (TypeVariable) Supertypes 

func (tv TypeVariable) Supertypes() []Type

func (TypeVariable) Types 

func (tv TypeVariable) Types() Types

type Typer 

type Typer interface {
	Type() Type
}

Typer is an Expression node that knows its own Type

type Types 

type Types []Type

Types represents a slice of types

func BorrowTypes 

func BorrowTypes(capacity int) Types

BorrowTypes creates a new slice of types with the given capacity This is for compatibility with object pooling patterns

type UnificationError 

type UnificationError struct {
	Have, Want Type
}

UnificationError represents errors during unification

func (UnificationError) Error 

func (e UnificationError) Error() string

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.