TNT macros: Variables (2)

Versión en español

In a previous entry I wrote about variable declaration under TNT macro language, in this post I show the most important aspect of variables: their access.

Variables can be accessed in two ways, for reading, in which the value stored on the variable is retrieved. The second access way is for writing, in which a value is assigned to a variable.

General variables

In TNT general variables (variables declared with var keyword) are accessed by its name inside single quotations (').

quote The number stored on variable is 'value' ;
hold 'number' ;

In this example, the number stored on value is printed and the number stored in number is used as the maximum tree hold. This is an important feature of the language: you can replace any command parameter by the value of variables. This gives an extraordinary flexibility to TNT's macros.

Sometimes, specially at linux version, it is necessary to use parenthesis to read successfully the variable:

hold ('numero') ;

To access arrays, the same format is used, with an index inside squared brackets ([]).

quote the value of the fourth element is  'vector [4]' ;

It can be a more complex (and useful) way for this example

quote the value of the 'i' element is 'vector ['i']' ;

Note that the variable i is also inside quotations. If you are somewhat familiar with some computer programming language, you note that quotations are a way to "dereference" of a variable.

This is an example for a multidimensional array

quote the value of the element 'i' , 'j' is 'mat ['i' , 'j']' ;

Using parenthesis (()) you can use math operations as index values. Here is an example with a two dimensional array, but that is exactly equal with any kind of array:

quote the value of the element 4, 'j' is 'mat [ (2 + 2 ) , 'j' ]' ;

Another option is the use of series

quote the value of the elements 3 to 8 is 'list [ 3 - 8 ]' ;

In this case, note that there are no parenthesis limiting the scope! If you put parenthesis, TNT interpret it as a mathematical operation.

To write values on general variables, the keword set is used with the name of the variable to assing, without quotations, and followed with the assigned value

set val 4 ;           /* Assigns 4 to val */
set res (3 + 4) ;     /* Assigns a math operation */
set num 'val' ;       /* Assigns the content of val to num */

Note that as is the value of the variable that is assigned to num, then val must be inside quotations. To assign arrays, it is possible to use the same format, just using one element at time.

set vec [4] 5 ;                 /* Assigns 5 to the 4th element of the array*/
set arreglo [ (2 + 3) ] 8 ;     /* Assigns 8 to the 5th element of the array */
set arreglo ['i'] 10 ;          /* Assigns 10 to the i-element of the array */
set arreglo [ ('j' + 'k') ] 7 ; /* Assigns 7 to the element j + k of the array */

Note that indexes must be dereferenced!

Many times, an operation to a variable is just a modification of its value, for example increase its value by one

set val 'val' + 1 ;

It is more clear and intuitive, modifying directly the variable without dereference it, this can be done using a C-like sintaxys

set val ++ ;              /* increase by 1 */
set arr [3] -- ;          /* decrease the content of element 3 in 1 */
set mat [2, 4] += 'val' ; /* adds the value of val to the element 2, 4 of mat */
set num *= (3 + 'j') ;    /* multiplies the content of num by (3 plus j)-times */
set arr [2] /= 3 ;        /* divides the content of element 2 of arr by  3 */
set val -= 4 ;            /* decreases the content of val in 4 */

In some cases, you want to store all array elements at the same time. This can be done with the keyword setarray. It is important that array dimensions coincide with the dimensions used in the declaration. The format of setarray is the name of the array followed by the name of the array an the elements.

var:
lista [5, 4]
;
setarray 5, 4 lista 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 2 2 2 2 ;

In this example, the following matrix is assigned to a 5x4 array

0 1 1 1
1 0 1 1
1 1 1 0
2 2 2 2

The order of the elements follows the dimensions from left to right, then the first four elements assigned to the array are the array elements [0, 0], [0, 1], [0, 2] and [0, 3].

Variables in loops

Usually, loop variables are control variables, so the best option is not modifying them. So in principle, write the code as if loop variables are read-only. If a loop variable needs to be modified TNT can do it, but that usually shows a design problem, and it is not a good practice to make that modifications.

Loop variables can be accessed using using names or number. Is a good practice to use names to identify loop variables.

To read a loop variable the number or name of the cicle must be preceded by number character (#). For example to save a simple search of several k values using implied weights [1]

loop =kval 1 10
keep 0 ;
piwe = #kval ;
mult ;
tsave* resu#kval.tre ; save; tsave /;
stop

As #kval is the name of the first cicle, then is possible to use #1, then to save the tree it would be

tsave* resu#1..tre ;

Note the double point after #1, that is because a point is interpreted by TNT as a decimal fraction, and assumes that the point is part of the name. In any case, it is better to use names ;). The numbering of loops is assigned in relation with its nestedness, starting with #1.

To modify a loop variable the keyword setloop is used, that change the most nested loop (i.e. the loop in which the instruction is used). As changing the value of loops distorts their sequence, you must be aware of infinite-loops. This is the reason that makes the change of loop variables unsafe and unrecommended. But, some times it is necessary a non-stop loop that finish only when a specified condition is meet. In that case, using endloop coupled with setloop can be very useful

var:
i
;

set i 0 ;
loop =non 0 1
/* several instructions */
if ('i' == 1)
  endloop ;
else
  setloop 0 ;
end ;
stop

It is assumed that somewhere inside the loop, the value of i is changed to 1.

Command line variables

Variables from command line are read-only. Then, we only can access their value. To access a command line variable it is used the percent sign (%).

set j %1 ;

Assigns j to the first parameter from the command line (by the way, %0 is the name of the macro). Trying to read more parameters than parameters actually provided, is an error and stops the execution. When you write a macro, keep in mind that command line parameters is the only way to communicate with the user, so it is necessary to do a good choice of reading order and default values.

As always, do not forgive to keep your TNT copy updated. And check the TNT wiki or join the TNT google group to deal with any question!

References

[1] Goloboff, P.A. 1993. Estimating character weights during tree search. Cladistics 9: 83-91. DOI: 10.1111/j.1096-0031.1993.tb00209.x

Previous post on TNT's macros

Intro

Variables (1)

TNT macros: variables (1)

Versión en español

I forget an important feature. The commentaries.

TNT's macro language support the same multiline comment style of C (but not the single line comment style), enclosing comments within /* and */. Comments has no effect on the script, but are very useful to document the code!

/* This is a comment */

Comments are really important, no only to made code legible to other people, but also to our own understanding (specially, if it is code written long time away!).

Comments are valid after the macro mode is open (using macro =).

Following a well knew tradition I put this simple macro ;)

macro =;
/* My first TNT macro */

quote Hello world! ;
p/ ;

Now, we can enter on the subject of variables...

Variables are objects that the program manipulates by an specific objective given by the user. Variables store values, that can be modified or read. Usually we are interested in that value. In other circumstances the variable value is useful for controlling the program flow. Also they are used to store values given by the user.

When macro mode is open, TNT sets a default number of variables (1000). They can be accessed by a number, starting with 0. It is possible to change the amount of variables using macro* N K ; where N is the number of loops, and K the number of variables.

General variables

Using numbers to access variables can be useful for small scripts, but with more complex macros, the management of code can be very difficult. Then, is a good practice to use names for variables. Variables can be named in any part of the code. It is a good practice naming it just after starting the macro's file (just after macro = ). Variables names are declared using the keyword var.

There are two ways to name variables, the first is explicit, that is useful to backward compatibility with scripts written in old versions of TNT.

Var =
0 variable1
1 variable2
5 variable 3
;

In this format, using var =, each variable is declared using the internal number of TNT. The declaration finish with a semi colon. The principal problem with this style, is that it is an invitation to use the numbers instead of the names. This can be dangerous when parts of the code change (for example, adding more variables).

A more elegant way, and more secure (protects against usage of unnamed variables), is declaring directly the names, using var : instead of var =

var :
variable1
variable2
variable3
;

Here, I always use this style, that produce a more legible code.

TNT variables can be simple, that is, just with one value, or can be arrays, a vector of several consecutive values. TNT arrays are static, that is, they cannot be resized in running time. Then declare them only after you know the size of the array. For example, just after reading the data, and we known the number of nodes in a tree.

An array declaration is simple, just as a normal variable, but dimensions inside brackets ([]), if it is a multidimensional matrix, use a comma (,) to separate the values, in a similar way that arrays are declared in pascal.

Var:
anArray [25]
aMatrix [3, 4]
;

Variables in loops

In TNT loop variables are independent from general variables. This variables are managed by TNT and not directly by the programmer. As general variables they can be named, o accessed using a number that start from 1, and increase in each nesting level. I generally use numbers. Maybe a better practice is to use names, as that freed the loop from its nesting level, an that's the only way to access some variables (for example, if you access it from another file).

Loop variables are declared using an equal before the name:

loop =cicle 1 10

Variables in the command line

When a macro is called, it is possible to assign some initial values from the command line associated with the script. This variables are sometimes known as arguments or parameters. For example, a macro called dojac can receive as parameters the number of replicates and the number of iterations per replicate

dojac 1000 20 ;

Then, dojac receives 1000 replicates and each replicate with 20 iterations.

As TNT's scripts are not interactive, this is the only way to the final user to modify the behavior of the scripts. Then, if the idea is to distribute the macro, calling the macro without parameters shows a help screen explaining the objective, the parameters, and the conditions necessary for using the macro in a correct way.

The function argnumber returns the number of arguments used when calling the macro.

Not forget to check out for TNT updates, and of course, several scripts and useful documentation at the TNT wiki :D

Algorithms for phylogenetics 0b: Trees

Versión en español

Another basic component of phylogenetic analysis' programs are the trees. Trees can be the result of an analysis (as in cladistic analysis' programs) or part of the data used (as in biogeography analysis' programs).

Trees are one of the most well known data structures of computer science. In computers science a tree is a collection of elements (nodes), nodes are related by a "kindship" relation that imposes a hierarchy on the nodes. Kinship is a pairwise relationship: one node is the ancestor and the other the descendant. A node can have an indefinite number of descendants, but, at maximum, only one ancestor.

In general, in phylogenetics, the term node is used only for elements with descendants, and terminal of leafs to elements without descendants (in computer science the used terms are internal node and terminal node, or leaf node. Here I will use the terminology from computer science, and when using node I refer to any element of the tree).

A trees has at maximum a single root node. A root node is an internal node without ancestor. Different from most abstract trees of computer science, the only elements with have the user data are the terminals (from the data matrix). Data stored by internal nodes is inferred through algoritmic means.

There are many ways to represent a tree. For me, the most natural one is using structures and pointers. Here is the basic node

typedef struct tagPHYLONODE PHYLONODE;

struct tagPHYLONODE {
PHYLONODE* anc;
PHYLONODE* left;
PHYLONODE* right;
STATES* recons;
};

This structure is a node from a binary tree, that is, each internal node have two descendants, the pointers left and right, note that they are pointers to PHYLONODE elements. The pointer to ancestor is anc. In this structure, the root node has anc as NULL (i.e. points to no elements), and terminal nodes has left and right as NULL. The array recons store the data (as bitfields).

I usually store the information from a terminal (extracted from data matrix) into an independent structure, for example

typedef struct tagTERMINAL TERMINAL;
struct tagTERMINAL {
char name [32];
STATES* chars;
};

And include a pointer to TERMINAL as part of PHYLONODE

struct tagPHYLONODE {
... //Otros campos aquí
TERMINAL* term;
};

Internal nodes has term as NULL.

A nice property of trees, is that subtrees have the same properties of a tree, then recursive algorithms a very natural way to work with trees. Nevertheless, I always prefer to have an independent structure to store the whole tree

typedef struct tagPHYLOTREE PHYLOTREE;
struct tagPHYLOTREE {
unsigned numNodes;
PHYLONODE* root;
PHYLONODE* nodeArray;
DATAMATRIX* matrix;
};

This structure store a pointer to the root node (root), an array to the nodes of the tree (nodeArray), a pointer to a data matrix (matix) and the number of nodes.

This approach has the advantage of having several independent sets of trees, each tree with his on characterisitcs (id, name, data matrix), that are no properties of any node, but of the whole set of nodes (A typical case: in biogeography, several cladograms form different organism are used).

Different from structures it is possible to store trees as coordinate arrays. This option is used in [1] for the example code, and it is also the way in which TNT macro language uses trees (the language does not support structures). The declarations of arrays is simple

int* anc;
int* left;
int* right;
STATES** chars;

In this case, all arrays are dynamic (they are declared as pointers, but as soon as they are assigned, they can be treated as arrays), and instead of have a pointer, they store the number that is the index of the array. As it is a coordinate array, every element with the same index is the same node. For example anc [17] = 20, assigns the node 20 as the ancestor of node 17. In this case, left [20] or right [20] must be equal to 17. chars [20] has the sates assigned to node 20. If you look at the tree entry in wikipedia (specially the entry on heaps) you will find that is the way used to keep trees.

For me, the bad side of that approximation is that requires an strict bookkeeping (take note that in TNT macro language, TNT automatically updates the information, so that is not a problem!). This is my own experience, I worked with tree reconciliation, and work with someone that does not know working with pointers. So I try a coordinate array approach. But we not know how many nodes would be on the tree after reconciliation, then the code turns messy and extremely difficult to update.

That experience does not show if some alternative is best than the other, just that sometimes the nature of the problem might constraint the way to resolve it, and that some styles of programming are better than others for some programmers ;). In this series I always will use structures.

Just to have some code, and to mark the recursivity of trees, here are a function to store a tree in a parenthetical notation (as in Hennig86, NONA and TNT)

#include < stdio.h >

void PrintTree (FILE* out, PHYLOTREE* tree) {
fprintf (out, "tread \'Simple tree output\'\n");
PrintNode (out, tree - > root)
fprintf (out, ";\np/;");
}

void PrintNode (FILE* out, PHYLONODE* node) {

if (node - > term != NULL) {
fprinf ("%s ", node - > term - > name);
return;
}
fprintf (out, "(");
PrintNode (out, node - > left);
PrintNode (out, node- > right);
fprintf (out, ") ");
}

This functions used standard IO operations. The function PrintTree puts the tree header for Hennig86/NONA/TNT trees. And call PrintNode on the root node. PrintNode checks if the node is a terminal, if this is true, it writes the terminal name, if not, the node is an internal one, so it prints the parenthesis and call recursively PrintNode on each one of its descendants.

I think that some time ago Mike Keesey write a post about trees under a object oriented paradigm. I'm unable to find the post, this one is the most closely alternative :P.

References
[1] Goloboff, P. A. 1997. Self weighted optimization: tree searches and character state reconstruction under implied transformation costs. Cladistics 13: 225-245. doi: 10.1111/j.1096-0031.1997.tb00317.x

Previous post on Algorithms for phylogenetics
0a. Bitfields

TNT macros: Intro

Versión es español

One of the most powerful utilities of TNT is its macro's language. This language allows access to TNT internal variables, and tree and data manipulation. This coupled with the computer power of TNT makes a terrific combination.

Unfortunatelly, maybe because of a lack of an extensive manual, or because there are few papers that explicitly use TNT macros (but they are growing!), then this capability is ignored for several users. In this series of posts, I want to give an introduction of the many possibilities allowed by the usage of macros.

Part of this idea born after I see the book "phylogenetics with R" [1], and the constant exchange with Santi Catalano about the TNT's wiki. I hope to post part of this series on the TNT's wiki, but for the moment, just to get the writing feeling, I post it first on my blog ;).

The style is somewhat orientated to programming--I'm powerfully influenced by Kenighan and Ritchie :)--because I think it is the best way to learn the language.

Notation

The TNT macro language is an interpreted language, this is, each instruction is executed as it is readed, then it is possible to “write” the programs in real time (just like the old BASIC, lisp, or the fashionable python).

This can be very nice, for example, to make some simple mathematical operations directly on TNT.

An example:

> macro = ;
Macro language is ON
> var: dest ;
> set dest 4 + 5 ;
> quote 'dest' ;
9

This simple calculator can introduce us in some particularities of the language.

To activate macros, the command macro = ; must be invoked, macro - ; deactivates the macros.

Each instruction finish with a semi colon (;). Although not necessary, for clarity, an space before the semicolon is a good practice.

The keyword var is used to declare variables.

The keyword set assigns a value to a variable. In the example it is a sum. Set accepts the four basic operations, as well as more complex combinations using parenthesis.

The command quote prints on the screen. In TNT to access the value stored into a variable, the name of the variable must be between simple quotes ('). Note that set assigns a value, so the name is written without quotations, but if the value assigned is stored into a variable, then that values must be in quotations:

set dest 'first' * 'second' ;

This operation assigns to dest the value of first times second.

But more important, is that TNT macros can be written on separate file, and executing like any commando of the program.

If the macro is saved with the ".run" extention, and is on the same working directory of the program (for example c:\bin\tnt) it is possible to call the macro just typing the name of the file. For example, TNT is distributed with the macro stats.run, that calculates consistency and retention index of the trees in memory. To execute it, only is necessary to type:

> stats ;

in the program command line, and the macro runs automatically.

As any file of TNT it can be accessed using proc command (but you lost the parameter list) of the macro. It is better to use the command run (or just write the macro's name). As any command macros can be accessed trough the OS command line.

Exercises

As exercises try to use the different ways to call a macro, as well as accessing values with the commands, think on scripts like this:

macro = ;
var:
numIts
numTrees
itTrees;

set numIts 100 ;
set itTrees 10 ;
set numTrees 'numIts' * 'itTrees' ;

rseed 0;
hold 'numTrees' ;
mult = replic 'numIts' hold 'itTrees' ;
nel * ;
p/ ;

That does noting that you can do more easily by hand, but allows you to get familiarity with the notation.

References
[1] Paradis, E. 2006. Analysis of phylogenetics and evolution with R. Springer

Algorithms for phylogenetics 0a: Bitfields

Versión en español

Intro

I want to start a series of post about the algorithms used in phylogenetic analyses. I feel a bit disappointed with the entry on computational phylogenetics (and related subjects) in wikipedia, that are somewhat biased towards model-based methods and "bioinformatics", with a poor representation of algorithms for phylogenetics.

There are two outstanding examples of algorithms for phylogenetics on the web. The book of Wheeler et al. [1], and, in a similar vein, a manuscript by DeLaet [2]. But their presentation of the algorithms is somewhat general, that is be nice for educational purpouse, but in some cases, far away from the actual implementation in computer software.

As the presentation of the algorithms in [1] and [2] is excellent, I want to focus on the implementation. The idea is to go from simpler to more complex algorithms (as far as I can comprehend them xD).

I want to acknowledge Pablo Goloboff. He always have the time to discuss with me about algorithms (and any topic on methodological phylogenetics) :D. Of course, any error in my implementations are my own errors!

As this series progress, I will post the source code on google source or sourceforge, if someone wants to check it, requires an knowledge of C programming language. Thanks to Rubén who showme some tips with the HTML :).

Bitfields

Characters are a basic component of phylogenetic analysis. For simplicity assume that we only have a single character in each terminal. Each character can be stored into a variable, assigning to them 0, 1, 2... as indicated by the character state. This idea is implicit in the original description of Wagner's "groundpland divergence" [3], and in Farris' formalization [4, see 5]. Then operations between characters would be operations of ranges. But it is more simpler to think about characters as a set of states [4, 6]. Then operations between characters would be set operations. This set has a peculiar property: they are perfectly boolean, that is, a taxon has or has not a particular state. This can be translated in two positive consequences: (i) character states can be stored as a bitfield: (ii) character operations are bifield operations.

Computers store numbers as binary numbers. A bitfields use this characteristic to represent a set of positioned bits. This example shows it better:

State    binary representation       "Number" (human)
0        0001                        1
1        0010                        2
2        0100                        4
3        1000                        8
0, 1     0011                        3
1, 3     0101                        5

As can be seen, each state has his on bit position, and the states combination is just the union of its states. Many programming languages include operations to work directly on bits (not, and, or and xor), then the translation from set operations to bit operations is direct.

In this series I will use char to store character states. In C, char has 8 bits, then only 8 states can be stored. I define the bitfield with a typedef, so changing the number of bits on the bitfield (and then the number of states) is easy.

#define BITS_ON_STATE 8
#define ALL_BITS_ON 255
typedef char STATES;

This small example reads the caracters of a taxon, from a file (in), and store it into an array of characters (chars). The number of characters is nc, and the functions getc (in stdio.h) reads a single character from the file, SkipSpaces ignores the blank characters, and isdigit (ctype.h) detects if the character is a number.

for (j = 0; j < nc; ++ j) {
error = SkipSpaces (in);
if (error != NO_ERROR) return error;
c = getc (in);
if (isdigit (c))
  chars [j] = 1 < < (c - '0');
else if ((c == '?') || (c == '-'))
  chars [j] = ALL_BITS_ON;
else return BAD_FORMAT;
}

The operation chars [j] 1 < < (c – '0') substract the ASCII value of '0' (30) from the ASCII value stored in c (a number, so it is form 30 to 39). The resulting value is used to shift the bits of 1. For example if a '0' is readed the operations are:

chars [j] = 1 < < (30 – 30)
chars [j] = 1 < < 0
     [0000 0001 < < 0 = 0000 0001]
chars [j] = 1

If a 5 is readed

chars [j] = 1 < < (35 – 30)
chars [j] = 1 < < 5
      [0000 0001 < < 5 = 0010 0000]
chars [j] = 32

The 1 is shifted five bits to the left.

Note that inapplicables and unknowns are coded with all bits on.

This work nicely with non additive characters. For additive characters, it is possible to “recode it” as several binary characters [7][8], then it is possible to use the character as independent binary characters.

There are more sophisticated usages of bitfields, packing several characters in a single variable (for example, eight 4-bit characters can be stored into a singel 32-bits variable) [8][9]. This packing allows an speed up during searches, because several characters can be examined simultaneously.

References
[1] Wheeler, W. et al. 2006. Dynamic homology and phylogenetic systematics: a unified approach using POY. American Mus. of Natural History, published in cooperation with NASA. online: http://research.amnh.org/scicomp/pdfs/wheeler/Wheeler_etal2006b.pdf
[2] DeLaet, J. 2005. Pseudocode for some tree search algorithms in phylogenetics. Manuscript online: http://www.plantsystematics.org/publications/jdelaet./algora.pdf
[3] Wagner, W.H. 1961. Problems in the classification of ferns. In: Recent advances in botany. Toronto Univ. Press. pp. 841-844.
[4] Farris, J.S. 1970. Methods for computing Wagner trees. Syst. Zool. 19: 83-92.
[5] Goloboff, P.A. et al. 2006. Continuos characters analyzed as such. Cladistics 22: 589-601. doi: 10.1111/j.1096-0031.2006.00122.x
[6] Fitch, W.M. 1971. Toward defining the course of evolution: minimum change for a specific tree topology. Syst. Zool. 20: 406-416.
[7] Farris, J.S. et al. 1970. A numerical approach to phylogenetic systematics. Syst. Zool. 19: 172-189.
[8] Moilanen, A. 1999. Searching for most parsimonious trees with simulated evolutionary optimization. Cladistics 15: 39-50. doi: 10.1111/j.1096-0031.1999.tb00393.x
[9] Goloboff, P.A. 2002. Optimization of polytomies: state and parallel set operations. Mol Phyl. Evol. 22: 269-275. doi: 10.1006/mpev.2001.1049

Core coding

En estos días, algunas de las ideas que tengo de mi proyecto, no están saliendo como yo quería, así que me he dedicado a la programación de algunos detalles computacionales... como el asunto, aunque muy relacionado con computadoras, pero poco con cladística (aparte claro, de ser parte de mi proy xD).. lo deje en mi blog personal :P.

English version:

How can Java (and several other languages) programmers live without pointers?

C--

Bueno, el post esta más relacionado con la programación que con la biogeografía... pero si les interesa, ahí puse algunas de mis experiencias recientes con el C++...

Seguir leyendo