Next step, adding restriction (8th week)

Published: 08/09/2022

What I did this week

1. Merged the generic function implementation

After drafting it for quite sometimes and solving the conflicts with the main branch, we finally have the prototype implementation for generic function merged into LPython (PR #900).

The array support that I mentioned in a previous post was also merged into LPython (PR #907). Unfortunately, although generic arrays work in LLVM, it does not yet work with CPython due to incompatible usage of TypeVar.

2. Worked on restrictions for type variables

The prototype implementation mentioned above would type check every function instantiated by a generic function call, which would slow down the compilation time. Ideally, we want a generics type system that only requires checks on the function call arguments.

To do so, I worked on adding restriction for type variables. An example we have right now is as follows:

from ltypes import TypeVar, SupportsPlus

T = TypeVar('T', bound=SupportsPlus)

def f(x: T, y: T) -> T:
    return x + y


Where SupportsPlus is a restriction. This denotes that the any argument that will substitute the type variable T must support the plus operation.

The type check is executed in the following two steps:

1. Check the function definition. If a generic parameter (x: T) is used for a certain operation O, then we have to check if the restriction R on T satisfies operation O.
2. Check the function call. If the argument substitutes a parameter with type
T and restriction R, we have to check if the actual type of the argument satisfies that restriction.

What is coming up next week

Continue working on restriction. Currently I have had only implemented a very simple type check on the generic function definition with restriction. Next would be implement type check on the generic function calls.

Did I get stuck anywhere

There were some conflicts with the main branch that I personally could not solve. These conflicts kept my PR from being merged. It turned out to be a section that I changed without properly cross-checking with the main branch. Thankfully, with the help of both my mentors it was solved right away.