luthfan's Blog

Working further on restriction type check (9th week)

luthfan
Published: 08/13/2022

What I did this week

Continuing on the restriction's work from last week, I implemented more support for restriction check on both generic function definition and generic function call. So let's say we have the following function:

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

def f(x: T) -> T
  print(x)
  x = 0
  return x

f(1)
f('a')

For the function definition, the assignment x = 0 would check whether the type of x supports zero assignment (SupportsZero) or not. In this case, it does, so it passes the type check.

For the first function call, because 1 is an integer, it is possible to reassign it with zero. But in the second function call, the character a cannot be reassigned with the number zero. The type check considers this and reject the second function call.

What is coming up next week

1. Access the current restriction design on ASR level
2. Provide more flexible support for generic array

Did I get stuck anywhere

I'm currently a bit confused on how to make a decision for the restriction design on the ASR level. My mentor has provided some high-level design that we want to realize in LPython, but I have not grasped the concrete design yet. I will consult on this matter with my mentor ASAP.

View Blog Post

Next step, adding restriction (8th week)

luthfan
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

print(f(1,2))
print(f("a","b"))

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.

View Blog Post

Adding more generic examples (7th week)

luthfan
Published: 07/31/2022

What I did this week

- Generic array types

I added support for generic array types. In the following simple example, T[:] signifies the type of one-dimensional array T.

T = TypeVar('T')

def f(lst: T[:], i: T) -> T:
    lst[0] = i
    return lst[0]

It is then possible to have different function calls involving different types of arrays:

f([1],2)
f([1.0],2.0)

To implement this, the type substitution checks between the formal parameter lst: T[:] and the argument [1] (i32[:]) match the type parameter T with i32 and to also check that the dimensions are equal.

- Merging TemplateFunction with Function

To distinguish generic functions from functions, I added a new syntactic construct TemplateFunction into LPython's intermediate representation ASR. However, this construct appears to be unnecessary and can be handled by the original Function construct by adding another field where type parameters are stored.

On a separate PR, I removed TemplateFunction from the grammar and modified the definition for Function.

What is coming up next week

There are tests that the compiler does not yet pass. So I will have to solve those first.

Did I get stuck anywhere

There was no issue specifically this week.

View Blog Post

Completing the generics early prototype (6th week)

luthfan
Published: 07/23/2022

What I did this week

I completed an early prototype of generic function support in LPython. Given the following simple generic function and its function calls:

T = TypeVar('T')

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

f(1,2)
f('a','b')

The compiler can correspondingly instantiate two functions each for the integer call f(1,2) and character call f('a','b'). The function body is properly generated for the instantiated functions.

Further, the program can also be compiled into LLVM. This is done simply by ignoring the type parameter declaration T = TypeVar('T') as well as the functions involving type parameters.

For reference, all my progress is still kept as an open pull request. This will be merged once we finalize the overall design of generic functions.

What is coming up next week

1. Making decisions on the design for generic functions.
2. Making other examples and adding support for other statements and expressions for generic functions.

Did I get stuck anywhere

While rebuilding the body of the instantiated functions from the generic function, I met more problems with the ASR (LPython's intermediate representation) verification. One particular issue was that it was impossible to understand the problem simply by looking at the structure of the generated ASR. I solved this issue by looking at the other existing visitor classes that also build function bodies and try to mimic their process.

View Blog Post

Getting the generated ASR for generic functions (5th week)

luthfan
Published: 07/15/2022

What I did this week

Following on the suggestion from my mentor, I reimplemented the generic function instantiation to use the already existing visitors within LPython compiler. My mentor also helped with some issues with the ASR verification which we solved by adding verification support for the constructs I added into the ASR.

This week I also worked on including another important missing piece of the instantiated generic functions, the function body.

What is coming up next week

1. Finishing up the function body of instantiated generic functions.
2. Work on LLVM compilation support for the generic functions.

Did I get stuck anywhere

I was not aware of the verification step for the ASR during the compilation and my mentor explained and helped with the implementation.

View Blog Post