[pypy-dev] Full Python Annotation

[Armin Rigo]

Hi Adam,

On Fri, Nov 25, 2005 at 10:13:25AM -0700, Adam Olsen wrote:
> Notes for description of value annotator

I know that you expect some answer, but there is really not much that we
can discuss about so far.  The notes you present are interesting but
they don't really touch the problems particular to Python.

This is similar to existing approaches (Samuele posted some links on
IRC), with aggressive specialization to get very precise results like
integer ranges.  I agree that, done right, this range analysis can prove
that many usages of integers in a program cannot actually overflow; I've
seen papers that got good results because user programs typically looked
like:

i = 0
while i < len(container):
    ...
    i += 1

The addition here cannot overflow, because i < len(container) <=
sys.maxint so that i+1 <= sys.maxint.

The problem, though, is that this kind of consideration is not what we
are interested in for PyPy.  A more interesting problem to consider
would be the unusual Python object model, where the position in the
class hierarchy of instance attributes is not declared.  However, we
already solved this one in our annotator.

If you target "full Python" (whatever is really meant by that), there
are many problems that we have mentioned to you already but that you
don't seem to start worrying about (and no, "exec" alone is not a
problem).  The more fundamental problems lie in that, on the one hand,
real-world programs build some of their own structure indirectly, and on
the other hand you cannot be sure that nobody is playing tricks.  There
are just too many tricks in Python to ensure that any type approximation
can be completely safe.  You would have to resort to expected-case
analysis and run-time guards or some kind of callbacks invalidating code
when things go out of hand at run-time.  None of that is impossible, but
none of that is straightforward either -- more precisely, I think that
this would easily swallow many "man-years" of work.  While *still* not
being what PyPy is about, discussing this kind of Python-oriented issues
here wouldn't be completely off-topic :-)

Instead of doing this, in PyPy we used the practical approach of RPython
to develop PyPy itself in, and then we are about to work on the JIT for
user code - "full Python" user code, as in "I type python xyz.py and I
get the expected result".


A bientot,

Armin