How is Python designed?

[Limin Fu]

I think code says thing clearer, here I pasted
a simplified version of my implementation with
depth-tranverse. Note: this simplified version cannot
handle unary computation. To read the real version,
please read one source file of Yuan at:
http://cvs.sourceforge.net/viewcvs.py/yuan-language/yuan_devel/source/yn_expression.cpp?view=markup

I just mention a few points in the following codes:
1. evaluation is done during traverse.
2. no need to store "node"s or temporary variables in
a list/queue/stack.
3. when eval() is called, it knows the exact type of
the object.

class node{
  // booleans to tell the type of node:
  bool isVariable,isSomethingElse; 

  char oper; // operator
  double  value; // temporary value
  something *tempVarForSomething;

  node *left,*right; // pointers to its sons
  node *parent;  // pointer to its parent
 
  void eval();
  void trav();
};

void node::eval()
{
   if(oper=='+')
     value=left->value+right->value;
   else if ....
}
void node::trav()
{
   node *p=this;
   while(1){
      // go along "right" to reach a leaf:
      while(p->right) p=p->right;

      if(p->isVariable){
         // get the value:
         p->value=...;
      }else if(p->isSomethingElse){
         // do something else
      }

      if(!p->parent) break;

      // if "p" is a "left" son:
      if(p==p->parent->left){
         // go back to "parent"
         p=p->parent;

         // evaluation:
         p->eval();

         if(p==this) break;
      }
      if(p==this) break;
      // Now "p" must be a "right" son,
      // jump to the "left"
      p=p->parent->left;
   }
}

--- "Diez B. Roggisch" <deetsNOSPAM at web.de> wrote:

> > 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
> -- 
> http://mail.python.org/mailman/listinfo/python-list
> 



		
__________________________________ 
Do you Yahoo!? 
Yahoo! Mail - Easier than ever with enhanced search. Learn more.
http://info.mail.yahoo.com/mail_250