How is Python designed?

[Diez B. Roggisch]

> No, in the depth-traversal implementation, a function
> can avoid calling itself (at least in my
> implementation it's like this).

How so? It has to keep state of which nodes to visit - so instead of calling
trav, you call functions to store and fetch nodes in a container like a
stl-list. That's the same cost, function-call is function call.

There is no difference - you simply decoupled the tree traversal from the
evaluation - but combined, its the same effort. It's like in my second
example with bytecodes - the traversal is done beforehand (and only once),
and then the eval is only done on the nodes in a row.

> Because you can write seperate functions: a function
> for depth-traversal (say trav()) and another function
> for evaluation (say eval()). trav() may call eval().
> And eval() NEVER call other functions. For one
> arithmetic tree, trav() is called once, and eval() is
> called by trav() at each node. So it is not recursive.
>> Now apart from that, I still fail to see where your
>> method of evaluation has
>> any speed gains.
> 
> And if you inplement eval() as an "inline" function,
> there will be no cost for function calls for eval().
> In this way it can gain some speeds.

No. Inlining works only when the actual type of your node is known, e.g.
like this (Constant and Variable are both of type :

{
Constant left;
Variable right;

left.eval();
right.eval();
}

Here the compiler can take advantage from the fact that it knows at
compiletime which eval to inline

But if you have 

{
list<Node> nodes;
for(nodes::iterator it = nodes.begin(); it != nodes.end(); it++) {
    (*exp).eval();
   }
}

the compiler can't possibly know which node is in exp- so it has to resort
to a vtable-lookup and a method call on the result.

-- 
Regards,

Diez B. Roggisch