terex

package
v0.1.0 Latest Latest
Warning

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

 Go to latest Published: Nov 13, 2021 License: BSD-3-Clause Imports: 8 Imported by: 7

README

TeREx: Term Rewriting Expressions

Parsing generates a parse tree, which is too verbose for further processing. Instead of long chains of grammar production symbols we usualy prefer a much more compact AST (abstract syntax tree). One possible variant of ASTs is a homogenous tree, i.e. one where the structure of all nodes is identical. This makes tree walking easy.

This module provides the core Go data types to create and modify homogenous trees. Homogenous trees are usually built around some Node type. However, there is a programming language specialized in homogenous lists and trees: Lisp (or Clojure, if you prefer). We implement node types which are reminiscent of Lisp CONS, and call the resulting mini-language TeREx (Term Rewriting Expressions).

With homogenous tree nodes there is always one caveat: type information of the implementing programming language is compromised. Therefore, in absence of generics, the code in this module heavily uses "interface{}" and relies on type switches and casts. This is sometimes cumbersome to read, but on the other hands brings convenience for a certain set of operations, including tree walking and tree restructuring.

Documentation

Overview

Package terex provides term rewriting expressions as a basis for rewriting parse-trees and ASTs. It implements types for a homogenous abstract syntax tree in a Lisp-like fashion.

Parsing generates a parse tree, which is too verbose for further processing. Instead of long chains of grammar production symbols we usualy prefer a much more compact AST (abstract syntax tree). One possible variant of ASTs is a *homogenous* tree, i.e. one where the structure of all nodes is identical. This makes tree walking easy.

This module provides the core Go data types to create and modify homogenous trees. Homogenous trees are usually built around some Node type. However, there is a programming language specialized in homogenous lists and trees: Lisp (or Clojure, if you prefer). We implement node types which are reminiscent of Lisp CONS, and call the resulting mini-language TeREx (Term Rewriting Expressions).

With homogenous tree nodes there is always one caveat: type information of the implementing programming language is compromised. Therefore, in absence of generics, the code in this module heavily uses "interface{}" and relies on type switches and casts. This is sometimes cumbersome to read, but on the other hands brings convenience for a certain set of operations, including tree walking and tree restructuring.

BSD License

Copyright (c) 2019–21, Norbert Pillmayer

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of this software nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func InitGlobalEnvironment 

func InitGlobalEnvironment()

InitGlobalEnvironment initializes the global environment. It is guarded against multiple execution. Without calling this, the "native" operators will not be found in the symbol table.

func T 

func T() tracing.Trace

T traces to the global syntax tracer.

Types

type Atom 

type Atom struct {
	Data interface{}
	// contains filtered or unexported fields
}

Atom is a type for atomic values (in lists). A cons will consist of an atom and a cdr. 

var NilAtom Atom = Atom{} // NIL

NilAtom is a zero value for atoms.

func Atomize 

func Atomize(thing interface{}) Atom

Atomize creates an Atom from an untyped value.

func ErrorAtom 

func ErrorAtom(msg string) Atom

ErrorAtom returns an error message wrapped in an Atom.

func (Atom) IsAtom 

func (a Atom) IsAtom() Atom

IsAtom returns t.

func (Atom) IsNil 

func (a Atom) IsNil() bool

func (Atom) ListString 

func (a Atom) ListString() string

ListString returns an Atom's string representation within a list. Will usually be called indirectly with GCons.ListString().

func (Atom) Match 

func (a Atom) Match(other Atom, env *Environment) bool

func (Atom) String 

func (a Atom) String() string

func (Atom) Type 

func (a Atom) Type() AtomType

Type returns an atom's type.

type AtomType 

type AtomType int

AtomType is a type specifier for an atom. 

const (
	NoType AtomType = iota
	ConsType
	VarType
	NumType
	StringType
	BoolType
	OperatorType
	TokenType
	EnvironmentType
	UserType
	AnyType
	ErrorType
)

func (AtomType) String 

func (i AtomType) String() string

type DefaultSymbolResolver 

type DefaultSymbolResolver struct {
}

func (DefaultSymbolResolver) Resolve 

func (dsr DefaultSymbolResolver) Resolve(atom Atom, env *Environment, asOp bool) (Element, error)

type Element 

type Element struct {
	// contains filtered or unexported fields
}

func Elem 

func Elem(thing interface{}) Element

func Eval 

func Eval(el Element, env *Environment) Element

func EvalAtom 

func EvalAtom(atom Element, env *Environment) Element

func (Element) AsAtom 

func (el Element) AsAtom() Atom

func (Element) AsList 

func (el Element) AsList() *GCons

func (Element) AsSymbol 

func (el Element) AsSymbol() *Symbol

func (Element) Dump 

func (el Element) Dump(L tracing.TraceLevel)

func (Element) First 

func (el Element) First() Element

func (Element) IsAtom 

func (el Element) IsAtom() bool

func (Element) IsError 

func (el Element) IsError() bool

func (Element) IsNil 

func (el Element) IsNil() bool

func (Element) String 

func (el Element) String() string

func (Element) Sublist 

func (el Element) Sublist() Element

func (Element) Type 

func (el Element) Type() AtomType

type Environment 

type Environment struct {
	Resolver SymbolResolver
	AST      *GCons
	// contains filtered or unexported fields
}

Environment is a type for a symbol environment. 

var GlobalEnvironment *Environment = NewEnvironment("#global", nil)

GlobalEnvironment is the base environment all other environments stem from.

func NewEnvironment 

func NewEnvironment(name string, parent *Environment) *Environment

NewEnvironment creates a new environment.

func (*Environment) Def 

func (env *Environment) Def(symname string, value Element) *Symbol

Def defines a symbol and stores a value for it, if any.

func (*Environment) Defn 

func (env *Environment) Defn(opname string, funcBody Mapper) *Symbol

Defn defines a new operator and stores its symbol in the given environment. funcBody is the operator function, called during eval().

func (*Environment) Dump 

func (env *Environment) Dump() string

Dump is a debugging helper, listing all known symbols in env.

func (*Environment) Error 

func (env *Environment) Error(e error)

Error sets an error occuring in this environment.

func (*Environment) Eval 

func (env *Environment) Eval(list *GCons) *GCons

func (*Environment) FindSymbol 

func (env *Environment) FindSymbol(name string, inherit bool) *Symbol

FindSymbol checks wether a symbol is defined in env and returns it, if found. Otherwise nil is returned.

func (*Environment) Intern 

func (env *Environment) Intern(name string, inherit bool) *Symbol

Intern interns a symbol name as a symbol, returning a reference to that symbol. If the symbol already exists, the existing symbol is returned. Parameter inherit dictates wether ancestor environments should be searched, too, to detect the symbol.

func (*Environment) LastError 

func (env *Environment) LastError() error

LastError returns the last error occuring in this environment.

func (*Environment) String 

func (env *Environment) String() string

type GCons 

type GCons struct {
	Car Atom
	Cdr *GCons
}

GCons is a type for a list cons.

func Cons 

func Cons(car Atom, cdr *GCons) *GCons

Cons creates a cons from a given Atom and a Cdr.

func List 

func List(things ...interface{}) *GCons

List makes a list from given elements.

func QuotedList 

func QuotedList(things ...interface{}) *GCons

QuotedList makes a list from given elements, quoting them.

func (*GCons) Append 

func (l *GCons) Append(other *GCons) *GCons

Append destructively appends a list to a list.

func (*GCons) Branch 

func (l *GCons) Branch(other *GCons) *GCons

Branch destructively appends a list as a sublist to l.

func (*GCons) Cadr 

func (l *GCons) Cadr() *GCons

Cadr returns Cdr(Car(...)) of a list/node.

func (*GCons) Cdar 

func (l *GCons) Cdar() Atom

Cdar returns Car(Cdr(...)) of a list/node.

func (*GCons) Cddar 

func (l *GCons) Cddar() Atom

Cddar returns Car(Cdr(Cdr(...))) of a list/node.

func (*GCons) Cddr 

func (l *GCons) Cddr() *GCons

Cddr returns Cdr(Cdr(...)) of a list/node.

func (*GCons) Concat 

func (l *GCons) Concat(other *GCons) *GCons

Concat appends a list or element at the end of the copy of a list.

func (*GCons) Drop 

func (l *GCons) Drop(filter func(Atom) bool) *GCons

Drop returns a copy of l with atom dropped if they are matched by a filter function.

func (*GCons) First 

func (l *GCons) First() Atom

First returns the Car atom of a list/cons.

func (*GCons) FirstN 

func (l *GCons) FirstN(n int) *GCons

FirstN returns the frist n elements of a list.

func (*GCons) IndentedListString 

func (l *GCons) IndentedListString() string

IndentedListString returns a string representing a list (or cons).

func (*GCons) IsAtom 

func (l *GCons) IsAtom() Atom

IsAtom returns false, i.e. NIL.

func (*GCons) IsLeaf 

func (l *GCons) IsLeaf() bool

IsLeaf returns true if this node does have neither a Cdr nor a left child.

func (*GCons) Last 

func (l *GCons) Last() *GCons

Last returns the last element of a list or nil.

func (*GCons) Length 

func (l *GCons) Length() int

Length returns the length of a list.

func (*GCons) ListString 

func (l *GCons) ListString() string

ListString returns a string representing a list (or cons).

func (*GCons) Map 

func (l *GCons) Map(mapper Mapper, env *Environment) *GCons

Map applies a mapping-function to every element of a list.

func (*GCons) Match 

func (l *GCons) Match(other *GCons, env *Environment) bool

Match an s-expr to a pattern.

From https://hanshuebner.github.io/lmman/fd-con.xml:

list-match-p object pattern

object is evaluated and matched against pattern; the value is t if it matches, nil otherwise. pattern is made with backquotes (Aids for Defining Macros); whereas normally a backquote expression says how to construct list structure out of constant and variable parts, in this context it says how to match list structure against constants and variables. Constant parts of the backquote expression must match exactly; variables preceded by commas can match anything but set the variable to what was matched. (Some of the variables may be set even if there is no match.) If a variable appears more than once, it must match the same thing (equal list structures) each time. ,ignore can be used to match anything and ignore it. For example, `(x (,y) . ,z) is a pattern that matches a list of length at least two whose first element is x and whose second element is a list of length one; if a list matches, the caadr of the list is stored into the value of y and the cddr of the list is stored into z. Variables set during the matching remain set after the list-match-p returns; in effect, list-match-p expands into code which can setq the variables. If the match fails, some or all of the variables may already have been set.

Example: 

(list-match-p foo
          `((a ,x) ,ignore . ,c))

is t if foo's value is a list of two or more elements, the first of which is a list of two elements; and in that case it sets x to (cadar foo) and c to (cddr foo).

List l is the pattern, other is the argument to be matched against the pattern.

func (*GCons) Nth 

func (l *GCons) Nth(n int) Atom

Nth returns the <n>th element of a list, or nil if the length of the list is < n.

func (*GCons) Push 

func (l *GCons) Push(a Atom) *GCons

Push prepends a list with atom a.

func (*GCons) Reduce 

func (l *GCons) Reduce(f func(Atom, Atom) Atom, initial Atom, env *Environment) Atom

Reduce applies a mapping-function to every element of a list.

func (*GCons) Rest 

func (l *GCons) Rest() *GCons

Rest returns the Cdr of a list/node.

func (GCons) String 

func (l GCons) String() string

func (*GCons) Tee 

func (l *GCons) Tee() *GCons

Tee returns the Car as a list, if it is of sublist-type, nil otherwise.

type Mapper 

type Mapper func(Element, *Environment) Element

A Mapper takes an atom or list and maps it to an atom or list

type Operator 

type Operator interface {
	String() string                     // returns the string representation of this operator
	Call(Element, *Environment) Element // takes and returns *GCons or Node

}

Operator is an interface to be implemented by every operator-symbol, i.e., one being able to operate on an argument list.

type Symbol 

type Symbol struct {
	Name string

	Value Element
	// contains filtered or unexported fields
}

Symbol is a type for language symbols (stored in the Environment). A symbol can change its value. A value may be any atom or s-expr type. A value of nil means the symbol is not yet bound.

func (Symbol) AtomValue 

func (sym Symbol) AtomValue() interface{}

func (*Symbol) Get 

func (sym *Symbol) Get(key string) Atom

Get returns a property value for a given key.

func (Symbol) IsNil 

func (sym Symbol) IsNil() bool

IsNil returns true if the symbol's value is NilAtom

func (Symbol) IsOperatorType 

func (sym Symbol) IsOperatorType() bool

IsOperatorType returns true if a symbol represents an atom (not a cons).

func (Symbol) String 

func (sym Symbol) String() string

func (Symbol) ValueType 

func (sym Symbol) ValueType() AtomType

ValueType returns the type of a symbols value

type SymbolResolver 

type SymbolResolver interface {
	Resolve(Atom, *Environment, bool) (Element, error)
}

type Token 

type Token struct {
	Name    string
	TokType int
	Token   interface{}
	Value   interface{}
}

Token represents a grammar terminal, and a corresponding input token, respectively.

func (Token) String 

func (t Token) String() string

Source Files

View all Source files

Directories

Path Synopsis
Package fp provides utilities for kind-of functional programming on TeREx lists.
 Package fp provides utilities for kind-of functional programming on TeREx lists.
Package terexlang provides a parser for TeREx (term rewriting).
 Package terexlang provides a parser for TeREx (term rewriting).
trepl
Package termr implements tools for term rewriting and construction of abstract syntax trees.
 Package termr implements tools for term rewriting and construction of abstract syntax trees.

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.