6 ms·

The big language design problem that I think this post highlights is that the flip side of Julia's composability is that composing generic code with types that

The big language design problem that I think this post highlights is that the flip side of Julia's composability is that composing generic code with types that implement abstractions can easily expose bugs when the caller and the callee don't agree on exactly what the abstraction is. Several of the bugs that Yuri reported are a very specific case of this: there's a lot of generic code that assumes that array indexing always starts at one, but that's not always the case since OffsetArrays allow indexing to start anywhere. The older code in the stats ecosystem is particularly badly hit by this because it often predates the existence of OffsetArrays and the APIs that were developed to allow writing efficient generic code that works with arrays that don't start at the typical index (or which might even want to be iterated in a different order). Fixing these specific OffsetArray bugs is a fairly straightforward matter of searching for `1:length(a)` and replacing it with `eachindex(a)`. But there's a bigger issue that this general problem raises: How does one, in general, check whether an implementation of an abstraction is correct? And how can one test if generic code for an abstraction uses the abstraction correctly? Many people have mentioned interfaces and seem to believe that they would solve this problem. I don't believe that they do, although they do help. Why not? Consider the OffsetArray example: nothing about `for i in 1:length(a)` violates anything about a hypothetical interface for AbstractArrays. Yes, an interface can tell you what methods you're supposed to implement. There's a couple of issues with that: 1) you might not actually need to implement all of them—some code doesn't actually use all of an interface; 2) you can find out what methods you need to implement just by running the code that uses the implementation and see what fails. What the interface would guarantee is that if you've implemented these methods, then no user of your implementation will hit a missing method error. But all that tells you is that you've implemented the entire surface area of the abstraction, not that you've implemented the abstraction at all correctly. And I think that covering the entire surface area of an abstraction when implementing it is the least hard part. What you really want is a way to generically express behaviors of an abstraction in a way that can be automatically tested. I think that Clojure's spec is much closer to what's needed than statically checked interfaces. The idea is that when someone implements an abstraction, they can automatically get tests that their implementation implements the abstraction correctly and fully, including the way it behaves. If you've implemented an AbstractArray, one of the tests might be that if you index the array with each index value returned by `eachindex(a)` that it works and doesn't produce a bounds error. On the other end, you also want some way of generating mock instances of an abstraction for testing generic code. We do a bit of this in Julia's test suite: there are GenericString and GenericSet types, which implement the minimal string/set abstraction, and use these to test generic code to verify that it doesn't assume more than it should about the string and set abstractions. For a GenericArray type, you'd want it to start at an arbitrary index and do other weird stuff that exotic array types are technically allowed to do, so that any generic code that makes invalid assumptions will get caught. You could call this type AdversarialArray or something like that. I've personally thought quite a bit about these issues, but as Keno has said, there hasn't been time to tackle these problems in the last couple of years. But they certainly are important and worth solving. On a personal note, Yuri, thanks for all the code and I'm sorry to see you go.

clhodapp 4y ago
> What you really want is a way to generically express behaviors of an abstraction in a way that can be automatically tested. The pure FP ecosystems in Scala often accomplish this in the form of "laws", which are essentially bundles of pre-made unit tests that they ship alongside their core abstraction libraries.
Sukera 4y ago
To expand on the "interfaces are not enough" part: Defining an interface on an abstract type only gives you that a implementation exists, not that it is correct, i.e. that the specific implementation for a subtype guarantees the same properties the interface specifies. On top of this, you really want to be alerted to when you expect more of an interface than the interface guarantees - this is what happened in the case of `1:length(A)` being assumed to give the indices into `A`, when the `AbstractArray` interface really only guarantees that a given set of methods exists. I feel like these sorts of issues more or less require more formal models being provided & checked by the compiler. Luckily for us, nothing in this space has been implemented or attempted in & for julia, while there are a lot of experiments with formal methods and proofing systems being researched right now (TLA+, coq,..). There are of course a lot of footguns[1], but the space is moving fast and I'd love to see something that makes use of this integrated into julia at some point. [1]: Why specifications don't compose - https://hillelwayne.com/post/spec-composition/ https://hillelwayne.com/post/spec-composition/
- tialaramex 4y ago
  > Defining an interface on an abstract type only gives you that a implementation exists, not that it is correct Pretty far off topic for Julia, but the definition of Rust's Traits over semantics rather than syntax (even though of course the compiler will only really check your syntax) gives me a lot of this. The fact that this Bunch<Doodad> claims to be IntoIterator<Item=Doodad> tells me that the person who implemented that explicitly intends that I can iterate over the Doodads. They can't accidentally be IntoIterator<Item=Doodad> the author has to literally write the implementation naming the Trait to be implemented. But that comes at a heavy price of course, if the author of Bunch never expected me to iterate over it, the best I can do is new type MyBunch and implement IntoIterator using whatever ingredients are provided on the surface of Bunch. This raises the price of composition considerably :/ > you really want to be alerted to when you expect more of an interface than the interface guarantees In the case alluded to (AbstractArray) I feel like the correct thing was not to implement the existing interface. That might have been disruptive at the time, but people adopting a new interface which explicitly warns them not to 1:length(A) are not likely to screw this up, and by now perhaps everything still popular would have upgraded. Re-purposing existing interfaces is probably always a bad idea, even if you can persuade yourself it never specifically said it was OK to use it the way you suspect everybody was in practice using it, Hyrum's Law very much applies. That interface is frozen in place, make a new one.

clhodapp 4y ago

> What you really want is a way to generically express behaviors of an abstraction in a way that can be automatically tested. The pure FP ecosystems in Scala often accomplish this in the form of "laws", which are essentially bundles of pre-made unit tests that they ship alongside their core abstraction libraries.

Sukera 4y ago

To expand on the "interfaces are not enough" part: Defining an interface on an abstract type only gives you that a implementation exists, not that it is correct, i.e. that the specific implementation for a subtype guarantees the same properties the interface specifies. On top of this, you really want to be alerted to when you expect more of an interface than the interface guarantees - this is what happened in the case of `1:length(A)` being assumed to give the indices into `A`, when the `AbstractArray` interface really only guarantees that a given set of methods exists. I feel like these sorts of issues more or less require more formal models being provided & checked by the compiler. Luckily for us, nothing in this space has been implemented or attempted in & for julia, while there are a lot of experiments with formal methods and proofing systems being researched right now (TLA+, coq,..). There are of course a lot of footguns[1], but the space is moving fast and I'd love to see something that makes use of this integrated into julia at some point. [1]: Why specifications don't compose - https://hillelwayne.com/post/spec-composition/ https://hillelwayne.com/post/spec-composition/

tialaramex 4y ago
> Defining an interface on an abstract type only gives you that a implementation exists, not that it is correct Pretty far off topic for Julia, but the definition of Rust's Traits over semantics rather than syntax (even though of course the compiler will only really check your syntax) gives me a lot of this. The fact that this Bunch<Doodad> claims to be IntoIterator<Item=Doodad> tells me that the person who implemented that explicitly intends that I can iterate over the Doodads. They can't accidentally be IntoIterator<Item=Doodad> the author has to literally write the implementation naming the Trait to be implemented. But that comes at a heavy price of course, if the author of Bunch never expected me to iterate over it, the best I can do is new type MyBunch and implement IntoIterator using whatever ingredients are provided on the surface of Bunch. This raises the price of composition considerably :/ > you really want to be alerted to when you expect more of an interface than the interface guarantees In the case alluded to (AbstractArray) I feel like the correct thing was not to implement the existing interface. That might have been disruptive at the time, but people adopting a new interface which explicitly warns them not to 1:length(A) are not likely to screw this up, and by now perhaps everything still popular would have upgraded. Re-purposing existing interfaces is probably always a bad idea, even if you can persuade yourself it never specifically said it was OK to use it the way you suspect everybody was in practice using it, Hyrum's Law very much applies. That interface is frozen in place, make a new one.