mast

package module
v0.0.0-...-46cfdfa Latest Latest
Warning

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

 Go to latest Published: Mar 11, 2017 License: MIT Imports: 2 Imported by: 0

README

Mast: a Math AST for Golang

CircleCI license

Because Go does not support operator overloading, most numerical libraries are messy to use. Mast is an attempt to write a domain-specific language for math, so that code can be written in a more simple way.

If it helps, think regular expressions, but for algebra.

// with Mast
mast.Eval("x = A' * b + c", &x, &A, &b, &c)

// without Mast
Transpose(&aT, &A)
Times(&Atb, &At, &b)
Plus(&x, &Atb, &c)

Parser

Mast mostly exists to create parsers for math-like languages. To use it, first create a *mast.Parser object, configuring the various operations and their precidence.

// A Parser configures the given operators in terms of precedence.
type Parser struct {
	// Define which operators appear in this language. These operators are
	// given in order of loosest to tightest (so addition/subtraction should
	// probably come before multiplication/division).
	Operators []Prec

	// Define which matching grouping operators are used.
	Groups []Group

	// If true, then "sin x" is legal and parses as "sin(x)" would. If false,
	// that is a syntax error.
	AdjacentIsApplication bool
}

Then you invoke the (p *mast.Parser).Parse(string) (*mast.Equation, error) function.

// Parses a single equation in the given source. On success, e is a
// parsed *Equation; iff not, error is non-nil and of type Unexpected{}.
func (p Parser) Parse(source string) (e *Equation, error) {
Example

Suppose we want to make a basic calculator parser. First, define which operations and grouping operators we want to support:

integers := &mast.Parser{
	// allow parentheses
	Groups: []Group{
		{"(", ")"},
	},
	
	// add plus, minux, multiply, divide, and modulo
	Operators: []Prec{
		{[]string{"+", "-"}, InfixLeft},
		{[]string{"*", "/", "%"}, InfixLeft},
		{[]string{"-", "+"}, Prefix},
	},
}

To parse a string using this language, invoke (p *mast.Parser) Parse(string) (*mast.Equation, error) with the source code to evaluate. For example, if we run:

tree, err := integers.Parse("y = (-a) * b + c")
fmt.Printf("tree: %v\n", tree)

then err will be nil and tree will be as follows:

tree := &Equation{
	Left: &Var{"y"},
	Right: &Binary{
		Op: "+",
		Left: &Binary{
			Op: "*",
			Left: &Unary{
				Op: "-",
				Elem: &Var{"a"},
			},
			Right: &Var{"b"},
		}
		Right: &Var{"c"}
	}
}

By iterating over the tree, your DSL can evaluate the mathematical expression while maintaining type integrity.

Evaluator

Mast includes a toy evaluator that handles matrices as [][]float64. To use it, invoke the Eval(code string, args ...interface{}) error function, passing pointers to the respective arguments.

// Evaluate the given expression with the given variables. Variables are
// assigned left to right based on first usage.
func Eval(code string, args ...interface{}) error {

Think %-arguments to fmt.Printf. To make setting up variables easier, arguments can be specified in three ways:

  • a [][]float64 for an n x m matrix;
  • a []float64 for an 1 x n column vector; or
  • a float64, for a 1 x 1 scalar.

All other types panic.

Example

Suppose we want to compute a linear transform (multiplying a vector by a matrix, and adding a vector). First, we set up the variables to compute:

A := [][]float64{
	[]float64{1, 2},
}

x := []float64{3, 4}
// same as := [][]float64{[]float64{5}, []float64{6}}

b := 5.0
// same as := [][]float64{[]float64{5.0}} 

y := 0

Once those are set up, the computation is fairly easy.

if err := mast.Eval("y = A * x + b", &y, &A, &x, &b); err != nil {
	handleError(err)
	return
}

The result is then available in y.

License

This code is covered under the MIT license.

Copyright (c) 2016 Jeremy Archer

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Documentation

Overview

Because Go does not support operator overloading, most numerical libraries are messy to use. M-AST is an attempt to write a domain-specific language for math, so that code can be written in a more simple way.

If it helps, think regular expressions, but for algebra. 

// with Mast
mast.Eval("x = A' * b + c", &x, &A, &b, &c)

// without Mast
Transpose(&aT, &A)
Times(&Atb, &At, &b)
Plus(&x, &Atb, &c)

Parser

Mast mostly exists to create parsers for math-like languages. To use it, first create a *mast.Parser object, configuring the various operations and their precidence. 

// A Parser configures the given operators in terms of precedence.
type Parser struct {
	// Define which operators appear in this language. These operators are
	// given in order of loosest to tightest (so addition/subtraction should
	// probably come before multiplication/division).
	Operators []Prec

	// Define which matching grouping operators are used.
	Groups []Group

	// If true, then "sin x" is legal and parses as "sin(x)" would. If false,
	// that is a syntax error.
	AdjacentIsApplication bool
}

Then you invoke the (p *mast.Parser).Parse(string) (*mast.Equation, error) function. 

// Parses a single equation in the given source. On success, e is a
// parsed *Equation; iff not, error is non-nil and of type Unexpected{}.
func (p Parser) Parse(source string) (e *Equation, error) {

Parser Example

Suppose we want to make a basic calculator parser. First, define which operations and grouping operators we want to support: 

integers := &mast.Parser{
	// allow parentheses
	Groups: []Group{
		{"(", ")"},
	},

	// add plus, minux, multiply, divide, and modulo
	Operators: []Prec{
		{[]string{"+", "-"}, InfixLeft},
		{[]string{"*", "/", "%"}, InfixLeft},
		{[]string{"-", "+"}, Prefix},
	},
}

To parse a string using this language, invoke (p *mast.Parser) Parse(string) (*mast.Equation, error) with the source code to evaluate. For example, if we run: 

tree, err := integers.Parse("y = (-a) * b + c")
fmt.Printf("tree: %v\n", tree)

then err will be nil and tree will be as follows: 

tree := &Equation{
	Left: &Var{"y"},
	Right: &Binary{
		Op: "+",
		Left: &Binary{
			Op: "*",
			Left: &Unary{
				Op: "-",
				Elem: &Var{"a"},
			},
			Right: &Var{"b"},
		}
		Right: &Var{"c"}
	}
}

By iterating over the tree, your DSL can evaluate the mathematical expression while maintaining type integrity.

Evaluator

Mast includes a toy evaluator that handles matrices as [][]float64. To use it, invoke the Eval(code string, args ...interface{}) error function, passing pointers to the respective arguments. 

// Evaluate the given expression with the given variables. Variables are
// assigned left to right based on first usage.
func Eval(code string, args ...interface{}) error {

Think %-arguments to fmt.Printf. To make setting up variables easier, arguments can be specified in three ways:

  • a [][]float64 for an n x m matrix;
  • a []float64 for an 1 x n column vector; or
  • a float64, for a 1 x 1 scalar.

All other types panic.

Evaluator Example

Suppose we want to compute a linear transform (multiplying a vector by a matrix, and adding a vector). First, we set up the variables to compute: 

A := [][]float64{
	[]float64{1, 2},
}

x := []float64{3, 4}
// same as := [][]float64{[]float64{5}, []float64{6}}

b := 5.0
// same as := [][]float64{[]float64{5.0}}

y := 0

Once those are set up, the computation is fairly easy. 

if err := mast.Eval("y = A * x + b", &y, &A, &x, &b); err != nil {
	handleError(err)
	return
}

The result is then available in y.

Example (Evaluate) 
package main

import (
	"fmt"
	"github.com/fatlotus/mast"
)

func main() {
	res := [][]float64{[]float64{0, 0}, []float64{0, 0}}
	b := [][]float64{[]float64{1, 2}, []float64{3, 4}}

	mast.MustEval("res = B * B'", &res, &b)
	fmt.Printf("res = %v\n", res)

}

Output:

res = [[5 11] [11 25]]
Example (Parse) 
package main

import (
	"fmt"
	"github.com/fatlotus/mast"
)

func main() {
	tree, err := mast.PEMDAS.Parse("res = inv(B * B')")
	if err != nil {
		panic(err)
	}

	fmt.Printf("%s\n", tree)
}

Output:

res = (inv (B * (' B)))

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Eval 

func Eval(code string, args ...interface{}) error

Evaluate the given expression with the given variables. Variables are assigned left to right based on first usage.

Example

Evaluate a simple linear equation, handling the error. 

y := []float64{0, 0}
A := [][]float64{[]float64{1, 2}, []float64{3, 4}}
x := []float64{5, 6}
b := []float64{7, 8}

if err := Eval("y = A * x + b", &y, &A, &x, &b); err != nil {
	handleError(err)
	return
}
fmt.Printf("y = [%.2f %.2f]^T", y[0], y[1])

Output:

y = [24.00 47.00]^T

func MustEval 

func MustEval(code string, args ...interface{})
Example

Evaluate a simple linear equation, but panic if something goes wrong. 

y := []float64{0, 0}
A := [][]float64{[]float64{1, 2}, []float64{3, 4}}
x := []float64{5, 6}
b := []float64{7, 8}

MustEval("y = A * x + b", &y, &A, &x, &b)
fmt.Printf("y = [%.2f %.2f]^T", y[0], y[1])

Output:

y = [24.00 47.00]^T

Types

type Apply 

type Apply struct {
	Operator Expr
	Operand  Expr
}

Represents function application, where an expression is invoked as an operator. Examples: 

sin x == Apply{Var{"sin"}, Var{"x"}}
inv(A + B) == Apply{Var{"inv"}, Binary{"+", Var{"A"}, Var{"B"}}}

func (*Apply) String 

func (a *Apply) String() string

Represents this application as a string.

type Binary 

type Binary struct {
	Op    string
	Left  Expr
	Right Expr
}

A Binary operator is one with two operands. Examples: 

a + b == Binary{"+", Var{"a"}, Var{"b"}}
a * b + c == Binary{"+", Binary{"*", Var{"a"}, Var{"b"}}, Var{"c"}}

func (*Binary) String 

func (o *Binary) String() string

Represent this binary operator as a string.

type Equation 

type Equation struct {
	Left  Expr
	Right Expr
}

An equation is an assignment of one side to the other. The engine provided can only evaluate an equation with a single variable on the left, but more advanced algebra systems could go further. Example: 

x = A\b  ==  Equation{Var{"x"}, Binary{"\\", Var{"A"}, Var{"b"}}}

func (*Equation) String 

func (e *Equation) String() string

Represent this Equation as a string.

type Expr 

type Expr interface {
	String() string
}

The Syntax tree returned by .Parse() is composed of Expr elements. Exprs are always of one of the following types: 

Apply   sin(t)
Var     x
Unary   -w
Binary  a + b

type Group 

type Group struct {
	Left  string
	Right string
}

A Group is a grouping operator, such as (), {}, or [].

type OpType 

type OpType int

An OpType represents the direction the operator associates and where it goes relative to the operands. 

const (
	// eg. a + b + c == (a + b) + c
	InfixLeft OpType = iota

	// eg. a ^ b ^ c == a ^ (b ^ c)
	InfixRight

	// eg. - - a == - (- a)
	Prefix

	// eg. A” = (A')'
	Suffix
)

type Parser 

type Parser struct {
	// Define which operators appear in this language. These operators are
	// given in order of loosest to tightest (so addition/subtraction should
	// probably come before multiplication/division).
	Operators []Prec

	// Define the invisible grouping operators. These are not part of the tree,
	// but do override order of operations [as in (a + b) * c].
	Parens []Group

	// Define structural grouping operators. These behave like parens, except
	// they also also empty groups, and turn into Unary and Var nodes.
	//
	// Examples:
	//   []     = Var{"[]"}
	//   [x]    = Unary{"[]", Var{"x"}}
	//   [a, b] = Unary{"[]", Binary{",", "a", "b"}}
	Brackets []Group

	// If true, then "sin x" is legal and parses as "sin(x)" would. If false,
	// that is a syntax error.
	AdjacentIsApplication bool
}

A Parser configures the given operators in terms of precedence. 

var PEMDAS Parser = Parser{
	Parens: []Group{
		{"(", ")"},
		{"[", "]"},
	},
	Brackets: []Group{
		{"{", "}"},
	},
	Operators: []Prec{
		{[]string{","}, InfixLeft},
		{[]string{"+", "-"}, InfixLeft},
		{[]string{"*", "/", "\\"}, InfixLeft},
		{[]string{"^"}, InfixRight},
		{[]string{"-", "+"}, Prefix},
		{[]string{"'"}, Suffix},
	},
	AdjacentIsApplication: true,
}

PEMDAS defines a typical multiply-first math language.

func (Parser) Parse 

func (p Parser) Parse(source string) (*Equation, error)

Parses a single equation in the given source. On success, Equation is a parsed Equation; iff not, error is non-nil and of type Unexpected{}.

func (Parser) ParseExpr 

func (p Parser) ParseExpr(source string) (Expr, error)

Parses an expression from source. On success, Expr is an expression; iff not, error is non-nil and of type Unexpected{}

type Prec 

type Prec struct {
	Glyphs []string
	Type   OpType
}

A Prec is a series of operators that share the same precedence, such as plus and minus. The Type represents the associativity and position of this operator.

type Unary 

type Unary struct {
	Op   string
	Elem Expr
}

A Unary operator is one with one operator. Examples: 

-a == Unary{"-", Var{"a"}}
A' == Unary{"'", Var{"A"}}

func (*Unary) String 

func (u *Unary) String() string

Represent this unary operator as a string.

type Unexpected 

type Unexpected struct {
	Found     string
	Expecting string
}

A parse error; all errors returned from .Parse are of this form. These indicate which token was found, and which tokens should have been provided.

func (Unexpected) Error 

func (u Unexpected) Error() string

Represent this Unexpected as a string.

type Var 

type Var struct {
	Name string
}

A Var is a named variable in the environment. Variables can be single or multiple letters.

func (*Var) String 

func (v *Var) String() string

Represent this Var as a context.

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.