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 ¶
- func InitGlobalEnvironment()
- func T() tracing.Trace
- type Atom
- type AtomType
- type DefaultSymbolResolver
- type Element
- func (el Element) AsAtom() Atom
- func (el Element) AsList() *GCons
- func (el Element) AsSymbol() *Symbol
- func (el Element) Dump(L tracing.TraceLevel)
- func (el Element) First() Element
- func (el Element) IsAtom() bool
- func (el Element) IsError() bool
- func (el Element) IsNil() bool
- func (el Element) String() string
- func (el Element) Sublist() Element
- func (el Element) Type() AtomType
- type Environment
- func (env *Environment) Def(symname string, value Element) *Symbol
- func (env *Environment) Defn(opname string, funcBody Mapper) *Symbol
- func (env *Environment) Dump() string
- func (env *Environment) Error(e error)
- func (env *Environment) Eval(list *GCons) *GCons
- func (env *Environment) FindSymbol(name string, inherit bool) *Symbol
- func (env *Environment) Intern(name string, inherit bool) *Symbol
- func (env *Environment) LastError() error
- func (env *Environment) String() string
- type GCons
- func (l *GCons) Append(other *GCons) *GCons
- func (l *GCons) Branch(other *GCons) *GCons
- func (l *GCons) Cadr() *GCons
- func (l *GCons) Cdar() Atom
- func (l *GCons) Cddar() Atom
- func (l *GCons) Cddr() *GCons
- func (l *GCons) Concat(other *GCons) *GCons
- func (l *GCons) Drop(filter func(Atom) bool) *GCons
- func (l *GCons) First() Atom
- func (l *GCons) FirstN(n int) *GCons
- func (l *GCons) IndentedListString() string
- func (l *GCons) IsAtom() Atom
- func (l *GCons) IsLeaf() bool
- func (l *GCons) Last() *GCons
- func (l *GCons) Length() int
- func (l *GCons) ListString() string
- func (l *GCons) Map(mapper Mapper, env *Environment) *GCons
- func (l *GCons) Match(other *GCons, env *Environment) bool
- func (l *GCons) Nth(n int) Atom
- func (l *GCons) Push(a Atom) *GCons
- func (l *GCons) Reduce(f func(Atom, Atom) Atom, initial Atom, env *Environment) Atom
- func (l *GCons) Rest() *GCons
- func (l GCons) String() string
- func (l *GCons) Tee() *GCons
- type Mapper
- type Operator
- type Symbol
- type SymbolResolver
- type Token
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.
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.
func (Atom) ListString ¶
ListString returns an Atom's string representation within a list. Will usually be called indirectly with GCons.ListString().
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 Eval ¶
func Eval(el Element, env *Environment) Element
func EvalAtom ¶
func EvalAtom(atom Element, env *Environment) Element
func (Element) Dump ¶
func (el Element) Dump(L tracing.TraceLevel)
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 ¶
GCons is a type for a list cons.
func QuotedList ¶
func QuotedList(things ...interface{}) *GCons
QuotedList makes a list from given elements, quoting them.
func (*GCons) Drop ¶
Drop returns a copy of l with atom dropped if they are matched by a filter function.
func (*GCons) IndentedListString ¶
IndentedListString returns a string representing a list (or cons).
func (*GCons) ListString ¶
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 ¶
Nth returns the <n>th element of a list, or nil if the length of the list is < n.
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 ¶
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) IsOperatorType ¶
IsOperatorType returns true if a symbol represents an atom (not a cons).
type SymbolResolver ¶
type SymbolResolver interface {
Resolve(Atom, *Environment, bool) (Element, error)
}
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). |
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. |