[Proposal] [Leo RFC] Arbitrary-size integers

[acoglio]

💥 Proposal - Leo RFC

Summary

Besides the integer types with fixed sizes, we may consider supporting a type that can contain any integer, as done in other languages (e.g. Lisp, Python). We may also consider a type that can contain any non-negative integer.

Motivation

Arbitrary-size integers are convenient and avoid unexpected wraparounds or errors. They spare the user from having to figure out the appropriate bit size for certain computations, letting the machine take care of the details (i.e. "use as many bits as needed for this").

Design

Given the u<n> and i<n> naming, we could use i* for the type of all signed (i.e. negative and non-negative) integers, and u* for the type of all unsigned (i.e. non-negative) integers. Or some other name(s).

These types should not be used for inputs and outputs exchanged between Leo code and the external world (i.e. the Aleo blockchain), but they may be used internally to a program. Given Leo's requirements for "static finiteness" (bounded loops, etc.), it should be always possible for the compiler to figure out at least some upper bound on the number of bits needed.

This proposal is independent from #627. However, if that proposal is adopted, then one of the transformations made by the Leo compiler could be to replace all the uses of i* and u* with i<n> and u<n> for appropriate <n> (different ones in different places). The proof of correctness for this transformation would show that the use of the former types is equivalent to the use of the latter types.

Note: This proposal requires a bit more research and analysis.

Drawbacks

This adds complexity to the language and compiler, requiring the capability to automatically infer (upper bounds on) bit sizes.

The upper bounds for numbers of bits inferred by the compiler has to be conservative and therefore may be surprisingly large in some cases. This may be mitigated by appropriate warning messages, by user help, and by the ability to report sufficiently detailed information to the user about the circuit size.

Effect on Ecosystem

None?

Alternatives

Stick to integer types with explicit sizes. (Either the current 5 sizes, or the flexible sizes proposed in #627.)