Re: How is Python designed?
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" <[EMAIL PROTECTED]> 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 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
--
http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
> 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 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
Re: How is Python designed?
> So maybe you're right in claiming it beeing > recursive. But then, > depth-traversal is recursive, too. No, in the depth-traversal implementation, a function can avoid calling itself (at least in my implementation it's like this). 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. Best regards, Limin __ Do you Yahoo!? Yahoo! Mail - Easier than ever with enhanced search. Learn more. http://info.mail.yahoo.com/mail_250 -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
> agree that they called the functions for the same > number of times, the difference is how they are > called. What do you mean by difference in calling - a call is a call, no? -- Regards, Diez B. Roggisch -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
> I'm sure the code in my example is recursive. As I > have said, you may show those codes I gave as example > to somebody know C++ well to check if it is recursive. I just had second thoughts about tree-traversal beeing recursive - and I have to admit that I'm not entirely sure if I can hold up the statement that it's not recursive. It might be counted as that, as the strategy of traversing a tree certainly is of a recursive nature, as its styled somewhat like this: def treewalk(node): for child in node.childs: treewalk(child) node.do_something() So maybe you're right in claiming it beeing recursive. But then, depth-traversal is recursive, too. Now apart from that, I still fail to see where your method of evaluation has any speed gains. -- Regards, Diez B. Roggisch -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
It seems that we focused on different things. I was talking about the example I have given for arithmetic evaluation. And you focused the AST-based evaluation, which, I belive, is different from my example. I also agree that they called the functions for the same number of times, the difference is how they are called. Resursive function is a function called itself. Am I wrong? I'm sure the code in my example is recursive. As I have said, you may show those codes I gave as example to somebody know C++ well to check if it is recursive. Best regards, Limin __ Do you Yahoo!? Read only the mail you want - Yahoo! Mail SpamGuard. http://promotions.yahoo.com/new_mail -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
> Of course for such simple expression, that function > will not run recursively, but for more complex > expressions, it will, as a example: > a + b * ( c + ( d - e ) / f )... No, it won't. You seem to not properly understand what recursion is, and confuse it with overloaded methods. The compute-method of an expression ast node is called once for every node - to yield its value. Not more - not less. The fact for a * b the compute methods of objects representing the variables a and b is called inside a binary operator object neither makes it recursive nor costs more time. So there are three compute calls - first on the *-Operator object, then on a and b. Using depth-first-search, there are three calls of compute - first on a, b, then on *. So three compute calls in both cases. As I said before: No reason not to do depth-first, if it suits your needs. But it won't buy you anything. -- Regards, Diez B. Roggisch -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Of course for such simple expression, that function will not run recursively, but for more complex expressions, it will, as a example: a + b * ( c + ( d - e ) / f )... --- LutherRevisited <[EMAIL PROTECTED]> wrote: > Kinda off subject, just thought I'd add that 0! = 1 > for that recursion example, > since that wasn't considered. Nice post though. > -- > http://mail.python.org/mailman/listinfo/python-list > __ Do you Yahoo!? The all-new My Yahoo! - What will yours do? http://my.yahoo.com -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Kinda off subject, just thought I'd add that 0! = 1 for that recursion example, since that wasn't considered. Nice post though. -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Hi,
> why did you choose that technique and not a common
> parser generator? The
Because I didn't know the standard parse technique
when I started to implement Yuan :)
> kind of parsing you use is somewhat oldfashioned -
> back in the times where
> parsing theory wasn't evolved enough. The
> disadvantage is that without a
> proper theory and a grammar explaining what
> statements are legal and
> meaningful and which not is uneccessary complicated.
>
> Look into the python language reference how use is
> made of a grammar to
> explain language constructs.
I will try to read something about the standard
technique, then dicide what to do with parsing.
Approximately how many lines of C/C++ code, do you
think, are required to implement the standard parser?
>
> > I supposed you would have done like:
> > class node{
> > ...
> > char oper;
> > node *left,*right;
> > void compute();
> > };
> > void node::compute()
> > {
> >if(left) left->compute();
> >if(right) right->compute();
> >if(oper=='+'){
> >
> >}else if(...){
> >
> >}
> > }
> > This is a kind of recursive evaluation of
> arithmetic
> > tree. Now I believe that's not what you have used.
> > Ah, yes. That's exactly what I mean.
>
> That is what I meant. But thats not recursive - the
> compute-calls account
> for the tree-traversal. Nothing recursive there.
Not true. It is not a tranvesal, it is recursive.
Because after compiling, The code I have given becomes
something like:
void compute(node *p)
{
if(p->left) compute(p->left);
if(p->right) compute(p->right);
if(p->oper=='+'){
...
}else if(...){
}
}
You see it is a recursion indeed(if you don't believe,
you can check with other people). And it's unefficient
due to pushing functions into function stack.
>
> > That's avoidable, using depth first seach.
>
> No. Traversal is traversal. A tree of size n needs
> O(n) to be traversed -
> otherwise you missed some nodes.
>
> You can of course cache the results of a tree
> traversal in a list, and call
> the compute method then in a loop:
>
> for node in nodelist:
> ??? = node.compute()
>
> But then you need to explicitely deal with where to
> store the resulting
> values of that computation, so you can access them
> lateron. That will most
> probably eat up the time saved by using that cache.
Temporary results can be saved in class "node" as
member data instead of cache, so there is no extra
cost of time.
Best,
Limin
__
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
--
http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Hi,
> it is executed. In this technique, indeed, checking
> patterns is a little complicated. In Yuan this part is
> not optimally implemented, somethings have to be
> improved or changed.
why did you choose that technique and not a common parser generator? The
kind of parsing you use is somewhat oldfashioned - back in the times where
parsing theory wasn't evolved enough. The disadvantage is that without a
proper theory and a grammar explaining what statements are legal and
meaningful and which not is uneccessary complicated.
Look into the python language reference how use is made of a grammar to
explain language constructs.
> I supposed you would have done like:
> class node{
> ...
> char oper;
> node *left,*right;
> void compute();
> };
> void node::compute()
> {
>if(left) left->compute();
>if(right) right->compute();
>if(oper=='+'){
>
>}else if(...){
>
>}
> }
> This is a kind of recursive evaluation of arithmetic
> tree. Now I believe that's not what you have used.
> Ah, yes. That's exactly what I mean.
That is what I meant. But thats not recursive - the compute-calls account
for the tree-traversal. Nothing recursive there.
> That's avoidable, using depth first seach.
No. Traversal is traversal. A tree of size n needs O(n) to be traversed -
otherwise you missed some nodes.
You can of course cache the results of a tree traversal in a list, and call
the compute method then in a loop:
for node in nodelist:
??? = node.compute()
But then you need to explicitely deal with where to store the resulting
values of that computation, so you can access them lateron. That will most
probably eat up the time saved by using that cache.
>
> It seemed to me that it made much difference in
> efficiency so that I reimplemented it by depth-first
> search. Maybe because I didn't implement the recursive
> evaluation properly :), I will check.
As I said before: AST traversal is post-order with a stack/lifo as node
container, deepth-first is using a queue/fifo instead - but there is _no_
gain in terms of speed here - both have to visit all nodes.
There is no reason to change you running system - but your hopes for more
performance that way aren't fulfilled either.
--
Regards,
Diez B. Roggisch
--
http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Hi,
> So I guess you don't use classic parser techniques
> then?
You are right. The Yuan interpreter scans the tokens
resulted from lexical analysis and matches them to the
syntax patterns. There are 3 basic patterns defined in
Yuan: arithmetic "a*b+c", chain (as I called it)
"objs[i]->func()" and regular expression "/\d*[abc]/",
each of which is represented by a class. And the other
patterns are a combination of these 3 basic pattern,
e.g. array enumeration "a=[1,a+1,func()]" etc. There
are functions responsible to parse the token patterns
to phrase objects. After all phrase objects are
generated, logical and loop controls are checked, so
that each phrase object "knows" if it should "step to"
the next phrase object or "jump to" another one when
it is executed. In this technique, indeed, checking
patterns is a little complicated. In Yuan this part is
not optimally implemented, somethings have to be
improved or changed.
> I'm still not sure what you mean by "recursive" - to
> me, recursion is the
> act of a function calling itself until some
> condition is met that markes
> the end (or actually begin I think) of the
> recursion, like this:
>
> def fac(n):
> if n == 1:
> return 1
> return n * fac(n-1)
>
> Thats recursion.
I supposed you would have done like:
class node{
...
char oper;
node *left,*right;
void compute();
};
void node::compute()
{
if(left) left->compute();
if(right) right->compute();
if(oper=='+'){
}else if(...){
}
}
This is a kind of recursive evaluation of arithmetic
tree. Now I believe that's not what you have used.
> If you mean by recursion that the top-node is called
> for evaluation which
> then delegates the evaluation to its children -
Ah, yes. That's exactly what I mean.
> well, that's unavoidable -
That's avoidable, using depth first seach.
> but also in both cases. As I mentioned before, the
> only difference I see is
> the order of evaluation - but that is invariant, as
> long as for all
> expression's their respective sub-expressions are
> evaluated beforehand.
It seemed to me that it made much difference in
efficiency so that I reimplemented it by depth-first
search. Maybe because I didn't implement the recursive
evaluation properly :), I will check.
>
> I'm not upset - I feared you were :) And I perceive
Ok, since non of us is upseted, let's forget it :)
Best,
Limin
__
Do you Yahoo!?
Yahoo! Mail - Helps protect you from nasty viruses.
http://promotions.yahoo.com/new_mail
--
http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Hi,
>
> Not really. You think in this way, maybe because you
> know more about AST and less about that technique I
> mentioned. I thinked in the opposite
> way because I know different things better.
> Hehe.
So I guess you don't use classic parser techniques then?
> Sorry maybe I didn't understand that part correctly
> and took grant that it would be implemented in
> recursive way. I just wondered if the following can be
> extended for arbitrary length arithmetic expressions:
> Assignment("foo", BinaryOp("+", Get("a"),
> BinaryOp("*", Get("b"), Get("c"
I'm still not sure what you mean by "recursive" - to me, recursion is the
act of a function calling itself until some condition is met that markes
the end (or actually begin I think) of the recursion, like this:
def fac(n):
if n == 1:
return 1
return n * fac(n-1)
Thats recursion.
The AST on the other hand has as much nodes as the expression denotes - each
subexpression is its own node. But that's true for your approach too -
after all, it has to be that way, otherwise you'd miss some part of the
expression :)
If you mean by recursion that the top-node is called for evaluation which
then delegates the evaluation to its children - well, that's unavoidable -
but also in both cases. As I mentioned before, the only difference I see is
the order of evaluation - but that is invariant, as long as for all
expression's their respective sub-expressions are evaluated beforehand.
> If I upseted you or anybody here by un-properly used
> words, please forgive me. I always feel my english
> must be improved :)
I'm not upset - I feared you were :) And I perceive your english at beeing
pretty good.
English isn't my native tongue either, so sometimes it might be that my
answers are shorter (and thus more likely percieved unfriendly) because its
difficult to express one's opininon.
--
Regards,
Diez B. Roggisch
--
http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
> I'm > > not that type who is afraid of negative opinions > :) In fact, I was trying to say it in joking way. Unfortunately, it is not obvious due to my poor english! Limin __ Do you Yahoo!? Yahoo! Mail - now with 250MB free storage. Learn more. http://info.mail.yahoo.com/mail_250 -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Hi,
> Ok, thats clearer. This whole thing sounds familiar
> - the technique you
> describe seems to resemble continuation passing
> style. For a brief
> discussion read here:
>
>
http://www.ps.uni-sb.de/~duchier/python/continuations.html
>
> Python has a continuation-based interpreter
> implementation - its called
> "stackless python". Google for it. It certainly is
> interesting.
That's interesting. I heared of stackless pyton a few
days ago, I will have a more careful look at it.
> And I don't see that the ast is more complicated, at
> least implementation
> wise - in fact, your method requires more analysis
> as for each statement
> its pollible successors have to be computed and made
> known to it - where an
> ast node only knows about its children that more or
> less directly stem from
> the syntax analysis.
Not really. You think in this way, maybe because you
know more about AST and less about that technique I
mentioned. I thinked in the opposite
way because I know different things better.
Hehe.
> I have to admit that I don't know if
> continuation-based evaluation has
> inherent performance-gains. The only thing I can
> think of is that you don't
> need a stackframe in some cases as tail-recursion -
> useful, but not so
> common that one would expect significant performance
> gains there. But as I
> said - I'm not on sure ground here.
I'm not sure either. Certainly it depends very much in
the implementation. If anybody want, we can make some
tests to check. I don't know if it's important,
because it seems people dosen't really care about the
efficiency of an interpreter (as long as it is not
really really too slow).
> Can you elaborate on what you consider beeing an
> unefficient recursive call
> and where there is a difference between your method
> of evaluation and the
> ast-evaluation I mentioned? After all, the
> ast-evaluation is a postorder
> traversal which has the same complexity of a depth
> first search - the only
> difference beeing the latter one using a fifo, the
> forme a lifo for
> managing the list of untraversed nodes. I don't see
> any difference here.
Sorry maybe I didn't understand that part correctly
and took grant that it would be implemented in
recursive way. I just wondered if the following can be
extended for arbitrary length arithmetic expressions:
Assignment("foo", BinaryOp("+", Get("a"),
BinaryOp("*", Get("b"), Get("c"
> I don't have negative opinions about yuan and by no
> meants want to
> discourage you developing it. Its a nice project.
>
If I upseted you or anybody here by un-properly used
words, please forgive me. I always feel my english
must be improved :)
Best regards,
Limin
__
Do you Yahoo!?
Yahoo! Mail - Easier than ever with enhanced search. Learn more.
http://info.mail.yahoo.com/mail_250
--
http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Well, you are the first who really want to join to the development of Yuan, I'm quite glad. We can further discuss in detail outside of this python mailing list, since it is not the place for such discussion. Here I just mention a few things here, maybe I can also get some advices from some experienced guys, hopefully. First, I don't doubt your C++ skill, theoretical background and passion for developing a scripting language. BUT YOU SHOULD MAKE SURE IF YUAN IS THE SAME AS WHAT YOUR HAVE THOUGHT. I should point out that, there is no virtual machine in Yuan, you can read some discussion posts I made with others people in this list. I can give more details on Yuan if you want. You may also have a look to the website: http://yuan-language.sourceforge.net/ Though Yuan is not well documented yet, you can get some impression of it from that website. Second, it is about licensing. Yuan will always be available under GPL (as long as it will survive). But I also wanted it can be used for commercial applications. Now what I'm thinking and planing to do is, to add one or two exceptions to GPL, so that Yuan can be used for certain types of commercial application without charging a fee, but COMPLETE integration (I mean when the communication between Yuan and other applications is beyond certain predefined interfaces) of Yuan with no GPLed applications would require a license fee(of course part of it will be share by the developers proportional to their contribution and the other part will be used to promote Yuan). The main reason I want to do so is, I want to setup a more or less stable(maybe not, I want to try it out) financial source for the development of Yuan. I am not sure if this licensing model will work for the interpreter of a scripting language :). Anyone tried it? In the case of scripting language, licensing is just a matter of strategy to enlarge the usage of itself (maybe I'm wrong). The reason I don't adopt the same strategy of python or perl etc. is that, I'm really not sure how many companies are willing to support such project voluntarily. Maybe somebody here can give me a hint. Anyway, anyone is welcome to join the develop of Yuan. If you don't agree with me on some of the above points, please tell me of your opinions, and I will consider them carefully. Thanks in advance. Best regards, Limin --- Robert <[EMAIL PROTECTED]> wrote: > Sorry for my interrupting the discussion : ). I am > a graduate student > in a chinese university, and i am very interested > in the Yuan > language. I'd like to join in the development of > Yuan and do some work > for this language. BTW, i like this word, "Yuan" : ) > > I have 3 or 4 years experience in C++, and i have > strong programming > skills about C++(at least in my opinion :) ) . I am > interested in the > compiling technology and virtual machine technology. > And i am reading > the C/C++> written by > Bill Blunden now. I had the thought of starting an > open source project > which contains a virtual machine and a scripting > language a few days > ago, just like a very simple python. Well, i know it > is very difficult, > but it is my dream : ). Luckly i found "Yuan" here. > So it is my > pleasure if i can become a member of "Yuan" :) > > Waiting for your reply. :) > > Best regards. > > > Ru Chen > > -- > http://mail.python.org/mailman/listinfo/python-list > __ Do you Yahoo!? The all-new My Yahoo! - What will yours do? http://my.yahoo.com -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Hi, > First, there is no abstract syntax tree generated for > the whole program, except for arithmetic > expression(even for this, it is slightly different > from what you said, I will come back to this point). > The Yuan (the name of the interpreter I designed) > interpreter first scans the source script, when it see > a pattern, for example "if(a>1)", it generates a > phrase object containing the arithmetic expression and > the ID (it is determined after all phrase objects are > created) of other two phrase objects. This phrase > object has a member method "execute()", whose > execution will return one of the IDs depending on the > value of "a>1". Then the next phrase object with that > ID is executed, and so on. I don't know how is the AST > for a whole program, I think it should be more > complicated than this. Ok, thats clearer. This whole thing sounds familiar - the technique you describe seems to resemble continuation passing style. For a brief discussion read here: http://www.ps.uni-sb.de/~duchier/python/continuations.html Python has a continuation-based interpreter implementation - its called "stackless python". Google for it. It certainly is interesting. And I don't see that the ast is more complicated, at least implementation wise - in fact, your method requires more analysis as for each statement its pollible successors have to be computed and made known to it - where an ast node only knows about its children that more or less directly stem from the syntax analysis. I have to admit that I don't know if continuation-based evaluation has inherent performance-gains. The only thing I can think of is that you don't need a stackframe in some cases as tail-recursion - useful, but not so common that one would expect significant performance gains there. But as I said - I'm not on sure ground here. > Then about arithmetic expression, indeed, it is > represented as tree. But in Yuan each node contains > all the information it need for evaluation. For > example, the leaves contains either a variable or a > constant value or a function call, and other nodes > contains the operators. So far it is more or less the > same as what you mentioned. But the evaluation is > performed on this tree directly with deep first > search, which is different from the two methods you > mentioned. The first one you mentioned is the same as > my first implementation, which results an unefficient > recursive function call. The second is the standard > way of evaluating arithmetic expressions. I guess I am > not the first one to evaluate arithmetic expression by > deep-first search on the tree (I would be surprised if > I am). Any way it is enough efficient. Can you elaborate on what you consider beeing an unefficient recursive call and where there is a difference between your method of evaluation and the ast-evaluation I mentioned? After all, the ast-evaluation is a postorder traversal which has the same complexity of a depth first search - the only difference beeing the latter one using a fifo, the forme a lifo for managing the list of untraversed nodes. I don't see any difference here. The second method I mentioned rids you of the traversal as it serialzes the nodes as simple statements in the order of choice - but the number of steps is the same. > Your further comments and discussion are welcome, I'm > not that type who is afraid of negative opinions :) > Any way I will continue to improve that interpreter, > it's an interesting thing for me. I don't have negative opinions about yuan and by no meants want to discourage you developing it. Its a nice project. -- Regards, Diez B. Roggisch -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Sorry for my interrupting the discussion : ). I am a graduate student in a chinese university, and i am very interested in the Yuan language. I'd like to join in the development of Yuan and do some work for this language. BTW, i like this word, "Yuan" : ) I have 3 or 4 years experience in C++, and i have strong programming skills about C++(at least in my opinion :) ) . I am interested in the compiling technology and virtual machine technology. And i am reading the written by Bill Blunden now. I had the thought of starting an open source project which contains a virtual machine and a scripting language a few days ago, just like a very simple python. Well, i know it is very difficult, but it is my dream : ). Luckly i found "Yuan" here. So it is my pleasure if i can become a member of "Yuan" :) Waiting for your reply. :) Best regards. Ru Chen -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Hi,
Probably you didn't understand well what I meant or
maybe I didn't express clearly what I meant. So I
think I need to spend more words to make it clear.
First, there is no abstract syntax tree generated for
the whole program, except for arithmetic
expression(even for this, it is slightly different
from what you said, I will come back to this point).
The Yuan (the name of the interpreter I designed)
interpreter first scans the source script, when it see
a pattern, for example "if(a>1)", it generates a
phrase object containing the arithmetic expression and
the ID (it is determined after all phrase objects are
created) of other two phrase objects. This phrase
object has a member method "execute()", whose
execution will return one of the IDs depending on the
value of "a>1". Then the next phrase object with that
ID is executed, and so on. I don't know how is the AST
for a whole program, I think it should be more
complicated than this.
Then about arithmetic expression, indeed, it is
represented as tree. But in Yuan each node contains
all the information it need for evaluation. For
example, the leaves contains either a variable or a
constant value or a function call, and other nodes
contains the operators. So far it is more or less the
same as what you mentioned. But the evaluation is
performed on this tree directly with deep first
search, which is different from the two methods you
mentioned. The first one you mentioned is the same as
my first implementation, which results an unefficient
recursive function call. The second is the standard
way of evaluating arithmetic expressions. I guess I am
not the first one to evaluate arithmetic expression by
deep-first search on the tree (I would be surprised if
I am). Any way it is enough efficient.
Your further comments and discussion are welcome, I'm
not that type who is afraid of negative opinions :)
Any way I will continue to improve that interpreter,
it's an interesting thing for me.
Regards,
Limin
> I'd say that's pretty much standard interpreter
> technique - an expression
> like this:
>
> foo = a + b * c
>
> is translated and reduced to an abstract-syntax-tree
> something like this:
>
> Assignment("foo", BinaryOp("+", Get("a"),
> BinaryOp("*", Get("b"),
> Get("c"
>
> Then on Assignment one can invoke eval(), and get
> the result. Assignment
> will invoke eval on its children, which in turn will
> do that for their
> operands, until something can be computed. The
> result is returned.
>
> By using an emulated stack or register-machine, you
> can flatten that to
> something like this:
>
> push Get("c")
> push Get("b")
> push BinaryOp("*")
> push Get("a")
> push BinaryOp("+")
> pop Assignment("foo")
>
> This is of course very makeshift - but you'll get
> the idea.
>
> This doesn't mean I want to discourage you - on the
> contraire. Developing
> your own language is highly educating, and I
> personally love it when I
> "invent" something and then later find out that
> people much cleverer than
> me did so before - it shows that I went down the
> same paths of thought :)
>
> --
> Regards,
>
> Diez B. Roggisch
> --
> http://mail.python.org/mailman/listinfo/python-list
>
__
Do you Yahoo!?
Read only the mail you want - Yahoo! Mail SpamGuard.
http://promotions.yahoo.com/new_mail
--
http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Hi,
> The basic idea of this technique is to create a class
> to represent each type of script phrase(that's the
> term I used in the program, it's just a piece of code
> for particular task such assignment,logical/loop
> control,function call, whatever). In the phase of
> compiling, phrase instances of such classed are made,
> and in the execution phase, starting from the first,
> each phrase instance is executed and jump to the next
> phrase instance for subsequential execution,
> like a finite state automa I would say. Currently the
> interpretation efficiency is comparable to most
> popular interpreters.
I'd say that's pretty much standard interpreter technique - an expression
like this:
foo = a + b * c
is translated and reduced to an abstract-syntax-tree something like this:
Assignment("foo", BinaryOp("+", Get("a"), BinaryOp("*", Get("b"),
Get("c"
Then on Assignment one can invoke eval(), and get the result. Assignment
will invoke eval on its children, which in turn will do that for their
operands, until something can be computed. The result is returned.
By using an emulated stack or register-machine, you can flatten that to
something like this:
push Get("c")
push Get("b")
push BinaryOp("*")
push Get("a")
push BinaryOp("+")
pop Assignment("foo")
This is of course very makeshift - but you'll get the idea.
This doesn't mean I want to discourage you - on the contraire. Developing
your own language is highly educating, and I personally love it when I
"invent" something and then later find out that people much cleverer than
me did so before - it shows that I went down the same paths of thought :)
--
Regards,
Diez B. Roggisch
--
http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
> If you want cutting-edge, mind twisting stuff, look > into > Psyco extension (Armin Rigo, 1.3 just announced > here) > Stackless extension (Christian Tismer) > PyPy (new interpreter written in Python, several > people, has EU funding) That would be interesting. However I am designing and implementing another interpreter. The techniques I'm using seems to be different from most of current interpreters (I hope so, I'm not very sure, that why I come to ask questions about interpretation techniques). The programming language is C++. The basic idea of this technique is to create a class to represent each type of script phrase(that's the term I used in the program, it's just a piece of code for particular task such assignment,logical/loop control,function call, whatever). In the phase of compiling, phrase instances of such classed are made, and in the execution phase, starting from the first, each phrase instance is executed and jump to the next phrase instance for subsequential execution, like a finite state automa I would say. Currently the interpretation efficiency is comparable to most popular interpreters. For more information, please have a look at: http://yuan-language.sourceforge.net/ Honest saying, it has just come out for a few monthes, it's not well tested and there is much things to be improved. So don't be surprised if some bugs come out when you run it. In this case, please let me known. Cheers, Limin __ Do you Yahoo!? Yahoo! Mail - Easier than ever with enhanced search. Learn more. http://info.mail.yahoo.com/mail_250 -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Limin, Look at this: http://wiki.cs.uiuc.edu/cs427/PYTHON I think it may help. Arthur Limin Fu <[EMAIL PROTECTED]> wrote in message news:<[EMAIL PROTECTED]>... > To clarify, I mean the internal structure and design > of python interpreter. Any hint? Thanks. > Regards, > Limin > > > > __ > Do you Yahoo!? > Yahoo! Mail - 250MB free storage. Do more. Manage less. > http://info.mail.yahoo.com/mail_250 -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
"Limin Fu" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > Thanks a lot for the explanations. > So CPython used more or less the standard technique to > implement the interpreter. Yes. Moreover, the code is still pretty clean (in most places, at least) after 15 years of development. These two facts facilitate joining the development team. If you want cutting-edge, mind twisting stuff, look into Psyco extension (Armin Rigo, 1.3 just announced here) Stackless extension (Christian Tismer) PyPy (new interpreter written in Python, several people, has EU funding) Terry J. Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Thanks a lot for the explanations. So CPython used more or less the standard technique to implement the interpreter. Are there any other interpretation techniques? I guess many. But I'm quite new in this field and I couldn't find good references on internet about this. If there is anybody has such references, please send me some if you don't mind. I would be appreciative very much. Best, Limin --- Terry Reedy <[EMAIL PROTECTED]> wrote: > > "Limin Fu" <[EMAIL PROTECTED]> wrote in message > > news:[EMAIL PROTECTED] > > To clarify, I mean the internal structure and > design > > of python interpreter. Any hint? Thanks. > > Ah... The interpreters (plural) are a separate issue > from the language > itself (a Python program is a list of Python > statements, etc). We'll > presume that you specifically mean the CPython > interpreter, as opposed to > Jython, Viper, Ironman, PyPy, Parrot, or the human > brain. For CPython: > > human or other source code generator ==> Python > source code > > CPython compile phase: > lexer ==> tokens > parser ==> ast tree > byte code generator ==> byte codes for Python > virtual machine > (see the Lib Ref chapter on the dis module for VM > commands) > > CPython runtime phase: > code evaluator ==> computations >(see source file ceval.c for the link between > byte codes and C > functions) > > CPython is currently both the reference > implementation and the most > commonly used implementation. Both facts could > change in the future, > possibly even with divergence between the two roles. > Since Python is meant > to be a practical computer language as well as an > abstract algorithm > language (for humans), a reference implementation is > needed to show that > proposed language features can be sensibly > implemented. > > Terry J. Reedy > > > > -- > http://mail.python.org/mailman/listinfo/python-list > __ Do you Yahoo!? Meet the all-new My Yahoo! - Try it today! http://my.yahoo.com -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
"Limin Fu" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > To clarify, I mean the internal structure and design > of python interpreter. Any hint? Thanks. Ah... The interpreters (plural) are a separate issue from the language itself (a Python program is a list of Python statements, etc). We'll presume that you specifically mean the CPython interpreter, as opposed to Jython, Viper, Ironman, PyPy, Parrot, or the human brain. For CPython: human or other source code generator ==> Python source code CPython compile phase: lexer ==> tokens parser ==> ast tree byte code generator ==> byte codes for Python virtual machine (see the Lib Ref chapter on the dis module for VM commands) CPython runtime phase: code evaluator ==> computations (see source file ceval.c for the link between byte codes and C functions) CPython is currently both the reference implementation and the most commonly used implementation. Both facts could change in the future, possibly even with divergence between the two roles. Since Python is meant to be a practical computer language as well as an abstract algorithm language (for humans), a reference implementation is needed to show that proposed language features can be sensibly implemented. Terry J. Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Limin Fu wrote: To clarify, I mean the internal structure and design of python interpreter. Any hint? Thanks. Regards, Limin In the open source world, of course, the usual answer from people like me (who don't delve deeply into the internals most of the time) is "use the source, Luke". But I'm sure you'll get plenty of useful answers here now the question is clear. regards Steve -- http://www.holdenweb.com http://pydish.holdenweb.com Holden Web LLC +1 800 494 3119 -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
To clarify, I mean the internal structure and design of python interpreter. Any hint? Thanks. Regards, Limin __ Do you Yahoo!? Yahoo! Mail - 250MB free storage. Do more. Manage less. http://info.mail.yahoo.com/mail_250 -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
--- Timo Virkkala <[EMAIL PROTECTED]> wrote: > > Do you mean the structure and design of the > language, or the process of > designing the language? I mean the structure and design of the language. Sorry for the umbiguous question. > > Well, in either case, you'll probably find your > answer at http://www.python.org > > Take a look at the Docs -> Language Reference and > PEP sections. I will have a look at there. Thanks. Limin __ Do you Yahoo!? Dress up your holiday email, Hollywood style. Learn more. http://celebrity.mail.yahoo.com -- http://mail.python.org/mailman/listinfo/python-list
RE: How is Python designed?
Roy Smith wrote: > As far as I can tell, the process works like this: > > Guido has an idea for something he wants to do and announces it. > > Everybody beats him up about it. > > He goes ahead and does it anyway. > > It's a strange process, but it seems to work. It's not quite that straightforward. For example, sometimes we beat someone else up as well. Tim Delaney -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
As far as I can tell, the process works like this: Guido has an idea for something he wants to do and announces it. Everybody beats him up about it. He goes ahead and does it anyway. It's a strange process, but it seems to work. -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
"Limin Fu" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > Is there any technical description on internet of how > python is designed? Or can somebody give a short > description about this? I'm just curious. One answer is that Python is currently designed by a group of voluntary developers 'chaired' by Guido van Rossum and communicating via the python-dev mailing list (gatewayed to gmane.comp.python.devel), the SourceForge tracker, and other means (technical details omitted). But if you meant 'how' differently, perhaps you could clarify what you want after looking around comp.lang.python and perhaps googling the newgroup archives. Terry J. Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: How is Python designed?
Limin Fu wrote: Hello, Is there any technical description on internet of how python is designed? Or can somebody give a short description about this? I'm just curious. Do you mean the structure and design of the language, or the process of designing the language? Well, in either case, you'll probably find your answer at http://www.python.org Take a look at the Docs -> Language Reference and PEP sections. -- Timo Virkkala -- http://mail.python.org/mailman/listinfo/python-list
