Handling Overloading

So we handle overloading through a unique object that has a specific type, a MultiType that is just a list of possible types.

Abusing from Multiype can quickly make the combinatorics of the type possibilities go wild, so we had to make a decision. Consider the following code:

def foo(x, y):
    return y in x

The in operator could be implemented as a MultiType, enumerating the possible valid signature (remember we know of all possible types in Pythran):

• Callable[[List[T0], T0], bool], a function that takes a list of T0 and a T0 and returns a boolean,
• Callable[[str, str], bool], a function that takes two strings and returns a boolean,

And so on, including for numpy arrays, but we'll comme back to this later and assume for now we only have these two types. So what is the type of foo? From the x in y expression, HM tells us that x can be a list of T0, and in that case y must be of type T0, or x is a string and so must be y. And in both cases, a boolean is returned.

We could consider both alternatives, follow the two type paths and in the end, compute the signature of foo as a MultiType holding the outcome of all paths. But that could mean a lot! What we do is an over-approximation: what is the common structure between List[T0] and str? Both are iterable, therefeore x must be iterable. Nothing good comes from T0 and str, and bool compared to bool results in a bool, so in the end foo takes an iterable and any value, and returns a boolean. That's not as strict as it could be, but that's definitively enough. However our type system is no longer sound (it does not reject all bad program).

In order to make it easier to perform this approximation, we chose a dedicated representation for containers. In our type system (oh, it's named tog by the way, so in the tog type system), containers are roughly described as a tuple of (name, sized, key, value, iter):

• a List[T0] is considered as (List, Sized, int, T0, T0)
• a Set[T0] is considered as (Set, Sized, NoKey, T0, T0)
• a Dict[T0, T1] is considered as (Dict, Sized, T0, T1, T0)
• a str is considered as (Str, Sized, int, Str, Str)
• a Generator[T0] is considered as (Generator, NoSized, NoKey, T0, T0)

As a consequence, an Iterable[T0], to be compatible with the over-approximation defined above, is a (Any, Any, Any, Any, T0).

Handling Option Types

When HM runs on the following Python code:

def foo(a):
    if a:
        n = 1
        range(n)
        return n
    else:
        return None

It runs into some troubles. The return from the True branch sets the return type of foo to int but the one from the False branch sets it to None. How could we make this unification valid? Option types are generally described as a parametric type, Optional[T0]. To be able to unify int and None, we would instead need to unify Optional[int] and None, thus marking n as Optional[int], which does not work, because range expects an int.

The solution we have adopted is to make type inference control-flow sensitive. When meeting an if, we generate a new copy of the variable environment for each branch, and we merge (not unify) the environments.

Likewise, if the condition is explicitely a check for None, as in:

if a is None:
    stuff()
else:
    return stuff(a)

the environment in the True branch holds the None type for a, and the int type in the False branch. This could be improved, as we support only a few patterns as the condition expression, there is something more generic to be done there.

This even led to improvement in our test base, as the following code was no longer correct:

def foo(x):
    v = x.get(1)
    return v + 1

Type inference computes that v is of type Optional[T0], which is not compatible with v + 1 and a PythranTypeError is raised. A compatible way to write this would be:

def foo(x):
    v = x.get(1)
    if v is None:
        pass  # or do stuff
    else:
        return v + 1

Handling Type Promotion

It's not uncommon to find this kind of code:

l = []
l.append(0)
l.append(3.14)

And there's nothing wrong with this in Python, but is this a type error for Pythran? In classical HM systems, that's a type error: [] is of type List[TO], list.append is of type Callable[[List[T0], T0], None] so unification sets T0 to int after first append, and fails upon the second append because unification between an int and a float fails.

Looking back in Python typing history, it seems that shedskin made the decision to consider it's not an error (see the blogpost announce on the topic. Several test cases of Pythran test suite would fail with a stricter typing, so let's try to achieve the same behavior as Shedskin, within HM.

The trick here is to consider a scalar as a tuple of four elements [0], one per scalar type we want to support. And then apply the following rule: the actual type of the scalar is the type of the first non variable type, starting from the lower index. Under that assumption,

• a bool is a (T0, T1, T2, bool)
• an int is a (T0, T1, int, T2)
• a float is a (T0, float, T1, T2)
• a complex is a (complex, T0, T1, T2)

When unifying an int with a float, regular unification yields (T0, float, int, T2) which is a float according to the previous definition.

If we want to enforce an int, say as argument of range, then we can define strict_int as (no-complex, no-float, int, T0) which still allows up-casting from bool to int but prevents up-casting from int to float.

Handling NDArray Type

numpy.ndarray is the corner stone of the numpy package. And it's super-flexible, allowing all kinds of broadcasting, reshaping, up-casting etc. Even if Pythran is far from supporting all of its features, it does support a wide set. The good news is that Pythran supports a lower version of ndarray, where the number of dimensions of an array does not change: it cannot be reshaped in place. For instance the C++ type returned by numpy.ones((10, 10)) is types::ndarray<double /*dtype*/, 2 /*nbdim*/>.

We've extended the typing module to provide NDArray. For Pythran, the Python equivalent of the above C++ type is NDArray[float, :, :].

And as we want it to be compatible with the way we defined an Iterable, an NDArray is actually a:

• List[T0] is considered as (List, Sized, int, T0, T0)
• Dict[T0, T1] is considered as (Dict, Sized, T0, T1, T0)
• ...
• NDArray[complex, :] is considered as (Array, Sized, T0, complex, complex)
• NDArray[complex, :, :] is considered as (Array, Sized, T0, complex, NDArray[complex, :])
• NDArray[complex, :, :, :] is considered as (Array, Sized, T0, complex, NDArray[complex, :, :])

That's a recursive definition, and that's pretty useful when used with our MultiType resolution. If we need to merge an NDArray[complex, :, :] and an NDArray[complex, :, :, :], we end up with (Array, Sized, T0, complex, (Array, Sized, T1, complex, T1)) which actually means an array of complex with at least two dimensions.

Acknowledgments

As usual, I'd like to thanks Pierrick Brunet for all his help. He keeps feeding me with relevant insights, criticisms and great ideas. Thanks to OpenDreamKit for sponsoring that work, and in particular to Logilab for their support. Thanks to Lancelot Six, w1gz and Nicolas M. Thiéry for proof reading this post too :-)

And last, I'm in debt to all Pythran users for keeping the motivation high!