Localized Type Inference in Python.notes

Wednesday, March 23, 2005

TITLE OF PAPER: Localized Type Inference in Python
URL OF PRESENTATION: _URL_of_powerpoint_presentation_
PRESENTED BY: Brett Cannon
REPRESENTING: California Polytechnic State University, San Luis Obispo

DATE: _date_of_your_conference_here_
LOCATION: _venue_and_room_in_venue_

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

Type Inferencing
    Tightest mapping of possible types to a variable
    Determined Statically
    Not allowed to make wrong inference
        compilation decisions based on this info

Can type inferencing be added to a python compiler for a performance increase?
    No semantic changes to language...

Review of type inference algorithms
        Standard ML / Haskell
        bottom up (W) or top down (M)
        allows abstract types
    Cartesion Product / Iterative type analysis
        Iteratively tries to find a fixed point where types don't change
        What Starkiller uses
        uses concrete types

The troublemakers

    The compiler
        Input of parse tree, output of bytecode
                bytecode typeless ...
        Problem: compiler does not check 'import' dependencies
            can compile code  that imports non-existent modeuls
            You can't depend on what is contained in external modules
    Problem: The language
        injection into global namespaces allow
        therefore an external module can change everything

The Other Problem

    An external module...
Bottom Lline
    everything at the global level must be considered unknown
    Can't infer squat!
    or can we?
Can infer

Atomic Types in Local Scope (no injection into local scopes)
    inference is specific to each block

[ demonstration of algorithm on if statement ]
[ demonstration of algorithm on loops ]
[ demonstration of algorithm on try/except/finally/else]

Type Annotations (optional)
    for functions or methods
    stored in 1st line of comment for a function
    completely optional
    basically type hints to the annotator

Other Tidbits
    supported closures (presumably he means nested scopes)
    highest accuracy for 'try' block not done
    contents of tuples left unknown
    didn't detect 'break' statements when 'else' is present

Introduce New (type specific) opcodes
    Done by annotating large programs and seeing what could be successfully annotated

New Opcodes
    [Name, Replaces, Speedup]

    SpamBayes - slowed down
    Pyrex (with/without annotations) - base = 1%, annotated = 1.6%
    PyBench -- (both sped up and slowed down)
    Parrotbench (with/without annotations)

It ain't worth it!
(python is so dynamic, it's really really hard)
at least at the bytecode/VM level (it may be different compiling to assembly or C)
At least at local level -- know a lot more globally.

Changes that could help
    unsimplify implementation
    timestamp/checksum import dependencies


Q: Jim: couldn't type for contents of list and dict?
A: multiple ways to get to dict that I wouldn't know about, would hose it

Q: Can detect people injecting themselves into the global namespace?
A: Probably (?): would have to be very sophisticated. Other issues is doing something good with them.

Q: Did you try to infer types of attributes?
A: people could change attrs af a class

Q: Can you detect at runtime if types of attributes can be inferred?
A: keep track of types things tend to hold at runtime, but it is possible

Q: Martin: did you detect type errors?
A: yes, you could detect type errors. int + string can be detected, for example.

Q: synthetic benchmarks?
A: no, I just ran the four major apps, to keep it in the realistic realm.

Q: LLVM instead of our own interpreter?
A: have no experience

Q: Michael Salib (Starkiller): is thesis online?
A: it will be, will be on python-announce, done in April.

Q: Jakob Hallen (PyPy) if you could trust there is no injection from external modules, how much inference could you do?
A: If nothing was injected, ... you could definitely tell what functions would return, as long as they were defined in the module

Q: Raymond Hettinger Gain: assumption: not ... namespace; make (?) constant (goal - limit global injection)
A: No, I didn't. Type annotation turned out to be useless.

Q: Did you use the return types of any of the built-ins (e.g. range)?
A: no, because I assumed they'd be overwritten by someone in the global namespace.

Q: Do you have an empirical sense of how often people inject things into the global namespace to change the type signature? (We do it to make things threadsafe, but we don't change the type signature.)
A: personally, I doubt very often, but ... overwrite builtins with global keyword or ...

Q: I see new python coders using "type" or "dict" as a variable all the time.

(I assume a gross hack :-)

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


CONTRIBUTORS: {add your name, e-mail address and URL below}
Ted Leung <twl@sauria.com.
Abhay Saxena <ark3@email.com>
Chris Shenton <chris@shenton.org>

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...