Decisions that go into implementing Stack

As part of a recent advanced TDD course, we took a careful look at a simple stack implementation TDD-style. Here are the decisions that went into designing and implementing the stack. First, the specification decisions:

  • Stack is an object
  • Name is “Stack”
  • There is an operation to add an element
  • It is called “push”
  • It takes a parameter
  • The type of the parameter is the same as the type of the stack
  • Stack has a type parameter
  • There is an operation to remove elements
  • Its name is “pop”
  • Its return value is the same as the type of the stack
  • Elements are ordered LIFO

Here are the implementation decisions:

  • Store the elements in a List
  • Type of the list is the same as the type of the stack
  • Implementation type is ArrayList
  • Add/remove elements at the beginning of the list

Here’s the exercise: start with any decision above & TDD, then another, and another. Pay attention to how frequently you can reach a green test. Pay attention to which sequences of decisions actually make sense.

What we found was that of the 15! permutations of decisions, many of them worked just fine and could be used for different purposes.

27 Comments

SteveNovember 5th, 2010 at 8:14 pm

I think TDD might get chance to become mainstream one day if its proponents stop using toy examples such as Stack to illustrate it.

adminNovember 5th, 2010 at 11:12 pm

Steve,

Thank you for the feedback. Did you try the exercise?

Regards,

Kent

KevinNovember 5th, 2010 at 11:18 pm

I was just thinking “huh?!?”

So what do we start out knowing, instead of what a stack is?

adminNovember 5th, 2010 at 11:45 pm

Have you tried it? Write a test, just for push, for example.

coreyhainesNovember 6th, 2010 at 12:42 am

I just finished teaching an introductory TDD course in Ghent; I always use the stack as the exercise for the first day. It is a great, ‘well-understood’ domain that people can use to practice the fundamentals. It is surprising how much depth there is in it to understand the fundamentals of TDD, no matter what your level.

Working with an easily understandable problem is a great way to practice your skills for when you are doing it on a less-understand problem. This is a why we always do Conway’s Game of Life at coderetreat: the rules are simple, but the subtleties are huge.

mikeNovember 6th, 2010 at 3:37 am

I found that leaving decison 3 till last causes the most fuss if you didn’t consider using a List interface. Although Steve has a point that stack is implemented in most languages so it is a bit of a folly, I kinda see the point that all developers understand what a stack is so it limits essential complexity allowing concentration to be on the exercise only. A nice exercise even for us .net’ers.

Bob NemecNovember 6th, 2010 at 4:56 am

This idea came up at ESUG 2007 as ‘Kata’ (as used in martial arts) programming: solving a simple well defined problem as a way to master the skill. This looks like an excellent application of the idea. If you’ve never done TDD, how else would you start?

Eugene WallingfordNovember 6th, 2010 at 11:43 am

This is a wonderful exercise. It is not an exercise I would use to “sell” TDD to someone. It is an exercise that I would use to help people learn the subtleties of small decisions — and to help someone learn that order of decisions matters far, far less than most of us tell ourselves.

David HarveyNovember 6th, 2010 at 1:30 pm

Keith Braithwaite runs a session called “TDD as if you meant it” which this reminds me of. Start by writing exactly one failing test, then make the test pass with code in the test itself. Repeat until done, refactoring only when you have to, and only to move things that you’ve `already extracted into methods in the test class. Gojko Adzic describes it here (http://gojko.net/2009/02/27/thought-provoking-tdd-exercise-at-the-software-craftsmanship-conference/) – I’ve not been able to find a writeup by Keith. This (like the above) is an exercise which really throws you back on your assumptions: for example, in TDDAIYMI even “Stack is an Object” would be too definite a place to start.

MikeNovember 6th, 2010 at 2:59 pm

Hi Kent,

It seems to me TDD is superfluous here. If you coded the stack in SPARK Ada and used static analysis you wouldn’t need to test it in this way. There is a good example of a stack in the High Integrity Software book by John Barns.

Mike

SteveNovember 6th, 2010 at 9:28 pm

Kent,

No, I haven’t done the exercise. I wrote a Stack class in TDD many, many years ago. I found it interesting but too trivial to be able to carry this experience in my daily job, where TDD is just close to impossible to apply for a variety of reasons, including technical, political and simple reality such as deadlines and market pressure.

Here is a challenge for you, though: write a TDD tutorial for a Selenium application.

If you can do this, then maybe more people will take TDD more seriously and think that maybe, it’s more than a theoretical toy limited to trivial cases.

David HarveyNovember 7th, 2010 at 1:32 am

Suspect some of the comments here miss the point. This is an _exercise_: use it in the same way as a musician might practice scales (and if your last experience of doing _this_ was as a reluctant ten-year-old, then talk to a real musician to understand what I mean. These basic things are exercises in self-awareness, control and feedback). Of course a stack is trivial, but that’s not the point…

David SaffNovember 7th, 2010 at 7:08 pm

Steve,

Can you define a “Selenium application”? Is this a web application that is tested with Selenium, a library built on top of Selenium, or something else? I’ve built medium-to-large systems in both domains using TDD, happy to share experiences.

adminNovember 7th, 2010 at 9:28 pm

Steve,

What I get from your messages is that you’d like the reassurance that TDD brings but you can’t see how in your situation. That’s a tough position to be in. I agree that this exercise is unlikely to help you achieve that goal. Instead, it is intended to help practicing TDDers understand how many degrees of freedom they have.

Jakub HolyNovember 8th, 2010 at 2:47 am

David,

I’d be interested in your experience applying TDD to the development of a medium-to-large web application (tested with Selenium). It would be really nice if you published it – and the criticts of too simple TDD examples could be then easily silenced by pointing them to it :-)

Best Regards, Jakub

adminNovember 8th, 2010 at 6:06 am

Jakub,

I may be able to help with that. I have been involved as an advisor in building an insurance application for the past 12 years. It has been built almost entirely test-driven and continues to be. We don’t use Selenium, because it didn’t exist when we started, but I think the lessons will carry across. Would you be interested in hearing about that?

Kent

Anil ChopraNovember 8th, 2010 at 6:21 am

Dear Kent,
How does one get in touch with you besides doing it through comments? Is there an email id you could share? Would really appreciate your response. Thanks.

Anil

adminNovember 8th, 2010 at 6:30 am

You can send mail to mailto:kent@threeriversinstitute.org

Richard TibbettsNovember 8th, 2010 at 6:35 am

Line by line test driven development seems like line by line commenting, rigorous modeling, or any other programming practice applied in the small. It might be a good idea for very inexperienced programmers, but once you are experienced doing testing as part of your development and maintaining your coverage metrics, it’s better to build a utility class like this (or even something more complicated and less likely to be in the standard library, like a currency future settlement date calculator) all at once along with it’s tests, focusing before-code testing effort on the parts you know are difficult, and using automated testing and metrics tools to validate that you have good coverage. When fixing bugs, writing failing tests first makes a lot of sense. But for greenfield development well within the programmers comfort zone, alternating constantly between testing and coding slows things down.

Examples like this imply that Test Driven Development is something that must be applied religiously, to the point where it impacts development process and time out of proportion to it’s value. Like commenting and modeling, professional programmers should know when it is appropriate to test first.

ChristianNovember 8th, 2010 at 6:54 am

I think this is a great exercise. As David points out, this is the programmer equivalent of simple exercises in other disciplines. Musicians practicing scales is a good example, another is body-builders doing push-ups. Body-builders probably already know how to do push-ups, but that doesn’t mean practicing them is meaningless.

As for the “Selenium argument”. In my experience, Selenium is the wrong tool for most kinds of testing, perhaps except for certain kinds of acceptance testing. Testing server-side logic with Selenium is – in my experience – painful and counter-intutive. If the problem here is that Selenium is used to test logic in the UI as well, you might be interested in a book I recently published, which teaches TDD for JavaScript, and has lots of examples on using TDD to build a browser based chat client: http://tddjs.com. Sorry for the shameless self-plug here, but I thought it might be relevant.

Keith RayNovember 8th, 2010 at 7:03 am

re: “But for greenfield development well within the programmers comfort zone, alternating constantly between testing and coding slows things down.”

I experienced a slow-down when I was learning TDD (years ago!). When I do greenfield development these days, not doing TDD will slow me down within an hour of starting to write code. So the “increased speed” I might experience without TDD is very short-lived.

TDD enables safe Refactoring, finds my mistakes within minutes of me creating them (and mistakes are not confined to “difficult” code, they are often “simple” mistakes), and allows me to avoid using the debugger much of the time.

adminNovember 8th, 2010 at 7:24 am

Richard,

My experience is that I am more effective when software development is a series of safe steps, where I believe I understand the consequences of each change. I’m often wrong, which is why I appreciate the feedback from the tests. What’s a safe step for me might be unsafe for someone else, and vice versa. It sounds like you’re comfortable taking larger steps than I am, which seems fine.

Johannes LinkNovember 8th, 2010 at 8:53 am

To all those asking for “real life” and “complex” TDD examples:
1. It’s very hard to make the simple (!) principles clear when you hide them in a complicated and convoluted environment. There are many open source systems out there with large chunks of test-driven code; the most obvious example is JUnit itself. Go there, read the code and tests and tell me if it helped you to understand the fundamental principles of TDD (given you didn’t know them before).
2. Having a complex domain does not free you from testing the simple parts in your system. As soon as you’ve mastered that, tackle the complex stuff – if any remains.
3. Doing something “complex” (from a domain perspective) in TDD often results in code that sceptics will call out as “too simple” again, thus making the whole argument self referential. Yes, I’ve seen that a couple of times.

My point: As simple as the stack exercise might look, it is an advanced exercise. To grasp the nuances you must have learned _and experienced_ the basics before. There is no way around that.

startupgrrlNovember 8th, 2010 at 4:41 pm

It’s good to see that TDD can waste scads of time on even the most trivial examples. Have fun testing for potential bugs that will never see the light of day in addition to reacting to bugs that traditional regression testing would find, boys.

adminNovember 8th, 2010 at 5:06 pm

The purpose of this exercise is to help programmers understand the actual constraints between technical decisions (which are much looser than they might appear). I am not clear whether you think that programmers don’t need to understand the actual constraints between technical decisions or if you are making a different point.

Tim HuntNovember 9th, 2010 at 1:08 am

People have so far missed the the place where TDD really pays off. Maintenance, and any time when you want to refactor your code. And if you are developing anything non-trivial, you will have to refactor along the way, so your tests will definitely pay for themselves during development.

To take a fairly trivial example, I was doing something that was basically the Strategy pattern, and I was really struggling with the class name. I knew what role the strategy had, but I could not find the words. The best name I could come up with was QuestionInteractionModel, which I was not very happy with, but I had to get on and write code. It was only after a lot of code was written, about the third time I talked someone new through it, explaining how all the code worked, that I eventually worked out that the whole thing was much more comprehensible if the class name was QuestionBehaviour. Fortunately I had done the whole thing TDD. I could make several passes through the code, renaming all the classes in the hierarchy and all the variables and fields that held references to those objects – and all the methods that returned them – and all the mentions of these things in comments. The whole thing took a few hours, and there were no regressions that my tests did not catch. Now the design of my system is much easier to understand from the code. I would never have dared to make that change without tests.

ZsoltJanuary 1st, 2011 at 9:04 am

Hi Kent,

I did your exercise with a constraint, and got some issues with testing. Can you have a look, and share some ideas how you would test it? Thanks.

http://www.zsoltfabok.com/blog/2010/12/11/testing-the-stack/

Cheers,
Zsolt