GSOC 2022 - LFortran - Implementing Generics
GSOC 2022 - LFortran - Implementing Generics
Final report - Oshanath Rajawasam
Mentors : Ondřej Čertík, Gagandeep Singh
Overview
This project was about implementing generics for LFortran. This project was implemented parallelly to the same project on LPython, so a lot of the same code is reused. The LPython counterpart was developed by Luthfan Lubis and it has progressed further than this project.
Reason for the Project
Functions and subroutines in Fortran have specific parameter types and return types associated with them. Since LFortran, at its core, is the same as Fortran, this is also the case for LFortran. This can be problematic when the application demands template-like structures. For example, when implementing a function to add 2 numbers, with current tools available, we would have to implement the same function for all data types it is intended to be used. But with templates, we can define the function once, and use it with any data type we wish.
The solution in a nutshell
LFortran works by parsing the code and creating a tree structure called AST, or abstract syntax tree, where no semantic meaning is held, but just the syntax. The AST is then visited one by one, and the ASR, or abstract semantic representation, is created, where all semantic meaning is generated. This ASR is then passed to the LLVM backend.
My work in this project was limited to the syntax and the semantics of the compiler. So it ranged all the way from parsing new language features, such as new keywords, creating new AST nodes and generating ASR nodes from it.
The overall idea is that, when a generic function is declared, we create an ASR node for that, with generic operators such as "TemplateBinop" included. When that function is instantiated, we use that generic function to create concrete instances of it, and add it into the ASR.
I have described below, several phases of the project.
Most of my work and progress is in a single Pull Request. That is because we have created some draft PRs that were never merged. All the functionality was in this single PR.
1. Introducing Template Syntax to the language
module swap_m
implicit none
private
public :: swap_t
template swap_t(T)
private
public :: swap
type :: t_pair
integer :: i
real :: x
end type
type :: T
end type
contains
subroutine swap_(x, y)
type(T), intent(inout) :: x, y
type(T) :: tmp
tmp = x
x = y
y = tmp
end subroutine
end template
end module
Above shows an example using template syntax. This syntax was proposed by the Fortran committee, and might be subject to change. In any case, only the syntax changes, not the template implementation in the AST and ASR level.
See the following Pull Request to for the implementation.
This PR
- includes changes to the parser and the tokenizer to introduce the new keyword "template".
- Adds new AST node, "Template".
2. Generating ASR from AST
For this step, I wrote code in the "ast_body_visitor.cpp" and "ast_symbol_table_visitor.cpp". When the compiler visits the AST nodes to create the ASR nodes, I added code to visit the Template AST node to create relevant ASR. Until recently we had "TemplatedFunction" and "TemplatedSubroutine". But Ondrej used Luthfan's code to merge them into one. So I had to check whether currently the visitor was in a template and output ASR accordingly.
The above PR also contains code from Luthfan's implementation of generics from LPython. It contains the templated versions of built-in operator types of the language. For example, we have BinOp (Binary operator) and TemplateBinOp (Templated Binary Operator). I had to create the correct one while visiting function AST, depending on whether the operand is a templated type or a concrete type.
3. Introducing Instantiation syntax to the language
The following code features the creation of a template function that adds two numbers and instantiates it twice with two types.
module add_m
implicit none
private
public :: add_t
template add_t(T)
private
public :: add
type :: T
end type
contains
function add_generic(x, y)
type(T) :: x, y, add_generic
add_generic = x + y
end function
end template
contains
subroutine test_template()
instantiate add_t(real), only: add_real => add_generic
real :: x, y
integer :: a, b
x = 5.1
y = 7.2
print*, "The result is ", add_real(x, y)
if (abs(add_real(x, y) - 12.3) > 1e-5) error stop
instantiate add_t(integer), only: add_integer => add_generic
a = 5
b = 9
print*, "The result is ", add_integer(a, b)
if (add_integer(a, b) /= 14) error stop
end subroutine
end module
program use_template_module
use add_m
implicit none
call test_template()
end program use_template_module
The above code introduces a new keyword, "instantiate", which was also implemented in the above PR. This time also, the parser, tokenizer and the AST.asdl file had to be edited to introduce the new keyword and the new AST node type.
I had to introduce a new type "%type <vec_ast> var_type_star" in the parser.yy file because there was no such type declared before and the instantiation should take a list of types as input.
4. Instantiation of generic functions
The code for this function is also contained in the above PR.
For this segment of the project also, some parts of Luthfan's code was very useful. He wrote the code in the files "instantiate_template.cpp" and "instantiate_template.h", in which the actual concrete function generation from the generic functions happens.
It requires the mapping between templated types and concrete types and I implemented that for LFortran since it is language dependent. Then inserted the newly created the concrete function to the ASR.
Product
The result of the project is the addition of template declaration and instantiation features to LFortran.
Future work
Even though this work is labeled as "future" work, some of it was intended to be completed within this GSOC period but couldn't be due to unexpected delays.
- Add a suite of examples and tests and make the current implementation comprehensive
- Add restrictions to LFortran