Documentation ¶
Overview ¶
Package sheepda implements a lambda calculus parser and interpreter.
See https://jtolio.github.io/sheepda/ for a GopherJS web playground or http://www.jtolio.com/writing/2017/03/whiteboard-problems-in-pure-lambda-calculus/ for a description.
Index ¶
Constants ¶
This section is empty.
Variables ¶
Functions ¶
func IsVariableRune ¶
IsVariableRune will return if the rune could be part of a variable name.
func ParseVariable ¶
ParseVariable will parse a variable out of a stream. It assumes the stream has been advanced to the beginning of the variable.
Types ¶
type ApplicationExpr ¶
ApplicationExpr represents a function application
func (*ApplicationExpr) String ¶
func (e *ApplicationExpr) String() string
type Closure ¶
type Closure struct { Scope *Scope Lambda *LambdaExpr // contains filtered or unexported fields }
A Closure represents an evaluated LambdaExpr. It has an associated Scope. Use NewClosure to create one.
type Expr ¶
type Expr interface {
String() string
}
Expr represents a parsed expression. Eval only knows how to deal with LambdaExprs, ApplicationExprs, VariableExprs, and ProgramExprs.
func ParseExpr ¶
ParseExpr will parse the next full expression. It does not know how to handle assignment syntax sugar, nor does it make sure the stream has been completely processed.
func ParseSubexpression ¶
ParseSubexpression will parse a parenthetical expression. If only one value is found in parentheses, it is simply an informational subexpression. If multiple values are found, a function application is assumed.
type LambdaExpr ¶
LambdaExpr represents a function definition.
func ParseLambda ¶
func ParseLambda(s *Stream) (*LambdaExpr, error)
ParseLambda parses a LambdaExpr out of a stream. It assumes the stream has been advanced to the beginning of the expression.
func (*LambdaExpr) String ¶
func (e *LambdaExpr) String() string
type ProgramExpr ¶
type ProgramExpr struct {
Expr
}
ProgramExpr represents a full program.
func Parse ¶
func Parse(s *Stream) (*ProgramExpr, error)
Parse will parse a full lambda calculus program out of the stream. It understands assignment syntax sugar, such as
var = \x.\y.x (do-something var)
func (*ProgramExpr) String ¶
func (e *ProgramExpr) String() string
String will regenerate a list of newline-delimited assignments to place at the beginning, unlike ProgramExpr.Expr.String() which is otherwise equivalent.
type Scope ¶
Scope represents a bunch of defined variables due to argument application and function calling.
func NewScopeWithBuiltins ¶
NewScopeWithBuiltins creates an empty scope (like NewScope) but then defines two functions.
PRINT_BYTE takes a Church-encoded numeral, turns it into the corresponding byte, then writes it to out, if out is not nil. The return value is the original numeral.
READ_BYTE throws away its argument, then returns a Church-encoded pair where the first element is true if data was read and the second element is a Church-encoded numeral representing the byte that was read. The only reason the first element could be false is due to EOF. Read errors, like other errors with builtins, halt the interpreter.
func (*Scope) Get ¶
Get will return the value in the current scope associated with name, or nil if no value is found.
func (*Scope) Set ¶
Set returns a new scope with all of the same values set as the previous scope, but will additionally have name set to value.
func (*Scope) SetBuiltin ¶
SetBuiltin defines a builtin in the scope called name that applies fn to the given value. A result value should be returned. If cacheable is true, then the result of the call may get memoized and the function may never be called again. Cacheable should be false for functions with side-effects (or I/O). If err is non-nil, the interpreter will be halted.
type Stream ¶
type Stream struct {
// contains filtered or unexported fields
}
Stream makes parsing a sequence of runes easier
func (*Stream) AssertMatch ¶
AssertMatch will make sure the current rune is in the set of possible options and error otherwise. Then it will swallow any whitespace.
func (*Stream) Next ¶
func (s *Stream) Next()
Next pops any current rune out of the stream. It won't advance the stream farther though.
func (*Stream) SwallowWhitespace ¶
SwallowWhitespace will advance the stream past any whitespace.
type Value ¶
type Value interface {
String() string
}
Value represents an evaluated result. Anything can be a value! Eval only knows how to call *Closure or *Builtin types, so if you have something else as a value, don't use it like a function.
func ChurchBool ¶
ChurchBool returns a Church-encoded boolean representation of val.
func ChurchNumeral ¶
ChurchNumeral returns a Church-encoded representation of the number val.
func ChurchPair ¶
ChurchPair returns a Church-encoded pair of the two values first and second.
type VariableExpr ¶
type VariableExpr struct {
Name string
}
VariableExpr represents a variable reference.
func (*VariableExpr) String ¶
func (e *VariableExpr) String() string