With i32, i64, etc. types. This file should probably be in src/runtime also. We should be importing it, and ensure that things just work with CPython with the same source code.

Reference code:

def main0():
    s: str
    s = 'aabbcc'
    c: str
    for c in s:
        print(c)

main0()

ASR:

semantic error: Only function call `range(..)` supported as for loop iteration for now
 --> c.py:5:5 - 6:16
  |
5 |        for c in s:
  |        ^^^^^^^^^^^...
...
  |
6 |            print(c)
  | ...^^^^^^^^^^^^^^^^

So stuff like divmod and chr should be all implemented in pure Python in a special module, let's say lfortran_builtin.py. And then we need to modify our AST to ASR to load this module if any of such functions are used, and effectively "import it" in the ASR.

The standard library like math, sys, etc. is already implemented, see how math.py works. So we can now just add more functions to it.

I think we also need to implement Constant so that we support simple types such as None. Now the question is, how to represent that in ASR? Do we need a Constant node in ASR?

I am thinking that we should use .lpy as the extension for lpython files. The main reason is that after supporting import statements we will have python interpreter error like:

+ integration_tests/test_math
+ python integration_tests/py_test_math.py
Traceback (most recent call last):
  File "/home/admin-pc/Smitlunagariya/lpython/integration_tests/py_test_math.py", line 5, in <module>
    from modules_math import factorial
  File "/home/admin-pc/Smitlunagariya/lpython/integration_tests/modules_math.py", line 1, in <module>
    def factorial(x: i32) -> i32:
NameError: name 'i32' is not defined

The requirement is that it works with CPython and NumPy, but also compiles using LPython. One option is:

def main():
    a: f32[10000] = numpy.empty(10000, dtype=numpy.float32)
    b: f32[10000] = numpy.empty(10000, dtype=numpy.float32)
    c: f32[10000] = numpy.empty(10000, dtype=numpy.float32)
    scalar: f32
    i: i32
    nsize: i32
    scalar = 10
    nsize = size(a)
    for i in range(nsize): # type: parallel
        a[i] = 5
        b[i] = 5
    triad(a, b, scalar, c)
    print("End Stream Triad")

So the syntax is:

    a: f32[10000] = numpy.empty(10000, dtype=numpy.float32)

But this is redundant, as the size 10000 is repeated twice and the type f32 and numpy.float32 is also repeated.

It would be nice to unify the type promotion rules of LFortran and LPython. Here is a very nice writeup how JAX does it: https://jax.readthedocs.io/en/latest/design_notes/type_promotion.html, and we probably might do exactly the same for LPython, possibly also introduce unsigned integers.

• Rename the lfortran binary to lpython
• Make --show-python-ast just --show-ast, the same with --show-asr, --show-cpp
• Merge a.py with lpython, probably using Cython
• Get --show-llvm working
• Get compiling to binaries working
• Remove all Fortran related files (parser, ast, ast -> asr, etc.)
• Rename namespaces from LFortran to LPython
• Add tests (run_tests.py for ASR mainly, and then integration_tests, we can simply call lpython on the main file and then run it, probably adapting cmake, so that we can use ctest to execute)

Currently string comparison such as assert x = "abc" doesn't work properly yet, I think we should implement the operation in LPython in the runtime library and the frontend should insert the call to it.

Once LPython can use ASR's generic function facilities, it should just be a generic function. In the meantime, let's implement:

• str_int(x) ... converts an integer to a string
• str_float(x) ... converts a floating point to a string

These will be implemented in pure Python, such as:

def str_int(x):
    ....
    # s = ...
    return s

For now, let's put this into one file, and print the result at the end. Some things will not be implemented in LPython yet, so let's open up issues for things that are not implemented yet, and we'll fix them.

Lambda expressions in python don't support annotations. See: https://www.python.org/dev/peps/pep-3107/#lambda
They can be simply mapped to ASR function but still will be a difficult task without knowing the argument type.

I had a look at the tests folders in Numba and Pythran. They have tested every feature explicitly by creating many functions: https://github.com/numba/numba/blob/6e7561b96452b0196ffdde7b6c33abb11cf9c9d3/numba/tests/test_tuples.py, and it is so easy to identify what is missing.

I propose we also do the same, as it would be easy to maintain the massive test suite in the long run.

We should refactor these soon.

In Cython you can do (https://cython.readthedocs.io/en/latest/src/userguide/memoryviews.html):

cpdef int sum3d(int[:, :, :] arr) nogil:
    cdef size_t i, j, k, I, J, K
    cdef int total = 0
    I = arr.shape[0]
    J = arr.shape[1]
    K = arr.shape[2]
    for i in range(I):
        for j in range(J):
            for k in range(K):
                total += arr[i, j, k]
    return total

In LPython this might look like:

def sum3d(arr: i64[:, :, :]) -> i64:
    i: i64, j: i64, k: i64, I: i64, J: i64, K: i64
    total: i64 = 0
    I = shape(arr, 0)
    J = shape(arr, 1)
    K = shape(arr, 2)
    for i in range(I):
        for j in range(J):
            for k in range(K):
                total += arr[i, j, k]
    return total

We need to implement assert in LLVM and use it in integration_tests to actually test for correctness.

In Fortran there are two options (thus both implemented in ASR):

function zeros1(n) result(r)
integer, intent(in) :: n
real :: r(n)
integer :: i
do i = 1, n
    r(i) = 0
end do
end function

and

function zeros2(n) result(r)
integer, intent(in) :: n
real, allocatable :: r(:)
integer :: i
allocate(r(n))
do i = 1, n
    r(i) = 0
end do
end function

They can both be used in the same way:

real :: A(4)
A = zeros1(4)
A = zeros2(4)

We'll eventually add an ASR optimizer that can effectively convert zeros2() into zeros1(), thus removing the allocatable heap allocation in many common cases, thus making the two equivalent.

In Python, the following syntax is allowed:

def zeros2(n: i32) -> f64[:]:
    A: f64[n]
    A = empty(n)
    i: i32
    for i in range(n):
        A[i] = 0.0
    return A

but this one is not:

def zeros1(n: i32) -> f64[n]:
    A: f64[n]
    A = empty(n)
    i: i32
    for i in range(n):
        A[i] = 0.0
    return A

which gives an error:

Traceback (most recent call last):
  File "/Users/ondrej/repos/lpython/integration_tests/test_numpy_02.py", line 6, in <module>
    def zeros(n: i32) -> f64[n]:
NameError: name 'n' is not defined

So we would have to create some alternative syntax for zeros1() style in Python. The zeros2() allocatable style works.

This is supported well at the ASR level, but we need to figure out a Python syntax. Whether via the ctypes FFI, or some other syntax.

I implemented the gcd function in the following way:

def gcd(a: i32, b: i32):
    temp: i32
    while b!=0:
        a = a % b
        temp = a
        a = b
        b = temp
    return a

(Module [
   (FunctionDef 
      gcd 
      ([] [
         (
            a 
            (Name 
               i32 
               Load) ()) 
         (
            b 
            (Name 
               i32 
               Load) ())] [] [] [] [] []) [
      (AnnAssign 
         (Name 
            temp 
            Store) 
         (Name 
            i32 
            Load) () 1) 
      (While 
         (Compare 
            (Name 
               b 
               Load) 
            NotEq [
            (ConstantInt 0 ())]) [
         (Assign [
            (Name 
               a 
               Store)] 
            (BinOp 
               (Name 
                  a 
                  Load) 
               Mod 
               (Name 
                  b 
                  Load)) ()) 
         (Assign [
            (Name 
               temp 
               Store)] 
            (Name 
               a 
               Load) ()) 
         (Assign [
            (Name 
               a 
               Store)] 
            (Name 
               b 
               Load) ()) 
         (Assign [
            (Name 
               b 
               Store)] 
            (Name 
               temp 
               Load) ())] []) 
      (Return 
         (Name 
            a 
            Load))] [] () ())] [])

semantic error: Binary operator type not supported
 --> ser.txt:1:1
  |
1 | 0 0 1 0 3 gcd 0 2 1 a 1 26 3 i32 0 0 1 b 1 26 3 i32 0 0 0 0 0 0 0 3 7 26 4 temp 1 26 3 i32 0 0 1 10 15 26 1 b 0 1 1 20 0 0 4 5 1 26 1 a 1 2 26 1 a 0 5 26 1 b 0 0 5 1 26 4 temp 1 26 1 a 0 0 5 1 26 1 a 1 26 1 b 0 0 5 1 26 1 b 1 26 4 temp 0 0 0 3 1 26 1 a 0 0 0 0 0 
  | ^ 


Note: if any of the above error or warning messages are not clear or are lacking
context please report it to us (we consider that a bug that needs to be fixed).

ASR gives Binary operator not supported because of % (modulo operator). In python AST we have Mod as the operator but in lfortran we use MODULO function at compile time:

static ASR::expr_t *eval_modulo(Allocator &al, const Location &loc, Vec<ASR::expr_t*> &args) {
        return eval_2args_ri(al, loc, args,
            &IntrinsicProcedures::lfortran_modulo,
            &IntrinsicProcedures::lfortran_modulo_i);
    }

How should we handle it in lpython?

Originally posted by @Smit-create in #2 (comment)

To be determined: how to handle automatic reallocation of the LHS, for things like:

real(dp), allocatable :: x(:)
x = [1, 2, 3]
x = [1, 2, 3, 5, 6]

And the same for strings:

character(:), allocatable :: s
s = "abc"
s = "abcdef"

The two options:

1. The ASR will contain implicit nodes for checking if s is allocated and deallocate it, such as:

real(dp), allocatable :: x(:)
if (allocated(x)) then deallocate(x)
allocate(x(3))
x = [1, 2, 3]
if (allocated(x)) then deallocate(x)
allocate(x(5))
x = [1, 2, 3, 5, 6]

We already have ImplicitDeallocate which I think does exactly if (allocated(x)) then deallocate(x).
And then we can add optimizations in ASR->ASR that would turn this into:

real(dp), allocatable :: x(:)
allocate(x(3))
x = [1, 2, 3]
deallocate(x)
allocate(x(5))
x = [1, 2, 3, 5, 6]

And ultimately we need optimizations to turn this into:

real(dp) :: x1(3), x2(5)
x1 = [1, 2, 3]
x2 = [1, 2, 3, 5, 6]

Depending on how the arrays are used. These optimizations we have to have anyway, to simplify such generic code into a faster code.

The other optimization that we need is that sometimes 3 and 5 is not known at compile time, but the sizes are still known as some kind of an expression, in the simplest case as variables n and m. Then this:

integer :: m, n
real(dp), allocatable :: x(:)
call assign_to_mn(m, n) ! reads from an input file
allocate(x(m))
x = 1
deallocate(x)
allocate(x(n))
x = 2

should be turned into:

function f(m, n)
integer, intent(in) :: m, n
real(dp) :: x1(m), x2(n)
x1 = 1
x2 = 2
end function

integer :: m, n
call assign_to_mn(m, n) ! reads from an input file
call f(m, n)

2. Handle this by the backends. That means we have to implement this logic into every backend. That seems suboptimal, the approach we chose is to encode everything into ASR explicitly, so that the backend doesn't have to handle any kind of such logic.

3. Write an ASR to ASR pass that tranforms the initial code into the code in 1. So far we chose to do this directly in AST to ASR, so that ASR is always well formed and explicit.

So it seems 1. is the way to go.

It seems this is analogous to the mem2reg pass in LLVM, where the frontend is encouraged to use alloca for everything and then the LLVM optimizers promote it to registers if they can. It seems it is possible to implement such optimizers in a robust way. The above optimizers turn "allocatable" into just regular "non-allocatable" arrays. And the AST to ASR just always turns x = y assignment where x is allocatable into the ImplicitDeallocate; Allocate; Assignment nodes.

So ASR Assignment only does a copy (to either allocatable or non-allocatable arrays), and it assumes that the size of the LHS is the same as RHS. The frontend checks this either at compile time or runtime (in Debug/Check mode). Assignment does not resize.

They are needed in the implementation of runtime built-in functions, like divmod() where we return a pair.

Here is how to do it: https://github.com/epassaro/cache-conda-envs

From the reference doc here: https://docs.python.org/3/library/stdtypes.html

We can see there are widely used built-in types supported in python like list, set, tuple, dict, etc. We should think of supporting them in lpython. I haven't found any related issue yet so thought to open one to keep track.

Let me know your thoughts on this.

cc @certik @namannimmo10 @Thirumalai-Shaktivel

Here is a roadmap that we can follow:

• Finish runtime library like comptime_eval.h in LFortran
• Be able to call a function like lpython_str_format that is our own LPython implementation of the % formatting operator, this function will be inserted by the frontend (tested by #256, which calls _lpython_imag)
• Implement the rest of str functionality (mostly in the LLVM backend) and fix all bugs related to strings (the remaining bug seems to be #273)
• C interop (#3)
• Generic functions (#141)
• NumPy support (#5)

This should allow us to implement large parts of the runtime library, and get LPython off the ground. After the above works, the other missing features that we need to implement are:

• Generics (#154)
• Interactivity (#329)

Other (lower priority):

• Improvements to C interop: #545

So that you can implement a function sin(x) in LPython, that would work both for f32 and f64.

The tricky part is to design this in such a way so that it works with CPython also.

I think we need to make some design changes to the C++ backend. Let's start with the requirements that I would like the backend to be able to do:

• Generate just pure C
• Generate readable natural C++
• Make it configurable what C++ features are used to represent a given ASR construct
• Select how arrays are represented:
  • Kokkos
  • XTensor
  • Some C approach, probably using macros to make it readable (needed for the C backend and also for the C++ backend to eliminate the dependency on 3rd party libraries)
  • Make it reasonable to add more array "backends"

I don't know if we have to have two backends, C and C++. Or if we can merge them, with if statements or using some base class and two subclasses. Probably the easiest is to start a separate backend for C and see what similarities there are and if things can be merged later.

For the C++ backend, it looks like the main thing to refactor is how arrays are handled.

It seems we should have some "Options" as part of the C++ backend visitor class, and then each method will consult the "Options" to see how a given feature should be generated.

It seems for each type (Complex, Real, array/scalar, ...) we store information about:

• how it is declared as a local variable, as a function argument (intent in/out/inout), how it is accessed, indexed, etc.

This might be general enough that we might reuse this machinery for both arrays and types like complex (different in C and C++), and possibly this might allow to have the same visitor for both C and C++.

The Python standard library has a lot of modules: https://docs.python.org/3/library/index.html, but many of them are rarely used. First we should concentrate on the most commonly used modules, probably:

• sys
• os
• string
• time
• datetime
• cmath
• decimal
• numbers
• fractions
• statistics
• glob
• tempfile
• itertools
• functools
• pickle
• csv
• argparse
• logging
• platform
• json
• pdb
• ast

Some of these might be initially difficult to implement, but some of these might be doable already.

Here is a benchmark that we should implement:

https://www.matecdev.com/posts/julia-python-numba-cython.html

And make it as fast as possible.

Python code:

def f(x: dict[i32, i32]):
    x[2] = 4

ASR:

Traceback (most recent call last):
  File "/Users/thebigbool/repos/lpython/src/bin/lpython.cpp", line 1478
    return emit_asr(arg_file, runtime_library_dir,
  File "/Users/thebigbool/repos/lpython/src/bin/lpython.cpp", line 553
    r = LFortran::Python::python_ast_to_asr(al, *ast, diagnostics, true);
  File "/Users/thebigbool/repos/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 2350
    Line not found
  File "/Users/thebigbool/repos/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 775
    void visit_Module(const AST::Module_t &x) {
  File "/Users/thebigbool/repos/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 526
    global_scope = nullptr;
  File "/Users/thebigbool/repos/lpython/src/libasr/../lpython/python_ast.h", line 1827
    void visit_stmt(const stmt_t &b) { visit_stmt_t(b, self()); }
  File "/Users/thebigbool/repos/lpython/src/libasr/../lpython/python_ast.h", line 1698
    case stmtType::FunctionDef: { v.visit_FunctionDef((const FunctionDef_t &)x); return; }
  File "/Users/thebigbool/repos/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 575
  File "/Users/thebigbool/repos/lpython/src/libasr/../libasr/asr_utils.h", line 650
    throw LFortranException("Not implemented.");
LFortranException: Not implemented.

I rebuilt from scratch using ./build0.sh and ./build1.sh on current main branch. I get the following error:

$ lpython --show-asr expr3.py 
python: can't open file '/home/admin-pc/Smitlunagariya/lpython/inst/bin/../share/lpython/lib/lpython_parser.py': [Errno 2] No such file or directory
The command 'python /home/admin-pc/Smitlunagariya/lpython/inst/bin/../share/lpython/lib/lpython_parser.py expr3.py' failed.

#51 (comment)

Currently the runtime library is only tested with LPython. We need to write it in a way (with the help of #115) to also work with CPython, and all tests must pass with both CPython and LPython. That will ensure robustness and correctness.

Reference code:

def test(a:i32, b:i32):
    return a**b

def check():
    a: i32
    a = test(2, 2)

(Module [
   (FunctionDef 
      test 
      ([] [
         (
            a 
            (Name 
               i32 
               Load) ()) 
         (
            b 
            (Name 
               i32 
               Load) ())] [] [] [] [] []) [
      (Return 
         (BinOp 
            (Name 
               a 
               Load) 
            Pow 
            (Name 
               b 
               Load)))] [] () ()) 
   (FunctionDef 
      check 
      ([] [] [] [] [] [] []) [
      (AnnAssign 
         (Name 
            a 
            Store) 
         (Name 
            i32 
            Load) () 1) 
      (Assign [
         (Name 
            a 
            Store)] 
         (Call 
            (Name 
               test 
               Load) [
            (ConstantInt 2 ()) 
            (ConstantInt 2 ())] []) ())] [] () ())] [])

Internal Compiler Error: Unhandled exception
Traceback (most recent call last):
  Binary file "/home/admin-pc/Smitlunagariya/lpython/src/bin/lpython", in _start()
  File "/build/glibc-S9d2JN/glibc-2.27/csu/../csu/libc-start.c", line 310, in __libc_start_main()
  File "/home/admin-pc/Smitlunagariya/lpython/src/bin/lpython.cpp", line 1485, in main()
    with_intrinsic_modules, compiler_options);
  File "/home/admin-pc/Smitlunagariya/lpython/src/bin/lpython.cpp", line 561, in emit_asr()
    r = LFortran::Python::python_ast_to_asr(al, *ast, diagnostics);
  File "/home/admin-pc/Smitlunagariya/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 1664, in LFortran::Python::python_ast_to_asr(Allocator&, LFortran::Python::AST::ast_t&, LFortran::diag::Diagnostics&)
    auto res2 = body_visitor(al, *ast_m, diagnostics, unit);
  File "/home/admin-pc/Smitlunagariya/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 1620, in LFortran::Python::body_visitor(Allocator&, LFortran::Python::AST::Module_t const&, LFortran::diag::Diagnostics&, LFortran::ASR::asr_t*)
    b.visit_Module(ast);
  File "/home/admin-pc/Smitlunagariya/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 397, in LFortran::Python::BodyVisitor::visit_Module(LFortran::Python::AST::Module_t const&)
    visit_stmt(*x.m_body[i]);
  File "/home/admin-pc/Smitlunagariya/lpython/src/libasr/../lpython/python_ast.h", line 1827, in LFortran::Python::AST::BaseVisitor<LFortran::Python::BodyVisitor>::visit_stmt(LFortran::Python::AST::stmt_t const&)
    void visit_stmt(const stmt_t &b) { visit_stmt_t(b, self()); }
  File "/home/admin-pc/Smitlunagariya/lpython/src/libasr/../lpython/python_ast.h", line 1698, in visit_stmt_t<LFortran::Python::BodyVisitor>()
    case stmtType::FunctionDef: { v.visit_FunctionDef((const FunctionDef_t &)x); return; }
  File "/home/admin-pc/Smitlunagariya/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 422, in LFortran::Python::BodyVisitor::visit_FunctionDef(LFortran::Python::AST::FunctionDef_t const&)
    handle_fn(x, *ASR::down_cast<ASR::Subroutine_t>(t));
  File "/home/admin-pc/Smitlunagariya/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 413, in void LFortran::Python::BodyVisitor::handle_fn<LFortran::ASR::Subroutine_t>(LFortran::Python::AST::FunctionDef_t const&, LFortran::ASR::Subroutine_t&)
    transform_stmts(body, x.n_body, x.m_body);
  File "/home/admin-pc/Smitlunagariya/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 377, in LFortran::Python::BodyVisitor::transform_stmts(LFortran::Vec<LFortran::ASR::stmt_t*>&, unsigned long, LFortran::Python::AST::stmt_t**)
    this->visit_stmt(*m_body[i]);
  File "/home/admin-pc/Smitlunagariya/lpython/src/libasr/../lpython/python_ast.h", line 1827, in LFortran::Python::AST::BaseVisitor<LFortran::Python::BodyVisitor>::visit_stmt(LFortran::Python::AST::stmt_t const&)
    void visit_stmt(const stmt_t &b) { visit_stmt_t(b, self()); }
  File "/home/admin-pc/Smitlunagariya/lpython/src/libasr/../lpython/python_ast.h", line 1701, in visit_stmt_t<LFortran::Python::BodyVisitor>()
    case stmtType::Return: { v.visit_Return((const Return_t &)x); return; }
AssertFailed: current_scope->scope.find(return_var_name) != current_scope->scope.end()

https://docs.python.org/3/library/math.html

Let's start with pure Python functions such as factorial.

Here is a simple example:

from numpy import empty, int32, all

def main0():
    x: i32[5] = empty(5, dtype=int32)
    x[:] = (2+3)*5
    assert all(x == 25)

main0()

or:

from numpy import empty, int32

def main0():
    x: i32[2] = empty(2, dtype=int32)
    x[0] = 3
    x[1] = 4
    assert x[0] == 3 && x[1] == 4

main0()

LFortran saves module files into a .mod file. LPython could probably be saving the .py module files into .lpy.

The main difference from LFortran is that in Fortran you have to call the compiler on each module by hand. In Python the semantics is that it should compile them automatically when import some_module is encountered.

This should work:

def main():
    a: i32
    a = 2
    b: i32
    b = 6 if a == 2 else 8

a: list[list[i32], list[i32]]
a = [[1, 2], [3, 4], [5, 6]]
print(a[1][0])

AST:

(Module [
   (AnnAssign
      (Name
         a
         Store)
      (Subscript
         (Name
            list
            Load)
         (Tuple [
            (Subscript
               (Name
                  list
                  Load)
               (Name
                  i32
                  Load)
               Load)
            (Subscript
               (Name
                  list
                  Load)
               (Name
                  i32
                  Load)
               Load)]
            Load)
         Load) () 1)
   (Assign [
      (Name
         a
         Store)]
      (List [
         (List [
            (ConstantInt 1 ())
            (ConstantInt 2 ())]
            Load)
         (List [
            (ConstantInt 3 ())
            (ConstantInt 4 ())]
            Load)
         (List [
            (ConstantInt 5 ())
            (ConstantInt 6 ())]
            Load)]
         Load) ())
   (Expr
      (Call
         (Name
            print
            Load) [
         (Subscript
            (Subscript
               (Name
                  a
                  Load)
               (ConstantInt 1 ())
               Load)
            (ConstantInt 0 ())
            Load)] []))] [])

ASR:

Internal Compiler Error: Unhandled exception
Traceback (most recent call last):
  File "/Users/namannimmo/Applications/oss/lpython/src/bin/lpython.cpp", line 1470
    return emit_asr(arg_file, runtime_library_dir,
  File "/Users/namannimmo/Applications/oss/lpython/src/bin/lpython.cpp", line 547
    r = LFortran::Python::python_ast_to_asr(al, *ast, diagnostics, true);
  File "/Users/namannimmo/Applications/oss/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 2567
    tu = res2.result;
  File "/Users/namannimmo/Applications/oss/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 2523
    Error error;
  File "/Users/namannimmo/Applications/oss/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 704
    visit_stmt(*x.m_body[i]);
  File "/Users/namannimmo/Applications/oss/lpython/src/lpython/python_ast.h", line 1827
    void visit_stmt(const stmt_t &b) { visit_stmt_t(b, self()); }
  File "/Users/namannimmo/Applications/oss/lpython/src/lpython/python_ast.h", line 1719
    case stmtType::Nonlocal: { v.visit_Nonlocal((const Nonlocal_t &)x); return; }
  File "/Users/namannimmo/Applications/oss/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 1885
    args.push_back(al, expr);
  File "/Users/namannimmo/Applications/oss/lpython/src/lpython/python_ast.h", line 1854
    void visit_expr(const expr_t &b) { visit_expr_t(b, self()); }
  File "/Users/namannimmo/Applications/oss/lpython/src/lpython/python_ast.h", line 1755
    case exprType::Attribute: { v.visit_Attribute((const Attribute_t &)x); return; }
  File "/Users/namannimmo/Applications/oss/lpython/src/lpython/semantics/python_ast_to_asr.cpp", line 912
    ASR::Variable_t *v = ASR::down_cast<ASR::Variable_t>(s);
  File "/Users/namannimmo/Applications/oss/lpython/src/libasr/asr.h", line 40
    LFORTRAN_ASSERT(is_a<T>(*f));
AssertFailed: is_a<T>(*f)

The current error is (https://github.com/lcompilers/lpython/runs/4854302427?check_suite_focus=true):

Traceback (most recent call last):
TEST: doconcurrentloop_01.py
  File "D:\a\lpython\lpython\run_tests.py", line 136, in <module>
    * ast    The JSON metadata differs against reference results
    main()
Reference JSON: tests\reference\ast-doconcurrentloop_01-ed7017b.json
  File "D:\a\lpython\lpython\run_tests.py", line 70, in main
Output JSON:    tests\output\ast-doconcurrentloop_01-ed7017b.json
    run_test("ast", "lpython --show-ast --no-color {infile} -o {outfile}",
Omitting 8 identical items
  File "D:\a\lpython\lpython\compiler_tester\tester.py", line 273, in run_test
Differing items:
    raise RunException("The reference result differs")
{'infile_hash': '1876de8c07abafd35379956fc2dd60ce2572da93cb2c4be90ee1f501'} != {'infile_hash': 'c3efb3a1f583c1cc5f973f560369378d784bf5df6fcace9962624266'}
compiler_tester.tester.RunException: The reference result differs
{'infile': 'tests\\doconcurrentloop_01.py'} != {'infile': 'tests/doconcurrentloop_01.py'}
{'stdout_hash': 'e3f4e27718c6733b68c6d7c395aa3fa8f0309bf02429b402b335efd4'} != {'stdout_hash': 'c13b7d1e89b1f88facf2326435b8d77a42955ac7a3f1e9870362e133'}
Diff against: tests\reference\ast-doconcurrentloop_01-ed7017b.stdout

In the current implementation of python ast to asr, visit_FunctionDef creates a subroutine(make_Subroutine_t)node as:

tmp = ASR::make_Subroutine_t(
            al, x.base.base.loc,
            /* a_symtab */ current_scope,
            /* a_name */ s2c(al, sym_name),
            /* a_args */ args.p,
            /* n_args */ args.size(),
            /* a_body */ nullptr,
            /* n_body */ 0,
            current_procedure_abi_type,
            s_access, deftype, bindc_name,
            is_pure, is_module);

We can also verify that Functiondef node in AST is converted to Subroutine node in ASR from below reference code:

(Module [
   (FunctionDef 
      check 
      ([] [] [] [] [] [] []) [
      (AnnAssign 
         (Name 
            r 
            Store) 
         (Name 
            i32 
            Load) () 1) 
      (Assign [
         (Name 
            r 
            Store)] 
         (ConstantInt 0 ()) ()) 
      (AugAssign 
         (Name 
            r 
            Store) 
         Add 
         (ConstantInt 4 ()))] [] () ())] [])

(TranslationUnit 
   (SymbolTable 
      1 
      {
         check: 
            (Subroutine 
               (SymbolTable 
                  2 
                  {
                     r: 
                        (Variable 
                           2 
                           r 
                           Local () () 
                           Default 
                           (Integer 4 []) 
                           Source 
                           Public 
                           Required .false.)
                  }) 
               check [] [
               (= 
                  (Var 2 r) (ConstantInteger 0 
                  (Integer 4 [])) ()) 
               (Assign 0 
                  )] 
               Source 
               Public 
               Implementation () .false. .false.)
      }) 
   [])

This also might be the reason for the failure of #2 (comment). How should we handle this Function vs Subroutine?

Sorry if this is very trivial question, I didn't find much difference between them and so thought to discuss over here.

This should work:

def main():
    s: str
    s = 'a' * 2
    s = 4 * 'bb'
    s = 3 * 'a' * 3

It seems much more natural to me, and consistent with quite a few codes and libraries:

• https://arrayfire.org/docs/gettingstarted.htm
• https://michaelhatherly.github.io/NumericSuffixes.jl/stable/
• JuliaLang/julia#24647
• https://docs.rs/cauchy/latest/cauchy/type.c64.html

Essentially, it means the complex number is composed of the 32 or 64 bit float. One says double precision complex number, and double precision is 64 bit, so it's 64 bit complex number, c64 (yes, it is represented by 128bits).

How about something like this?

(Source: Google images)

Both LPython and LFortran (#647) should be able to compile essentially equivalent code for the n-body benchmark from here: https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/nbody.html

Then in ASR we have to implement enough optimizations (mostly the 1/sqrt(x) and probably loop vectorization if LLVM itself cannot do it well) to get the best performance.

The code should look as simple as something like this:

  subroutine advance(tstep, x, v, mass)
    real(dp), intent(in) :: tstep
    real(dp), dimension(3,nb), intent(inout) :: x, v
    real(dp), dimension(nb), intent(in) :: mass
    real(dp) :: r(3,N), mag(N), d2
    integer :: i, j, m
    m = 1
    do i = 1, nb
       do j = i + 1, nb
          r(:,m) = x(:,i) - x(:,j)
          m = m + 1
       end do
    end do
    do m = 1, N
       d2 = sum(r(:,m)**2)
       mag(m) = tstep / sqrt(d2)**3
    end do
    m = 1
    do i = 1, nb
       do j = i + 1, nb
          v(:,i) = v(:,i) - r(:,m) * mass(j) * mag(m)
          v(:,j) = v(:,j) + r(:,m) * mass(i) * mag(m)
          m = m + 1
       end do
    end do
    x = x + tstep * v
  end subroutine

The advance subroutine is the main computation. For LPython we'll write an equivalent using NumPy.

This gets read from the surface language (Python, Fortran) into ASR in a straightforward manner.

Then we have to implement the following optimizations as ASR->ASR:

• sum(r(:,m)**2) into whatever is the most efficient loop or unrolled loop
• mag(m) = tstep / sqrt(d2)**3 this must be implemented using single precision 1/sqrt(x) and one or two newton iterations
• Loops must be unrolled so that they can be vectorized

The fastest implementation that they have is in C and it looks like this:

// compute rsqrt of distance between each pair of bodies
static inline void kernel(__m256d *r, double *w, __m256d *p) {
    for (int i = 1, k = 0; i < N; i++)
        for (int j = 0; j < i; j++, k++)
            r[k] = _mm256_sub_pd(p[i], p[j]);
    
    for (int k = 0; k < PAIRS; k += 4) {
        __m256d x0 = _mm256_mul_pd(r[k  ], r[k  ]);
        __m256d x1 = _mm256_mul_pd(r[k+1], r[k+1]);
        __m256d x2 = _mm256_mul_pd(r[k+2], r[k+2]);
        __m256d x3 = _mm256_mul_pd(r[k+3], r[k+3]);

        __m256d t0 = _mm256_hadd_pd(x0, x1);
        __m256d t1 = _mm256_hadd_pd(x2, x3);
        __m256d y0 = _mm256_permute2f128_pd(t0, t1, 0x21);
        __m256d y1 = _mm256_blend_pd(t0, t1, 0b1100);

        __m256d z = _mm256_add_pd(y0, y1);
        z = _mm256_rsqrt_pd(z);
        _mm256_store_pd(w+k, z);
    }
}

static void advance(int n, double dt, double *m, __m256d *p, __m256d *v) {
    __m256d r[PAIRS+3];
    double w[PAIRS+3] __attribute__((aligned(sizeof(__m256d))));

    r[PAIRS] = _mm256_set1_pd(1.0);
    r[PAIRS+1] = _mm256_set1_pd(1.0);
    r[PAIRS+2] = _mm256_set1_pd(1.0);

    __m256d rt = _mm256_set1_pd(dt);

    __m256d rm[N];
    for (int i = 0; i < N; i++)
        rm[i] = _mm256_set1_pd(m[i]);

    for (int s = 0; s < n; s++) {
        kernel(r, w, p);

        for (int k = 0; k < PAIRS; k += 4) {
            __m256d x = _mm256_load_pd(w+k);
            __m256d y = _mm256_mul_pd(x, x);
            __m256d z = _mm256_mul_pd(x, rt);
            x = _mm256_mul_pd(y, z);
            _mm256_store_pd(w+k, x);
        }

        for (int i = 1, k = 0; i < N; i++)
            for (int j = 0; j < i; j++, k++) {
                __m256d t = _mm256_set1_pd(w[k]);
                t = _mm256_mul_pd(r[k], t);
                __m256d x = _mm256_mul_pd(t, rm[j]);
                __m256d y = _mm256_mul_pd(t, rm[i]);

                v[i] = _mm256_sub_pd(v[i], x);
                v[j] = _mm256_add_pd(v[j], y);
            }

        for (int i = 0; i < N; i++) {
            __m256d t = _mm256_mul_pd(v[i], rt);
            p[i] = _mm256_add_pd(p[i], t);
        }
    }
}

So we just have to arrive at a similar code in ASR, and then hopefully LLVM can take it from there (if not, we'll have to figure it out).

This is a very good benchmark, because it is short and I think quite representative for the sort of array computation that is so common in HPC. It is also well studied and it is known what needs to happen to produce optimal code.

Python code:

def f(x: list[i32]):
    y: list[i32]
    k: i32
    y = [2*x[k] for k in range(len(x))]

ASR:

LFortranException: visit_ListComp() not implemented

Here is how to do that:

https://docs.github.com/en/actions/advanced-guides/storing-workflow-data-as-artifacts

This should work:

def main():
    s: str
    s = 'abc'
    c: str
    c = s[0] # works
    d: str
    d = s[1:2]

It seems one design that we can start with that should work is:

• All str are declared as Character with len=-2, that is, an allocatable string, except:
  • passing str to a function, which will be len=-1, that is, character(*), intent(in)
  • ConstantString will be len >= 0, that is, known at compile time

The len=-2 case must insert the ImplicitDeallocate nodes for every exit from the function. This should be done by generalizing such functionality from LFortran, into libasr.

Reference Code:

def test():
    i: i32
    a : i32
    a = 0
    for i in range(1, 10):
        a += i

(TranslationUnit 
   (SymbolTable 
      1 
      {
         test: 
            (Subroutine 
               (SymbolTable 
                  2 
                  {
                     a: 
                        (Variable 
                           2 
                           a 
                           Local () () 
                           Default 
                           (Integer 4 []) 
                           Source 
                           Public 
                           Required .false.), 
                     i: 
                        (Variable 
                           2 
                           i 
                           Local () () 
                           Default 
                           (Integer 4 []) 
                           Source 
                           Public 
                           Required .false.)
                  }) 
               test [] [
               (= 
                  (Var 2 a) (ConstantInteger 0 
                  (Integer 4 [])) ()) 
               (DoLoop 
                  (
                     (Var 2 i) (ConstantInteger 1 
                     (Integer 4 [])) (ConstantInteger 10 
                     (Integer 4 [])) (ConstantInteger 1 
                     (Integer 4 []))) [
                  (= 
                     (Var 2 a) 
                     (BinOp 
                        (Var 2 a) 
                        Add 
                        (Var 2 i) 
                        (Integer 4 []) () ()) ())])] 
               Source 
               Public 
               Implementation () .false. .false.)
      }) 
   [])

#include <iostream>
#include <string>
#include <vector>
#include <Kokkos_Core.hpp>
#include <lfortran_intrinsics.h>

template <typename T>
Kokkos::View<T*> from_std_vector(const std::vector<T> &v)
{
    Kokkos::View<T*> r("r", v.size());
    for (size_t i=0; i < v.size(); i++) {
        r(i) = v[i];
    }
    return r;
}

void test()
{
    int a;
    int i;
    a = 0;
    for (i=1; i<=10; i++) {
        a = a + i;
    };
}

So the issue is range(1, 10) considers it as [1, 10] instead of [1, 10)

Here is an initial list:

• https://transonic.readthedocs.io/en/latest/index.html
• https://seq-lang.org/
• https://cython.org/
• https://pythran.readthedocs.io/en/latest/
• https://numba.pydata.org/
• https://pytorch.org/
• https://github.com/google/jax
• https://www.weld.rs/
• https://cupy.dev/
• https://github.com/pyccel/pyccel
• https://github.com/Quansight-Labs/uarray

We need to allow writing generic functions (templates) and template constraints.

One idea that we can explore is to also support something like: #152 (comment):

>>> def str(val: i32 | f64):
...   # "isinstance" type guard
...   if isinstance(val, i32):
...     # type of `val` is narrowed to `i32`
...     return str_int(val)
...   elif isinstance(val, f64):
...     # else, type of `val` is narrowed to `f64`
...     return str_float(val)

def test_len():
    s: str
    s = "abcd"
    assert len(s) == 4
    s = ''
    assert len(s) == 0
    assert len("abcd") == 4
    assert len("") == 0

⬆️ When we run this under integration tests, it returns a codegen error, as it hits this line 👇