C++: A minimalistic symbolic expression tree interpreter

Binary or more generally, N-ary trees are very useful in symbolic computation, predicate calculus and so on.

Suppose we want to implement something simple, like an expression tree that can encode arithmetic formulas, something that could possibly look like this (I’ve added the node outputs as edge labels):

 

So we have:

1. Leaf nodes, or terminals, which generally contain a value (be it random or corresponding to some value from the dataset etc)
2. Non-leaf nodes, or functions, which execute an operation on their input

Let’s see how we can express this in C++, but first, since we are also interested in benchmarking our tree interpreter, we introduce an object counter using the Curiously Recurring Template Pattern (CRTP).

// Object counter
template <typename T>
struct ObjectCounter
{
    ObjectCounter()
    {
        ++objects_created;
        ++objects_alive;
    }

    virtual ~ObjectCounter()
    {
        --objects_alive;
    }

    static long int objects_created;
    static long int objects_alive;
};

template <typename T> long int ObjectCounter<T>::objects_created(0);
template <typename T> long int ObjectCounter<T>::objects_alive(0);

The different types of nodes should have a base class:

enum {TERMINAL, FUNCTION}; // node types

class Node : public ObjectCounter<Node>
{
public:
    explicit Node(int type) : nodeType(type), evaluated(false), evalValue(0.0) {}
    virtual ~Node() {}
    int Type() const { return nodeType; }
    void Type(int type) { nodeType = type; }
    bool Evaluated() const { return evaluated; }
    void Evaluated(bool value) { evaluated = value; }
    double EvalValue() const { return evalValue; }
    void EvalValue(double value) { evalValue = value; }
    virtual double Evaluate() =0; //!< update eval values and flags

protected:
    int nodeType;
    bool evaluated;
    double evalValue;
};

The Terminal is easiest to declare:

class Terminal : public Node
{
public:
    Terminal() : Node(TERMINAL) {}
    ~Terminal() {}
    double Value() const { return val; }
    void Value(double value_) { val = value_; }

    double Evaluate() { return val; }

private:
    double val;
};

For our Function class, we need to think about how we design and use our operators. Since I’m lazy, I wanted to use the binary operators from functional header, but using them raises one important issue: we’d like to store them in a container, like std::vector, which is not possible for operators like std::plus, std::minus, std::multiplies and std::divides due to the fact that their base class, std::binary_function is not a polymorphic base class (and if it were, I would need to store pointers to it, not copies). In short, something like

typedef std::binary_function<double,double,double> binary_op;
std::vector<binary_op> functions;

would not work.

Therefore, for our functions vector we need a function type that can wrap polymorphic function objects.
This is where we consider our options: we want binary operators that accept and return double values.
Before we start considering the alternatives, let’s take a look at how our Function class might look like:

class Function : public Node
{
public:
    Function() : Node(FUNCTION) {}
    ~Function()
    {
        for (auto i = children.begin(); i != children.end(); ++i)
            delete *i;
    }
    void setOp(binary_op& op_) { op = op_; }
    std::vector<Node*>& Children() { return children; }
    const std::string& Symbol() const { return symbol; }
    void setSymbol(std::string& symbol_) { symbol = symbol_; }

    double operator()(double a, double b) {
        return op(a,b);
    }

    double Evaluate()
    {
        EvalValue( (*this)(Children()[0]->Evaluate(), Children()[1]->Evaluate()) );
        return EvalValue();
    }

So a Function uses its () operator to apply a binary_op to its arguments. The problem is how do we define and use the binary_op.

1. First and easiest, boost::function:
   

   typedef boost::function<double(double,double)> binary_op;
   

2. Second, and a little bit “more lightweight”, is the std::tr1::function from the new C++0x standard:
   

   typedef std::tr1::function<double(double,double)> binary_op;
   

Benchmark

At this point, I was already very curious to see how well this tree interpreter performs. I tested its speed against a C# tree interpreter that is part of HeuristicLab, which is a framework for heuristic and evolutionary algorithms developed in C# using .NET 4.0, and also against an older project of mine which has a different (and less generic) design: different function node types which have different methods defining the operations they perform.

So I got the following figures:

• HeuristicLab arithmetic grammar tree interpreter: 3.37e+007 nodes/s
• Other project (more straightforward): 4.49e+007 nodes/s

At this point I was really curious to see how the minimalistic approach would perform, but unfortunately the figures were rather disappointing:

• Using boost::function: 2.45e+007 nodes/s
• Using std::tr1::function: 3.1e+007 nodes/s

Surprisingly, boost::function is quite slow, and although std::tr1::function is a bit faster, I still wasn’t happy.

This is when internet research comes in handy, as I have discovered the following way of wrapping function objects:

typedef double (*binary_op)(double,double);
template<typename F> typename F::result_type
functor(typename F::first_argument_type arg1, typename F::second_argument_type arg2)
{
    return F()(arg1, arg2);
}

Using the function above requires a small correction to the code. Where we previously had:

std::vector<binary_op> functions;
functions.push_back(std::plus<double>());

now we must have:

std::vector<binary_op> functions;
functions.push_back(functor< std::plus<double> >);

This approach gives a substantial speed boost: 3.54e+007 nodes/s, which is still not great, but, considering the simplicity of the design (a couple of node classes, a tree class and an evaluation function), I think its pretty ok.

Broken

“Things get broken. Some things can be put back together, if you recover all the lost pieces and their nature is such that they can be fixed. Except some things can never be fixed or repaired or put back together and given a new purpose.”

“Like a broken vase, you mean? Those things always get broken. Their second nature. Don’t use big words.”

“I mean when you drop something and it breaks in a million pieces, and you try to put it back together. you can’t restore its wholeness, and you think.. ok. it happened. I can’t be sad, it’s no big deal, everything is a transformation.”

“everything is. you can be sad, but you know it can’t be helped. sad or not sad.”

“but, everything that was created and I mean things and maybe also people, all of them have not been created without a purpose and that when something is broken, shattered or destroyed, even before it dies, it looses its purpose in this world, its essence, its ‘aiua’. like a watch that can’t tell time anymore.”

“destroyed but not defeated. isn’t that what Hemingway said? purpose — maybe thats true, but maybe it was meant to be this way. and things get broken, and maybe they die or they change and get another life, and you could call that a purpose, or at least a necessary step towards a greater.. destiny. if there is such a thing as destiny for things that get broken. or for people”

“reasoning is not right, things get complicated this way, and such a complicated purpose equals no purpose at all. destiny? can we even mention it or think about it, when we spend most of our lives not knowing it and maybe only seconds before death comes and slides our eyelids shut, with its skeleton hand, maybe only then we get a glimpse and if we’re lucky, with our last breath we acknowledge the fact that we’ve not lived in vain?”

“Especially people are weird this way. you should follow nature instead, its infinite simplicity.”

“the nature… of time”

“and space, and the human race”

“which one of us is the imaginary one?”

“you are. and I’m tired”

Saturday

“Have you ever been in love? Horrible isn’t it? It makes you so vulnerable. It opens your chest and it opens up your heart and it means that someone can get inside you and mess you up. You build up all these defenses, you build up a whole suit of armor, so that nothing can hurt you, then one stupid person, no different from any other stupid person, wanders into your stupid life…You give them a piece of you. They didn’t ask for it. They did something dumb one day, like kiss you or smile at you, and then your life isn’t your own anymore. Love takes hostages. It gets inside you. It eats you out and leaves you crying in the darkness, so simple a phrase like ‘maybe we should be just friends’ turns into a glass splinter working its way into your heart. It hurts. Not just in the imagination. Not just in the mind. It’s a soul-hurt, a real gets-inside-you-and-rips-you-apart pain. I hate love.” — Neil Gaiman

The world is all that is the case

I’ve always loved logic, because it makes life simple, clear, in a sense almost beautiful.

Wittgenstein, in his Tractatus Logico-Philosophicus:

1 The world is all that is the case.

1.1 The world is the totality of facts, not of things.

1.11 The world is determined by the facts, and by their being all the facts.

1.12 For the totality of facts determines what is the case, and also whatever is not the case.

1.13 The facts in the logical space are the world.

1.2 The world divides into facts.

1.21 Each item can be the case or not the case while everything else remains the same.

Generic Image Library: Save Raw Image Data to File

GIL (Generic Image Library) is “a C++ generic library which allows for writing generic imaging algorithms with performance comparable to hand-writing for a particular image type” and it’s now part of the Boost Libraries.

Today I wanted to implement a save_to_image function for a project I was working on this week, and I thought about using GIL. So after reading the docs I figured out how it works and it’s remarkably simple.

If we have the raw image data (or can produce it in some way), in the form of three channel vectors:

unsigned char r[width*height]; // red
unsigned char g[width*height]; // green
unsigned char b[width*height]; // blue

Then we can write it to a png file, for example, like this:

#include <boost/gil/extension/io/png_io.hpp>
boost::gil::rgb8c_planar_view_t view = boost::gil::planar_rgb_view(width, height, r, g, b, width);
boost::gil::png_write_view("gil.png", view);

Also, if your image data also contains an alpha channel, then it’s just:

unsigned char a[width*height]; // red

#include <boost/gil/extension/io/png_io.hpp>
boost::gil::rgba8c_planar_view_t view = boost::gil::planar_rgba_view(width, height, r, g, b, a, width);
boost::gil::png_write_view("gil.png", view);

Don’t forget to link your program with -lpng and, if you run into compile errors, try the following workaround:

/* work around some libpng errors */
#define png_infopp_NULL (png_infopp)NULL
#define int_p_NULL (int*)NULL

Project Euler Problems 39 and 75

If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?

The solution to this problem is using the following formulas for the iterative generation of new Pythagorean triples:

where:

This can be done easily using recursion:

/* Project Euler - Problems 39 and 75

   39. If p is the perimeter of a right angle triangle, {a, b, c},
       which value, for p ≤ 1000, has the most solutions?

   75. Find the number of different lengths of wire that can form
       a right angle triangle in only one way.

   http://mathworld.wolfram.com/PythagoreanTriple.html */

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

typedef unsigned long ulong;

#define N 1500000

class Problem39
{
public:
    void solve();
private:
    vector<int> p_;
    void r_(ulong a, ulong b, ulong c);
};

void
Problem39::r_(ulong a, ulong b, ulong c)
{
    ulong p = a + b + c;
    if (p > N) return;
    for (ulong i = p-1; i < N; i += p)
    {
        p_[i] += 1;
    }

    r_( a - 2*b + 2*c, 2*a - b + 2*c, 2*a - 2*b + 3*c );

    r_( a + 2*b + 2*c, 2*a + b + 2*c, 2*a + 2*b + 3*c );

    r_( -a + 2*b + 2*c, -2*a + b + 2*c, -2*a + 2*b + 3*c );
}

void
Problem39::solve()
{
    p_ = vector<int>(N, 0);
    r_ (3,4,5);

    ulong c = 0, max = p_[0], p;
    for (int i = 0; i < N; ++i)
    {
        if (max < p_[i])
        {
            max = p_[i];
            p = i+1;
        }
        if (p_[i] == 1)
            c++;
    }
    cout << "p = " << p << " (" << max << " solutions)" << endl;
    cout << "c = " << c << endl;
}

int main(void)
{
    Problem39 p;
    p.solve();
    return 0;
}

Noica — jurnal filozofic (fragmente)

Caut să văd ce va trebui încercat la Școală: a gândi — cum se spune — viu. Dar ce înseamnă a gândi viu?

Cred că două lucruri: 1) A proceda prin întreguri, nu prin părți; întru câtva organic, nu de la simplu la compus; în nici un caz fals cartezian (fiindcă nici Descartes nu gândea așa), geometric și sistematic. 2) A lăsa întregurile să reiasă din elementul infinitezimal; a gândi deci, până la un punct, intuitiv: văzând — nu făcând, construind.

Pentru ultimul punct, Aristotel — singura dată când mă atrage — are un exemplu sugestiv. Închipuiți-vă o oaste, spune el; o oaste pusă pe fugă în neorânduială. La un moment dat (asta e tot: ”la un moment dat”), un soldat se oprește. În jurul lui se opresc alți patru–cinci. Apoi, în jurul nucleului format de ei se strând și alții, și iată dintr-o dată oastea întreagă întorcând fața către dușman și gata să primească din nou lupta.

Asta înseamnă ”viu”: unul singur, elementul infinitezimal poate să coaguleze restul. Un singur individ vertebrează totul. Nu urci matematic și gradat, de la simplu la compus, ci urci, fără compoziție, de la simplu la întreg. E paradoxul vieții, dar e paradoxul oricărei vieți.

Și mă gândesc la o concluzie ciudată: un adevărat colectivism e mai individualist decât cel care își zice așa. Sau invers: un adevărat individualism ar trebui să fie colectivist. Căci numai acesta din urmă, cel care deține întregul, știe adevăratul preț al părții. În oastea lui Aristotel, soldatul înseamnă ceva, poate ceva. Ce poate el dincolo?

Încă unul din scandalurile vieții, în istorie și dincolo de istorie.

*

Tulburătoare, vorba aceasta a lui Simmel: ”viața ca totalitate de fiecare clipă”. Așa o văd acum; așa este. În fiecare ceas simți că ești un întreg. Ai goluri, firește, dar le cunoști, deci le-ai umplut într-un oarecare fel. Ești o ființă împlinită.

Dar citești o carte: cum puteai trăi până acum fără gândurile ei? Legi o prietenie nouă: cum te puteai crede întreg fără ea? Abia acum simți golul adevărat, golul pe care ar fi trebuit să-l simți. Dar acum ești ”întreg”. Totalitate de fiecare clipă. Trăim alături unii de alții, totalitate lângă totalitate, într-o lume care nu totalizează, dar care se totalizează, parcă, în noi.

*

Singurătatea absolută? O concep câteodată așa: în tren, pe un culoar ticsit, stând pe geamantan. Ești atunci departe nu numai de orice om, mai ales de cei care te împiedică să te miști; dar ești departe și de orice punct fix în spațiu. Ești undeva, între o stație și alta, rupt de ceva, în drup spre altceva, scos din timp, scos din rost, purtat de tren, purtând după tine un alt tren, cu oameni, situații, mărfuri, idei, una peste alta, în vagoane pe care le lași în stații, le pierzi între stații, le uiți în spații, golind lumea, gonind peste lume, singur, mai singur, nicăieri de singur.

Ești undeva, între o stație și alta,
rupt de ceva,
în drup spre altceva,
scos din timp,
scos din rost,
purtat de tren,
purtând după tine un alt tren,
cu oameni, situații, mărfuri, idei,
una peste alta,
în vagoane pe care le lași în stații,
le pierzi între stații,
le uiți în spații,
golind lumea,
gonind peste lume,
singur,
mai singur,
nicăieri de singur.

Saving my face

Transfigurare

Cu toate că i-am spus că nu vreau,
Mi-a dat noaptea-n somn să beau
Întuneric, și am băut urna întreagă.
Ce-o fi să fie, o să se aleagă.

Puteam să știu că-n zeama ei suava
Albastră-alburie, era otravă ?
M-am îmbătat ? Am murit ?
Lasați-mă să dorm… M-am copilărit.

Cine mai bate, nu sunt acasă,
Cine întreabă, lasă…
Cui mai pot să-i ies în drum
Cu sufletul meu de acum?…

— Tudor Arghezi

Somebody get me out of here

I don’t need an education
I learned all I need from you
They’ve got me on some medication
My point of balance was askew
It keeps my temperature from rising
My blood is pumping through my veins

Chorus:
Somebody get me out of here
I’m tearing at myself
Nobody gives a damn about me or anybody else

I wear myself out in the morning
You’re asleep when I get home
Please don’t call me self defending
You know it cuts me to the bone
And it’s really not surprising
I hold a force I can’t contain

Chorus

And still you call me co-dependent
Somehow you lay the blame on me
And still you call me co-dependent
Somehow you lay the blame on me

Somebody get me out of here
I’m tearing at myself
I’ve got to make a point these days
To extricate myself

Chorus

And still you call me co-dependent
Somehow you lay the blame on me
And still you call me co-dependent

Somehow you lay the blame on me