runtime

package
v0.0.0-...-ae32867 Latest Latest
Warning

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

 Go to latest Published: Dec 12, 2020 License: BSD-3-Clause Imports: 7 Imported by: 0

Documentation

Overview

Package runtime implements an interpreter runtime, consisting of scopes, memory frames and symbols (variable declarations and references).

For a thorough discussion of an interpreter's runtime environment, refer to "Language Implementation Patterns" by Terence Parr.

Symbol Table and Scope Tree

This module implements data structures for scope trees and symbol tables attached to them.

Memory Frames

This module implements a stack of memory frames. Memory frames are used by an interpreter to allocate local storage for active scopes.

Expression Stack

This module implements a stack of expressions. It is used for expression evaluation during a parser walk of an expression AST. Expressions can be of type numeric or of type pair.

Complexity arises from the fact that we handle not only known quantities, but unknown ones, too. Unknown variables will be handled as terms in linear polynomials. Numeric expressions on the stack are always represented by linear polynomials, containing solved and unsolved variables.

The expression stack is connected to a system of linear equations (LEQ). If an equation is constructed from 2 polynomials, it is put into the LEQ. The LEQ operates on generic identifiers and knows nothing of the 'real life' symbols we use in the parser. The expression stack is a bridge between both worlds: It holds a table (VariableResolver) to map LEQ-internal variables to real-life symbols. The variable resolver will receive a message from the LEQ whenever an equation gets solved, i.e. variables become known.

Other types of expression are not considered native expressions for the stack, but it is nevertheless possible to put them on the stack. They are stored as interface{} and there are no supporting methods or arithmetic operations defined for them.

----------------------------------------------------------------------

BSD License

Copyright (c) 2017-20, 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 or 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

View Source 
const (
	Undefined int = iota
	IntegerType
	PairType
	PathType
	PenType
	ColorType
	StringType
)

Pre-defined symbol types, if you want to use them.

Variables

This section is empty.

Functions

func T 

func T() tracing.Trace

Configurable trace; tracing to the SyntaxTracer

Types

type Assignable 

type Assignable interface {
	GetValue() interface{}
	SetValue(interface{})
	IsKnown() bool
}

Some symbols are lvalues, i.e. can be assigned a value

type DynamicMemoryFrame 

type DynamicMemoryFrame struct {
	Name        string
	Scope       *Scope
	SymbolTable *SymbolTable
	Parent      *DynamicMemoryFrame
}

A memory frame, representing a piece of memory for a scope

func NewDynamicMemoryFrame 

func NewDynamicMemoryFrame(nm string, scope *Scope) *DynamicMemoryFrame

Create a new memory frame

func (*DynamicMemoryFrame) GetName 

func (mf *DynamicMemoryFrame) GetName() string

Return the name of the memory frame.

func (*DynamicMemoryFrame) GetScope 

func (mf *DynamicMemoryFrame) GetScope() *Scope

Return the corresponding scope for this frame.

func (*DynamicMemoryFrame) IsRoot 

func (mf *DynamicMemoryFrame) IsRoot() bool

Is this a root frame?

func (*DynamicMemoryFrame) String 

func (mf *DynamicMemoryFrame) String() string

Prettyfied Stringer.

func (*DynamicMemoryFrame) Symbols 

func (mf *DynamicMemoryFrame) Symbols() *SymbolTable

Access to the memory frame's symbol table.

type ExprNode 

type ExprNode struct {
	XPolyn arithm.Polynomial
	YPolyn arithm.Polynomial
	IsPair bool
	Other  interface{}
}

Expressions will contain linear polynomials, possibly with variables of unknown value. Expressions are either of type pair or type numeric. Numeric expressions are modelled as pair values, with the y-part set to 0.

Sometimes it is convenient to push a different type of expression onto the stack (or to complement a numeric expression with additional info), so expressions are allowed to point to 'other' data (GetOther()).

func NewNumericExpression 

func NewNumericExpression(p arithm.Polynomial) *ExprNode

Create a new expression node given a polynomial.

func NewNumericVarExpression 

func NewNumericVarExpression(v Symbol) *ExprNode

Create a non-constant numeric expression node.

func NewOtherExpression 

func NewOtherExpression(something interface{}) *ExprNode

Create an expression node with other information

func NewPairExpression 

func NewPairExpression(xp arithm.Polynomial, yp arithm.Polynomial) *ExprNode

Create a new pair expression node. Arguments are x-part and y-part for the pair. If no y-part is supplied, the type of the expression will still be type pair – although an invalid one.

func NewPairVarExpression 

func NewPairVarExpression(xpart Symbol, ypart Symbol) *ExprNode

Create a non-constant pair expression node. Arguments are x-part and y-part for the pair.

func (*ExprNode) GetConstNumeric 

func (e *ExprNode) GetConstNumeric() (dec.Decimal, bool)

func (*ExprNode) GetConstPair 

func (e *ExprNode) GetConstPair() (arithm.Pair, bool)

func (*ExprNode) IsValid 

func (e *ExprNode) IsValid() bool

Is this a valid numeric or pair expression, i.e. non-nil?

func (*ExprNode) String 

func (e *ExprNode) String() string

Stringer for expressions.

type ExprStack 

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

Type ExprStack. This implements a stack of numeric or pair expressions. Various mathematical operations may be performed on the stack values.

The expression stack is connected to a system of linear equations (LEQ). If an equation is constructed from 2 polynomials, it is put into the LEQ. The LEQ operates on generic identifiers and knows nothing of the 'real life' symbols we use in the parser. The expression stack is a bridge between both worlds: It holds a table (VariableResolver) to map LEQ-internal variables to real-life symbols. The variable resolver will receive a message from the LEQ whenever an equation gets solved, i.e. variables become known.

The connection between symbols and LEQ-variables is by symbol-ID: symbol "a" with ID=7 will be x.7 in LEQ.

func NewExprStack 

func NewExprStack() *ExprStack

Create a new expression stack. It is fully initialized and empty.

func (*ExprStack) AddTOS2OS 

func (es *ExprStack) AddTOS2OS() error

Add TOS and 2ndOS. Allowed for known and unknown terms.

func (*ExprStack) AnnounceVariable 

func (es *ExprStack) AnnounceVariable(v Symbol)

Give notice of a new variable used in expressions / polynomials. This will put the variable's symbol into the variable resolver's table.

Example: symbol "a"|ID=7 ⟹ resolver table[7] = "a"

If a variable ID is not known by the resolver, it is assumed to be a "capsule", which is MetaFont's notation for a variable that has fallen out of scope.

func (*ExprStack) CheckOperands 

func (es *ExprStack) CheckOperands(n int, op string) error

Check the operands on the stack for an arithmetic operation. Currently will panic if operands are invalid or not enough operands (n) on stack.

func (*ExprStack) DivideTOS2OS 

func (es *ExprStack) DivideTOS2OS() error

Divide 2ndOS by TOS. Divisor must be numeric non-0 constant.

func (*ExprStack) Dump 

func (es *ExprStack) Dump()

Internal helper: dump expression stack. This is printed to the trace with level=DEBUG.

func (*ExprStack) EncapsuleVariable 

func (es *ExprStack) EncapsuleVariable(id int)

Drop the name of a variable from the variable resolver. The variable itself is not dropped, but rather lives on as an anonymous quantity (i.e., a capsule) as long as it is part of an equation.

func (*ExprStack) EquateTOS2OS 

func (es *ExprStack) EquateTOS2OS() error

Create an equation of the polynomials of TOS and 2ndOS. Introduces the equation to the solver's linear equation system.

If the polynomials are of type pair polynomial, then there will be 2 equations, one for the x-part and one for the y-part. LEQ will only handle numeric linear equations.

func (*ExprStack) GetVariable 

func (es *ExprStack) GetVariable(e *ExprNode) Symbol

If an expression is a simple variable reference, return the symbol / variable reference. The variable must have been previously announced (see PushVariable(v)).

func (*ExprStack) GetVariableName 

func (es *ExprStack) GetVariableName(id int) string

Return the name of a variable, given its ID. Will return the string "?nnnn" for capsules.

Interface VariableResolver.

func (*ExprStack) Interpolate 

func (es *ExprStack) Interpolate() (err error)

Numeric interpolation operation. Either n must be known or a and b. Calulated as: 

n[a,b] ⟹ a - na + nb.

func (*ExprStack) InterpolatePair 

func (es *ExprStack) InterpolatePair(n *ExprNode, z1 *ExprNode, z2 *ExprNode) error

Pair interpolation operation. Either n must be known or z1 and z2. 

n[z1,z2] ⟹ z1 - n*z1 + n*z2.

func (*ExprStack) IsCapsule 

func (es *ExprStack) IsCapsule(id int) bool

Is a variable (index) a capsule, i.e., has it gone out of scope? The terminus stems from MetaFont (with "whatever" being a prominent example for a capsule).

Interface VariableResolver.

func (*ExprStack) IsEmpty 

func (es *ExprStack) IsEmpty() bool

Stack functionality.

func (*ExprStack) LengthTOS 

func (es *ExprStack) LengthTOS() error

Length of a pair (i.e., distance from origin). Argument must be a known pair.

func (*ExprStack) MultiplyTOS2OS 

func (es *ExprStack) MultiplyTOS2OS() error

Multiply TOS and 2ndOS. One multiplicant must be a known numeric constant.

func (*ExprStack) Pop 

func (es *ExprStack) Pop() (*ExprNode, bool)

Stack functionality.

func (*ExprStack) PopAsNumeric 

func (es *ExprStack) PopAsNumeric() (dec.Decimal, bool)

Convenience method: return TOS as a numeric constant.

func (*ExprStack) PopAsOther 

func (es *ExprStack) PopAsOther() (interface{}, bool)

Convenience method: return TOS as interface{}

func (*ExprStack) PopAsPair 

func (es *ExprStack) PopAsPair() (arithm.Pair, bool)

Convenience method: return TOS as a pair constant. If TOS is not a known pair, returns (0,0) and false.

func (*ExprStack) Push 

func (es *ExprStack) Push(e *ExprNode) *ExprStack

Stack functionality.

func (*ExprStack) PushConstant 

func (es *ExprStack) PushConstant(c dec.Decimal) *ExprStack

Push a numeric constant onto the stack. It will be wrapped into a polynomial p = c. For pair constants use PushPairConstant(c).

func (*ExprStack) PushOtherConstant 

func (es *ExprStack) PushOtherConstant(o interface{}) *ExprStack

Push a typeless constant onto the stack.

func (*ExprStack) PushPairConstant 

func (es *ExprStack) PushPairConstant(pc arithm.Pair) *ExprStack

Push a pair constant onto the stack. It will be wrapped into a polynomial p = c. For numeric constants use PushConstant(c).

func (*ExprStack) PushPairVariable 

func (es *ExprStack) PushPairVariable(XPart Symbol, xconst dec.Decimal, YPart Symbol,
	yconst dec.Decimal) *ExprStack

Push a pair variable onto the stack. The ID of the variable must be > 0 ! It will be wrapped into two polynomials p = 0 + 1 * xpart/ypart(v).

func (*ExprStack) PushVariable 

func (es *ExprStack) PushVariable(v Symbol, w Symbol) *ExprStack

Push a variable onto the stack. The ID of the variable must be > 0 ! It will be wrapped into a polynomial p = 0 + 1 * v. If the variable is of type pair we will push a pair expression.

func (*ExprStack) Rotate2OSbyTOS 

func (es *ExprStack) Rotate2OSbyTOS() error

Rotate a pair around origin for TOS degrees, counterclockwise. TOS must be a known numeric constant.

func (*ExprStack) SetVariableSolved 

func (es *ExprStack) SetVariableSolved(id int, val dec.Decimal)

Set the value of a variable. If the LEQ solves a variable and it becomes known, the LEQ will send us this message.

Interface VariableResolver.

func (*ExprStack) Size 

func (es *ExprStack) Size() int

Stack functionality.

func (*ExprStack) SubtractTOS2OS 

func (es *ExprStack) SubtractTOS2OS() error

Subtract TOS from 2ndOS. Allowed for known and unknown terms.

func (*ExprStack) Summary 

func (es *ExprStack) Summary()

Print a summary of LEQ and stack contents.

func (*ExprStack) Top 

func (es *ExprStack) Top() *ExprNode

Stack functionality. Will return an invalid expression if stack is empty.

func (*ExprStack) TraceString 

func (es *ExprStack) TraceString(e *ExprNode) string

Pretty print an expression.

type MemoryFrameStack 

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

A (call-)stack of memory frames

func (*MemoryFrameStack) Current 

func (mfst *MemoryFrameStack) Current() *DynamicMemoryFrame

Get the current memory frame of a stack (TOS).

func (*MemoryFrameStack) FindMemoryFrameWithScope 

func (mfst *MemoryFrameStack) FindMemoryFrameWithScope(scope *Scope) *DynamicMemoryFrame

Find the top-most memory frame pointing to scope.

func (*MemoryFrameStack) Globals 

func (mfst *MemoryFrameStack) Globals() *DynamicMemoryFrame

Get the outermost memory frame, containing global symbols.

func (*MemoryFrameStack) PopMemoryFrame 

func (mfst *MemoryFrameStack) PopMemoryFrame() *DynamicMemoryFrame

Pop a memory frame. Returns the popped frame.

func (*MemoryFrameStack) PushNewMemoryFrame 

func (mfst *MemoryFrameStack) PushNewMemoryFrame(nm string, scope *Scope) *DynamicMemoryFrame

Push a memory frame. A frame is constructed, having the recent TOS as its * parent. If the new frame is not the bottommost frame, it will copy the * symbol-creator from the parent frame. Otherwise callers will have to provide * a scope (if needed) in a separate step.

type Runtime 

type Runtime struct {
	ScopeTree     *ScopeTree        // collect scopes
	MemFrameStack *MemoryFrameStack // runtime stack of memory frames
	ExprStack     *ExprStack        // evaluate arithmetic expressions
}

A type implementing a runtime environment for an interpreter

func NewRuntimeEnvironment 

func NewRuntimeEnvironment(withDeclarations func(string) Symbol) *Runtime

Construct a new runtime environment, initialized. Accepts a symbol creator for * variable declarations to be used within this runtime environment.

type Scope 

type Scope struct {
	Name   string
	Parent *Scope
	// contains filtered or unexported fields
}

A named scope, which may contain symbol definitions. Scopes link back to a parent scope, forming a tree.

func NewScope 

func NewScope(nm string, parent *Scope, symcreator func(string) Symbol) *Scope

Create a new scope.

func (*Scope) DefineSymbol 

func (s *Scope) DefineSymbol(symname string) (Symbol, Symbol)

Define a symbol in the scope. Returns the new symbol and the previously * stored symbol under this key, if any.

func (*Scope) GetName 

func (s *Scope) GetName() string

Return the name of a scope.

func (*Scope) ResolveSymbol 

func (s *Scope) ResolveSymbol(symname string) (Symbol, *Scope)

Find a symbol. Returns the symbol (or nil) and a scope. The scope is * the scope (of a scope-tree-path) the symbol was found in.

func (*Scope) String 

func (s *Scope) String() string

Prettyfied Stringer.

func (*Scope) Symbols 

func (s *Scope) Symbols() *SymbolTable

Return the symbol table of a scope.

type ScopeTree 

type ScopeTree struct {
	ScopeBase *Scope
	ScopeTOS  *Scope
}

Scope tree. Can be treated as a stack during static analysis, thus * building a tree from scopes which are pushed an popped to/from the stack.

func (*ScopeTree) Current 

func (scst *ScopeTree) Current() *Scope

Get the current scope of a stack (TOS).

func (*ScopeTree) Globals 

func (scst *ScopeTree) Globals() *Scope

Get the outermost scope, containing global symbols.

func (*ScopeTree) PopScope 

func (scst *ScopeTree) PopScope() *Scope

Pop a scope.

func (*ScopeTree) PushNewScope 

func (scst *ScopeTree) PushNewScope(nm string, symcreator func(string) Symbol) *Scope

Push a scope. A scope is constructed, including a symbol table * for variable declarations.

type StdSymbol 

type StdSymbol struct {
	Name     string
	Id       int
	Symtype  int
	Sibling  TreeNode
	Children TreeNode
}

Our goto-symbol implements all of the interfaces above.

func (*StdSymbol) AppendChild 

func (s *StdSymbol) AppendChild(ch TreeNode) TreeNode

Complex symbols: add a sub-symbol.

func (*StdSymbol) GetFirstChild 

func (s *StdSymbol) GetFirstChild() TreeNode

Complex symbols: get the first sub-symbol.

func (*StdSymbol) GetID 

func (s *StdSymbol) GetID() int

Interface Symbol: get the ID of the symbol.

func (*StdSymbol) GetName 

func (s *StdSymbol) GetName() string

Interface Symbol: get the name of the symbol.

func (*StdSymbol) GetSibling 

func (s *StdSymbol) GetSibling() TreeNode

Complex symbols: get the next adjacent symbol.

func (*StdSymbol) GetType 

func (s *StdSymbol) GetType() int

Interface Typeable: get the symbols type.

func (*StdSymbol) SetFirstChild 

func (s *StdSymbol) SetFirstChild(ch TreeNode)

Complex symbols: set the first sub-symbol.

func (*StdSymbol) SetSibling 

func (s *StdSymbol) SetSibling(sibling TreeNode)

Complex symbols: set the next adjacent symbol.

func (*StdSymbol) SetType 

func (s *StdSymbol) SetType(tp int) int

Interface Typeable: set the symbols type.

func (*StdSymbol) String 

func (s *StdSymbol) String() string

A debug Stringer for symbols.

type Symbol 

type Symbol interface {
	GetName() string
	GetID() int
}

The most basic symbol needs a name to be referenced under.

func NewStdSymbol 

func NewStdSymbol(nm string) Symbol

Create a new standard symbol, with a new ID.

type SymbolTable 

type SymbolTable struct {
	Table map[string]Symbol
	// contains filtered or unexported fields
}

Symbol tables to store symbols (map-like semantics).

func NewSymbolTable 

func NewSymbolTable(symcreator func(string) Symbol) *SymbolTable

Create an empty symbol table. Clients may pass a function to create new * symbols, thus enabling the symbol table to create missing symbols on the * fly. If none is given and the demand for a new symbol arises, a StdSymbol * is created.

func (*SymbolTable) DefineSymbol 

func (t *SymbolTable) DefineSymbol(symname string) (Symbol, Symbol)

Create a new symbol to store into the symbol table. The symbol's name may not be empty Overwrites existing symbol with this name, if any. Returns the new symbol and the previously stored symbol (or nil).

func (*SymbolTable) Each 

func (t *SymbolTable) Each(mapper func(string, Symbol))

Iterate over each symbol in the table, executing a mapper function.

func (*SymbolTable) GetSymbolCreator 

func (t *SymbolTable) GetSymbolCreator() func(string) Symbol

Retrieve the symbol creation function.

func (*SymbolTable) InsertSymbol 

func (t *SymbolTable) InsertSymbol(sym Symbol) Symbol

Insert a pre-created symbol.

func (*SymbolTable) ResolveOrDefineSymbol 

func (t *SymbolTable) ResolveOrDefineSymbol(symname string) (Symbol, bool)

Find a symbol in the table, insert a new one if not found. * The symcreator function is used for creating non-existent symbols on * the fly. Returns the symbol and a flag, signalling wether the symbol * already has been present.

func (*SymbolTable) ResolveSymbol 

func (t *SymbolTable) ResolveSymbol(symname string) Symbol

Check for a symbol in the symbol table. * Returns a symbol or nil.

func (*SymbolTable) Size 

func (t *SymbolTable) Size() int

Count the symbols in a symbol table.

type TreeNode 

type TreeNode interface {
	GetSibling() TreeNode
	SetSibling(TreeNode)
	GetFirstChild() TreeNode
	SetFirstChild(TreeNode)
}

Some symbols are non-atomic.

type Typable 

type Typable interface {
	Typed
	SetType(int) int
}

Some symbols may be typable.

type Typed 

type Typed interface {
	GetType() int
}

Some symbols may be typed.

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.