Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ASR: Add BitVector and ModularInteger #1578

Open
certik opened this issue Mar 14, 2023 · 2 comments · May be fixed by lfortran/lfortran#1442
Open

ASR: Add BitVector and ModularInteger #1578

certik opened this issue Mar 14, 2023 · 2 comments · May be fixed by lfortran/lfortran#1442

Comments

@certik
Copy link
Contributor

certik commented Mar 14, 2023

--- 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
Copy link
Contributor Author

certik commented Mar 14, 2023

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
Copy link
Contributor Author

certik commented Mar 14, 2023

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant