Musings on the Impossibility of Testing
blog.cerebralab.com
blog.cerebralab.com
val result = factorize(367)
assertEquals(367, result.reduce(_ * _))
Another type of test not considered here is a "redundant" check for a simple case. If we write a test like:
assertEquals(multiply(83, 83), pow(83, 2))
It also bears considering that even an entirely redundant test may be useful in providing (and explaining) a use case for an API. If we've just implemented the map() function for lists, then a test like:
def f(x: Int) = x * 2
val input = List(1, 2, 3)
var result = List.empty()
for { element <- input }
result :+= f(element)
assertEquals(result, input map f)
A lot of time you only have weaker properties to test so you have to look for other methodologies such as using vectors of inputs/expected results or building a simpler reference implementation to test the optimized version.
Is this a "human validation" that P!=NP ? ;)
The question is, why are you unit testing ML functions? ML is not software engineering, and unit tests not a good way to broadly evaluate them, outside some “third rail” type tests for insanely important cases. You’d typically use statistical testing (e.g. f1 scores) to determine whether your models are performing as expected, but they are ultimately probabilistic in nature and highly unlikely to satisfy all of the intended cases simultaneously.
There is of course the philosophical question of how you determine the quality of your tests, which are themselves software. The practical answer is to keep your testing software as trivially simple, obvious, and boring as possible; tests can then be validated with the mark I eyeball.
None of this has any bearing on the usefulness or otherwise of automated testing.
In practice, I agree with this, and that's how I usually write my tests when dealing with ML code. Though honestly I think this perspective could well extend beyond ML code to any code with very broad input and output spaces.
> You’d typically use statistical testing (e.g. f1 scores) to determine whether your models are performing as expected, but they are ultimately probabilistic in nature and highly unlikely to satisfy all of the intended cases simultaneously.
Yes, but the solution to that (in practice) is to basically benchmark against your own (previous) code and alternative implementations. Based on the idea that "if 10x tried it, and mine is better, than I must be doing something correctly" and/or "if the previous version did worst, well, then something must be improving".
Again, I think this is equally true for testing a ray tracer or compilation times as it is for testing an ML algorithm.
> There is of course the philosophical question of how you determine the quality of your tests, which are themselves software. The practical answer is to keep your testing software as trivially simple, obvious, and boring as possible; tests can then be validated with the mark I eyeball.
But this results in a situation where "good" tests are extremely subjective, and replacing a team of engineers with another (or even just a member of that team) would result in the need to replace the tests.
> Testing is obviously not impossible, so let’s set that aside for a moment. > None of this has any bearing on the usefulness or otherwise of automated testing.
To me it seems to have baring in that, unless I am able to have at least some heuristic based on which I can define "good" or "sufficient" testing the question of what to test and how much time to allocate to it becomes impossible to answer. And that is a very useful question I'd want to have an answer to that is better than just "based on my intuition and what I think is sufficient as to not have my bosses/customer scream at me when stuff breaks, this amount of testing is good".
I disagree with that statement. Unit tests are very helpful for complex models, as they can guard against regressions in future changes. If the original author tested all their expectations, I am less worried that I may break something I didn't anticipate.
If all of software engineering is an infinite space, software testing is always infinite+1.
The problem always starts at human-defined logic and ends at human-defined interpretation.
There is no amount of testing that can replicate eyes on those expectations defined on either end, and my own personal politics reflect that:
Tests are simply reinforcing these vectors from human to human where we might have a black, grey box that is incompletely understood by its contributors.
The point is to reduce complexity and optimize those vectors so those expectations directly align.
If you're writing the consistency of crêpe-like tests, perhaps those goals don't align. I've been there. Something surely has to change. Tests should be very simple validations and should be very developer interpretable. In fact, they should be enlightening to that vertical code.
They should necessarily be an aside to the larger architecture where we generally understand what is supposed to happen. They should define a ruleset to its operation at each discrete step.
Never a validation of "what function functions?".
I've seen too many PMs, execs, and can-do engineers get lost beyond the design because they were building on sand and justifying their castle.
Just stop.
Bring testing to the 'else' case on 'if, else if, elsif, ...' where we can actually understand that path.
Goodness.
Addendum: perhaps I've not worked in complex enough systems. I would appreciate any constructive argument towards my personal views.
Static types do not help at all with software quality, beyond catching some typos. You can never, ever write a static type that enforces anything of substance, because for that to happen you’d need to execute arbitrary code within the compiler (as happens with dependent types, and of course there is the constant fear of undecidable or infinite type checking in that system).
The classic example is that there’s an infinite number of functions with type int -> int. The logic of these functions are extremely varied, and the type doesn’t help you at all. Enum types are very useful for knowing what values you are allowed to write, but don’t help with correctness.
The author brings up large input spaces, but conveniently leaves out input space partitioning, which any non-novice tester has to employ in their test case management. The category partition method is a fantastic way of covering large swaths of a seemingly infinite input space with relatively few tests. Of course there’s combinatorial explosion, but that can be mitigated with constraints on the input combinations.
I’m not saying testing is perfect - it’s not. But, the burden of proof is on the critic of testing, not testing itself. How else can you reliably change a large software product dozens of times a week, for 20 years in a row? And what’s the alternative when I see products that large teams produce break weekly?
This is not something that “ship it and iterate” has had any meaningful impact on. Eventually you get people who don’t intimately know the whole codebase, and make a breaking change unintentionally. What is the alternative to some kind of testing?
I strongly disagree. A type like 'NonEmptyList(A) -> B' gives us more information than 'List(A) -> B': in programming terms it eliminates the empty case; in logical terms it provides a proof of 'A'. Note that we can represent 'NonEmptyList(A)' using 'Pair(A, List(A))', but give it a nicer list-like API.
Even simple nominal typing can provide useful guarantees, e.g. 'query : String' allows SQL injection, which we can eliminate by defining a separate 'SQL' type. We can represent 'SQL' using a string (we can even make it zero-cost using 'newtype', 'AnyVal', etc.), but crucially we can restrict its API to only allow safe operations, e.g. we can guarantee that strings are escaped by making the escaping function the only way to convert 'String' to 'SQL'; this also prevents double-escaping, since we we can't pass 'SQL' into the escaping function). The exact same technique prevents any injection attack (shell injection, 'eval', etc.).
Maybe such things could be called 'typos', but that's just a rhetorical sleight-of-hand; if injection attacks are typos then typos are incredibly dangerous (e.g. https://nakedsecurity.sophos.com/2018/02/19/hackers-sentence... ). We could say static types are great for software quality, since they can even catch typos (which, as we've established, are incredibly dangerous)!
Static typing is a tool, just like unit testing, integration testing, and code reviews.
We combine these tools in order to maximize software quality, ease of development and maintenance.
Static typing eliminates a whole class of errors that good code bases in dynamic languages usually have to manually test (instance and type tests)
Also, static types _are_ manual testing, you need to write the types.
I really like this talk: https://fsharpforfunandprofit.com/ddd/
It is a well-known result of Computer Science how static types and mathematical proofs are equivalent (see https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...).
If you make static types sufficiently good, you get a full theorem prover to prove mathematical properties. There is a whole family of modern programming languages used in verification that exploit this; for example, Agda, Idris and Coq are all practical theorem provers built on static types.
If you want to go half the way, try Haskell, where you can express slightly less (but still many) correctness requirements with static types, while still maintaining quite easy ergonomics.
If you would like to learn more about theorem proving with Haskell in particular, there is an online 3-hour workshop at MuniHac on "Liquid Haskell" in 3 hours (see https://munihac.de/2020.html#programme). It's free and may change your opinion on software correctness significantly.
Now, that is one hell of a correspondence and I don’t mean to downplay it at all. But the reason why this isn’t practical in daily programming is that a type represents a set, so all that the isomorphism gets you is knowing that given a member of one type as input you get a member of another type as the output. _Any_ member.
This is the problem - the difficulty in verifying logic is showing that the correct output _value_ is given for all input values.
Trust me, I have played with Coq for quite a while. Realizing this is what made me abandon the belief that types are some kind of savior. They can be useful, but the program (or proof) itself is what is difficult to get right. I rarely return the wrong type from a function.
Static types are a tool. You can use that tool well, or poorly. There are applications that tool plain doesn't fit.
But it is absolutely the case that it can be an important part of enforcing things "of substance" from a very real engineering standpoint (whatever you think of them theoretically).
My go-to example from my own experience: I was working on an experimental C project in an environment that demanded minimum latency at low-to-moderate throughput on (expensive) commodity hardware.
Our approach was to pin individual threads, dedicated to their task, on individual processors which were otherwise unused.
Some functions could only be called on certain threads, usually because some resources could only be accessed from specific threads to avoid locking. Providing an additional argument that labelled the thread let us catch when a change in requirements (which is inevitable when the goal is experimentation) meant logic in the hot path could now be moved somewhere else or what have you.
Testing might have turned up race conditions; running them down would likely have been substantial effort. The type system told me "you're calling foo on the wrong thread on line 1234, dummy" and it told me that quickly.
None of this is to say we shouldn't be testing - indeed, over the course of the project testing caught a handful of deadlocks the types (at least, those types) couldn't prevent. But the types were invaluable.
But are they really int to begin with, as in actually ratio values? Perhaps you're inputting the units requested and getting units available back, which will be completely different from a function that takes an int for the items currently in the basket and returns a new total of items in the basket. Can you compose all those functions into each other? If not, they're not really using the same type but you're representing them as such. That would be undesired behaviour you can totally avoid through subtypes StockAmount and BasketItems.
Edit: If you're talking about the math domain, obviously subtyping doesn't apply.
I've been thinking about writing a proposal for C++. Problem isn't easy to find something worth writing. Either it is obviously too simple to fit my needs, or it is so complex that I wouldn't accept it if I were on the committee - and this the thought exercise stage where true rigor of reasoning hasn't been applied.
Yet there is precisely one function with type 'forall a. a -> a', so the type guarantees it's the identity function.
Likewise there are precisely two functions with type 'forall a. a -> a -> a': the type guarantees that it will return one of its two arguments (it's equivalent to branching on a boolean). The same pattern holds for selecting between any number of values (which can be useful if we need our caller to make a choice for us).
Type constraints are also useful for proving guarantees about our code; e.g. if we have a function like 'forall a. List(a) -> List(a)' then it could do all sorts of rearranging of the elements; whereas 'forall f a. Poppable(f) => f(a) -> f(a)' can only use functions provided by 'Poppable' (presumably: popping elements off the start). We can still pass around 'List(a)' values, as long as 'List' implements 'Poppable', but (a) we guarantee more about the behaviour of these functions (b) the functions are easier to write (since there are fewer things we can get wrong) and (c) the functions are more generic than using a concrete type like 'List'.
Note that constraints provide stronger guarantees than subtypes or interfaces, e.g. in Scala 'Poppable[A] => Poppable[A]'. The latter doesn't force the input and output types to be the same, so returning an empty 'List' will work; whereas the constraint requires we return an 'f(a)' for all possible 'f'; hence we're forced to use the input value (in the same way that 'forall a. a -> a' forces us to return the input).
Of course, constraints can always be desugared into dictionary passing (e.g. http://www.haskellforall.com/2012/05/scrap-your-type-classes... ); e.g. 'forall f a. (f a -> (a, f a)) -> f a -> f a', where the '(f a -> (a, f a))' argument is some sort of 'pop' function; however, we still benefit from static types to ensure that all of these arguments line up (i.e. the same 'f' and 'a' are used in each occurrence), and we benefit from parametricity giving us 'theorems for free' about the possible behaviour.
You're dismissing countless person-years of research, development and experience, across academia and industry, without providing any evidence; you're dismissing specific counterexamples as not being True Scotsmen; and your very gradiose claims are laden with weasel words.
What are your thoughts on automated/unit tests used to guarantee expectations do not change in future revisions (a regression suite) and also used to present example inputs usages of the API that was designed?
To be honest, this is one idea I was toying around with. As in, have a test suite that generates a "state" file for your program and then, in any given patch, list the items in the state that you'd expect to change.
That way, one can basically catch a lot of "bugs" which often boil down to "this change I made here to affect X is also unexpectedly affecting Y".
My main problem with this are:
1. I see nobody doing this, and I'm not sure why. 2. The tooling for this doesn't really seem to exist, and I'm not sure how easy one could bring it into existence and/or if a generic version of it could be written. 3. This breaks down with a lot of software where a tiny change can affect, well, everything (e.g. modifying a random seed or changing an error-checking constant)
It is very clear that you have not worked on large, complex systems.
Also, un-tenable with any code that is non-deterministic, like multiple threads or external I/O.
What do you mean here?
Do you mean you would run a specific function with specific inputs and record specific outputs and compare them?
E.g. given a program with variables
a1 = array a2 = int a3 = string
Running might get the state flow:
a1 = []
a2 = 10
a3 = 'abc'
a3 = 'dd1'
a2 = 200
a1 = [200,'dd1']
Then, if a change is made, the programmer can say "I expect this change to only affect the state of a2" and if you get the state flow:
a1 = []
a2 = 11
a3 = 'abc'
a3 = 'dd1'
a2 = 500
a1 = [200,'dd1']
Then the test passes
If you get the state flow:
a1 = []
a2 = 11
a3 = 'abc'
a3 = 'dd1'
a2 = 500
a1 = [500,'dd1']
The test fails with error "The change you expected to only affect a2 also had an effect upon a1"
But again, the actual state you capture here and the way you check for equality (e.g. to you check for equality among all the states during the whole runtime, or just in the final state of the program ? If the former how is state-change ordering handled ? If the later, what about relevant state that is out of scope by the time the program finishes running ?)
e.g.
[TestCase(null, null)]
[TestCase(10, 11)]
[TestCase('abc', 'abc')]
[TestCase('dd1', 'dd1')]
[TestCase(500, 500)]
[TestCase([200, 'dd1'], [200, 'dd1'])]
public void StateChanges(input, expected) {
actual = DoThing(input);
Assert.AreEqual(actual, expected);
}"Don't be snarky."
"Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. Assume good faith."
A related problem are Rotten green tests [1]
e.g. if no regressions ever get picked up by the test subsequently
If you are part way or all the way through your refactor and think you're on the right track and then you unexpectedly have a failing test, then I would say that that was a useful bit of test code.