[pypy-dev] Re: Notes on compiler package

[Armin Rigo]

Hello Jeremy,

On Thu, Jan 23, 2003 at 11:20:35AM -0500, Jeremy Hylton wrote:
> I believe the stack depth computation is still pretty bogus, although
> Mark Hammond did a good job of getting it mostly correct.

I suddenly realize that I've got a toy that can be modified in 10 minutes to 
compute the stack depth with very little chance of a complex bug sneaking in.  
(Sorry, I don't have it right under my hand.)

The toy is the main loop of a Python interpreter in Python (which some of us
already worked on for fun, with a Frame class and with a method for each of
the opcodes).  In other words, we (the PyPython project) don't need to worry
abot computing the stack depth with data flow analysis or whatever because our
project will automatically produce such a tool for free!  That's "abstract
interpretation".

To explain what I have in mind, let me first describe the PyPython main loop.  
First let me insist again on the separation between interpreter-level objects
and application-level objects.  Imagine that the stack in the interpreter is
maintained as a list, and that at some point in the interpretation the stack
contains the integers 1, 2 and 3.  Then the stack list must *not* be the list 
[1, 2, 3].  That's the point I already discussed: it must be a list of three 
*complex objects* that represent the application-level integers 1, 2 and 3.  
For example, it could be [PyInt(1), PyInt(2), PyInt(3)], where PyInt is one of 
our custom classes.  To show the confusion that would araise from a stack that 
would really contain [1, 2, 3], try to see how the interpreter should 
implement type()!  You cannot.  But it is trivial to add an ob_type() method 
to the PyInt class.

Now to the point.  If you take the same Python code that implements the main
loop and all the opcodes, but you *replace* PyInt, PyStr, etc. with a trivial
empty class Placeholder, you get an abstract interpreter.  Running it against
a real code object, you will see the stack evolve with no real objects in it.  
For example, at the point where the stack could have hold [PyInt(1), PyInt(2),
PyInt(3)], now it is just [Placeholder(), Placeholder(), Placeholder()].

So what we need to do to compute the stack depth is interpret the code object
once.  On conditional jumps, we "fork", i.e. we try both paths.  When we jump
back to an already-seen position, we "merge", i.e. we keep the longest of the
previous and the current stack for that position.  When this process finishes,
we know exactly how long the stack can be at each position.

Note that the same technique can be extended to make a bytecode checker that
can prove that an arbitrary bytecode is correct, in the sense that it will not
crash the interpreter.  This is what I was trying to do in my toy code.

What's interesting here is that there seems to be a general pattern about
re-using the Python-in-Python main loop.  Psyco also works like this, only
merging is more subtle.  In all the cases (regular interpretation, stack depth
computation, bytecode checking, Psyco) the PyPython main loop is *exactly* the
same; the things that change are:

* the implementation of PyInt, PyStr, etc.  For regular interpretation it is
implemented with a real int, str, etc. object.  For stack depth it is a dummy
placeholder.  For Psyco it is a more complex structure that can tell apart
run-time and compile-time values.

* how we do forking.  The (generic) JUMP_IF_TRUE opcode could be written with 
something like:

    def JUMP_IF_TRUE(self, arg):  # self=frame, arg=offset to jump target
        v = self.tos()            # top-of-stack object
        if v.istrue():
            self.next_instr += arg  # jump forward by 'arg'

The meaning is clear in the case of regular interpretation.  For stack depth
computation, the istrue() method does some magic: it forks the current frame
and returns twice to its caller, once returning 'false' so that JUMP_IF_TRUE()  
will continue to inspect the 'false' branch, and later returning 'true' to
inspect the other branch.  Yes, returning twice from a call is what
*continuations* are for.  No, Python has no such notion.  Yes, Stackless would
be very handy there.  No, I'm not suggesting that we are stuck to enhancing
CPython or switching to an altogether different language that has
continuations.  PyPython core should at some place be translated to other
languages automatically; this translation can write continuation-passing-style
functions if needed (in C or again in Python!).

* finally, merging is important in all but the regular interpretation case, to
detect when we reached a point that we have already seen.  That's some action
that must be done at regular interval, between two opcodes.  So if PyPython
contains a "poll()" call where CPython contains the regular-interval checks,
we can implement poll() to do whatever is required for the intended usage of
PyPython, e.g. poll the Unix signals for regular interpretation, or merge for
the stack depth computer.

I hope you are convinced now that the interpreter stack must not be [1, 2, 3]
:-)


A bientôt,

Armin.