[swift-evolution] Marking sort and sorted with rethrows

John McCall rjmccall at apple.com
Thu Jun 9 15:36:00 CDT 2016


> On Jun 9, 2016, at 12:59 PM, Dave Abrahams <dabrahams at apple.com> wrote:
> on Thu Jun 09 2016, John McCall <rjmccall-AT-apple.com> wrote:
> 
>>> On Jun 9, 2016, at 9:04 AM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>> on Wed Jun 08 2016, Brent Royal-Gordon <brent-AT-architechies.com <http://brent-at-architechies.com/>> wrote:
>>> 
>>>>> I'm not sure that these ideas are consistent with the Swift
>>>>> error-handling philosophy, which IIUC is very consciously designed *not*
>> 
>>>>> to support things like file- and database-backed Collections.  My
>>>>> understanding is that if you have something like that, you're not
>>>>> supposed to throw errors on failure, but instead find some alternative
>>>>> means of error handling.  These cases seem very much in the same
>>>>> ballpark.
>>>> 
>>>> I'm not talking about the Collection itself being backed by a file,
>>>> but rather the instances inside it being backed by a file. 
>>> 
>>> Those amount to the same thing.  If instances can be backed by a file,
>>> subscripting needs to be able to throw, and therefore practically every
>>> generic function (or protocol extension method) on Collection would also
>>> need to be marked as throwing.  When Swift error handling was designed,
>>> it was decided that these cases were out-of-scope.
>> 
>> Right.  It would be simple to change core library protocols to permit operations
>> to throw, but then every use of an algorithm over those protocols would throw.
>> This is the sort of problem that we address with 'rethrows', but that's quite a bit
>> more complex to apply to protocol conformances because you need to be more
>> specific about which requirements, exactly, will cause you to rethrow.  
> 
> Can you show an example?  It seems simple to me: if you're going to
> possibly rethrow you can use any requirements that might throw, and if
> you're not going to rethrow then you can't.

Right, but we don't have a way to talk about whether individual requirements or
even conformances might throw.  It's not obvious that something as coarse-grained
as "a conformance is non-throwing if every throwing requirement of the protocol
and everything it inherits is satisfied by a non-throwing function" is actually good
enough to express the constraints we want to express, especially if we ever want
to allow programmers to add additional (defaulted) requirements in protocol
extensions.

>> It also causes problems for generic types, which might have arbitrary
>> methods that rethrow based on the conformances of their generic
>> arguments; and perhaps the result of that decision would also need to
>> be expressible in a rethrow constraint on some other operation, etc.
>> We haven't been able to find a language design here that isn't
>> extremely bureaucratic.
> 
> We also haven't really tried, IMO.  My understanding was that Swift
> error handling was explicitly *not supposed* to handle these cases, as
> though it was a design goal.  When you start with that as a basis you're
> not going to find a good answer because you're not supposed to be
> solving the problem in the first place.

I really try not write things off a priori like that.  I remember spending several weeks
investigating what I thought would be necessary to make conditional throws
propagation work in the generics model and was not very satisfied with the results.
IIRC, my concerns were partly around the complexity of specification, given that I
was very worried that a coarse-grained model was not going to prove expressive
enough, and partly because I didn't feel that the model applied very cleanly to
generic types.

At that point, I made the call that, as far as I was concerned, the use cases for
throwing conformances weren't worth complicating the initial proposal over.
I don't consider it a closed question; I just don't think it was feasible to solve it
in the first release, and it hasn't been a priority to revisit.

Other people may have been more summary.  I can't speak for them.

>> In short, there are three options that we have discovered so far:
>> 1) Introduce massive complexity and bureaucracy into the generics system
>>  to propagate rethrows-like dependencies on throwing conformances.
>> 2) Abandon typed propagation.
>> 3) Force protocols to make a choice, with the understanding that this will
>>  generally mean forbidding throwing conformances.
>> 
>> We do not consider (1) or (2) acceptable, so we chose (3).  If someone
>> finds a way to express typed propagation in generics at minimal
>> expressive cost, we'd be happy to reconsider this decision.
> 
> AFAICT, this is not that hard to do.  IIUC, my original proposal for the
> “rethrows” keyword would have solved these problems.  My understanding
> was that it got no traction because solving them was considered an
> anti-goal.

Like I said, I think it really depends on how coarse-grained the tracking is allowed to be,
and what impact that has on the rest of the language and its evolution.

John.


> 
>>>> I suppose you're trying to acknowledge that distinction when you say
>>>> these cases are "in the same ballpark", but I don't think that's
>>>> really a sustainable objection.
>>> 
>>> Why not?
>>> 
>>>> There *are* sensible alternatives, like the early-terminating block
>>>> pattern, to throwing sequences and perhaps even throwing collections:
>>>> 
>>>> 	try database.withQuery(sql) { rows in
>>>> 		for row in rows {
>>>> 			// If fetching a row fails, this loop terminates early and `withQuery` throws
>>>>>>>> 		}
>>>> 	}
>>> 
>>> That strategy doesn't begin to cover the use cases for collections.
>>> 
>>> Also, how is it supposed to work? You need a way to report a failure to
>>> fetch the row—a way that doesn't involve throwing.  Who terminates the
>>> loop, and how?  How does withQuery detect that the loop exited early?
>>> 
>>>> But throwing operations on stuff-inside-a-collection? That's just part
>>>> of the language, and making errors during sorting extraordinarily
>>>> difficult to handle won't stop the errors from being possible.
>>> 
>>> There's basically no distinction.  If it's reasonable to have sort with
>>> a throwing predicate, it's also reasonable to have a Comparable type
>>> whose < operator throws, and it's reasonable to use the sort overload
>>> that takes no explicit predicate, and now you have a Collection protocol
>>> method that throws directly, rather than rethrowing.  IIUC from the
>>> people who designed Swift error handling, if you find yourself doing
>>> that, you've done something wrong.
>>> 
>>>> * * *
>>>> 
>>>> I actually think there *is* a sensible way to define the behavior of a
>>>> throwing `sort(_:)`: you treat the comparison as though it returned
>>>> `false` and continue sorting. 
>>>> If there's any sort of stability to the errors being thrown by
>>>> `isOrderedBefore`, this will end up behaving like a sort with
>>>> unordered elements, much like an array of floating-point types with
>>>> some NaNs in it. You not be able to rethrow all of the errors
>>>> encountered during the sort—you'd have to pick the first or last—but a
>>>> representative error would probably cover the use cases here.
>>> 
>>> As Dmitri pointed out, that predicate doesn't satisfy the requirements
>>> for sorting.  It's quite possible that a predicate that doesn't satisfy
>>> an algorithm's requirements causes the algorithm to do invalid indexing
>>> or some other evil nonsense.
>>> 
>>>> You could implement this with today's Swift in terms of our existing `sort(_:)`:
>>>> 
>>>> 	mutating func sort(isOrderedBefore: (Element, Element) throws -> Bool) throws {
>>>> 		var lastError: Error?
>>>> 
>>>> 		sort {
>>>> 			do {
>>>> 				return try isOrderedBefore($0, $1)
>>>> 			}
>>>> 			catch {
>>>> 				lastError = error
>>>> 				return false
>>>> 			}
>>>> 		}
>>>> 
>>>> 		if lastError = lastError { throw lastError }
>>>> 	}
>>> 
>>> Aside from the problems mentioned above, this is extremely inefficient
>>> if the collection is large and backed a resource that fails slowly, such
>>> as a network connection with retry and timeout.
>>> 
>>>> I don't think you could currently do one version with `rethrows`,
>>>> because any way you do this, you'll need to save an error in a
>>>> variable and `throw` it later, which I don't believe `rethrows` will
>>>> permit. 
>>> 
>>> Right.  That's a problem with the error-handling model.
>>> 
>>>> However, I saw a suggestion in the bottom type thread that, given both
>>>> a `throws` keyword that can take an error type and a bottom type to
>>>> represent the error type of a non-throwing function, `rethrows` could
>>>> essentially be syntactic sugar for a function with a generic error
>>>> type. This would give us additional flexibility in cases like this
>>>> where `rethrows` doesn't quite do what we need.
>>>> 
>>>> With the necessary features in place, we could implement a `rethrows`-ish `sort(_:)` like this:
>>>> 
>>>> 	// This declaration has rethrows-like behavior: if `isOrderedBefore`'s error type is `Never`, then 
>>>> 	// `sort(_:)`'s error type is also `Never`, and there's no reason to require a `try` on the call to this method.
>>>> 	mutating func sort<Error: ErrorProtocol>(isOrderedBefore: (Element, Element) throws Error -> Bool) throws Error {
>>>> 		var lastError: Error?
>>>> 
>>>> 		func isOrderedBeforeWithUnorderedErrors(a: Element, b: Element) -> Bool {
>>>> 			do {
>>>> 				return try isOrderedBefore(a, b)
>>>> 			}
>>>> 			catch {
>>>> 				lastError = error
>>>> 				return false
>>>> 			}
>>>> 		}
>>>> 
>>>> 		// Do the actual sorting here.
>>>> 
>>>> 		if lastError = lastError { throw lastError }
>>>> 	 }
>>> 
>>> That's cute, but IIUC the designers of the error handling model
>>> explicitly did *not* want to thread throwing-ness through generics in
>>> this way.  This is roughly the same mechanism as would be required to
>>> accomplish other things I'd like to see, like the
>>> sorting-throwing-Comparables thing I mentioned above, but that were
>>> designed out of the model.
>>> 
>>> FWIW, it would need to be generalized further, in case there were two
>>> operations that throw different Error types.  Also, I know some will
>>> disagree, but IMO you really don't want to get into a situation where
>>> people are annotating most throwing functions with the exact Error types
>>> that can be thrown.
>>> 
>>> You need a way to express the type
>>> 
>>>   if (E0, E1, ... EN).contains(Bottom) then Bottom else ErrorProtocol
>>> 
>>> where Ei is one of the thrown error types, and for protocol methods that
>>> are not marked with an explicit throws annotation, that type should be
>>> synthesized automatically from the error types that can propagate from
>>> any operations in protocol dependencies... but ah, as I say, IIUC this
>>> sort of thing was designed out of the model.  
>>> 
>>> My point isn't that what you're trying to do is wrong.  My point is that
>>> it seems inconsistent with the Swift approach to error-handling, and
>>> that if you want to do these things, you may need to convince someone to
>>> change that approach.
>>> 
>>>> With a fair bit of work, it might even be possible to allow it to throw *all* of the errors it encountered:
>>>> 
>>>> 	// This is structured slightly strangely to ensure that, if Error is Never, then MultipleErrors<Never> 
>>>> 	// is an empty enum (since all cases require a Never associated value), and thus (hopefully!) 
>>>> 	// is itself a synonym for Never.
>>>> 	enum MultipleErrors<Error: ErrorProtocol>: ErrorProtocol {
>>>> 		case one (Error)
>>>> 		indirect case many (Error, ErrorList<Error>)
>>>> 
>>>> 		func appending(_ newError: Error) -> MultipleErrors<Error> {
>>>> 			switch self {
>>>> 			case let .one(oldError):
>>>> 				return .many(oldError, .one(newError))
>>>> 			case let .many(firstError, restErrors):
>>>> 				return .many(firstError, restErrors.appending(newError))
>>>> 			}
>>>> 		}		
>>>> 	}
>>>> 
>>>> 	extension<Error: ErrorProtocol> Optional where Wrapped == MultipleErrors<Error> {
>>>> 		func appending(_ newError: Error) -> MultipleErrors<Error>? {
>>>> 			switch self {
>>>> 			case .none:
>>>> 				return .some(.one(newError))
>>>> 			case .some(let errors):
>>>> 				return .some(errors.appending(newError))
>>>> 			}
>>>> 		}
>>>> 	}
>>>> 
>>>> 	mutating func sort<Error: ErrorProtocol>(isOrderedBefore: (Element, Element) throws Error -> Bool) throws MultipleErrors<Error> {
>>>> 		var errors: MultipleErrors<Error>?
>>>> 
>>>> 		func isOrderedBeforeWithUnorderedErrors(a: Element, b: Element) -> Bool {
>>>> 			do {
>>>> 				return try isOrderedBefore(a, b)
>>>> 			}
>>>> 			catch {
>>>> 				errors = errors.appending(error)
>>>> 				return false
>>>> 			}
>>>> 		}
>>>> 
>>>> 		// Do the actual sorting here.
>>>> 
>>>> 		if errors = errors { throw errors }
>>>> 	 }
>>> 
>>> IMO that would be a collosal waste of resources.  The only interesting
>>> error is the first one.  This is notionally a sort that failed partway
>>> through, and that we had no mechanism for interrupting.  The fact that
>>> you have to continue sorting after that error is just an artifact of
>>> language limitations.  Either we should reaffirm our current (implicit)
>>> declaration that these kinds of use-cases are off the table for Swift
>>> error handling, or the philosophy of Swift error-handling should change
>>> to allow us to support stopping at the right time.
>>> 
>>> -- 
>>> Dave
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>> <https://lists.swift.org/mailman/listinfo/swift-evolution>
> 
> -- 
> Dave



More information about the swift-evolution mailing list