[Pre-Pitch] Arithmetic operators that emit NIL on overflow

Evolution Pitches
1

I've been using the FixedWidthIntger.*ReportingOverflow methods so much to safely detect wraparound in my iterators (to return nil on first overreach), I wonder if we can be more direct and take advantage of Swift's nil processing.

precedencegroup CheckedMultiplicationPrecedence {
    higherThan: AdditionPrecedence
    lowerThan: BitwiseShiftPrecedence
    associativity: none
    assignment: false
}

precedencegroup CheckedAdditionPrecedence {
    higherThan: RangeFormationPrecedence
    lowerThan: MultiplicationPrecedence
    associativity: none
    assignment: false
}

infix operator *? : CheckedMultiplicationPrecedence
infix operator /? : CheckedMultiplicationPrecedence
infix operator %? : CheckedMultiplicationPrecedence
infix operator +? : CheckedAdditionPrecedence
infix operator -? : CheckedAdditionPrecedence

extension FixedWidthInteger {

    /// Returns the product of the two given values, emitting `nil` in case of
    /// any overflow.
    @inlinable
    public static func *? (lhs: Self, rhs: Self) -> Self? {
        let result = lhs.multipliedReportingOverflow(by: rhs)
        return result.overflow ? nil : result.partialValue
    }

    /// Returns the quotient of the two given values, emitting `nil` in case of
    /// any overflow.
    @inlinable
    public static func /? (lhs: Self, rhs: Self) -> Self? {
        let result = lhs.dividedReportingOverflow(by: rhs)
        return result.overflow ? nil : result.partialValue
    }

    /// Returns the remainder of the two given values, emitting `nil` in case of
    /// any overflow.
    @inlinable
    public static func %? (lhs: Self, rhs: Self) -> Self? {
        let result = lhs.remainderReportingOverflow(dividingBy: rhs)
        return result.overflow ? nil : result.partialValue
    }

    /// Returns the sum of the two given values, emitting `nil` in case of any
    /// overflow.
    @inlinable
    public static func +? (lhs: Self, rhs: Self) -> Self? {
        let result = lhs.addingReportingOverflow(rhs)
        return result.overflow ? nil : result.partialValue
    }

    /// Returns the difference of the two given values, emitting `nil` in case
    /// of any overflow.
    @inlinable
    public static func -? (lhs: Self, rhs: Self) -> Self? {
        let result = lhs.subtractingReportingOverflow(rhs)
        return result.overflow ? nil : result.partialValue
    }

}

You can use them like:

let two, five, sixtyfour: Int8
two = 2
five = 5
sixtyfour = 64

two +? five  // 7
two -? five  // -3
two *? five  // 10
five /? two  // 2
five %? two  // 1

// All of these return `nil`
sixtyfour *? five
sixtyfour /? 0
sixtyfour %? 0
Int8.min /? -1
sixtyfour +? sixtyfour
sixtyfour -? Int8.min

Instead of using them straight like the above, you'll likely use them with constructs like "guard let", etc. At the time the various "&???" wrapping operators were added, were operators like the above considered to be added as counterparts?

Instead of separate precedence levels, should we let them use the existing MultiplicationPrecedence and AdditionPrecedence? Would we have to add overloads that take one Optional<Self> operand, and an extension for "Optional where Wrapped: FixedWidthInteger" to make overloads when both operands are Optional?

3 Likes
2

You only need the versions of the operators that take Optional on both sides. Non-optional values will be automatically promoted. And of course the operators should use the existing precedence groups.

That said, I believe it was an intentional decision not to provide operators for these functions in the standard library. I could be mistaken though.

1 Like
3

Small nit, I think I would prefer the opposite order of symbols here. Instead of +? I would go with ?+ (for all operators).

4

I'm not really sure that this is something I'd like to see in the standard library. It seems like it would encourage developers to omit handling errors by simply accepting nil as an outcome of their math. While that might sometimes be exactly what you want, other times it might be a programming error that you would want to catch.

That's not to say that every other Swift feature doesn't encourage omission of error handling, like everything this can be abused and used for good. Just my two cents :slight_smile:

1 Like
5

I thought "?+" was restricted. Turns out, although there are restrictions on how {".", "?", "!"} can be used in custom operators, the change you suggested isn't one of them.

You got my intent completely backwards. The new operators are to encourage more error checking, since now we can hook into Swift's Optional-checking machinery, like get let, if let, and compactMap. As-is, you need a custom two-step process. (And if you try ignoring a nil return, you'd get the unused-result error.) For those wanting to ensure everything is OK, an Optional you can check is way better than a surprise run-time error or surprise negative result.

For the same reason, I want us to add a startingIndex: Index? computed property to Collection, to fix the similar problem where checking the first element's index is also a two-step process. Currently, we can't just plop startIndex into a subscript; we need to check if it's less than endIndex first. (We probably need a finalIndex for bidirectional collections too.)

3 Likes
6

The alternative today is to just crash, since realistically the ‘alternative’ that practically everyone uses is to use the regular arithmetic operators and completely ignore the possibility of overflow or other failure cases.

Making a non-crashing approach less painful - one which sensibly utilises Swift’s relatively excellent handling of optionality - is a big step towards more robust & numerically correct code.

As such, I strongly support this in spirit & direction, at the very least. I worry that in substantial, practical use there’ll be quite a lot of optional-handling boilerplate and developer exhaustion consequently, but I don’t know that much can be done about that in the short term - it requires substantial evolution of Swift’s constraints & type system(s). In the interim, this seems like still a great improvement and definitely a step in the right direction (of practically eliminating use of crashtastic operators in idiomatic Swift… one day…).

1 Like
7

Might be a stupid quick thought, but what if we had typed throws and every non throwing operation would technically equal throws Never and the underlying fatalErrors calls would be rewritten to throws fatalError(...), could we start to explicitly opt in and catch fatal errors?

let (lhs, rhs): (UInt8, UInt8) = (.max, 1)
let sum: UInt8
do {
  sum = try (lhs + rhs)
} catch {
  // would this work?
}

If that‘s not that unreasonable, then we wouldn‘t need a whole new set of arithmetic operators and overloads.

Borrowed some parts from this idea:

2 Likes
8

I’m intrigued by the idea of catching fatal errors but it would need to be explicit or else Existing code might start to surprisingly catch fatal errors where before the coder relied on a hard crash.

1 Like
9

The Optional approach requires the evaluation of operators that can be shorted even if overflow errors occur.
I think the throws approach is reasonable rather than the Optional approach.

infix operator +? : AdditionPrecedence
infix operator -? : AdditionPrecedence
infix operator *? : MultiplicationPrecedence
infix operator /? : MultiplicationPrecedence
infix operator %? : MultiplicationPrecedence

struct OverflowError: Error {
}

extension FixedWidthInteger {
    static func +? (a: Self, b: Self) throws -> Self {
        let result = a.addingReportingOverflow(b)
        guard !result.overflow else { throw OverflowError() }
        return result.partialValue
    }

    static func -? (a: Self, b: Self) throws -> Self {
        let result = a.subtractingReportingOverflow(b)
        guard !result.overflow else { throw OverflowError() }
        return result.partialValue
    }

    static func *? (a: Self, b: Self) throws -> Self {
        let result = a.multipliedReportingOverflow(by: b)
        guard !result.overflow else { throw OverflowError() }
        return result.partialValue
    }

    static func /? (a: Self, b: Self) throws -> Self {
        let result = a.dividedReportingOverflow(by: b)
        guard !result.overflow else { throw OverflowError() }
        return result.partialValue
    }

    static func %? (a: Self, b: Self) throws -> Self {
        let result = a.remainderReportingOverflow(dividingBy: b)
        guard !result.overflow else { throw OverflowError() }
        return result.partialValue
    }
}

do {
    let x1 = try 5 +? 4 -? 3 *? 2 /? 1
    print("Result1:", x1)
    let x2 = try 5 +? 4 -? 3 *? 2 /? 0
    print("Result2:", x2)
} catch {
    print(error)
}

// Result1: 3
// OverflowError()
1 Like
10

Or include an arbitrary width integer type which can't overflow (well, not unless you run out of RAM, anyway).

11

Optional-handling seems to be a lot more common than exception handling, so replacing the *Overflow dance with a do/try/catch one seems worse than replacing it with the guard-let or if-let ones. Especially in places like IteratorProtocol.next(), where you can't throw out of.

1 Like
12

I suggested this a couple of years ago and got shouted off the list, but I still support it...

13

The way I spelled it was to allow throws! which is just like throws, but with an implicit try! in front of the call. This allows you to opt-in to see the error, or to get an optional by using try and try? respectively. Then you don't even need new operators (just replace the fatalErrors with throw). It would also be usable by throwing functions in general.

let sum = a + b ///Normal +. Crashes on error
let throwingSum = try a + b ///Now it throws in case of an error
let optionalSum = try? a + b ///Returns an optional in case of an error
6 Likes
14

Do you think we would need a special error type for the arithmetic operations, or would you think Never is already correct type of error to catch here?

15

I've been using the past few days to work on the code that inspired this thread, and more people are talking about exceptions. I have to stomp on these dreams now.

Exceptions are generally for things you can't handle. In other words: if you fail, you bail. They are not for general flow control.

I originally handled my prime-searching code with custom sequences. Then I moved to a special protocol with a fixed partner sequence. I switched to these custom operators in between. Here's my old Sieve of Eratosthenes:

public struct LimitedPrimalitySequence<Integer: FixedWidthInteger>: LazySequenceProtocol {
    @inlinable public init() {}

    public struct Iterator: IteratorProtocol {
        @usableFromInline var upcoming: Integer?
        @usableFromInline
        var primeMultiples: PriorityQueue<(multiple: Integer, prime: Integer)>
        @usableFromInline var pastSquareRoot = false

        @inlinable init() {
            upcoming = Integer(exactly: 2)
            primeMultiples = PriorityQueue(priority: .min, by: <)
        }

        public mutating func next() -> (Integer, Bool)? {
            guard let subject = upcoming else { return nil }
            defer {
                let (successor, failed) = subject.addingReportingOverflow(1)
                upcoming = failed ? nil : successor
            }

            var gotPrime = true
            while let (multiple, prime) = primeMultiples.first, multiple == subject {
                // Indicate a composite was found.
                gotPrime = false

                // Move this prime factor to its next multiple.
                let (nextMultiple, failed) = multiple.addingReportingOverflow(prime)
                if failed {
                    // The counter will overflow before reaching the next
                    // multiple, so don't bother keeping it.
                    primeMultiples.removeFirst()
                } else {
                    _ = primeMultiples.movedFirstAfterUpdating {
                        $0.multiple = nextMultiple
                    }
                }
            }
            if gotPrime, !pastSquareRoot {
                let (square, failed) = subject.multipliedReportingOverflow(by: subject)
                if failed {
                    // Note that all new primes will have their first required
                    // multiple happen after the counter goes past Integer.max,
                    // so don't bother storing them.
                    pastSquareRoot = true
                } else {
                    primeMultiples.push((multiple: square, prime: subject))
                }
            }
            return (subject, gotPrime)
        }
    }

    @inlinable public func makeIterator() -> Iterator { return Iterator() }

    @inlinable
    public var underestimatedCount: Int {
        Integer.max < 2 ? 0 : Int(clamping: Integer.max - 1)
    }
}

It uses the overflow dance. Here's the new version, as part of implementing a protocol.

public struct LimitedPriorityQueueEratosthenesSieve<Integer: FixedWidthInteger>: WheeledPrimeChecker {
    typealias PrimeMultiple = (multiple: Integer, prime: Integer)
    var primeMultiples = PriorityQueue<PrimeMultiple>(priority: .min, by: <)
    var pastSquareRoot = false

    @inlinable public init<S: Sequence>(basis: S) where S.Element == Integer {}

    public mutating func isNextPrime(_ coprime: Integer) -> Bool {
        var gotPrime = true
        while let (multiple, prime) = primeMultiples.first, multiple <= coprime {
            if multiple == coprime {
                gotPrime = false
            }

            if let nextMultiple = multiple +? prime {
                _ = primeMultiples.movedFirstAfterUpdating {
                    $0.multiple = nextMultiple
                }
            } else {
                primeMultiples.removeFirst()
            }
        }
        if gotPrime, !pastSquareRoot {
            if let square = coprime *? coprime {
                primeMultiples.push((multiple: square, prime: coprime))
            } else {
                pastSquareRoot = true
            }
        }
        return gotPrime
    }
}

In neither case do I bail on a wrap around; which means my needs here are not exceptional. On wrap-around, I take another branch instead to end some part of my iteration. And both branches are method-local. Since I don't kick the wrap-around to external code, a theoretical throwing operator would require a do/try/catch mechanism within the method. That exception dance would be even bigger than the overflow dance.

Plus, since IteratorProtocol.next can't throw, I would have to include an universal catch in the first version if I used throwing operators. Overall, Optional-handling is much better for me in this case.

1 Like
16

I wouldn't describe it as stupid, but there are disadvantages which is why it hasn't been done.

Perhaps the biggest is that the code at the site of failure should have taken responsibility for recovering and throwing an Error if recovery seemed obvious or appropriate. A precondition failure for example means the state of the program was found to be inconsistent - there is no commonly understood way on how to get that state consistent. Instead of continuing with inconsistent state, the application is terminated immediately to increase the chance of the problem being found and fixed.

There were suggestions in the past to bound that state into an execution context, and terminate that context rather than the process itself. For example, in a server environment running multiple actors, a precondition failure might instead lead to that actor being terminated.

Math is an example where a propagating error makes sense, but instead the goal was to add checked operations to accommodate cases where the developer is planning to accommodate for math errors like overflows.

Using Optional, thrown errors, or even Result are basically tacking on a 'NaN' case to integers (with throwing being a signaling NaN, and Result possibly allowing for application error state). These have additional state and performance impacts unfortunately. Having overflow be a fatal error is nice because it doesn't require any state or have any performance impact, because it can leverage the interrupts/signalling of the CPU/OS - and because terminating an application doesn't require a whole lot of state tracking.

17

Having optionals and exceptions at all are all extra overhead - much more efficient to just crash the whole process.

18

Not crash, but yes for aborting the process.

19

Do you think end users care about that semantic distinction?

20

Unless, arguably, you want to run tests. The pain point inspiring my pitch above was that I wanted my sequences to detect when they're about to overflow and just simply end, instead of crashing (which loses your last test and anything that would have gone after).