PyPy and Type Inference.notes

Saturday, March 26, 2005

TITLE OF PAPER: PyPy and Type Inference
URL OF PRESENTATION: _URL_of_powerpoint_presentation_
REPRESENTING: _name_of_the_company_they_represent_

DATE: March 23. 2005
LOCATION: Marvin auditorium

{If you've contributed, add your name, e-mail & URL at the bottom}

PyPy Status
    Python implementation, quite complete/compliant
    Can do interesting things that CPython cannot
        like implement thunks

How does PyPy work?
    Interpreter - works with black boxes
    Object space - answers queries from the interpreter about the black boxes
    We can plug in a different object space to change data semantics
    (the interpreter's semantics are unchanged)
    Delayed/thunked interpretation is achieved by inserting a "proxied" object space
    This also allows abstract interpretation using the proper object space
        object space produces flow graphs

On to the new stuff...

Staticness conditions
    Do whatever Python magic you want at "boot"(import) time
    After that behavior must be static
        then no more dynamic function/class creation
        constant globals
    Can use exceptions

In PyPy, a type means a set of objects

[demonstration of type annotation using abstract interpretation object space ]
    "Naive" forward propagation of types to find types of variables in the space
        Ends up with a list of possible types for the variable
        May need to do fixed point computation of possible types (in loops/recursion)

    Analyzes the pre-initialized program in-memory
    No user annotation required!
    Full-program analysis tool
    Mostly language-independent
    Some other restrictions on types

So, in essence, you first load up your Python proggie, do whatever black magic you
    want--dynamically add functions, import weird things, generally raise Cain--and
    then you run PyPy over it, and it infers types based on the state of the bytecode.
Sound right?
Except for "bytecode". His point is that this is done via "abstract interpretation" and
    thus is not dependent on things like bytecode.
What's it "interpreting", then?
The interpreter is interpreting Python/bytecode/whatever, but the analysis happens due
    to the abstract object space.
This stuff may be worthy of a question.
Aha! From the abstract of this talk: "Python programs and then compile them to various lower-level languages (currently C, Lisp, Pyrex and Java). This analysis works on fully standard Python sources (bytecodes, actually), and the distinguishing feature of the techniques we use -- "abstract interpretation" -- is to allow type inference to be performed for any language for which we have an interpreter."
Is there an easier way to hard-wrap paragraphs in SubEthaEdit?

Compare to:
    decoration-based declarations
    limited syntax extension (Brett Cannon, next talk)
    full program analysis (starkiller)

Related tools
    Psyco (fully run-time)
    dot + custom PyGame app for call graph building and viewing

PyPy's type model
    primitive types (int, float, etc.)
    tuple list dict iter
    prebuild constants
    class, instance

Code Generation
    Can generate Pyrex (shown last year)
    Can generate a C extension module (slow, like Python2C)
    can do Common Lisp / Java / LLVM, etc

Next Steps
    Generate C code that uses the annotations (good C code)
    Java, for object model (Python on JVM)
    LLVM in development (Carl Friedrich Bolz)

    PyPy CPython-compliancy: OK
    PyPy on top of CPython: nice but too slow (4000 times slower)
    Type inferencing tools: OK
    Infer types in PyPy source: OK
    Generate fast typed code : next step

REFERENCES: {as documents / sites are referenced add them below}


CONTRIBUTORS: {add your name, e-mail address and URL below}

Ted Leung <>, <>
Erik Rose <>
Abhay Saxena <>

E-MAIL BOUNCEBACK: {add your e-mail address separated by commas }

A headline (like a field in a database) will be CAPITALISED
    This differentiates from the text that follows
A variable that you can change will be surrounded by _underscores_
    Spaces in variables are also replaced with under_scores
    This allows people to select the whole variable with a simple double-click
A tool-tip is lower case and surrounded by {curly brackets / parentheses}
    These supply helpful contextual information.

Copyright shared between all the participants unless otherwise stated...