Show HN: TDD Screencast #3: Implementing Kind Sort
waterlink.github.io
waterlink.github.io
In video #2 we saw the evolution of a bubble sort. In video #3 we saw a quicksort.
However, nothing in the tests lead to one design over the other. It was only in the mind of the developer, and the only difference to get to the different designs was the statement that #3 must return a new list. Which can be done (as was said) by a copy, so that didn't really drive the development or design.
In fact, there are no simple tests that can drive one implementation over the other. It's only by counting the number of swaps, or measuring the performance, and with performance requirements, that one version comes out better than the other.
One of my issues with TDD is the 'refactor' step, which is supposed to take place during green. One of the refactor transformations is "Substitute Algorithm." I've always thought that was a huge loophole as the appropriate tests for a new algorithm can be quite different than the tests for the existing algorithm, but TDD says not to worry about that.
That issue is applicable here, as #3 really is a "Substitute Algorithm" refactor of #2. It could have started with the previous sort test cases, and shown how refactor the algorithm in the TDD framework rather than redo the code from scratch. So far I haven't actually seen any of the TDD example walkthroughs do it, at least with a non-trivial example like sorting, so showing this might also be enlightening or at least novel.
A test case goal should be to convince people that the code works. The test cases here aren't enough. For example, there is no test for when values are equal, and I don't recall the spec saying duplicate values were disallowed. This is important because some broken sort implementations might get into a loop for this case.
If this were implemented in Python then there's a maximum recursion depth. I think the worst case for this quicksort implementation is if the input is sorted. So I would want to try sorting 100,000 sorted to feel more comfortable. This sort of error analysis must be part of TDD, but it doesn't really fit into the red/green test cycle because it's a test you write when you expect the code to pass, not fail.
Also, from an API perspective, if the input is the empty list then this code returns the original list, otherwise it returns a new list. I would prefer to always get a new list, so I have a better idea of ownership.
> One of my issues with TDD is the 'refactor' step, which is supposed to take place during green. One of the refactor transformations is "Substitute Algorithm." I've always thought that was a huge loophole as the appropriate tests for a new algorithm can be quite different than the tests for the existing algorithm, but TDD says not to worry about that.
I think in this case, I would write new test suite for new algorithm, and then replace both old test suite and old implementation in one step. In case, when tests suite can be shared, it makes sense to re-use it.
> That issue is applicable here, as #3 really is a "Substitute Algorithm" refactor of #2. It could have started with the previous sort test cases, and shown how refactor the algorithm in the TDD framework rather than redo the code from scratch. So far I haven't actually seen any of the TDD example walkthroughs do it, at least with a non-trivial example like sorting, so showing this might also be enlightening or at least novel.
I would like to research if that is possible. If it is, I will make an episode for that.
> A test case goal should be to convince people that the code works. The test cases here aren't enough. For example, there is no test for when values are equal, and I don't recall the spec saying duplicate values were disallowed. This is important because some broken sort implementations might get into a loop for this case.
Thank you for catching this, I wasn't focusing enough on this point.
> If this were implemented in Python then there's a maximum recursion depth. I think the worst case for this quicksort implementation is if the input is sorted. So I would want to try sorting 100,000 sorted to feel more comfortable. This sort of error analysis must be part of TDD, but it doesn't really fit into the red/green test cycle because it's a test you write when you expect the code to pass, not fail.
This can, actually, fit in red/green cycle. By writing a test that creates a worst case scenario of 100,000 sorted elements. And see it fail with stack overflow. And then fix it by randomizing element that is used for partitioning. WDYT?
> Also, from an API perspective, if the input is the empty list then this code returns the original list, otherwise it returns a new list. I would prefer to always get a new list, so I have a better idea of ownership.
Thanks for pointing this too. Next time I would add specific tests for that. In that case, it is reasonable to check it for empty, one-element and N-element array.
---
Now that I think about that, I will make an episode #4 or #5 a re-visit of #3 - with all these problems pointed out and fixed ;)
It's tough to put together a screeencast, much less a series. You have my respect for doing so, and for choosing a simple but non-trivial problem like sorting that people use every day, instead of something like Fibonacci.
> I think in this case, I would write new test suite
I think that's reasonable. I bring this up to point out how the TDD formalism, as red-green-refactor, doesn't work. This means the "refactor" in TDD uses a subset of the available refactoring operations, which further means TDD cannot be the only thing which drives the design.
(My usual example is going from naive string search to Knuth–Morris–Pratt. I think in the future I'll talking about moving from classic quicksort to Timsort. I've also used this to demonstrate that TDD is a form of white-box testing.)
> I wasn't focusing enough on this point.
One of my complaints about TDD is that it focuses on tests for the next small code transformation. This is very helpful for a lot of people! But maintaining that focus means that other aspects receive less attention.
> And see it fail with stack overflow
But what if it doesn't fail? Do you leave the test in? Or do you tweak the parameters until if fails? What if a recursive implementation never fails, perhaps because the compiler used tail recursion? How many non-failing tests do you add?
Test case analysis is part of the traditional QA process, and I feel that too many TDD people reject it because they see after-the-fact tests as being counter to the TDD philosophy.
Thanks!
> > I think in this case, I would write new test suite
> I think that's reasonable. I bring this up to point out how the TDD formalism, as red-green-refactor, doesn't work. This means the "refactor" in TDD uses a subset of the available refactoring operations, which further means TDD cannot be the only thing which drives the design.
I believe, that is always the case with any best practice. You hit a point, where the problem you are facing requires something else, or combination of techniques, some analysis and thought. Reminds me about quadrants with "Known", "Knowable", "Complex" and "Chaotic".
> .. TDD is a form of white-box testing ..
I kind of agree on this one. In a lot of cases it is true.
> > I wasn't focusing enough on this point.
> One of my complaints about TDD is that it focuses on tests for the next small code transformation. This is very helpful for a lot of people! But maintaining that focus means that other aspects receive less attention.
And that is exactly my intention: I want to help TDD spreading to the people (at least, the ones I have in reach here, in Berlin), who are not doing testing at all. (or doing it only from time to time). I want to infect them with a concept, and afterwards they will be on their own journey of discovery, what fits their tastes and their problems best; but they will no longer be able to write low-test-covered code. Do you think it is a good idea? Or maybe can be implemented in a better way?
> > And see it fail with stack overflow
> But what if it doesn't fail? Do you leave the test in? Or do you tweak the parameters until if fails? What if a recursive implementation never fails, perhaps because the compiler used tail recursion? How many non-failing tests do you add?
I was playing around with that today. I have actually added (and left in) not only stack-overflow test, but performance test. I was increasing parameters, until reasonable, like 3 * 10 ^ 7 elements, which still can complete in reasonable time for running inside of the test suite.
> Test case analysis is part of the traditional QA process, and I feel that too many TDD people reject it because they see after-the-fact tests as being counter to the TDD philosophy.
I think after-the-fact tests added after you already have decent coverage is a good thing to do, I usually do that, especially in times, when the solution emerged too fast, and you didn't covered some edge cases; how you got to this coverage is a different question, be it a TDD, property-based testing, after-the-fact tests, all-tests-first, and/or anything else. After-the-fact tests help you validate your assumptions about your code you have just written, which allows to spot problems earlier and make code future-proof.
My opinion on TDD philosophy is that it is something that doesn't drive complete design of the thing under implementation (nor it designed to do so, programmers are the ones who should do that), but it does force you to design it in a unit-testable fashion. Which makes adding after-the-fact tests really simple and enjoyable.
Well, I've tried TDD several times myself, and as part of our local Python User's Group kata. I find it to be a frustrating technique, but I can't deny there are many people who find it useful.
I've watched a handful of video walkthroughs of TDD, and gotten frustrated at the lack of good testing or development in them. One example is Robert Martin's primes kata. His solution works, but realistically only for small numbers. He never specified an input domain, and during development never tried to identify ambiguities between the API 'promise' that the function would take int32, the expectation by most that it's fast to factor 2,147,483,647 (2^31-1), and the reality that his code would take a long time for that.
You write "I think after-the-fact tests added after you already have decent coverage".
I love code coverage as a way to identify missing tests. For me that's usually in error handling.
Many of the TDD writings, going back to Kent Beck, say that TDD will naturally lead to high code coverage. I think that's wrong. I again thing many of the TDD writings ignore the problems that can come up during refactoring.
I think Martin's TDD style works because the problem he uses are "simple" in an algorithm sense, which is why he can talk about a 'Transformation Priority Premise'. Martin says "Refactorings are simple operations that change the structure of code without changing its behavior", but as I wrote before, 'substitute algorithm' is not a simple operation.
Then again, I think most businesses only need simple algorithms, even if the overall goal is quite complex. My complaint is about where TDD isn't enough.
So if you also include coverage and after-the-fact tests, that would be far beyond what I've seen so far in TDD walkthroughs.
That said, I don't think many people will watch a code walkthrough, so don't expect much fame or uptake from your series.
That said, yes, I think it's a good idea.
"but it does force you to design it in a unit-testable fashion"
You might want to read http://www.rbcs-us.com/documents/Why-Most-Unit-Testing-is-Wa... . There's a follow-up as well. He argues that most time should be spent on integration testing, and I agree.
I think unit tests implicitly enforce an API on the code, even when there's no need for an API. It's a special purpose internal API designed for testing. Because they are internal functions, you should have the freedom to refactor them, but the unit test burden keeps you from doing so. (In one TDD kata we did, we got working code, then compared it to others who were there. Our code was several times larger because we had tests for multiple code layers, while they only had one layer. We could have removed the layers, but that would have called for rewriting most of the unit tests, and I think that inhibited our design sense.)
In my own code, most of my tests are base on a unit-test framework but I almost only use the public API (for the library code) or a call to main() (for the command-line code). I feel this gives me more freedom to refactor without worrying about the extra work to change the unittests.
Anyway, Coplien describes it much better than I, and my comments just now don't even apply to a "sort()" function as that would be a public API.
I think in one of the videos I watched, he explicitly said, that this is lame implementation and can be optimized (for example by looping until square root of the number). The interesting point, is that one wouldn't have to change tests for that. One would want to write a benchmark for that, to use instead of test. As in: normal tests are tests for logic, while benchmarks are tests for performance. Additionally, it is always true, that premature optimization is not a good idea. If you have an evidence, that current algorithm is not fast enough (knowledge of your dataset sizes + understanding on what would the reasonable speed be + benchmark to verify all of that), then you optimize, without behavior change.
> I think Martin's TDD style works because the problem he uses are "simple" in an algorithm sense, which is why he can talk about a 'Transformation Priority Premise'. Martin says "Refactorings are simple operations that change the structure of code without changing its behavior", but as I wrote before, 'substitute algorithm' is not a simple operation.
Funny thing I have found about 'SubstituteAlgorithm' refactoring, is its example here: http://refactoring.com/catalog/substituteAlgorithm.html - it is not changing algorithm, it simply eliminates 'if' statements. That is something that I usually do naturally, and don't even consider underlying algorithm to be changed... So maybe, Martin Fowler, when coining this term, meant something different?
> So if you also include coverage and after-the-fact tests, that would be far beyond what I've seen so far in TDD walkthroughs.
It is definitely on my mind. Since that is what I usually do. It will be hard to demonstrate code coverage in Crystal, though, since I will have to write a library for that (there is none at the moment); so I might as well go for showing test coverage use in a different language for a change (like Clojure or Ruby). After the fact tests are definitely important too.
> That said, I don't think many people will watch a code walkthrough, so don't expect much fame or uptake from your series.
I know about that, that is why I am not only doing screencasts, but additionally, I am generally blogging, speaking at meetups (and hopefully in the future on conferences), simply speak to people and debate with them (I am ENTP after all), pair-program with random people, and I have in mind joining as a teacher/mentor one of the organization we have here in Berlin to teach beginners.
> I think unit tests implicitly enforce an API on the code, even when there's no need for an API. It's a special purpose internal API designed for testing. Because they are internal functions, you should have the freedom to refactor them, but the unit test burden keeps you from doing so.
"special purpose internal API designed for testing" is actually a smell to my knowledge. This emerges, when one tries to unit-test something that is not decoupled enough, or when one has too big objects/functions, read: violating one or many points of SOLID. That is why there is such a phrase going around: "Other word for 'testable' is 'decoupled'".
I did see this happening a lot of times. Even I had to do such weird test-only APIs myself, when I had less experience. And yes, it was weird and painful to test. Now that I analyze my knowledge: indeed, the problem was is that the object/function under test was initially badly designed. If I were to go back to the past, I would tell myself: "You see here one method. I see here 4 objects.".
Currently, I use that as an indicator - whenever I need to know something "intimate" about function or object, so that I need special API; means, that function or object under test is, most probably, should be split; and dependency injection should be used to combine the parts. This works both in OO and FP world for me: it is just a question of combining independent objects or independent functions together.
Now that I think about it, all my objects/functions in the professional code I write tend to be public-API-ish. I never test private methods/functions. But I have to say, that my objects usually have only one or two public methods (and they are extremely small).
> You might want to read http://www.rbcs-us.com/documents/Why-Most-Unit-Testing-is-Wa.... . There's a follow-up as well. He argues that most time should be spent on integration testing, and I agree.
Notion of Unit vs Integration goes on as long as I remember. And from one year to another, someone always coins "Unit tests are dead, long live Integration tests"; another year and someone says: "Integration tests are dead, long live Unit tests". It flips over and over again.
What I think, is that both are important. Which is more important, depends on lots of factors.
I am biased towards Unit testing, since I like being able to do some actual productive work on the airplane on a low-energy battery in my laptop, if I have to, and it will just simply work, because it is very well-tested. That is why, my code typically has 90-95% of unit tests and 5-10% for everything else.
---
Thanks for such a conversation, you have really provided a lot of interesting insights for me! That is quite rare to find someone, who would do that.
Was this the same video where he chastised programmers who mentioned the Sieve of Eratosthenes? Without actually explaining why that was the wrong solution?
> while benchmarks are tests for performance
Certainly benchmarks are useful tests. But so are edge conditions. Consider "average(i, j)". The simple solution is (i+j)/2, but if i+j overflows then the answer will be wrong. If max signed/unsigned int is allowed as an input value, or an overflow might happen in an intermediate value, then those should surely be part of the tests which drive the code. Without it, it's all too easy to have a silent integer overflow.
Going back to the primes code, 2^31-1 might be seen as a performance test. Or if the code was written well in the first place, it might just be a simple bounds check.
For that matter, if 'well-written unit tests ... provide a working specification of your functional code', then where's the documentation which defines the expected or at least preferred input range? Or the step to point out that the input spec is under-defined and needs clarification?
> So maybe, Martin Fowler, when coining this term, meant something different?
Funny thing that. If you look around, you'll see that most people quote his example almost verbatim. In general they like to replace user code with system code. This makes me think that most people either think it's trivially obvious, or haven't really thought about it. (I think few people really do algorithm development, so neither one would surprise me.)
In "Refactoring: Improving the Design of Existing Code" p. 139, at https://books.google.com/books?id=HmrDHwgkbPsC&pg=PA139&lpg=... , you'll that Fowler says to apply "Substitute Algorithm" only if the newer algorithm is clearer. He also says that if it compiles and passes all of the existing tests, then your done.
My complaint is that even a clearer algorithm can have different edge cases, so you have to analyze the code and perhaps add new tests before you are done.
> is actually a smell to my knowledge
My statement was based on reviewing Martin's FitNesse code some six years ago. I can no longer recall if my memory is accurate, and withdraw my comment.
> from one year to another, someone always coins "Unit tests are dead, long live Integration tests"; another year and someone says: "Integration tests are dead, long live Unit tests". It flips over and over again.
Coplien doesn't say that. While he believes that most unit tests are a waste, he encourages unit tests for "key algorithms for which there is a broad, formal, independent oracle of correctness, and for which there is ascribable business value". Sorting definitely falls into that category.
He also points out that maintaining unit tests which are also covered by your functional tests is a waste of maintenance time, and says to get rid of those unit tests.
I've always found it hard to work in an airplane, and don't travel anywhere often enough to need to worry about it. :)
Thanks also for your compliment. Best of wishes.
Have you tried something like that?