LamCalc

README

LamCalc

LamCalc is a simple library in Go to evaluate and work with lambda calculus.

This project also contains the cLC (cLamCalc) which is a commandline application build upon LamCalc to experiment with and learn about lambda calculus.

To learn more about the library and the cLC visit the project's wiki.

Documentation

Index

• Variables
• type Abst
  • func (la Abst) AlphaEquivalent(other Term) bool
  • func (la Abst) AorReduce() (Term, error)
  • func (la Abst) BetaReduce(sub Term) Term
  • func (la Abst) EtaReduce() Term
  • func (la Abst) NorReduce() (Term, error)
  • func (la Abst) Reduce() (Term, error)
  • func (la Abst) Serialize() string
  • func (la Abst) String() string
  • func (la Abst) WHNF() Abst
• type Appl
  • func (lx Appl) AlphaEquivalent(other Term) bool
  • func (lx Appl) AorReduce() (Term, error)
  • func (lx Appl) EtaReduce() Term
  • func (lx Appl) NorReduce() (Term, error)
  • func (lx Appl) Reduce() (Term, error)
  • func (lx Appl) Serialize() string
  • func (lx Appl) String() string
  • func (lx Appl) WHNF() Abst
• type Term
  • func Deserialize(inpt string) (Term, error)
  • func MustDeserialize(inpt string) Term
• type Var
  • func (lv Var) AlphaEquivalent(other Term) bool
  • func (lv Var) AorReduce() (Term, error)
  • func (lv Var) EtaReduce() Term
  • func (lv Var) NorReduce() (Term, error)
  • func (lv Var) Reduce() (Term, error)
  • func (lv Var) Serialize() string
  • func (lv Var) String() string
  • func (lv Var) WHNF() Abst

Variables

var MaxReductions = 10000

MaxReductions determines the maximum amount of expansions before we give up use a negative value to have no limit (use with care...)

Types

type Abst

type Abst [1]Term

Abst represents a lambda abstraction

func (Abst) AlphaEquivalent

func (la Abst) AlphaEquivalent(other Term) bool

AlphaEquivalent checks whether a Abst and a Term are identical

func (Abst) AorReduce

func (la Abst) AorReduce() (Term, error)

AorReduce reduces a lambda abstraction using applicative order

func (Abst) BetaReduce

func (la Abst) BetaReduce(sub Term) Term

BetaReduce substitutes the locally bound variable of the Abst by sub

func (Abst) EtaReduce

func (la Abst) EtaReduce() Term

EtaReduce applies eta-reduction to the Abst when possible

func (Abst) NorReduce

func (la Abst) NorReduce() (Term, error)

NorReduce reduces a lambda abstraction using normal order

func (Abst) Reduce

func (la Abst) Reduce() (Term, error)

Reduce reduces a lambda abstraction

func (Abst) Serialize

func (la Abst) Serialize() string

Serialize returns the lambda abstraction as a De Bruijn index representation

func (Abst) String

func (la Abst) String() string

String returns the lambda abstraction as a string

func (Abst) WHNF

func (la Abst) WHNF() Abst

WHNF returns the abstraction

type Appl

type Appl [2]Term

Appl represents an application

func (Appl) AlphaEquivalent

func (lx Appl) AlphaEquivalent(other Term) bool

AlphaEquivalent checks whether the Appl is identical to a Term

func (Appl) AorReduce

func (lx Appl) AorReduce() (Term, error)

AorReduce reduces an application using applicative order

func (Appl) EtaReduce

func (lx Appl) EtaReduce() Term

EtaReduce applies eta-reduction to the Appl when possible

func (Appl) NorReduce

func (lx Appl) NorReduce() (Term, error)

NorReduce reduces an application using normal order

func (Appl) Reduce

func (lx Appl) Reduce() (Term, error)

Reduce reduces an application

func (Appl) Serialize

func (lx Appl) Serialize() string

Serialize returns the application as a De Bruijn index representation

func (Appl) String

func (lx Appl) String() string

String returns the Lambda Expression as a string

func (Appl) WHNF

func (lx Appl) WHNF() Abst

WHNF encapsulates the expression in a lambda abstraction

type Term

type Term interface {
	AlphaEquivalent(Term) bool
	EtaReduce() Term

	String() string

	Reduce() (Term, error)
	NorReduce() (Term, error)
	AorReduce() (Term, error)

	WHNF() Abst

	Serialize() string
	// contains filtered or unexported methods
}

Term is a general type to represent both Applns, Absts and Vars

func Deserialize

func Deserialize(inpt string) (Term, error)

Deserialize turns a De Bruijn index representation into the internal representation

func MustDeserialize

func MustDeserialize(inpt string) Term

MustDeserialize turns a De Bruijn index representation into the internal representation, panics on error

type Var

type Var uint

Var is the De Bruijn index of a variable minus one

func (Var) AlphaEquivalent

func (lv Var) AlphaEquivalent(other Term) bool

AlphaEquivalent checks whether a Var and a Term are identical

func (Var) AorReduce

func (lv Var) AorReduce() (Term, error)

AorReduce returns the variable itself

func (Var) EtaReduce

func (lv Var) EtaReduce() Term

EtaReduce returns the variable

func (Var) NorReduce

func (lv Var) NorReduce() (Term, error)

NorReduce returns the variable itself

func (Var) Reduce

func (lv Var) Reduce() (Term, error)

Reduce returns the variable itself

func (Var) Serialize

func (lv Var) Serialize() string

Serialize returns the variable as a De Bruijn index representation

func (Var) String

func (lv Var) String() string

String returns the lambda variable as a string

func (Var) WHNF

func (lv Var) WHNF() Abst

WHNF encapsulates the Lambda variable inside of a lambda abstraction