sheepda

package module
v0.0.0-...-84daf16 Latest Latest
Warning

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

 Go to latest Published: Sep 30, 2021 License: Apache-2.0 Imports: 5 Imported by: 2

README

sheepda

A memoizing pure lambda calculus interpreter in Go with only two builtins:

  • PRINT_BYTE - takes a Church-encoded numeral and writes the corresponding byte to the configured output stream.
  • READ_BYTE - returns a Church-encoded pair value, where the first element is a Church-encoded boolean about whether or not any data was read, and the second element is a Church-encoded numeral representing the byte that was read if successful, and 0 otherwise. The only reason no data was read was if EOF was reached. Other errors stop execution.

When run in output mode, PRINT_BYTE goes to stdout. READ_BYTE comes from stdin. If you use the sheepda library from your own Go program instead, you can configure input and output to be any io.Writer or io.Reader, in addition to defining your own builtins.

Usage
cd $(mktemp -d)
GOPATH=$(pwd) go get github.com/jtolio/sheepda/bin/sheepda
bin/sheepda output src/github.com/jtolio/sheepda/interview-probs/{prelude,hello-world}.shp

Usage: bin/sheepda [-a] <parsed|output|result> <file1.shp> [<file2.shp> ...]
  -a	if provided, skip assignments when pretty-printing in parsed mode
Examples

Check out interview-probs and especially prelude.shp for how some abstraction towers can be built up for solving common whiteboard problems in pure lambda calculus.

Here is Fizzbuzz in pure lambda calculus with only PRINT_BYTE added. Much of the definition is building up supporting structures like lists and numbers and logic.

((λU.((λY.((λvoid.((λ0.((λsucc.((λ+.((λ*.((λ1.((λ2.((λ3.((λ4.((λ5.((λ6.((λ7.
((λ8.((λ9.((λ10.((λnum.((λtrue.((λfalse.((λif.((λnot.((λand.((λmake-pair.
((λpair-first.((λpair-second.((λzero?.((λpred.((λ-.((λeq?.((λ/.((λ%.((λnil.
((λnil?.((λcons.((λcar.((λcdr.((λdo2.((λfor.((λprint-byte.((λprint-list.
((λprint-newline.((λzero-byte.((λitoa.((λfizzmsg.((λbuzzmsg.((λfizzbuzzmsg.
((λfizzbuzz.(fizzbuzz (((num 1) 0) 0))) λn.((for n) λi.((do2 (((if (zero?
((% i) 3))) λ_.(((if (zero? ((% i) 5))) λ_.(print-list fizzbuzzmsg)) λ_.
(print-list fizzmsg))) λ_.(((if (zero? ((% i) 5))) λ_.(print-list buzzmsg))
λ_.(print-list (itoa i))))) (print-newline nil))))) ((cons (((num 0) 7) 0))
((cons (((num 1) 0) 5)) ((cons (((num 1) 2) 2)) ((cons (((num 1) 2) 2)) ((cons
(((num 0) 9) 8)) ((cons (((num 1) 1) 7)) ((cons (((num 1) 2) 2)) ((cons (((num
1) 2) 2)) nil)))))))))) ((cons (((num 0) 6) 6)) ((cons (((num 1) 1) 7)) ((cons
(((num 1) 2) 2)) ((cons (((num 1) 2) 2)) nil)))))) ((cons (((num 0) 7) 0))
((cons (((num 1) 0) 5)) ((cons (((num 1) 2) 2)) ((cons (((num 1) 2) 2))
nil)))))) λn.(((Y λrecurse.λn.λresult.(((if (zero? n)) λ_.(((if (nil? result))
λ_.((cons zero-byte) nil)) λ_.result)) λ_.((recurse ((/ n) 10)) ((cons
((+ zero-byte) ((% n) 10))) result)))) n) nil))) (((num 0) 4) 8))) λ_.
(print-byte (((num 0) 1) 0)))) (Y λrecurse.λl.(((if (nil? l)) λ_.void) λ_.
((do2 (print-byte (car l))) (recurse (cdr l))))))) PRINT_BYTE)) λn.λf.((((Y
λrecurse.λremaining.λcurrent.λf.(((if (zero? remaining)) λ_.void) λ_.((do2 (f
current)) (((recurse (pred remaining)) (succ current)) f)))) n) 0) f))) λa.λb.
b)) λl.(pair-second (pair-second l)))) λl.(pair-first (pair-second l)))) λe.λl.
((make-pair true) ((make-pair e) l)))) λl.(not (pair-first l)))) ((make-pair
false) void))) λm.λn.((- m) ((* ((/ m) n)) n)))) (Y λ/.λm.λn.(((if ((eq? m) n))
λ_.1) λ_.(((if (zero? ((- m) n))) λ_.0) λ_.((+ 1) ((/ ((- m) n)) n))))))) λm.
λn.((and (zero? ((- m) n))) (zero? ((- n) m))))) λm.λn.((n pred) m))) λn.
((((λn.λf.λx.(pair-second ((n λp.((make-pair (f (pair-first p))) (pair-first
p))) ((make-pair x) x)))) n) succ) 0))) λn.((n λ_.false) true))) λp.(p false)))
λp.(p true))) λx.λy.λt.((t x) y))) λa.λb.((a b) false))) λp.λt.λf.((p f) t)))
λp.λa.λb.(((p a) b) void))) λt.λf.f)) λt.λf.t)) λa.λb.λc.((+ ((+ ((* ((* 10)
10)) a)) ((* 10) b))) c))) (succ 9))) (succ 8))) (succ 7))) (succ 6))) (succ
5))) (succ 4))) (succ 3))) (succ 2))) (succ 1))) (succ 0))) λm.λn.λx.(m (n
x)))) λm.λn.λf.λx.((((m succ) n) f) x))) λn.λf.λx.(f ((n f) x)))) λf.λx.x))
λx.(U U))) (U λh.λf.(f λx.(((h h) f) x))))) λf.(f f))

Formatted and without dependent subproblems:

fizzbuzz = λn.
  (for n λi.
    (do2
      (if (zero? (% i 3))
          λ_. (if (zero? (% i 5))
                  λ_. (print-list fizzbuzzmsg)
                  λ_. (print-list fizzmsg))
          λ_. (if (zero? (% i 5))
                  λ_. (print-list buzzmsg)
                  λ_. (print-list (itoa i))))
      (print-newline nil)))
Grammar
<expr> ::= <variable>
         | `λ` <variable> `.` <expr>
         | `(` <expr> <expr> `)`

Note that the backslash character \ can be used instead of the lambda character λ.

Parser-level syntax sugar

Two forms of syntax sugar are understood by the parser.

Assignments

Every valid lambda calculus program consists of exactly one expression, but this doesn't lend itself to easy construction. So, before the main expression, if

<variable> `=` <expr>
<rest>

is encountered, it is turned into a function call application to define the variable, like so:

`(` `λ` <variable> `.` <rest> <expr> `)`

Example:

true = λx.λy.x

(true a b)

is turned into

(λtrue.(true a b) λx.λy.x)

Every valid program is therefore a list of zero or more assignments followed by a single expression.

Currying

If more than one argument is encountered, it is assumed to be curried. For example, instead of chaining arguments like this:

((((f a1) a2) a3) a4)

you can instead use the form:

(f a1 a2 a3 a4)
License

Copyright (C) 2017 JT Olds. See LICENSE for copying information.

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

View Source 
var (
	Lambdas = map[rune]bool{
		'Λ': true, 'λ': true, 'ᴧ': true, 'Ⲗ': true, 'ⲗ': true, '𝚲': true,
		'𝛌': true, '𝛬': true, '𝜆': true, '𝜦': true, '𝝀': true, '𝝠': true,
		'𝝺': true, '𝞚': true, '𝞴': true, '\\': true,
	}
)

Functions

func IsVariableRune 

func IsVariableRune(ch rune) bool

IsVariableRune will return if the rune could be part of a variable name.

func ParseVariable 

func ParseVariable(s *Stream) (name string, err error)

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 

type ApplicationExpr struct {
	Func Expr
	Arg  Expr
}

ApplicationExpr represents a function application

func (*ApplicationExpr) String 

func (e *ApplicationExpr) String() string

type Builtin 

type Builtin struct {
	Name      string
	Transform func(Value) (val Value, cacheable bool, err error)
}

func (*Builtin) String 

func (b *Builtin) 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.

func NewClosure 

func NewClosure(s *Scope, l *LambdaExpr) *Closure

NewClosure creates a Closure

func (*Closure) String 

func (c *Closure) String() string

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 

func ParseExpr(s *Stream) (Expr, error)

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 

func ParseSubexpression(s *Stream) (Expr, error)

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 

type LambdaExpr struct {
	Arg  string
	Body Expr
}

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 

type Scope struct {
	Name   string
	Value  Value
	Parent *Scope
}

Scope represents a bunch of defined variables due to argument application and function calling.

func NewScope 

func NewScope() *Scope

NewScope returns an empty scope with nothing defined.

func NewScopeWithBuiltins 

func NewScopeWithBuiltins(out io.Writer, in io.Reader) *Scope

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 

func (s *Scope) Get(name string) Value

Get will return the value in the current scope associated with name, or nil if no value is found.

func (*Scope) Set 

func (s *Scope) Set(name string, value Value) *Scope

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 

func (s *Scope) SetBuiltin(name string,
	fn func(Value) (v Value, cacheable bool, err error)) *Scope

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 NewStream 

func NewStream(in io.Reader) *Stream

NewStream creates a new stream from an io.Reader

func (*Stream) AssertMatch 

func (s *Stream) AssertMatch(options map[rune]bool) error

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

func (s *Stream) EOF() bool

EOF returns if the stream has ended.

func (*Stream) Get 

func (s *Stream) Get() (r rune, err error)

Get will advance the stream and return the next rune.

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

func (s *Stream) Peek() (rune, error)

Peek returns the next rune but does not pop it out of the stream.

func (*Stream) SwallowWhitespace 

func (s *Stream) SwallowWhitespace() error

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 

func ChurchBool(val bool) Value

ChurchBool returns a Church-encoded boolean representation of val.

func ChurchNumeral 

func ChurchNumeral(val uint) Value

ChurchNumeral returns a Church-encoded representation of the number val.

func ChurchPair 

func ChurchPair(first, second Value) Value

ChurchPair returns a Church-encoded pair of the two values first and second.

func Eval 

func Eval(s *Scope, expr Expr) (val Value, err error)

Eval evaluates an expression in the given scope and returns the resulting value.

type VariableExpr 

type VariableExpr struct {
	Name string
}

VariableExpr represents a variable reference.

func (*VariableExpr) String 

func (e *VariableExpr) String() string

Source Files

View all Source files

Directories

Path Synopsis
bin
sheepda
sheepdajs

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.