combinator

package module

v0.0.0-...-475c420 Latest Latest Go to latest Published: Apr 15, 2024 License: MIT Imports: 6 Imported by: 0

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

README ¶

Combinator

A complete and open source implementation of Moses Schönfinkel's 1924 paper - On the Building Blocks of Mathematical Logic.

Guide

See the section-by-section guide to the paper here.

Progress

Usage

go get github.com/planetlambert/combinator@latest

import (
    "context"
    "fmt"

    "github.com/planetlambert/combinator"
)

func main() {
    ctx := context.Background()

    // Use a built-in basis (SKI in this example)
    transformedStatement, _ := combinator.SKI.Transform(ctx, "S(K(SI))Kab")

    // Prints "ba" - S(K(SI))K is the "reversal" combinator
    fmt.Println(transformedStatement)

}

Go Package Documentation here.

Testing

go test ./...

Documentation ¶

Index ¶

Variables
func Unparse(tree *Tree) string
func WellDefined(statement string) (bool, error)
type Basis
type Combinator
- func (c Combinator) Transform(ctx context.Context, statement string) (string, error)
type Tree

Constants ¶

This section is empty.

Variables ¶

View Source

var (
	// Identity
	I = Combinator{
		Name:       "I",
		Arguments:  []string{"x"},
		Definition: "x",
	}

	// Constancy
	K = Combinator{
		Name:       "K",
		Arguments:  []string{"x", "y"},
		Definition: "x",
	}

	// Interchange
	T = Combinator{
		Name:       "T",
		Arguments:  []string{"x", "y", "z"},
		Definition: "xzy",
	}

	// Composition
	Z = Combinator{
		Name:       "Z",
		Arguments:  []string{"x", "y", "z"},
		Definition: "x(yz)",
	}

	// Fusion
	S = Combinator{
		Name:       "S",
		Arguments:  []string{"x", "y", "z"},
		Definition: "xz(yz)",
	}

	// All of Schönfinkel's defined combinators
	Schonfinkel = Basis{I, K, T, Z, S}
)

From section 3 of the paper

View Source

var (
	SK  = Basis{S, K}
	SKI = Basis{S, K, I}
)

SK and SKI (https://en.wikipedia.org/wiki/SKI_combinator_calculus)

View Source

var (
	B = Combinator{
		Name:       "B",
		Arguments:  []string{"x", "y", "z"},
		Definition: "x(yz)",
	}

	C = Combinator{
		Name:       "C",
		Arguments:  []string{"x", "y", "z"},
		Definition: "xzy",
	}

	W = Combinator{
		Name:       "W",
		Arguments:  []string{"x", "y"},
		Definition: "xyy",
	}

	BCKW = Basis{B, C, K, W}
)

BCKW (https://en.wikipedia.org/wiki/B,_C,_K,_W_system)

View Source

var (
	Zero = Combinator{
		Name:       "0",
		Arguments:  []string{"f", "x"},
		Definition: "x",
	}

	Succ = Combinator{
		Name:       "S",
		Arguments:  []string{"n", "f", "x"},
		Definition: "f(nfx)",
	}

	Plus = Combinator{
		Name:       "P",
		Arguments:  []string{"m", "n", "f", "x"},
		Definition: "mf(nfx)",
	}

	Mult = Combinator{
		Name:       "M",
		Arguments:  []string{"m", "n", "f", "x"},
		Definition: "m(nf)x",
	}

	Exp = Combinator{
		Name:       "E",
		Arguments:  []string{"m", "n", "f", "x"},
		Definition: "nmfx",
	}

	Church = Basis{Zero, Succ, Plus, Mult, Exp}
)

Church Encoding (https://en.wikipedia.org/wiki/Church_encoding)

View Source

var (
	Iota = Basis{
		S,
		K,
		Combinator{
			Name:      "i",
			Arguments: []string{"x"},

			Definition: "xSK",
		},
	}
)

Iota (https://en.wikipedia.org/wiki/Iota_and_Jot)

View Source

var MaxFrames = 1000000

Functions ¶

func Unparse ¶

func Unparse(tree *Tree) string

Parses the statement into a Tree

func WellDefined ¶

func WellDefined(statement string) (bool, error)

Returns whether the statement is well defined or not

Types ¶

type Basis ¶

type Basis []Combinator

func (Basis) Reduce ¶

func (b Basis) Reduce(ctx context.Context, tree *Tree) (*Tree, error)

Reduces the Tree using the Basis `b`

func (Basis) Transform ¶

func (b Basis) Transform(ctx context.Context, statement string) (string, error)

Transforms the statement using the Basis `b`

func (Basis) With ¶

func (b Basis) With(combinator Combinator) Basis

Adds an additional Combinator to the Basis

type Combinator ¶

type Combinator struct {
	Name       string
	Arguments  []string
	Definition string
}

func (Combinator) Transform ¶

func (c Combinator) Transform(ctx context.Context, statement string) (string, error)

Transforms the statement using the Combinator `c`

type Tree ¶

type Tree struct {
	Left   *Tree
	Right  *Tree
	Parent *Tree
	IsLeaf bool
	IsRoot bool
	Leaf   string // If `IsLeaf`, the leaf's content
}

A simple binary tree

func Copy ¶

func Copy(t *Tree) *Tree

Produces a copy of the tree

func Join ¶

func Join(trees ...*Tree) *Tree

Joins the trees together under a new root

func Parse ¶

func Parse(statement string) *Tree

Parses the statement into a Tree

Source Files ¶

View all Source files

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL