Arithmetic seems to be under-specified

[enkore]

ints and arithmetic on them seem to be a little bit loosy-goosy in the spec

• The size of int is implementation defined, but there is no minimum required size. Hypothetically, 3 + 3 = <dynamic error> would be compliant. A reasonable minimum might be 32 or 64 bits.
• There are ways to manipulate the bit-representation of an int, but the spec doesn't say what that is. The spec should likely define int as two's complement. (Yeah I know this is kinda nitpicky, since two's complement is practically universal)
• It's not specified whether shifts are arithmetic (i.e. sign-extending) or logical. Python shifts are purely arithmetic (x << n is a shorthand for x * 2**n, x >> n is short for x // 2**n).
• Shift amounts larger than the size of int should probably be a dynamic error (currently: "Implementations may impose a limit on the second operand of a left shift.")
• Starlark does not have Python's ** operator.

[alandonovan]

ints and arithmetic on them seem to be a little bit loosy-goosy in the spec

Indeed.

The size of int is implementation defined ... A reasonable minimum might be 32 or 64 bits.

The Java implementation, like the Go one, now has multiprecision integers and exact arithmetic. The Rust implementation appears to use int64 (https://github.com/google/starlark-rust/blob/8be4061e89ff088b5b219e59fa3ef360c291167c/starlark/src/values/int.rs#L88), but I am not fluent in Rust.

I would like the spec to require that implementations can represent all the values of uint64 and int64 without loss, as this is a prerequisite for analysis of protocol messages. However, the difficulty and efficiency of implementing "int65" is about the same as bigint, so the spec should really just require infinite precision. It is certainly cleaner and more useful. Perhaps the Starlark-rust folks (@damienmg, @stepancheg) could chime in: how hard would it be for the Rust impl to support big ints?

There are ways to manipulate the bit-representation of an int, but the spec doesn't say what that is. The spec should likely define int as two's complement.

Agreed. This is implied, but should be stated.

It's not specified whether shifts are arithmetic (i.e. sign-extending) or logical. Python shifts are purely arithmetic (x << n is a shorthand for x * 2n, x >> n is short for x // 2n).

Like Python, Starlark shifts are arithmetic. This should be stated in the spec, along with the means of achieving a logical right shift.

Shift amounts larger than the size of int should probably be a dynamic error (currently: "Implementations may impose a limit on the second operand of a left shift.")

With infinite precision, there is no "size of an int". However, one still needs a limit to avoid consuming all available memory. I think it's fine to leave that limit as an implementation detail.

With finite precision, the operation may succeed but discard some high bits. It would be impractical to make it an error if the result is lossy, as this is a widely used operation, but this makes the finite vs infinite precision implementations very different. The ideal outcome is that precision is required to be infinite.

Starlark does not have Python's ** operator.

Seems like a reasonable addition, though there is little demand so far for a math package.

[illicitonion]

ints and arithmetic on them seem to be a little bit loosy-goosy in the spec

Indeed.

The size of int is implementation defined ... A reasonable minimum might be 32 or 64 bits.

The Java implementation, like the Go one, now has multiprecision integers and exact arithmetic. The Rust implementation appears to use int64 (https://github.com/google/starlark-rust/blob/8be4061e89ff088b5b219e59fa3ef360c291167c/starlark/src/values/int.rs#L88), but I am not fluent in Rust.

I would like the spec to require that implementations can represent all the values of uint64 and int64 without loss, as this is a prerequisite for analysis of protocol messages. However, the difficulty and efficiency of implementing "int65" is about the same as bigint, so the spec should really just require infinite precision. It is certainly cleaner and more useful. Perhaps the Starlark-rust folks (@damienmg, @stepancheg) could chime in: how hard would it be for the Rust impl to support big ints?

Should be fairly trivial using something like https://github.com/rust-num/num-bigint and Rust has good support for checked operations with overflow detection, so it would be fairly simple to promote to bigints only where necessary.

[alandonovan]

Ping @stepancheg?

[stepancheg]

how hard would it be for the Rust impl to support big ints?

• Relatively easy provided the external bigint library is good enough
• I think it's OK for some implementation to lag behind the spec or explicitly deviate from the spec for some reasons technical or otherwise; this repo test suite can be adjusted to handle these cases

For example Jython (which looks dead, but nevertheless) is quite different from CPython https://www.jython.org/jython-old-sites/archive/21/docs/differences.html but still it was useful for lots of project.

[alandonovan]

Thanks, Stepan. I agree that partial or nonconforming implementation are still useful, but I want to make sure we all agree that multiprecision integer arithmetic is the right goal. If so, the maintainers of the Rust implementation can treat its current behavior as a bug with whatever priority you decide.

[stepancheg]

CC @ndmitchell

[ndmitchell]

I plan to add bigint support, since it makes the language more predictable. It's not particularly high on the todo list though, since its also not very impactful. But it is definitely on the todo list, and I agree its the right goal.

[alandonovan]

Ok, thanks. (As a practical matter, make sure your API is ready for bigints even if the implementation isn't; it'll save you time later.)