bertini::node::Node Class Reference

An interface for all nodes in a function tree, and for a function object as well. More...

#include <node.hpp>

Inheritance diagram for bertini::node::Node:

Collaboration diagram for bertini::node::Node:

Public Types
typedef RetT	VisitReturnType
	The type returned when a visitor accepts this object.

Public Member Functions
virtual	~Node ()=default
virtual std::shared_ptr< Node >	Simplified () const
	Functionally simplify this tree, returning a NEW simplified tree.
virtual std::shared_ptr< Node >	Subs (SubstitutionMap const &substitutions) const
	Symbolically substitute variables, returning a NEW tree.
virtual void	print (std::ostream &target) const =0
	Virtual method for printing Nodes to arbitrary output streams.
virtual unsigned	Precedence () const
	The printing precedence of this node, deciding parenthesization.
virtual bool	IsLiteralZero () const
	Is this node the literal constant 0?
virtual bool	IsLiteralOne () const
	Is this node the literal constant 1?
std::size_t	Hash () const
	Memoized structural hash of this node.
std::shared_ptr< const void >	EvalProgram () const
	Opaque, lazily-populated cache of a compiled evaluator for this expression.
void	SetEvalProgram (std::shared_ptr< const void > p) const
	Stash a compiled evaluator for this expression (type-erased; see EvalProgram()).
virtual bool	IsSame (Node const &other) const
	Order-sensitive structural equality, shallow given interned children.
virtual std::shared_ptr< Node >	Differentiate (std::shared_ptr< Variable > const &v=nullptr) const =0
	Compute the derivative with respect to a single variable.
std::shared_ptr< Node >	Differentiate (std::shared_ptr< Variable > const &v, unsigned count) const
	Differentiate repeatedly with respect to a single variable.
std::shared_ptr< Node >	Differentiate (VariableGroup const &vars) const
	Differentiate with respect to each variable in a group, in sequence.
virtual int	Degree (std::shared_ptr< Variable > const &v=nullptr) const =0
	Compute the degree, optionally with respect to a single variable.
std::vector< int >	MultiDegree (VariableGroup const &vars) const
	Compute the multidegree with respect to a variable group.
virtual std::vector< int >	MultiDegreeImpl (VariableGroup const &vars) const =0
	Per-node-type multidegree.
virtual int	Degree (VariableGroup const &vars) const =0
	Compute the overall degree with respect to a variable group.
virtual std::shared_ptr< Node >	Homogenized (VariableGroup const &vars, std::shared_ptr< Variable > const &homvar) const
	Homogenize a tree, returning a NEW homogenized tree (functional / non-mutating).
virtual bool	IsHomogeneous (std::shared_ptr< Variable > const &v=nullptr) const =0
	Check for homogeneity, absolutely with respect to all variables, including path variables and all other variable types, or with respect to a single varaible, if passed.
virtual bool	IsHomogeneous (VariableGroup const &vars) const =0
	Check for homogeneity, with respect to a variable group.
bool	IsPolynomial (std::shared_ptr< Variable > const &v=nullptr) const
	Check if a Node is polynomial – it has degree at least 0.
bool	IsPolynomial (VariableGroup const &v) const
	Check if a Node is polynomial – it has degree at least 0.
virtual VisitReturnType	Accept (VisitorBase &)=0
	Accept a visitor (dispatch to the visitor's Visit for this concrete type).

Protected Member Functions
virtual std::size_t	HashImpl () const
	Compute this node's structural hash.
	Node ()

Static Protected Member Functions
static void	HashCombine (std::size_t &seed, std::size_t value)
	Combine an extra value into a running hash (boost::hash_combine recipe).
template<typename T>
static VisitReturnType	AcceptBase (T &visited, VisitorBase &guest)
	Abstract method for how to accept a visitor.

Protected Attributes
std::optional< std::size_t >	structural_hash_
	Memoized structural hash (computed on first Hash() call; nodes are immutable so it never needs invalidating).
std::shared_ptr< const void >	eval_program_
	Opaque compiled-evaluator cache (a system-layer StraightLineProgram for [this]); see EvalProgram().

Friends
class	boost::serialization::access
std::ostream &	operator<< (std::ostream &out, const Node &N)
	a single layer of indirection, though which to call the overridden virtual print() method which must be defined for each non-abstract Node type.

Detailed Description

An interface for all nodes in a function tree, and for a function object as well.

Almost all methods that will be called on a node must be declared in this class. The main evaluation method is defined in this class.

Bertini function trees are created using std::shared_ptr's to Node base class, generally.

Abstract base class for the Bertini hybrid-precision (double-multiple) expression tree.

Member Typedef Documentation

VisitReturnType

template<typename RetT = void, template< class, class > class CatchAll = policy::DefaultCatchAll>

typedef RetT bertini::VisitableBase< RetT, CatchAll >::VisitReturnType

inherited

The type returned when a visitor accepts this object.

Constructor & Destructor Documentation

~Node()

virtual bertini::node::Node::~Node ( )

virtualdefault

Node()

bertini::node::Node::Node ( )

protected

Member Function Documentation

Accept()

template<typename RetT = void, template< class, class > class CatchAll = policy::DefaultCatchAll>

virtual VisitReturnType bertini::VisitableBase< RetT, CatchAll >::Accept ( VisitorBase & )

pure virtualinherited

Accept a visitor (dispatch to the visitor's Visit for this concrete type).

AcceptBase()

template<typename RetT = void, template< class, class > class CatchAll = policy::DefaultCatchAll>

template<typename T>

VisitReturnType bertini::VisitableBase< RetT, CatchAll >::AcceptBase ( T & visited, VisitorBase & guest )

inlinestaticprotectedinherited

Abstract method for how to accept a visitor.

This function simply Forwards to the Visit method of the visitor, if the visitor's type is known. If known, invokes the behaviour defined by the CatchAll template parameter.

Template Parameters

T	The type of the visited object. Should be inferred by the compiler.

Parameters

visited	The visited visitable object.
guest	The visiting object.

Degree() [1/2]

virtual int bertini::node::Node::Degree ( std::shared_ptr< Variable > const & v = nullptr ) const

pure virtual

Compute the degree, optionally with respect to a single variable.

Parameters

v	Shared pointer to variable with respect to which you want to compute the degree of the Node.

Returns

The degree. Will be negative if the Node is non-polynomial.

Implemented in bertini::node::Differential, bertini::node::IntegerPowerOperator, bertini::node::MultOperator, bertini::node::NamedExpression, bertini::node::NegateOperator, bertini::node::Number, bertini::node::PowerOperator, bertini::node::SumOperator, bertini::node::UnaryOperator, and bertini::node::Variable.

Degree() [2/2]

virtual int bertini::node::Node::Degree ( VariableGroup const & vars ) const

pure virtual

Compute the overall degree with respect to a variable group.

Parameters

vars	A group of variables.

Returns

The degree. Will be negative if the Node is non-polynomial.

Implemented in bertini::node::Differential, bertini::node::IntegerPowerOperator, bertini::node::MultOperator, bertini::node::NamedExpression, bertini::node::NegateOperator, bertini::node::Number, bertini::node::PowerOperator, bertini::node::SumOperator, bertini::node::UnaryOperator, and bertini::node::Variable.

Differentiate() [1/3]

std::shared_ptr< Node > bertini::node::Node::Differentiate	(	std::shared_ptr< Variable > const &	v,
		unsigned	count ) const

Differentiate repeatedly with respect to a single variable.

Applies the single-variable derivative count times, e.g. Differentiate(x, 2) is the second partial derivative with respect to x. A count of zero returns the node itself.

Parameters

v	The variable to differentiate with respect to.
count	How many times to differentiate.

Returns

The count-th partial derivative with respect to v (a regular Node).

Differentiate() [2/3]

virtual std::shared_ptr< Node > bertini::node::Node::Differentiate ( std::shared_ptr< Variable > const & v = nullptr ) const

pure virtual

Compute the derivative with respect to a single variable.

Virtual method for differentiating the node. If no variable is passed, produces a Jacobian tree when all is said and done, which is used for evaluating the Jacobian.

Returns

The result of differentiation. Jacobian or regular Node depending on what you passed in.

Implemented in bertini::node::ArcCosOperator, bertini::node::ArcSinOperator, bertini::node::ArcTanOperator, bertini::node::CosOperator, bertini::node::Differential, bertini::node::ExpOperator, bertini::node::IntegerPowerOperator, bertini::node::LogOperator, bertini::node::MultOperator, bertini::node::NamedExpression, bertini::node::NegateOperator, bertini::node::Number, bertini::node::PowerOperator, bertini::node::SinOperator, bertini::node::SqrtOperator, bertini::node::SumOperator, bertini::node::TanOperator, and bertini::node::Variable.

Differentiate() [3/3]

std::shared_ptr< Node > bertini::node::Node::Differentiate

(

VariableGroup const &

vars

)

const

Differentiate with respect to each variable in a group, in sequence.

Applies the single-variable derivative once for each variable in vars, in order, e.g. Differentiate({x, x, y}) is ∂³/∂y∂x². Repeated entries are allowed. An empty group returns the node itself. (For polynomials mixed partials commute, so the order is immaterial.)

Parameters

vars	The variables to differentiate with respect to, in application order.

Returns

The mixed partial derivative (a regular Node).

EvalProgram()

std::shared_ptr< const void > bertini::node::Node::EvalProgram ( ) const

inline

Opaque, lazily-populated cache of a compiled evaluator for this expression.

The system layer (EvalExpression / f.eval) compiles a StraightLineProgram for ([this], canonical-by-name variable order) on first use and stashes it here, so repeated evaluations of the same (hash-consed, immutable) expression reuse it — like the memoized Hash(). The type is erased because the SLP lives in the system layer, above function_tree; the compiled program holds no node pointers (its constants are value recipes, ADR-0027), so there is no reference cycle. Transient: not serialized; a clone recompiles on demand.

Hash()

std::size_t bertini::node::Node::Hash

(

)

const

Memoized structural hash of this node.

Order-sensitive: equal structures hash equal, where children are folded in by their own Hash() and operand order / signs / exponents participate. The default (leaves and any node not overriding HashImpl) is node identity (the object's address), so distinct objects hash distinctly; value nodes (Integer/Rational/Complex) and operators override to be structural. Memoized – valid because nodes are immutable post-construction – and deliberately independent of the mutable working precision (stable across precision()).

This is the predicate layer for the hash-consing intern table; nothing wires it into construction yet.

HashCombine()

void bertini::node::Node::HashCombine ( std::size_t & seed, std::size_t value )

inlinestaticprotected

Combine an extra value into a running hash (boost::hash_combine recipe).

HashImpl()

virtual std::size_t bertini::node::Node::HashImpl ( ) const

protectedvirtual

Compute this node's structural hash.

Default: identity (the object address), so distinct nodes hash distinctly. Value/operator nodes override to be structural.

Reimplemented in bertini::node::Complex, bertini::node::Integer, bertini::node::IntegerPowerOperator, bertini::node::MultOperator, bertini::node::NamedExpression, bertini::node::PowerOperator, bertini::node::Rational, bertini::node::special_number::E, bertini::node::special_number::Pi, bertini::node::SumOperator, bertini::node::UnaryOperator, and bertini::node::Variable.

Homogenized()

virtual std::shared_ptr< Node > bertini::node::Node::Homogenized ( VariableGroup const & vars, std::shared_ptr< Variable > const & homvar ) const

virtual

Homogenize a tree, returning a NEW homogenized tree (functional / non-mutating).

Input a variable group holding the non-homogeneous variables, and the new homogenizing variable. The homvar may be an element of the variable group, that's perfectly ok.

The input tree is never modified; degree-deficient summands are padded with powers of homvar in a freshly-built tree (so a throw on a non-polynomial term can't leave a half-homogenized tree behind). The default (leaves, and anything with nothing to homogenize) returns the node unchanged.

Parameters

homvar	The homogenizing variable, which is multiplied against terms with degree deficiency with repect to other terms.
vars	A group of variables, with respect to which you wish to homogenize.

Returns

A homogenized tree (possibly the same node, if nothing changed).

Reimplemented in bertini::node::ArcCosOperator, bertini::node::ArcSinOperator, bertini::node::ArcTanOperator, bertini::node::CosOperator, bertini::node::ExpOperator, bertini::node::IntegerPowerOperator, bertini::node::LogOperator, bertini::node::MultOperator, bertini::node::NamedExpression, bertini::node::NegateOperator, bertini::node::PowerOperator, bertini::node::SinOperator, bertini::node::SqrtOperator, bertini::node::SumOperator, and bertini::node::TanOperator.

IsHomogeneous() [1/2]

virtual bool bertini::node::Node::IsHomogeneous ( std::shared_ptr< Variable > const & v = nullptr ) const

pure virtual

Check for homogeneity, absolutely with respect to all variables, including path variables and all other variable types, or with respect to a single varaible, if passed.

Returns

True if it is homogeneous, false if not.

Implemented in bertini::node::Differential, bertini::node::IntegerPowerOperator, bertini::node::MultOperator, bertini::node::NamedExpression, bertini::node::NegateOperator, bertini::node::Number, bertini::node::PowerOperator, bertini::node::SumOperator, bertini::node::UnaryOperator, and bertini::node::Variable.

IsHomogeneous() [2/2]

virtual bool bertini::node::Node::IsHomogeneous ( VariableGroup const & vars ) const

pure virtual

Check for homogeneity, with respect to a variable group.

Returns

True if it is homogeneous, false if not.

Implemented in bertini::node::Differential, bertini::node::IntegerPowerOperator, bertini::node::MultOperator, bertini::node::NamedExpression, bertini::node::NegateOperator, bertini::node::Number, bertini::node::PowerOperator, bertini::node::SumOperator, bertini::node::UnaryOperator, and bertini::node::Variable.

IsLiteralOne()

virtual bool bertini::node::Node::IsLiteralOne ( ) const

inlinevirtual

Is this node the literal constant 1?

See also

IsLiteralZero

Reimplemented in bertini::node::Complex, bertini::node::Integer, and bertini::node::Rational.

IsLiteralZero()

virtual bool bertini::node::Node::IsLiteralZero ( ) const

inlinevirtual

Is this node the literal constant 0?

Exact check on stored literal values (Integer/Complex/Rational override); false for everything else, including non-literal expressions that happen to evaluate to zero. Used by differentiation to build already-simplified trees without evaluating anything.

Reimplemented in bertini::node::Complex, bertini::node::Integer, and bertini::node::Rational.

IsPolynomial() [1/2]

bool bertini::node::Node::IsPolynomial

(

std::shared_ptr< Variable > const &

v = nullptr

)

const

Check if a Node is polynomial – it has degree at least 0.

Negative degrees indicate non-polynomial.

Returns

True if it is polynomial, false if not.

IsPolynomial() [2/2]

bool bertini::node::Node::IsPolynomial

(

VariableGroup const &

v

)

const

Check if a Node is polynomial – it has degree at least 0.

Negative degrees indicate non-polynomial.

Returns

True if it is polynomial, false if not.

IsSame()

virtual bool bertini::node::Node::IsSame ( Node const & other ) const

virtual

Order-sensitive structural equality, shallow given interned children.

Two nodes are the same iff they have the same dynamic type, the same operator payload (signs / mult-or-div flags / integer exponent / literal value), and the same operands by pointer** (operands are not recursed – in the hash-consed world children are already canonical, so pointer-equality is structural equality). The default is node identity; value/operator nodes override. Consistent with Hash(): IsSame(a,b) implies a.Hash()==b.Hash().

Reimplemented in bertini::node::Complex, bertini::node::Integer, bertini::node::IntegerPowerOperator, bertini::node::MultOperator, bertini::node::NamedExpression, bertini::node::PowerOperator, bertini::node::Rational, bertini::node::special_number::E, bertini::node::special_number::Pi, bertini::node::SumOperator, bertini::node::UnaryOperator, and bertini::node::Variable.

MultiDegree()

std::vector< int > bertini::node::Node::MultiDegree

(

VariableGroup const &

vars

)

const

Compute the multidegree with respect to a variable group.

This is for homogenization, and testing for homogeneity.

Returns

A vector containing the degrees. Negative entries indicate non-polynomiality. Compute the multidegree with respect to a variable group.

DAG-AWARE: this is a non-virtual wrapper that memoizes by node identity FOR THE DURATION OF ONE TOP-LEVEL CALL, so a shared subtree is visited once however many times it is reached. The per-type work lives in MultiDegreeImpl.

Why it exists (b2#417): the node graph is hash-consed, so a small DAG can stand for an enormous expansion – measured, a 46-node expression whose printed form is 196 KB. A plain recursive walk visits the TREE, so it costs O(expansion) where the structure is O(DAG). CanonicalizeNaryOperands calls this for every operand of every n-ary construction, which is how a 46-node expression came to cost 13 ms to multiply by a variable, and how a cofactor expansion inside a deflation stage came to run for hours with a DAG that never exceeded 1102 nodes.

Caching the RESULT between calls does not fix this and was measured 29% SLOWER – filling such a cache costs the same walk it is trying to avoid, so it only pays from a node's second mention. The memo has to be inside the traversal, which is what this is.

MultiDegreeImpl()

virtual std::vector< int > bertini::node::Node::MultiDegreeImpl ( VariableGroup const & vars ) const

pure virtual

Per-node-type multidegree.

Recurses through MultiDegree(), so children are memoized; never call this directly unless you want the unmemoized walk.

Implemented in bertini::node::Differential, bertini::node::MultOperator, bertini::node::NamedExpression, bertini::node::Number, bertini::node::PowerOperator, bertini::node::SumOperator, bertini::node::UnaryOperator, and bertini::node::Variable.

Precedence()

virtual unsigned bertini::node::Node::Precedence ( ) const

inlinevirtual

The printing precedence of this node, deciding parenthesization.

Defaults to PrecAtom: leaves and self-delimiting nodes are never wrapped. Operator nodes override this; printing parents wrap a child only when its precedence is too low for the position it occupies.

Reimplemented in bertini::node::Complex, bertini::node::Integer, bertini::node::IntegerPowerOperator, bertini::node::MultOperator, bertini::node::NegateOperator, bertini::node::PowerOperator, bertini::node::Rational, and bertini::node::SumOperator.

print()

virtual void bertini::node::Node::print ( std::ostream & target ) const

pure virtual

Virtual method for printing Nodes to arbitrary output streams.

Implemented in bertini::node::ArcCosOperator, bertini::node::ArcSinOperator, bertini::node::ArcTanOperator, bertini::node::Complex, bertini::node::CosOperator, bertini::node::Differential, bertini::node::ExpOperator, bertini::node::Integer, bertini::node::IntegerPowerOperator, bertini::node::LogOperator, bertini::node::MultOperator, bertini::node::NamedExpression, bertini::node::NamedSymbol, bertini::node::NegateOperator, bertini::node::PowerOperator, bertini::node::Rational, bertini::node::SinOperator, bertini::node::special_number::E, bertini::node::special_number::Pi, bertini::node::SqrtOperator, bertini::node::SumOperator, and bertini::node::TanOperator.

SetEvalProgram()

void bertini::node::Node::SetEvalProgram ( std::shared_ptr< const void > p ) const

inline

Stash a compiled evaluator for this expression (type-erased; see EvalProgram()).

Simplified()

virtual std::shared_ptr< Node > bertini::node::Node::Simplified ( ) const

virtual

Functionally simplify this tree, returning a NEW simplified tree.

Non-mutating successor to the in-place EliminateZeros / EliminateOnes / ReduceDepth machinery (ADR-0011, issue 251). The input tree is never modified; a fresh simplified tree is returned, built through the SimplifiedSum / SimplifiedMult / SimplifiedNegate factories so that literal zeros/ones vanish and exact constants fold. The default (leaves, and any node with nothing to simplify) returns the node unchanged – structural sharing preserved.

Returns

A simplified tree (possibly the same node, if nothing simplified).

Reimplemented in bertini::node::ArcCosOperator, bertini::node::ArcSinOperator, bertini::node::ArcTanOperator, bertini::node::CosOperator, bertini::node::ExpOperator, bertini::node::IntegerPowerOperator, bertini::node::LogOperator, bertini::node::MultOperator, bertini::node::NegateOperator, bertini::node::PowerOperator, bertini::node::SinOperator, bertini::node::SqrtOperator, bertini::node::SumOperator, and bertini::node::TanOperator.

Subs()

virtual std::shared_ptr< Node > bertini::node::Node::Subs ( SubstitutionMap const & substitutions ) const

virtual

Symbolically substitute variables, returning a NEW tree.

Replaces each Variable leaf named in substitutions with its associated node, functionally (the input tree is never modified). Substitution is simultaneous and single-pass: a leaf is replaced at most once and the replacement is not itself descended into, so {x:y, y:z} maps x+y to y+z (no cascade) and the order of the map is irrelevant. A variable absent from the map is left unchanged. The result is rebuilt through the simplifying factories (like differentiation), so constants fold. The default (leaves with nothing to replace) returns the node unchanged – structural sharing preserved.

Only Variable leaves are matched (variable -> node substitution); substituting into a Jacobian tree containing Differentials is not supported.

Parameters

substitutions

A map from variable name to the node to put in that variable's place.

Returns

The substituted tree (possibly the same node, if nothing matched).

Reimplemented in bertini::node::ArcCosOperator, bertini::node::ArcSinOperator, bertini::node::ArcTanOperator, bertini::node::CosOperator, bertini::node::ExpOperator, bertini::node::IntegerPowerOperator, bertini::node::LogOperator, bertini::node::MultOperator, bertini::node::NamedExpression, bertini::node::NegateOperator, bertini::node::PowerOperator, bertini::node::SinOperator, bertini::node::SqrtOperator, bertini::node::SumOperator, bertini::node::TanOperator, and bertini::node::Variable.

Friends And Related Symbol Documentation

boost::serialization::access

friend class boost::serialization::access

friend

operator<<

std::ostream & operator<< ( std::ostream & out, const Node & N )

friend

a single layer of indirection, though which to call the overridden virtual print() method which must be defined for each non-abstract Node type.

Member Data Documentation

eval_program_

std::shared_ptr<const void> bertini::node::Node::eval_program_

mutableprotected

Opaque compiled-evaluator cache (a system-layer StraightLineProgram for [this]); see EvalProgram().

Lazily populated by EvalExpression; transient, not serialized.

structural_hash_

std::optional<std::size_t> bertini::node::Node::structural_hash_

mutableprotected

Memoized structural hash (computed on first Hash() call; nodes are immutable so it never needs invalidating).

Not serialized – a clone recomputes it on demand.