11 ms·

Is API compatibility computable in general? My instinct is that it is, but I’ve never seen a theorem.

by User23 8y ago

ShaneWilton 8y ago
I'd imagine it isn't, at least depending on how you define API compatibility, and whether you're only looking at the API interfaces. Imagine two versions of a library that implement the function "add". Version 1: add Int -> Int -> Int add x y = x + y Version 2: add Int -> Int -> Int add x y = x * y Both versions expose the same API interface, but the functions that conform to that interface are semantically different. A stronger type system could probably differentiate between the two functions, but I doubt you could generally compute whether both functions implement the same behavior. Perhaps with some sort of functional extensionality you'd be able to compute compatibility perfectly, but I can't imagine that ever being feasible in practice. That being said, what Elm does offer is still a huge improvement over humans trying to guess whether they made any breaking changes :)
- toast0 8y ago
  I don't think 'does it work exactly the same' isn't necessarily the right question, given there are expected to be bug fixes which may change the behavior in some functions.
  - marcosdumay 8y ago
    The right question is "what's the difference between a bug-fix and a breaking change?"
    - Nadya 8y ago
      Irrelevant. If fixing a bug is a breaking change then it is a breaking change. This is the importance of pre-releases/"nightly" branches so that you don't have a mistake of addNumbers(5,5) returning 25 instead of 10 and not being caught and then needing to increment a major number to fix a typo of × to +. A bug fix is a change. A breaking change is a change that breaks the API. Doesn't matter if the previous status was the intended one or not. SemVer not working is almost entirely people simply not following it correctly. The projects that follow it as best as they can have very few mistakes were "woops that was a major change" occurs while projects that use it as a guideline may as well not be using it at all.
      - hluska 8y ago
        Irrelevant?? That is the most relevant question that a developer could ask in this situation. Often, there are ways to work around bugs in an API. And, just as often, those workarounds will break as soon as the bug is fixed. The API developer is in a particularly poor place to judge whether a bug fix is breaking or not. Sometimes, they can talk to users to see if a change will break their code, but other times they can't. Thus, it comes down to how well a developer can predict whether a fix will break projects in the wild.
        tremon 8y ago
        Irrelevant?? That is the most relevant question that a developer could ask in this situation. No, it isn't. The most relevant question is "can somebody be using the current API". It doesn't matter if your current API matches the documentation, what matters is whether your current API is out there for others to build on. Don't try to use a crystal ball or other form of divination to predict what your downstream users have been doing with the code; you will always lose. Instead, suck it up, acknowledge the mistake, and signal the breaking change by bumping the major version. Maybe next time your developers will spend more time validating their public contract, so they won't have to endure the embarrassment of a major version bump.
        hluska 8y ago
        Using that logic, every single bug fix that even remotely changes how the API operates would be considered a major version. What would be the point of semver? Semver both acknowledges and is predicated upon the fact that every bug fix has a range of possible impacts. At one end, some bug fixes have almost no chance of breaking an application. At the other end, some bug fixes will almost certainly break applications. This is not divination. It is understanding your application and its users. Finally, in regards to your last paragraph, I genuinely hope that you don't speak to developers like that. Mistakes will always happen. Have a little bit of respect and treat people with kindness.
        Nadya 8y ago
    - lmm 8y ago
      A bug fix makes the function behave as it's documented to, a breaking change involves a change to the documentation?
- codebje 8y ago
  You certainly cannot determine that two programs do or do not have the same behaviour in the general case. In specific cases, the proofs can be pretty trivial: https://tinyurl.com/ycx2245q https://tinyurl.com/ycx2245q - proof your two programs are different https://tinyurl.com/y7lcv3re https://tinyurl.com/y7lcv3re - proof 'y + x' is the same as Version 1. These proofs weren't automatically discovered, though for such simple programs I'd expect an SMT solver to be able to find the proof or a counterexample easily enough. But even proving they're the same value for all inputs isn't all that helpful, because of lazy Haskell code like: version 1: fib :: Int -> Int fib n = if n < 3 then 1 else fib (n - 2) + fib (n - 1) version 2: fib :: Int -> Int fib n = let fs = 1:1:zipWith (+) fs (tail fs) in fs !! n They're (provably) the same for all (positive) input values, but if you call version 1 with n greater than, say, 35, you'll be waiting quite a while for an answer, while version 2 will be very snappy for the first few hundred thousand values of n, at least, after which the size of the answer will be a bottleneck. If a library switched from the latter to the former, it'd have a good chance of breaking code. While obviously exponential code is obviously exponential, this sort of behavioural change can show up in less obvious ways - a change in memory usage might blow your heap after a supposedly minor version change, eg. In the end I don't think the value judgement of 'breaking' or even 'significant' is computable, and you'd need to rely on a human doing something that approximates to 'right' for your world view with their version numbering.
beefsack 8y ago
Only as far as the type system supports, but I feel like constraining the minimum version unit to increment is far better than doing nothing. Disallowing incrementing the patch version when the types of existing API changes is great.
dbaupp 8y ago
No, it isn't computable (that is, correctly determining one of "these functions behave the same" or "these functions behave differently", and not "unknown") in general, as it is equivalent to the halting problem. Consider these two versions of a function, are they API compatible? def foo(): return True def foo(): return halts("some turing machine program") They're only truly API compatible if the program halts, but the program can be arbitrary, so proving that any 'foo' of this style are equivalent is solving the halting problem. Of course, one can still likely get useful answers of "definitely incompatible" etc., with much more tractable analyses. AIUI, the Elm version ends up just looking at the function signature, and catches things like removing or adding arguments: for appropriately restricted languages, it is likely to even be possible to determine if downstream code will still compile, but that's not a guarantee it will behave correctly.
- gmueckl 8y ago
  I wonder if tighter guarantees can be given if tools can work with constructs like D's contracts. These are extra sections in each function that are intended to check invariants. If these invariants change, then they were either broken and needed fixing or the function had a semantic change.
  - pjmlp 8y ago
    There can still be a semantic change, even if conditions are unchanged and valid.
  - dbaupp 8y ago
    That's an interesting idea. It seems like it would be a way for tools to flag "this function is likely to have changed in an interesting way", but changing invariants doesn't necessarily mean the function breaks semver. For one, an invariant might be changed syntactically, without actually changing what it is asserting, reducing to exactly my example above: in its simplest form, the contract could go from in(true) to in(halts("...")). Secondly, an contract could have been made more permissive, e.g. in(x > 1) becoming in(x > 0), or out(y > 0) becoming out(y > 1). Assuming violating a contract is regarded as a programming error (as in, it isn't considered breaking to go from failing an assertion to not failing), these are also non-breaking changes. Lastly, changing behaviour doesn't necessarily mean changing invariants/contracts.
jopsen 8y ago
Type compatibility between two APIs would usually be decidable, because otherwise the type systems would be useless. But behavior testing is undecidable, easily follows from halting theorem. I doubt it would even be recognizable.

Is API compatibility computable in general? My instinct is that it is, but I’ve never seen a theorem.

by User23 8y ago

Is API compatibility computable in general? My instinct is that it is, but I’ve never seen a theorem.

I'd imagine it isn't, at least depending on how you define API compatibility, and whether you're only looking at the API interfaces. Imagine two versions of a library that implement the function "add". Version 1: add Int -> Int -> Int add x y = x + y Version 2: add Int -> Int -> Int add x y = x * y Both versions expose the same API interface, but the functions that conform to that interface are semantically different. A stronger type system could probably differentiate between the two functions, but I doubt you could generally compute whether both functions implement the same behavior. Perhaps with some sort of functional extensionality you'd be able to compute compatibility perfectly, but I can't imagine that ever being feasible in practice. That being said, what Elm does offer is still a huge improvement over humans trying to guess whether they made any breaking changes :)

toast0 8y ago
I don't think 'does it work exactly the same' isn't necessarily the right question, given there are expected to be bug fixes which may change the behavior in some functions.
- marcosdumay 8y ago
  The right question is "what's the difference between a bug-fix and a breaking change?"
  - Nadya 8y ago
    Irrelevant. If fixing a bug is a breaking change then it is a breaking change. This is the importance of pre-releases/"nightly" branches so that you don't have a mistake of addNumbers(5,5) returning 25 instead of 10 and not being caught and then needing to increment a major number to fix a typo of × to +. A bug fix is a change. A breaking change is a change that breaks the API. Doesn't matter if the previous status was the intended one or not. SemVer not working is almost entirely people simply not following it correctly. The projects that follow it as best as they can have very few mistakes were "woops that was a major change" occurs while projects that use it as a guideline may as well not be using it at all.
    - hluska 8y ago
      Irrelevant?? That is the most relevant question that a developer could ask in this situation. Often, there are ways to work around bugs in an API. And, just as often, those workarounds will break as soon as the bug is fixed. The API developer is in a particularly poor place to judge whether a bug fix is breaking or not. Sometimes, they can talk to users to see if a change will break their code, but other times they can't. Thus, it comes down to how well a developer can predict whether a fix will break projects in the wild.
      - tremon 8y ago
        Irrelevant?? That is the most relevant question that a developer could ask in this situation. No, it isn't. The most relevant question is "can somebody be using the current API". It doesn't matter if your current API matches the documentation, what matters is whether your current API is out there for others to build on. Don't try to use a crystal ball or other form of divination to predict what your downstream users have been doing with the code; you will always lose. Instead, suck it up, acknowledge the mistake, and signal the breaking change by bumping the major version. Maybe next time your developers will spend more time validating their public contract, so they won't have to endure the embarrassment of a major version bump.
        hluska 8y ago
        Using that logic, every single bug fix that even remotely changes how the API operates would be considered a major version. What would be the point of semver? Semver both acknowledges and is predicated upon the fact that every bug fix has a range of possible impacts. At one end, some bug fixes have almost no chance of breaking an application. At the other end, some bug fixes will almost certainly break applications. This is not divination. It is understanding your application and its users. Finally, in regards to your last paragraph, I genuinely hope that you don't speak to developers like that. Mistakes will always happen. Have a little bit of respect and treat people with kindness.
        Nadya 8y ago
  - lmm 8y ago
    A bug fix makes the function behave as it's documented to, a breaking change involves a change to the documentation?
codebje 8y ago
You certainly cannot determine that two programs do or do not have the same behaviour in the general case. In specific cases, the proofs can be pretty trivial: https://tinyurl.com/ycx2245q https://tinyurl.com/ycx2245q - proof your two programs are different https://tinyurl.com/y7lcv3re https://tinyurl.com/y7lcv3re - proof 'y + x' is the same as Version 1. These proofs weren't automatically discovered, though for such simple programs I'd expect an SMT solver to be able to find the proof or a counterexample easily enough. But even proving they're the same value for all inputs isn't all that helpful, because of lazy Haskell code like: version 1: fib :: Int -> Int fib n = if n < 3 then 1 else fib (n - 2) + fib (n - 1) version 2: fib :: Int -> Int fib n = let fs = 1:1:zipWith (+) fs (tail fs) in fs !! n They're (provably) the same for all (positive) input values, but if you call version 1 with n greater than, say, 35, you'll be waiting quite a while for an answer, while version 2 will be very snappy for the first few hundred thousand values of n, at least, after which the size of the answer will be a bottleneck. If a library switched from the latter to the former, it'd have a good chance of breaking code. While obviously exponential code is obviously exponential, this sort of behavioural change can show up in less obvious ways - a change in memory usage might blow your heap after a supposedly minor version change, eg. In the end I don't think the value judgement of 'breaking' or even 'significant' is computable, and you'd need to rely on a human doing something that approximates to 'right' for your world view with their version numbering.

beefsack 8y ago

Only as far as the type system supports, but I feel like constraining the minimum version unit to increment is far better than doing nothing. Disallowing incrementing the patch version when the types of existing API changes is great.

dbaupp 8y ago

No, it isn't computable (that is, correctly determining one of "these functions behave the same" or "these functions behave differently", and not "unknown") in general, as it is equivalent to the halting problem. Consider these two versions of a function, are they API compatible? def foo(): return True def foo(): return halts("some turing machine program") They're only truly API compatible if the program halts, but the program can be arbitrary, so proving that any 'foo' of this style are equivalent is solving the halting problem. Of course, one can still likely get useful answers of "definitely incompatible" etc., with much more tractable analyses. AIUI, the Elm version ends up just looking at the function signature, and catches things like removing or adding arguments: for appropriately restricted languages, it is likely to even be possible to determine if downstream code will still compile, but that's not a guarantee it will behave correctly.

gmueckl 8y ago
I wonder if tighter guarantees can be given if tools can work with constructs like D's contracts. These are extra sections in each function that are intended to check invariants. If these invariants change, then they were either broken and needed fixing or the function had a semantic change.
- pjmlp 8y ago
  There can still be a semantic change, even if conditions are unchanged and valid.
- dbaupp 8y ago
  That's an interesting idea. It seems like it would be a way for tools to flag "this function is likely to have changed in an interesting way", but changing invariants doesn't necessarily mean the function breaks semver. For one, an invariant might be changed syntactically, without actually changing what it is asserting, reducing to exactly my example above: in its simplest form, the contract could go from in(true) to in(halts("...")). Secondly, an contract could have been made more permissive, e.g. in(x > 1) becoming in(x > 0), or out(y > 0) becoming out(y > 1). Assuming violating a contract is regarded as a programming error (as in, it isn't considered breaking to go from failing an assertion to not failing), these are also non-breaking changes. Lastly, changing behaviour doesn't necessarily mean changing invariants/contracts.

jopsen 8y ago

Type compatibility between two APIs would usually be decidable, because otherwise the type systems would be useless. But behavior testing is undecidable, easily follows from halting theorem. I doubt it would even be recognizable.