Articles on luthfan's Blog

Generic function support for LPython - Report

luthfanlubis@gmail.com (luthfan) — Thu, 08 Sep 2022 14:45:40 +0000

Overview

Project: Generic function support for LPython (https://github.com/lcompilers/lpython)
Organization: Python Software Foundation (LPython)
Mentors: Ondřej Čertík, Gagandeep Singh, Rohit Goswami
Contributor: Luthfan Anshar Lubis

Project Summary

Generics is a common functionality found in statically-typed programming languages to allow easier maintenance of programs with identical implementations but different type signatures. LPython, a statically-typed Python compiler does not yet support this. In this project, we introduce generic functions as functions with type variables; these variables are statically type-checked and made concrete when lower-level code is generated. To allow type checks for generic function calls, restrictions (similar to traits in Rust) are provided to ensure safety of type parameters.

Background

Programs in LPython are statically-typed, requiring type annotations by users. They are first compiled into Abstract Semantic Representation (ASR), an intermediate representation that carries all the syntactic and semantic (including typing) information of the programs. From this IR, the programs are further compiled to lower level languages such as C and LLVM.

Another important feature of LPython is ensuring that programs for LPython can also be run in CPython.

Implementation

The project will be explained through several phases:

1. Introducing type variables

The first phase of the implementation was adding syntax support for type variable declarations. On the Python level, we rely on TypeVar provided by Python 3. On the ASR level, I added a new kind of type for expression called TypeParameter. This allows the declaration of the following function:

T = TypeVar('T')

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

The arguments and return value of the function add are typed with a TypeParameter on the ASR level.

Simple checks on the type variable declarations are also implemented. First, ensuring that a type variable declaration is unique. Second, ensuring that a function can only be typed with an already declared type variable.

Related blog posts:

Adding type variable support to LPython, link: https://blogs.python-gsoc.org/en/luthfans-blog/adding-type-variable-support-to-lpython-1st-week/
Dealing with conflict and ASR, link: https://blogs.python-gsoc.org/en/luthfans-blog/dealing-with-conflict-and-asr-2nd-week/

2. Implementing generic function instantiation

A big leap from the first phase, I implemented a working generic function instantiation that can be compiled to LLVM and can be run, but still without type checks.

Using the example from the previous phase, it is now possible to have the following code:

T = TypeVar('T')

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

print(add(1,2))
print(add('a','b'))

The two function calls add(1,2) and add('a','b') instantiate the function add into two different functions on the ASR level, each with different type signatures. If we were to express it with Python syntax, we would have:

def __lpython_generic_add_0(x: i32, y: i32) -> i32: ...
def __lpython_generic_add_1(x: str, y: str) -> str: ...

Here, i32 represents 32-bit integer and str represents string.

At the same time, the function calls themselves are correspondingly renamed into:

print(__lpython_generic_add_0(1,2))
print(__lpython_generic_add_1('a','b'))

At the function call site, the consistence of the type substitution between the arguments types (i32 or str) with the type variables (T) is also checked. The function call add(1,'a') is rejected.

To allow compilation to LLVM, the generic function (add) is ignored while the instantiated functions (__lpython_generic_add_0, __lpython_generic_add_1) and renamed functions calls are compiled normally with the existing compilation.

This step particularly took a long time due to several reasons. First, the lack of familiarity with the already existing tools within LPython that can be utilized for function instantiations. Originally I started with a function instantiator that I personally defined, although later on finding out from one of the mentors about an ASR duplicator. Second, we did not start with a concrete design for the ASR grammar. This resulted in a couple iterations on the grammar for generic functions.

Related blog posts:

Instantiating generic functions Into valid functions in ASR, link: https://blogs.python-gsoc.org/en/luthfans-blog/instantiating-generic-functions-into-valid-functions-in-asr-3rd-week/
Revisiting function generation, link: https://blogs.python-gsoc.org/en/luthfans-blog/revisiting-function-generation-4th-week/
Getting the generated ASR, link: https://blogs.python-gsoc.org/en/luthfans-blog/getting-the-generated-asr-for-generic-functions-5th-week/
Completing the generics early prototype, link: https://blogs.python-gsoc.org/en/luthfans-blog/completing-the-generics-early-prototype-6th-week/

3. Adding necessary functionalities and handling ASR changes

I added support for Array and List types, along with corresponding examples where these types are used.

I also added support for generic Subfunction (functions without return values). However, during the implementation, the main branch of LPython made a change and combined both Function and Subfunction, requiring modifications on the generic functions support.

Related blog posts:

Adding more generic examples, link: https://blogs.python-gsoc.org/en/luthfans-blog/adding-more-generic-examples-7th-week/

4. Adding hard-coded restrictions for type variables

The next step is adding a mechanism to type check generic function calls and operations involving values with type variables. Consider again the add program, there was no check on the operation x+y against the arguments with type T. There was also no type check on add(1,2) to make sure that the arguments 1 and 2 can handle the operation inside add.

As the first approach to this, I added restrictions on the type variable declarations. The restrictions I added were SupportsPlus, SupportsZero, and Divisible. These restrictions are hard-coded in the way that they are hard-coded into the compiler to be associated with specific computations. With restrictions, type variables declarations become:

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

The restriction SupportsPlus is associated with addition between integer, real, and string. However, it only supports addition between same typed arguments.

With these restrictions, it is possible to check whether the generic operation x+y is safe by checking the restrictions on the type variables associated with both arguments. It is also possible to check whether add(1,2) is safe by checking that 1 and 2 are typed as integers which does support addition.

Related blog posts:

Next step, adding restriction, link: https://blogs.python-gsoc.org/en/luthfans-blog/next-step-adding-restriction-8th-week/
Working further on restriction type check, link: https://blogs.python-gsoc.org/en/luthfans-blog/working-further-on-restriction-type-check-9th-week/
Extending restriction and handling ASR changes, link: https://blogs.python-gsoc.org/en/luthfans-blog/extending-restriction-and-handling-asr-changes-10th-week/

5. Designing and implementing user-defined restrictions

The above approach to restrictions does handle type check on operations, but limit them to only those hard-coded into the compilers. We require a mechanism that can allow users to freely define restrictions according to need.

To illustrate this, let us consider a different generic function meanthat takes a list of T as arguments and calculate the mean value of the elements in the list:

def mean(x: list[T]) -> f64:
    k: i32 = len(x)
    if k == 0:
        return 0.0
    res: T
    res = 0.0
    i: i32
    for i in range(k):
        res = res + x[i]
    return res/k

Several computations are made on the variable res with type T. A zero assignment, an addition, and a division. To type check the body of mean, we can abstract the computations as restrictions, expressed as body-less functions.

@restriction
def zero(x: T) -> T:
    pass

@restriction
def add(x: T, y: T) -> T:
    pass

@restriction
def div(x: T, k: i32) -> f64:
    pass

def mean(x: list[T], **kwargs) -> f64:
    k: i32 = len(x)
    if k == 0:
        return 0.0
    res: T
    res = zero(x[0])
    i: i32
    for i in range(k):
        res = plus(res, x[i])
    return div(res/k)

Then, the function calls can assign specific functions that will take over the place of these restrictions (add, zero, div).

print(mean([1,2], zero=int.__zero__, add=int.__add__, div=int.__div__))
print(mean([1.0,2.0], zero=real.__zero__, add=real.__add__, div=real.__div__))

The assignment between a restriction (eg. zero) and a function (eg. int.__zero__) is also checked by making sure if the type substitution remains consistent or not.

Related blog posts:

Designing user-defined restrictions, link: https://blogs.python-gsoc.org/en/luthfans-blog/designing-user-defined-restrictions-11th-week/

Result

I have completed a prototype implementation for LPython. The implementation is strongly type-checked (strong concept) by using restrictions to define computations on type variables. Type-checked generic function calls are compiled into ASR then LLVM.

Future Work

- More complicated generic functions, such as recursive generic functions and nested generic function calls will require some modifications on both type checks and function instantiations
- Designs can be further simplified to avoid defining similar restrictions

Designing user-defined restrictions (11th week)

luthfanlubis@gmail.com (luthfan) — Mon, 29 Aug 2022 18:29:44 +0000

My apologies for posting this very late.

What I did this week

1. Merged the hard-coded restrictions

After making some fixes on the implementation, I had the hard-coded restriction that I explained in the previous post merged.

2. Designed user-defined restrictions

Ultimately, the restrictions on type parameters that we want for LPython is one that users can freely defined according to need. While the hard-coded restrictions can support generics to a certain degree, it cannot handle the various functions that users may define.

Take the mean example from the previous week. With user-defined restrictions, it turns into:

T = TypeVar('T')

@restriction
def zero(x: T) -> T:
    pass

@restriction
def plus(x: T, y: T) -> T:
    pass

@restriction
def div(x: T, k: i32) -> f64:
    pass

def mean(x: list[T]) -> f64:
    k: i32 = len(x)
    if k == 0:
        return 0.0
    res: T
    res = zero(x[0])
    i: i32
    for i in range(k):
        res = plus(res, x[i])
    return div(res, k)

With the hard-coded restrictions, the mean function is limited to handling numbers. However, with user-defined restrictions, it would be possible to pass arguments of any types as long as they have the restriction functions plus, zero, and div provided.

What is coming up next week

I have to conduct a meeting with my mentor and evaluate the current design for user-defined restrictions. Then iterate again on the designs based on the meeting.

Did I get stuck anywhere

I did not have any issue this week as I was freely designing the grammar for the restrictions.

Extending restriction and handling ASR changes (10th week)

luthfanlubis@gmail.com (luthfan) — Sun, 21 Aug 2022 05:26:15 +0000

What I did this week

1. Adding more types of hard-coded restrictions

Again, continuing from last week's work, I added more types of restrictions for type parameters.

Currently there are four restrictions: SupportsZero, SupportsPlus, Divisible, Any. These restrictions are hard-coded into the compiler's frontend, meaning that each restriction is essentially associated with specific basic types available in LPython. For example, a type parameter restricted to SupportsZero has to be of type Integer or Real.

With these restrictions, it is possible to have the following generic function:

T = TypeVar('T', bound=SupportsPlus|SupportsZero|Divisible)

def mean(x: list[T]) -> f64:
    k: i32 = len(x)
    if k == 0:
        return 0.0
    sum: T
    sum = 0
    i: i32
    for i in range(k):
        sum = sum + x[i]
    return sum/k 

print(mean([1,2,3]))
print(mean([1.0,2.0,3.0]))

Given the restrictions, any function instantiation is only required to check against the generic function's signature.

2. Handling ASR changes

The ASR design was recently changed so that Subroutine (function without return values) is merged into Function. Therefore I had to make modifications when adding generic functions and subroutines into the symbol table. This was done in PR #957 and has been subsequently merged.

What is coming up next week

1. Finalize the current hard-coded restrictions and have it merged
2. I did not have the time to handle arrays last week, so hopefully I can work on adding more support for generic arrays next week

Did I get stuck anywhere

This week was smooth sailing, although it took some iterations to have a clean pull request for supporting generic subroutines.

Working further on restriction type check (9th week)

luthfanlubis@gmail.com (luthfan) — Sat, 13 Aug 2022 11:26:49 +0000

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.

Next step, adding restriction (8th week)

luthfanlubis@gmail.com (luthfan) — Tue, 09 Aug 2022 07:06:49 +0000

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.

Adding more generic examples (7th week)

luthfanlubis@gmail.com (luthfan) — Sun, 31 Jul 2022 04:38:17 +0000

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.

Completing the generics early prototype (6th week)

luthfanlubis@gmail.com (luthfan) — Sat, 23 Jul 2022 11:26:08 +0000

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.

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

luthfanlubis@gmail.com (luthfan) — Fri, 15 Jul 2022 15:17:33 +0000

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.

Revisiting function generation (4th week)

luthfanlubis@gmail.com (luthfan) — Mon, 11 Jul 2022 01:57:40 +0000

What I did this week

I'm afraid there is not much progress this week because I've been visiting relatives. I've improved the function generation implemented last week.

What is coming up next week

Finishing up the initial example case for generics. This means getting an ASR without triggering any errors.

Did I gets stuck anywhere

I had a personal meeting with my mentor to discuss the progress far and I found a simpler way to implement the work than what I am doing right now.

Instantiating generic functions into valid functions in ASR (3rd week)

luthfanlubis@gmail.com (luthfan) — Fri, 01 Jul 2022 07:42:00 +0000

I made some good progress this week in handling generic functions on LPython's ASR level.

What I did this week

I managed to get the type parameters in the generic functions to be instantiated by different function calls. Currently, I'm working with a very simple function f that can take two values x and y of type T and returns a value of type T.

T = TypeVar('T')

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

This function is called in two different places with different types. First with integers, second with floats.

print(f(1,2))
print(f(1.0,1.0))

This week I managed to have each function call generates a new overloaded function for f. It also checks the consistencies of the assigned types and the type parameters.

What is coming up next week

Next I have to also handle the function calls themselves, because they technically are calling overloaded functions. LPython actually have already supported function overloading, so what I need to do is to learn the compiler and apply that overloading to these generic function calls.

Did I get stuck anywhere

Nowhere especially for this week.

Dealing with conflict and ASR (2nd week)

luthfanlubis@gmail.com (luthfan) — Fri, 24 Jun 2022 14:07:56 +0000

Hello again, here's a quick update on my second week with LPython!

What I did this week

It turned out that there were conflicts between my last week's work and the project's upstream, so the first thing I did this week was resolving that conflict. I also found another issue with existing integration tests, so some changes had to be made to make it possible for my work from last week to be submitted.

I also spent time to understand the differences between two AST visitors that build the ASR: a visitor that builds the symbol table and a visitor that transforms the statements.

What is coming up next week

I want to start implementing support to allow the following function declaration with type parameters:

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

Did I get stuck anywhere

I didn't exactly understand the cause of the conflict at the beginning, but consulting with my mentor solved that issue.

Adding type variable support to LPython (1st week)

luthfanlubis@gmail.com (luthfan) — Sat, 18 Jun 2022 13:58:22 +0000

Hello, here is a quick update of my first week with LPython project!

What I did this week

Unfortunately due to a personal issue, I had a very late start. I could not start until Thursday. Spent the day to reintroduce myself to the project and finally started making progress on Friday.

As planned, the first week was to give support for Python's type variable declaration T = TypeVar('T'). The syntax was already extended, so that's a okay. What I had to do then was to support the type variable in the underlying ASR (Abstract Semantic Representation) into which the Python AST will be translated. By the way, ASR is an IR from which we compile the program into lower languages like LLVM.

To do so, what I did was adding a new kind of type to the underlying ASR, the type variable. Then, while scanning through the AST, the type variable declaration T = TypeVar('T') is converted into a variable that is typed with an ASR type variable and then placed into the symbol table of the program, so that later on functions can identify these variables as type variables.

Slight note though, since I'm messing around with the ASR, the code generation for these type variables have to also be added later on.

What is coming up next week

Next week I will have to handle functions with type parameters. One important issue would be how to handle the type check on these functions, because they can't be type checked as usual where the base types are all present.

Did I get stuck anywhere

I was confused on whether to approach the issue by tinkering with the AST or going straight to ASR. However, since the ASR has many utilities for handling symbol table, I decided to go straight with ASR.