Behavior on overflow (Index, Signed, ....)

[martijnbastiaan]

#688 has been open for almost two years now, and I feel bad that we haven't responded to it properly. This mostly stems from the fact that its a "controversial" idea, with lots of different opinions. I'm opening a discussion for two reasons:

• To reach a conclusion on that PR, even if it ends in closing/rejecting it.
• To test GitHub discussions :)

The gist of this issue is captured in this trace:

>>> (3 :: Index 4) + 1
<error>
>>> (3 :: Unsigned 2) + 1
0

There are a couple of hypothetical reasons this decrepancy is currently there:

• In most programming languages Unsigned and Signed do not raise an error on overflow. Either because their implementation is bigint (Python, Ruby) or because of -presumably- performance considerations (Haskell, C++, Java). A notable exception to this rule is 🦀 Rust 🦀, it throws an exception in "debug" mode and reverts to silently overflowing on "release" mode.
• Clash inherits Haskell's overflow behavior for Int, it makes sense to mirror them for Unsigned/Signed/..
• Index needs bound checking anyway to be useful, so raising an error is not a performance consideration.

Options

I believe we have a couple of options. If you'd like one added to the list, please edit this post or leave a comment.

Option 1: keep as is (reject PR)

Self-explanatory.

Option 2: make saturation mode wrapping by default for Index (~accept PR)

Do not error on overflow for operations on Index. (I'd like to save discussions on an exact implemenation for later.)

Option 3: make saturation mode non-wrapping (error) by default for Unsigned, Signed, ..

Similar to Rust, we could make overflowing an error for all Clash data types.

Type-level saturation mode

PR #688 also implements a way of specifying saturation mode at the type-level. However, I think we pretty much all agree that @alex-mckenna's proposal makes most sense here. If this does happen to be contentious, we should discuss it elsewhere.

[martijnbastiaan]

My personal opinion on this matter can be captured in a few points:

• I strongly believe that silent overflowing is an historical coincidence, of which the biggest part was "ease of implementation" and in a smaller part "performance". I believe this due to C (and perhaps C++) defining overflow on signed integers as undefined.
• I believe that in most situations silent overflow is not what the developer intented. This argument is weakened by the fact that Clash developers choose their integer widths, but my guess is it still holds.
• I believe the following points are relevant in this discussion (from the Python Zen, ofc):
  • Explicit is better than implicit.
  • In the face of ambiguity, refuse the temptation to guess.
  • Errors should never pass silently.

These points lead me to believe the orange crab language got it right once more, and we should go with Option 3: make saturation mode non-wrapping (error) by default for Unsigned, Signed, ...

---

Couple of points:

• I wouldn't be opposed to a -fno-oob-checks on clash-prelude that'd model the debug/release mode of Rust.
• Int and friends would remain default Haskell behavior, but I think usage of those types should be discouraged in Clash anyway.

[alex-mckenna]

C (and perhaps C++) defining overflow on unsigned integers as undefined

FWIW C/C++ define overflow on signed numbers as being UB (although most implementations wrap, they don't have to) but overflow on unsigned is impossible because it's defined as always wrapping. To quote the C standard:

A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

[alex-mckenna]

I would also be somewhat against a flag in clash-prelude for changing the default. It's not "typical" Haskell to keep changing package flags during development like this IME and I think it would end up being ignored by most users

[martijnbastiaan]

Woops, I meant signed.

[christiaanb]

Clash wraps around on overflow (for Signed and Unsigned) because that's how numerical operators (adders, multipliers, etc.) in their most basic form work in hardware, so it's not an historical coincidence.

[martijnbastiaan]

If we'd merge @alex-mckenna's proposal we'd have to two options I think:

• a `wrapAdd` b (and friends). This would be similar to Rust's wrapping_add.
• a + b in combination with the newtype wrappers

[christiaanb]

Right, so primitives like Clash.Sized.Internal.Unsigned.+# :: Unsigned n -> Unsigned n -> Unsigned n will still wrap around on overflow.

[martijnbastiaan]

Oh yeah, internal primitives would remain the same. I was just thinking about the API we expose to users.

[martijnbastiaan]

(Sorry didn't see your comment @rowanG077)

[martijnbastiaan]

But it's important how backwards compatibility is handled. This would be an API change, is it possible to give a deprecation notice instead of an error when overflow occurs during simulation? That way we could write something like: warning overflow detected. Please use this and that to get proper overflow behavior. this warning will turn into an error from clash x.y.z forward.

I agree, we should think about this and that's probably possible. However, I'd like to postpone discussing implementation details a bit and focus on the direction we're heading. If an option turns out to be infeasible to implement, we can revisit. I don't want another two years of limbo 😄 .

[alex-mckenna]

For reference: my proposal also comes with a mostly finished implementation at clash-num-newtypes

[martijnbastiaan]

This is great :). Any particular reason it's stuck, or just some loose ends?

[alex-mckenna]

IIRC the tests were fiddly to get right and then I got distracted by something else. So it goes

[martijnbastiaan]

So it goes.

[gergoerdi]

So x + negate x == 0 wouldn't be true anymore for Unsigned?

[alex-mckenna]

It would still be true with option 2, I guess @martijnbastiaan prefers option 3 though. I don't think we have consensus on any particular direction yet though, at least not that I'm aware

[martijnbastiaan]

Either @basile-henry's suggestion or x `wrapAdd` negate x == 0 would work.

It would still be true with option 2, I guess @martijnbastiaan prefers option 3 though

Yes, I'm in favor of option 3. I'd like to hear other POVs though!

[basile-henry]

or x wrapAdd negate x == 0 would work

I thought negate would still be an issue here if Unsigned is not allowed wrap.

[alex-mckenna]

Yes, it would error on every call to negate x where x /= 0. So you'd also want to use a safe negate like the one in Wrapping

[martijnbastiaan]

I thought negate would still be an issue here if Unsigned is not allowed wrap.

Yep. I think we need a 🤦 reaction emoji.

[gergoerdi]

Completely anecdotal data point: I have hacked Clash 1.4 locally so that +# and -# error out on over/underflows, to simulate option #3, and then tried to get https://github.com/gergoerdi/clash-compucolor2 working again. It... wasn't pleasant at all.

Even though it's quite a small code base, it was written through and through with the assumption that Unsigned n wraps around. I never even realized it's not part of the intended interface. So then I run the Intel 8080 test suite, and it errors out in simulation with "(+): overflow", but then finding where these additions and subtractions hide (in fun places like using += from Lens) is very painful and only felt doable because the code is so small.

Now, I realize existing code shouldn't be an argument against progress especially if the current behaviour is "wrong" or at least not intended to be exploited by user code, but the wraparound behaviour of Unsigned felt like such a natural thing that I'm sure I can't be the only one who ended up with code depending on it.

(Option #2 sounds great by the way, I was never quite sure why Index doesn't wrap around; I ended up being vaguely convinced that it would be inefficient to do that).

BTW, I was so convinced that the wraparound behaviour of Unsigned is intended, that I even explicitly spelled it out it as such in the upcoming Retroclash book:

[Unsigned and Signed] types are instances of Eq , Ord , Num etc. as one would expect (the Num instance is overflowing, e.g. 6 + 4 :: Unsigned 3 is 2).

[martijnbastiaan]

I love this, thanks @gergoerdi. This is a pretty strong case against defaulting to error.

Now, I realize existing code shouldn't be an argument against progress especially if the current behaviour is "wrong" or at least not intended to be exploited by user code,

I think it's a reasonable argument in cases where the compiler won't tell you to change your code after upgrading.

but then finding where these additions and subtractions hide (in fun places like using += from Lens) is very painful and only felt doable because the code is so small.

Tracking down bottoms is definitely too hard right now.

[rowanG077]

While I agree that migration is hard I feel this is also exactly the reason why you would want this change. The reason migration is hard is because it's unclear when an operation should be allowed to overflow or not so it's not a copy-paste level refactor. It's kind of a double edged sword either you get tortured during the refactor or your design might be subtly wrong because of silent overflows.

Another possibility for #2 would be to be fine with overflow behavior as it is currently and add an overflow error reporting newtype wrapper.

Personally I would still prefer #3 with a reasonably long transition period so people have ample time to migrate but optional error reporting is kinda sexy too.

[martijnbastiaan]

I was never quite sure why Index doesn't wrap around; I ended up being vaguely convinced that it would be inefficient to do that

@christiaanb Could you comment on this? Naively I would say that this is true, as I don't think there's a way without a == plus a mux to implement this.

Also, @christiaanb, a while ago you mentioned that stack traces without profiling builds or HasCallStack constraints might be coming to GHC. If this has any chance of being merged, we might (and I think I prefer) want to do nothing for now (option 1) and reevaluate once that's in a sufficient number of GHCs supported by Clash.

[martijnbastiaan]

As an additional anecdote to this thread: I once spent two days tracking down the source of a bottom in a commercial codebase. It's no fun at all.

[christiaanb]

@martijnbastiaan With regards to error vs wrap-around for Index: My mantra is basically: "performance above all". With Clash you build circuits, you are building circuits instead of writing software because you need that edge on performance. So the compiler and the standard library should do their best to give you the best performing circuit by default. If you want better functionality at the cost of performance, that should be an active choice.

Adding wrap-around to the operators for Index results in an additional multiplexer (we could optimize this away for powers-of-two), thus increasing both area and propagation delay.

With regards to stack traces without profiling and without dwarf, see: https://gitlab.haskell.org/ghc/ghc/-/merge_requests/5456

[martijnbastiaan]

To everyone who replied on this thread:

• Making wrapping by default (option 2) is a no-go, as it would generate additional muxes over the status-quo.
• Keeping everything as (option 1) or being loud about overflows everywhere (option 3) is still up for debate - with the added note that tracking down bottoms with today's Haskell/GHC is unreasonably hard.
• Thanks to @rowanG077's proposal and @alex-mckenna's implementation we now have a very nice way of switching wrapping modes on the type level (https://github.com/clash-lang/clash-compiler/tree/8a52fa339292a14e32bc865b3a4a456844991167/clash-prelude/src/Clash/Num).

Until we have "sane" stack trace support in GHC (https://gitlab.haskell.org/ghc/ghc/-/merge_requests/5456), I'd like to close this discussion. Once that has landed we can revisit to see if option 3 would be reasonable. I'd like to close #688 as this implements wrapping by default (option 2), which to reiterate has been rejected on (HDL) performance concerns.

[rowanG077]

@martijnbastiaan I agree, I have closed #688 as it has been superseded by the wrappers.