How is Python designed?

[Diez B. Roggisch]

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