[Python-3000] Type Comparisons with Godel Numbers

Guido van Rossum guido at python.org
Fri Apr 21 13:31:19 CEST 2006


This seems a good idea to remember when we get to that point.

But let me point out that the key concern I have about the expense of
type checking is what would be done when unchecked code calls a
function with type-checked arguments. If I have some utterly dynamic
code that comes up with a list of a million ints, and then I pass that
as an argument to a function that requests the argument type is
list[int], then I don't see how we can prevent the cost of doing a
million checks to ensure that each and every item in the list is an
int; either we do it all at once at the call site, or we amortize the
cost over the lifetime of every list object, whether or not it is ever
going to be used in a typechecked call. Neither sounds very
attractive, and AFAICT your approach doesn't solve this particular
issue.

--Guido

On 4/21/06, Birch, Bill <birchb at anz.com> wrote:
> With reference to the last Gfdl blog on type checking (http://www.artima.com/weblogs/viewpost.jsp?thread=87182). There is concern that type comparison at runtime using objects will be quite expensive, so this posting is about optimisation.
> An idea is to compute a single canonical string which summarizes the _structural_ type of something. Think of it as a Godel number for the type. (http://diary.carolyn.org/godel2.html) Well not actually a Godel number, since they are very expensive to calculate and large. But close. Lets call them "type Godel strings" with the following properties:
> * the godel string for identical types will be equal
> * the godel strings for common types are small and very fast to compare.
> * godel strings are stateless and serializable
> You may have experienced something similar in C++ name mangling. (http://en.wikipedia.org/wiki/Name_mangling) There is an algorithm for creating a string from a type. However we are not proposing to mangle anything :-)
> Here are C++ name mangling examples:
>    void h(int, char) // is mangled to:  _Z1hic
>    void h(int) // is mangled to: _Z1hi
> For Python types we do not need the names so we would have something like:
>    h(int, str) -> void   -  '1is'
> I don't want to guess what the strings would look like.  The algorithm design could use some kind of statistical analysis to come up with an optimally short encoding. Huffman maybe?
> Type comparison operators would only need a deep inspection of the types when the godel strings don't match. If most comparisons will be an exact match (not a subtype) the lookup should be faster. My hunch is that in real systems, exact matches will be very common. Some statistical work on real programs would be a good idea... The subtype operator would do:
>    if object_type.godel() == required_type.godel():
>                      # fast string comparison
>       # exact match so OK proceed
>    else:
>       if object_type <: type :  # slow to execute
>          Yes proceed.
> Godel strings would be cacheable. The type comparison operators could be memoized to store the type-subtype lattice, not as a lattice of type objects, but as a lattice type godel strings. The cache would also be able to remember relationships between types for which the original type expression objects have been deleted.
> This idea implies that every type object in Python must provide a godel() method as a standard.
> Individual value objects could (provided they were immutable) cache their type's godel string accessible from a godel() method. This would speed up type comparison, since the type checking may not need to visit every sub- component of the object. Mutable objects would see little benefit, since its type can change with every update. At best this plan optimises away the analysis of the required type, but not the mutable instance to be compared.
> The idea also requires that type expressions be immutable, which is probably not a bad thing anyway. What possible use could there be for a mutable type expression?
>
> _______________________________________________
> Python-3000 mailing list
> Python-3000 at python.org
> http://mail.python.org/mailman/listinfo/python-3000
> Unsubscribe: http://mail.python.org/mailman/options/python-3000/guido%40python.org
>


--
--Guido van Rossum (home page: http://www.python.org/~guido/)


More information about the Python-3000 mailing list