[Python-3000] Type Comparisons with Godel Numbers

[Michael Chermside]

Building from Aahz's example, what you really want is a mechanism
for typechecking that any accessed elements are ints when dynamic
code generates a list of a million elements and passes it to a
function declared to take a parameter of type "list[int]". And
then make sure the following two examples have the desired
performance:

#
# Accesses only a small (but unknown) number
# of elements in the list, 'n'. Performance
# of typechecking should be O(n), which is far
# better than O(len(a)).
#
def few_accesses(a -> list[int]):
    i = 0
    while a[i] != 42:
        i += 1
    return i

#
# Accesses the list a large (but unknown) number
# of times, 'b'. Performance of typechecking should
# be O(len(a)), which is far better than O(b*len(a)).
#
def many_accesses(a -> list[int], b int):
    for i in range(b):
        for x in a:
            do_something(b, x)

It is easy for me to come up with an approach to optimizing
typechecking for each function, but analysizing code to decide
which is appropriate is right out, and it is difficult for me
to imagine a single approach that satisfies both. Perhaps
some super-clever technique that starts out wrapping accesses
but switches to pre-checking the entire list and then dropping
all wrappers once some threshhold of accesses has been reached?
That sounds WAY too clever and implicit... it's sure to cause
problems.

-- Michael Chermside