Documentation for
Parse Tree Routines

Contents

Parameter Setting(Top)

void Variables(int n);

This routine sets the number of real variable used by the system. The default setting is 1, the number of variables may be from 1 to 255 and the variables use one base counting when referenced elsewhere.
(up)

void CRange(double lo,double hi);

This routine sets the maximum and minimum value of ephemeral real constants that appear in the parse trees. The default value is -1 to 1.
(up)

void OpOn(int opcode);

This routine enables an OpCode, in other words it adds a binary or unary operation to the collection available for use in parse trees. By default all operations start enabled. The opcodes for operations are as follows.
OpCodeOperation
256negation
257sin
258cos
259atan
260exp
261log
262sqr
263scale
512plus
513minus
514times
515divide
(up)

void OpOff(int opcode);

This routine disables an OpCode, in other words it removes a binary or unary operation from use by the parse tree system. The intervention to remove the opcode happens only when parse trees are generated, this does not remove the operation from existing parse trees. The default is for all operations to be enabled. The opcodes for operations are given in the description of OpOn.
(up)

void PEC(int P);

The leaves of a parse tree are either variables or ephemeral constants. This routine takes an integer argument in the range 0-100 that sets the fraction of ephemeral constants in randomly generated pare tree leaves to 1% to 100%.
(up)

Input/Output(Top)

At present the only available I/O routine is an output routine overloading the C++ stream insertion operation. Thus: 
   cout << tree << endl;
will output one of these trees.
(up)

Parse tree management(Top)

node *randtree(int n);

This routine generates a random parse tree with n nodes (leaves and operations). The return type is a pointer to a node data structure which holds the root node of the tree.
(up)

void killtree(node *t);

This routine deallocates all the storage used by a tree, recursively traversing the tree and deleting all its nodes. Called on a nil pointer this routine will do nothing. Called on a pointer that has already been deallocated this routine will produce a spectacular segmentation fault.
(up)

node *copytree(node *t);

This routine does everything required, including dynamic allocation, to make a copy of a parse tree. The return type is a pointer to a node data structure holding the root node of the copy. The tree copied is not modified in any way.
(up)

node *subtree(node *t,int &n);

This routine returns a pointer to the nth node in the tree. The counting scheme is to count the current node, the left descendants (if any) and then the right descendants (if any) recursively, using zero base counting. This routine is mostly used by other routines. If there are fewer than n nodes in the tree this routine returns a nil pointer. The size of the tree can be computed with the sizetree(node *t) routine.
(up)

node *randsubtree(node *t);

This routine returns a pointer to a node selected uniformly at random from the parse tree.
(up)

node *D(node *t,int q);

This routine returns a pointer to the root node of a parse tree holding the the partial differential with respect to the qth variable of the parse tree pointer to be t. Failing to dispose of dynamically allocated derivatives is a super way to use up the system's heap.
(up)

node *randcleaf(node *t);

This routine returns a pointer to a node containing an ephemeral constant, selected uniformly at random from those in the tree. If none are available this routine returns a null pointer. Such nodes include both ephemeral constant leaves and the unary scale operation that scale their argument by an ephemeral constant.
(up)

Parse tree characterization(Top)

int sizetree(node*t);

This routine returns the number of nodes in a tree.
(up)

int constP(node *t,int q);

This routine scans a tree for the presence of the qth variable. If it is present, then the routine returns zero, otherwise it returns one. This routine is a predicate for being constant with respect to a particular variable.
(up)

Genetic operations(Top)

void stmutate(node *t);

This routine picks a node of the tree t uniformly at random and replaces the sub-tree rooted at that point with a new random subtree with the same number of nodes. This is a type of sub-tree mutation.
(up)

void ndmutate(node *t);

This routine picks a node in the tree t uniformly at random and changes its type without changing its arity. Ephemeral constants have their value changed to a new random value. Variables are replaced with new variables selected uniformly at random. Unary and binary operations are similarly replaced. If only one object is available, e.g. one variable, this routine will make a change that makes no difference.
(up)

void cnmutate(node *t,double sd);

This routine picks a node with an ephemeral constant (if there are any, otherwise it does nothing) within t and adds a normally distributed random variable to it with mean zero and standard deviation sd. Both ephemeral constant leaves and the ephemeral constants in scale operations are affected by this mutation.
(up)

void cross(node *t,node *s);

This routine selects a node, uniformly at random, in each of its arguments and then exchanges the sub-trees rooted at those nodes. This is the classical sub-tree crossover operation.
(up)

void chop(node *t,int k);

This routine examines the tree t. As long as t has more than k nodes, t is replaced with one of the arguments of its root node. If the parameter k has a value less than 2 it is treated as if its value was 2. This routine is used to control the size of parse trees, which can grow quite rapidly if sub-tree crossover is used.
(up)

Evaluation(Top)

double eval(node *t,double *x);

This routine takes as arguments a parse tree t and a vector (array) x with as many entries as the number of variables currently being used. It returns the value of the formula represented by t on the values stored in x/
(up)