lcompilers / lpython

Python compiler
https://lpython.org/
Other
1.5k stars 160 forks source link

ASR: Add BitVector and ModularInteger #1578

Open certik opened 1 year ago

certik commented 1 year ago
--- a/src/libasr/ASR.asdl
+++ b/src/libasr/ASR.asdl
@@ -343,6 +343,8 @@ expr

 ttype
     = Integer(int kind, dimension* dims)
+    | BitVector(int kind, dimension* dims)
+    | ModularInteger(int kind, dimension* dims)
     | Real(int kind, dimension* dims)
     | Complex(int kind, dimension* dims)
     | Character(int kind, int len, expr? len_expr, dimension* dims)

The bit operations are allowed only on BitVector and we should remove it from the Integer / ModularInteger types. The frontend will insert appropriate implicit casting as needed. Arithmetic operators are defined for both Integer (wrap around is a runtime error in Debug mode) and ModularInteger (that wrap around). Comparison is also defined for both integers.

ModularInteger is not allowed as a loop variable. Initially the ModularInteger would be of modulo 2^8, 2^16, 2^32, 2^64 only, fast on hardware. Later we can add more (not as fast on hardware obviously).

We have to be careful to avoid the pitfalls here: https://github.com/lcompilers/lpython/wiki/ASR-Design#unsigned-integers

The two use cases of BitVector (bit fields) and ModularInteger (modular arithmetic) are good use cases, they should not make things complex. We will see if every other use case of "unsigned integer" can be handled by the combination of these two.

certik commented 1 year ago

In CPython, we can use https://pypi.org/project/BitVector/ to represent BitVector, and for ModularInteger, we could use the unsigned integers from NumPy or CTypes (possibly wrapped in our own class), or 3rd party packages like mod.

certik commented 1 year ago

In C, the signed integer overflow is undefined, while unsigned integer overflow wraps around. So ModularInteger wraps around and overflow cannot happen. Integer on the other hand should give a runtime error in Debug mode for overflows, like accessing an array out of bounds.

When interfacing C, the most common usage of unsigned integers is to represent ordinal numbers. In that case, they correspond to ModularInteger, not BitVector. So in BindC we should map ModularInteger to unsigned integer in C.