Implement other List methods

[Thirumalai-Shaktivel]

Currently we support: append(), insert(), remove() and pop().
TODO:

• extend()
• clear() - Supporting list of lists, list of tuples and tuples with lists #952
• index()
• count()
• reverse()
• copy()
• sort()

Source: https://docs.python.org/3/tutorial/datastructures.html#more-on-lists

[certik]

Yes, we should implement all these. Given the requirement for list to work for all types, it might be easier to just implement in the backend directly, until we have working generics.

[certik]

Other operations that we can think about adding later, taken from std::vector (once we have a C++ frontend, we'll need these):

• reserve()
• capacity()
• resize()

Also in order for our ASR list to be usable as an std::vector implementation, we probably need some way to construct a list from a pointer and a size (we have to figure out who owns what), so that an existing C++ function that accepts or returns an std::vector, say an external function, can be interfaced with ASR without any need for a copy. Although this might be possible to solve with arrays, we need the same mechanism for arrays as well, so that ASR can just use arrays, but one can pass in std::vector as an argument (with some cast), that does not copy data. Anyway, that's for later.

[namannimmo10]

Given the requirement for a list to work for all types, it might be easier to just implement in the backend directly, until we have working generics

Do you mean possibly adding an ASR node for each method?

[certik]

Do you mean possibly adding an ASR node for each method?

That path is clear and we might start with that.

I am hoping to keep the ASR minimal, but we can I think figure it out later how to implement some of this functionality another way.

[namannimmo10]

Hmm... It's still not clear to me what we really want.
Quoting from what you wrote in the "Intrinsic Functions Design" doc:

Next step from a "minimal design":

• Add to ASR all nodes that are shared across all frontends. That includes all nodes that must be implemented by the backend, but it also includes nodes that could have been implemented in the frontend, such as StringRepeat.
• This "broader scope" can be restated as: each frontend only has to maintain its "runtime library" of functions that are specific to that frontend. If it is shared with another frontend, it can go into ASR itself as a node. In another words: we do not need to maintain a set of ASR functionality/library shared across languages. Everything is either as ASR nodes, or in the frontend (and not shared with other frontends).
• Whether this broader design makes sense remains to be seen. Currently we only use it for StringRepeat.

If you want the ASR to be minimal and not have frontend-specific nodes, then shouldn't we focus on the runtime library (or possibly explore another option)?

[certik]

Yes, it's not clear either to me. I am hoping to avoid having 200 such functions in ASR.

I think what we need is to figure out which of these can be implemented in the runtime library, and if they can, we should. If they can't, then they should be part of ASR.

[czgdp1807]

Here’s what I think,
extend() - Can be implemented in the frontend and backend both. In frontend we need generics to achieve this. In backend you can call realloc and write new elements using while loop. Both seem equally good to me.
clear() - Can only be implemented in the backend because we need low level information to implement this. It would involve setting the current_end_point to 0. It might be tempting to call free on list data but I won’t do it because the user can call append in the very next loop and there we can reuse the already allocated data part of list. Lesser malloc calls the better.
index() - Can be easily implemented in the frontend using generics.
count() - Same with generics can go into frontend.
reverse() - Again same as above two, generics will come to the rescue.
copy() - We already do it via assignment so just implement it as a subroutine call and intercept in the LLVM or any other backend and use list_api->deepcopy
sort() - Easily implemented using generics in the frontend.

So only 2 (at max) out of the above need backend implementation. Rest can go into frontend with the help of generics. Now implementing all of these in backend via ASR nodes will be very redundant and pollution of ASR.

[namannimmo10]

Alright, then I agree it's better to wait until we have working generics.

[czgdp1807]

runtime library, and if they can, we should

I would prioritise options as follows,

1. Frontend - If we don’t need to manipulate any low level information like (current_end_point, capacity in case of list) then the feature should go into frontend.
2. Programmatically adding to ASR - If a feature needs sharing across LCompilers (like optimisations) then programmatically adding to ASR is the way to go. It provides scalability and minimality of ASR at the same time.
3. Backend - If we need to manipulate the low level information (like in case of arrays we need the descriptor to return size, dimension size, in case of list we need end point for length) then it should go into backend.
4. C Runtime Library - Should be used when no other options work. For example malloc calls, free can be done only via C runtime library. The reason to keep it as a last option is because it has performance issues (like C runtime functions cannot be inlined, and hence calls to these should only be made when extremely necessary).

So all in all, list features can be done either via frontend implementation or via backend implementation. Other options aren’t required to be considered IMO.

[suhanigarg29]

Hey! I am interested in working on this issue, can I get some help on how to start and exactly how to implement this?

[rsaba5612]

class List:
def init(self, items):
self.items = items

def append(self, item):
    self.items = self.items + [item]

def insert(self, index, item):
    self.items = self.items[:index] + [item] + self.items[index:]

def remove(self, item):
    self.items = [i for i in self.items if i != item]

def pop(self, index=-1):
    item = self.items[index]
    self.items = self.items[:index] + self.items[index+1:]
    return item

def extend(self, iterable):
    self.items += iterable

def clear(self):
    self.items = []

def index(self, item):
    for i, x in enumerate(self.items):
        if x == item:
            return i
    raise ValueError(f"{item} is not in list")

def count(self, item):
    return sum(1 for x in self.items if x == item)

def reverse(self):
    self.items = self.items[::-1]

def copy(self):
    return List(self.items[:])

def sort(self):
    self.items = sorted(self.items)

Note that this implementation does not use any built-in Python methods for simplicity. Also note that this implementation assumes the list only contains items of the same type. If you want to support lists of lists or tuples with lists, you may need to modify the code accordingly.