I worked on introducing sets and adding functionality to existing data structures.

- Set (#2122)

We already had initial implementation for dictionaries. Sets are similar, but unlike dictionaries, do not have key-value pairs. As with dictionaries, an abstract set interface is created, so we can use different collision-resolution techniques. There is some duplication of code such as hash computation, but for now we focus on providing basic functionality for set.

I used linear-probing collision-resolution, where we find the next empty spot starting from the hash position. While deleting an element, we mark it with a special marker (tombstone). This helps in ignoring it in further reads, and indicates that elements with the same hash can be present at later positions.

Further, I implemented functions to write items into the set. This involved resolving collisions for reading and writing, and also for rehashing the entire set while increasing the underlying list size. This technique is not effective for string elements, as in that case we just compute hashes of the character-array pointers. We will use separate chaining for this in the coming weeks.

Next, I worked on functions for deep-copying sets, and retrieving its length.

- Dictionary keys and values (#2023)

I corrected earlier functions to obtain lists of keys and values, when linear probing is used. This involved using the key-mask to identify whether elements are set or not.

Directly testing this did not work, as CPython does not return list items for these functions. Rather, it returns a view, with limited functionality; for example, we cannot index a view. Thus, I tried copying the results into a list, but it turns out that LPython does not fully support nested iterables with dictionaries yet. I will work on this in the next week.

- List comparison (#2025)

Earlier, I had implemented the less than operation for lists and tuples. I extended this to other comparison operations, and used LLVM's CreateCmp instructions that allow specifying a predicate. This helps prevent unnecessary replication of code, and we just switch the predicate using an overload_id.

---

Next week, I will continue adding more functions to sets, and try to resolve the nested dictionary issue.

I was out for the week of 26 June.

This week, I continued to improve list, tuple, and dictionary data structures.

Last week, I had worked on an improvement to support nested tuples. In some parts, I made use of raw memory allocation using new and delete. This was pointed in the PR comments.

I corrected this (PR 2018), using an allocator for memory management. This is used in general throughout the existing code as well, preventing memory leaks.

Further, I worked on adding some functionality to dictionaries. Issue 1881 is to support iteration through a dictionary as

d: dict[i32, i32]
d = {1:2, 3:4, 5:6}
for k in d:
    print(k)

This code iterates over the dictionary keys. We discussed in our meet on how to implement this, and concluded that it would be good to first implement dict.keys and dict.values as in CPython. For now, we are not using views, but rather returning lists.

I implemented some of this (PR 2023), but it turns out that the keys list has some extra values. I will discuss on this further.

Next, I also started work on supporting list comparison (Issue 1832). At the moment, we only have equality comparison. I started with implementing less than operation (PR 2025). I am trying to abstract out code for various comparison operations, so that same code is not used repeatedly.

I worked on improving existing data structures

• 1932 - Support nested tuples.
  • For example, tuple[tuple[i32, f64], i32]
• 1940 - Support optional parameters in list index method.
  • Now the method signature is list.index(x[, start[, end]]), as in CPython.

In the coming week, I will continue to add and improve other data structure methods.

I continued work on adding methods to existing data structures, and improving others.

• Added list repeat (1888). Fixed warnings from a couple of other functions
• Fixed an issue to disallow zero step in list, string slicing (1879).
• Completed work for 1845 - there was an issue in popping from nested iterables

For the next week, I plan to work on known issues. This includes

• Supporting nested tuples (1886)
• List index with optional arguments