Infinite precision intermediate arithmetic: how much would break?

language design
1

I wonder how much stuff would break if the rules for evaluating arithmetic expressions were changed like so:

  1. All arithmetic expressions are evaluated as-if in ℝ (or ℂ if necessary). In particular, all widening conversions become redundant, and / and >> produce the mathematically correct dividend.
  2. At each point where the result of an arithmetic evaluation must be ascribed a definite type, that type is chosen based on surrounding context, and it is an error if the compiler cannot prove that all possible outputs of the calculation are representable in that type.
  3. You can fix those errors by writing explicit narrowing conversions that tell the compiler what to do when the result is inexact or out of range. Generated machine code is guaranteed to truncate or round results only where one of these explicit conversions appears.
  4. There is a way to write pure functions that take arguments and/or return values in the infinite-precision intermediate representation (this is necessary at least to implement the math library; it can probably be private to std to begin with).

For example, with these rules let sum: u64 = a.saturating_add(b).saturating_add(c) could become let sum:u64 = (a + b + c).saturate().

I'm sure there are a whole bunch of problems with this idea, but the thing is, the last several times I got in a fight with Rust's type system all involved needing to write a zillion explicit conversions among u32, u64 and usize, so right now my gut feeling is the fallout might be worth it.

2 Likes
2

This is, btw, essentially what C does, except the "infinite" precision is just to long int, and narrowing coercions back are implicit.

Realistically, this proposal hinges on the ability of the compiler to prove non-overflow in "typical uses", and that would require importing a lot of machinery to the front end from LLVM, be difficult to write a specification for, and would probably fail often enough that people would get massively frustrated when their i += 1 doesn't work and has to be rewritten as i = (i + 1).unwrap() or something. Proving anything about basic arithmetic is, of course, undecidable in the fully general case and NP-complete in somewhat less general cases; the optimizer gets away with it because it works strictly on a best effort basis. But surface language semantics cannot be best-effort.

3

(This is not what C does, C only implicitly goes up to int.)

4

Oops, should've checked, I thought it was to long (which is the same thing in many cases, but anyway…) Fixed.

5

The first problem is performance. Widening integer operations to i/u128 makes them way more expensive; widening float operations to ℝ will require extremely costly software calculations.

The second problem is that this is silently breaking a lot of code and there is basically no way to estimate the breakage; this is the worst kind of breakage.

But the worst of all is that C has shown that promotion rules are deeply unintuitive and confusing, and the vast majority of developers never understand them well. The current "no implicit conversions" policy is a very good idea even if it sometimes costs in extra characters. Performing implicit widening conversions is bad but acceptable; performing implicit narrowing conversions, like you suggest here, is a terrible idea.

3 Likes
6

Besides what @jrose already said about this, there is a huge practical difference between "only goes up to [some fixed-length type]" and actually going to infinity in both directions. For example, in C comparisons between signed and unsigned values silently do the Wrong Thing, and in Rust (as it is now)

pub fn isless(a: i32, b: u32) -> bool {
    a < b
}

fails to compile but the suggested fix does not produce code that computes the mathematically correct answer. Under my proposal this would be equivalent to

pub fn isless(a: i32, b: u32) -> bool {
    // a u32 value that doesn't fit in i32 must be greater than all
    // possible i32 values
    i32::try_from(b).map(|ib| a < ib).unwrap_or(true)
}

It is my hope that the same proofs of non-overflow that are required anyway can also be used to prove that register-sized calculations are correct in most cases. We would presumably have to relax the principle somewhat for transcendental functions, because of the Table-Maker's Dilemma.

promotion rules are deeply unintuitive and confusing, and the vast majority of developers never understand them well

I am explicitly claiming, as part of this proposal, that the rule "all calculations behave as-if they were carried out in the mathematical real numbers, and then, if the result doesn't always fit in the type of the target variable, you have to say what should happen for the edge cases" will be much easier to understand. I believe this claim because that rule is already basically what high-level interpreted languages like Python and Lisp do, and you never hear about people struggling with their promotion rules.

Also, there are no implicit narrowing conversions under this proposal. Only situations where the compiler can prove that no conversion is required.

This is a legit concern but I think a forward-only value range propagation pass, using rules like what we already have for whether it's OK to write "let blah;" with no initializer, will probably be good enough and not too much hassle to specify or implement. Whether I'm right, probably requires actually trying it to answer. (Java's "definite assignment" rules are also in the same ballpark and are, at least, not an undue burden on implementations; I cannot say whether people who've written a lot of Java find them annoying, though.)

7

The intermediate representation has to be infinite-precision for something like this to work correctly. (And it is much easier to implement with ints than with floats.)

I do think this is generally the correct approach to take, because it's both easy to use as a programmer and means you reliably get an error when overflow isn't handled correctly. However, there are a lot of cases that make it hard for a compiler to reason about. For example:

fn count_odd_elements(slice: &[usize]) -> usize {
    let mut count = 0;
    for element in slice { count += element % 2; }
    count
}

Here, count cannot overflow because the length of the slice (and thus the number of loop iterations) is less than usize::MAX. But proving the lack of overflow requires reasoning about the code as a whole – the count += element % 2; line could potentially overflow if count were initialized to a higher value.

This makes me think that it would be very hard to retrofit an approach like this onto Rust: you would probably need to bake the reasoning about integer ranges into the entire language.

1 Like
8

In green-field there's a version of this that works great, actually. I don't think it'd be feasible to more Rust's default numerics to doing it, but for something new (or maybe a new type in Rust?) it actually works wonderfully.

Basically, you have a const-generic Int<MIN, MAX> type that represents values in MIN <= x <= MAX. A literal 4 has type Int<4, 4>. And you use the well-known rules (https://en.wikipedia.org/wiki/Interval_arithmetic#Interval_operators) to expand the range accordingly.

For example, in (a + b) / 2 if a and b are both Int<-10, 100>, then a + b has type Int<-20, 200> and 2 has type Int<2, 2>, and thus (a + b) / 2 also has type Int<-10, 100>. Exactly back to the original type, computing the correct value, and zero need to think about wrapping and such ever. Thus no need for u32::midpoint and friends, plus it automatically works for things we don't have methods for today: a binomial filter like (a + 3 * b + 3 * c + d)/8 also just works.

It's clearly a net win to only have to think about saturate/checked/wrap once at the end of an expression instead of for every step in the middle. And LLVM will already optimize down the size of your intermediates if you don't need them as big based on how it's used in the end: see https://rust.godbolt.org/z/c3fT4GcvE for an example, and note that while the rust code has u128 multiplication and addition, it's optimized down to just u32 operations.

Which means that, no

isn't the case because they're only widened if you actually need the extra precision.

Correct-by-default is the way to go, even if that can sometimes be more expensive, since you can always recover the previous behaviour by manually narrowing intermediate results if you want to give up correctness for performance in some places.

The actual "downside" here is that you have to specify the types of mutable integers like loop accumulators, and things like += basically stop working inside loops. But arguably that's a good thing -- if you're summing a whole bunch of u8s you probably didn't actually want a u8 result -- and better overall than needing to worry about overflow at every operation.

In languages like C it would be really painful because for (i = 0; i < n; ++i) wouldn't work, but obviously in Rust we spell that for i in 0..n where the Range type would just do the right thing, like it does today.

(Constructing a RangeInclusiveIter from start: Integer<A, B> and last: Integer<C, D> would give you an impl Iterator<Item = Integer<A, D>>, for example. Where you'll notice that B and C are irrelevant, which is nice.)

5 Likes
9

The research term for this, by the way, is "AIR model" ("as-if infinitely ranged"). As mentioned, it's much easier to implement for integers than floats, and it would be a good idea to treat them as separate problems. (I also agree that retrofitting it onto Rust today is probably a non-starter—even the behavior of implicitly panicking on overflow is probably depended on by somebody.)

I do think allowing mixed-width mixed-signedness comparisons is more viable; Swift managed to pull that one off. Even that can cause confusion sometimes though, for people used to C semantics.

(Alas, "this is what Lisp and Python" do is brushing over the hard part. Those languages will implicitly allocate when numbers get big, but they won't panic, saturate, or wrap the result; it just stays as is. Every number in those languages is effectively a bigint, some of them just have optimized representations.)

2 Likes
10

On a more practical level, this would be lovely to have in a const context specifically. It's not a huge deal most of the time, but having things decay into i32s when I never wanted them to can be annoying to work around, and it would be part of making fluent looking bigints.

11

We have algebraic arithmetic methods on floats. We could have them on integers.

12

I want a compile-time-only bigint specifically. At compile time doing like Python does and allocating when it gets big would be completely fine. And it would be really nice to just use Foo<const BAR: BigInt> without needing to pick a size at all in places where you don't really care.

2 Likes
13

Having this in combination with some implemented-but-unstable const features would effectively give us int<min, max>. That's my holy grail that I eventually want in the compiler, but will settle for deranged if needed.

14

While this might work for arithmetic (though not when retrofitted), what about bit twiddling? It seems error prone to me if the compiler tries to guess the integer width in that type of code.

Personally that is common for me (SWAR and SIMD code with lots of bit twiddling), so I would rather that sort of code has less footguns, as such code is far trickier than general arithmetic code to begin with.

1 Like
15

it's totally possible to figure out the exact range of bit-twiddled values (when working an operator at a time), and from the range you can deduce the width in bits. it is a bit complicated so I'm not going to write it all out here, but e.g. !v is just -1 - v and v << s is just v * 2.pow(s).

I'd want ranged integers int<min..=max> and also arbitrary fixed bit-width integers u<N>/i<N>.

1 Like
16

For existing Rust code: Yes, it would break too many things (e.g. if someone relies on wrapping behavior with --release). But I don't think we need or necessarily want a new type for this. It would probably be better to add a block that lets you change the behavior of these operators, that way you can easily switch between them and not need to replace + with *_add everywhere.

Example:

// Keep the existing behavior (i.e. wrapping in --release, checked in debug builds)
a + b * c;

// A block that allows implicit type changes as long as there are provably no
// overflows and it behaves as it would with arbitrary-size integers
// (i.e. the behavior proposed in this thread)
bikeshed {a + b * c};

// Explicitly opt-into wrapping in both cases (both do the same thing)
a.wrapping_add(b.wrapping_mul(c));
wrapping {a + b * c};

// Saturating
a.saturating_add(b.saturating_mul(c));
saturating {a + b * c};

// Checked with result propagation
checked {a + b * c}.unwrap(); // checked block returns option
// Roughly equivalent to:
function foo(a: usize, b: usize, c: usize) -> Option<usize> {
    a.checked_add(b.checked_mul(c)?)
}
foo(a,b,c).unwrap()

Inspiration: unchecked in solidity which removes overflow checks.

With pattern types (might have been called something else) that'd be like your Int<MIN, MAX> but easier to use together with normal integer types. Implementing a separate type would probably be easier than arithmetic mode blocks + (internal) pattern types, but using the existing integer types makes it feel more natural and part of the language. [1]

Another advantage is that you could if that is desired (for new projects or after careful consideration of all arithmetic) set the default for an entire module/crate. To me being able to specify the behavior of a block of operations feels more useful and flexible for the future than completely separate types or not having AIR in the language entirely (+ it's convenient for things like wrapping behavior).

Those blocks might be possible to do with a macro, but the AIR part (named bikeshed above) probably isn't.

  1. If I remember correctly there was also the proposal to replace/alias the primitives with Int<MIN,MAX> as an alternative to pattern types. ↩︎

1 Like
17

!v definitely depends on the bit width. What does one do with !i32::min() otherwise? Panic or extend? If this is then & or | with a value, there are questions of what width those operations work at. Sign extension also comes into play. What of bit-twiddling like Fast inverse square root - Wikipedia as well?

18

!i32::MIN == i32::MAX at every bit width.

!, & and | behave the same at every signed bit width, and Python has them on infinite width. The only issue is that ! automatically wraps on unsigned types.

19

In infinite-bit-width two’s complement arithmetic, you abstractly never have a single sign bit at all; instead, the integer has either an infinite sequence of zeroes to the left (if nonnegative) or an infinite sequence of ones to the left (if negative). This is the same thing as sign extension, just expressed as an intrinsic property of the number rather than a conversion step.

5 Likes
20

One reason that twos-complement ends up working well is that in the same sense as 1 + 2 + 3 + 4 + ... = -1/12, you can easily see that 1 + 2 + 4 + 8 + ... = -1:

 S = 1 + 2 + 4 + 8 + ...

2S = 2 + 4 + 8 + 16 + ...

2S - S =       (2 + 4 + 8 + 16 + ...)
         - (1 + 2 + 4 + 8 + ...)

     S = -1

and thus 0b111...111 being -1 is, in a sense, more mathematically correct than treating it as a sign-magnitude representation.

So infinite precision bitops are thus really not a problem at all.

2 Likes