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

Popular posts from this blog