TITLE: The Polymorphism Challenge AUTHOR: Eugene Wallingford DATE: February 19, 2012 12:17 PM DESC: ----- BODY: Back at SIGCSE 2005, Joe Bergin and ran a workshop called The Polymorphism Challenge that I mentioned at the time but never elaborated on. It's been on my mind again for the last week. First I saw a link to an OOP challenge aimed at helping programmers move toward OO's ideal of small classes and short methods. Then Kent Beck tweeted about the Anti-IF Campaign, which, as its name suggests, wants to help programmers "avoid dangerous ifs and use objects to build a code that is flexible, changeable, and easily testable". That was the goal of The Polymorphism Challenge. I decided it was time to write up the challenge and make our workshop materials available to everyone. Background Beginning in the mid-1990s, Joe and I have been part of a cabal of CS educators trying to teach object-oriented programming style better. We saw dynamic polymorphism as one of the key advantages to be found in OOP. Getting procedural programmers to embrace it, including many university instructors, was a big challenge. At ChiliPLoP 2003, our group was riffing on the idea of extreme refactoring, during which Joe and I created a couple of contrived examples eliminating if statements from a specific part of Karel the Robot that seemed to require them. This led Joe to propose a programming exercise he called an étude, similar to what these days are called katas, which I summarized in Practice for Practice's Sake:
Write a particular program with a budget of n if-statements or fewer, for some small value of n. Forcing oneself to not use an if statement wherever it feels comfortable forces the programmer to confront how choices can be made at run-time, and how polymorphism in the program can do the job. The goal isn't necessarily to create an application to keep and use. Indeed, if n is small enough and the task challenging enough, the resulting program may well be stilted beyond all maintainability. But in writing it the programmer may learn something about polymorphism and when it should be used.
Motivated by the Three Bears pattern, Joe and I went a step further. Perhaps the best way to know that you don't need if-statements everywhere is not to use them anywhere. Turn the dials to 11 and make 'em all go away! Thus was born the challenge, as a workshop for CS educators at SIGCSE 2005. We think it is useful for all programmers. Below are the materials we used to run the workshop, with only light editing. Task Working in pairs, you will write (or re-write) simple but complete programs that normally use if statements, to completely remove all selection structures in favor of polymorphism. Objective The purpose of this exercise is not to demonstrate that if statements are bad, but that they aren't necessary. Once you can program effectively this way, you have a better perspective from which to choose the right tool. It is directed at skilled procedural programmers, not at novices. Rules You should attempt to build the solutions to one of the challenge problems without using if statements or the equivalent. You may use the libraries arbitrarily, even when you are pretty sure that they are implemented with if statements. You may use exceptions only when really needed and not as a substitute for if statements. Similarly, while loops are not to be used to simulate if statements. Your problems should be solved with polymorphism: dynamic and parameterized. Note that if you use (for example) a hash map and the program cannot control what is used as a key in a get (user input, for example). then it might return null. You are allowed to use an exception to handle this situation, or even an if. If you can't get all if statements out of your code, then see how few you really need to live with. Challenges Participants worked in pairs. They had a choice of programming scenarios, some of which were adapted from work by others: This pdf file contains the full descriptions given to participants, including some we did not try with workshop participants. If you come up with a good scenario for this challenge, or variations on ours, please let me know. Hints When participants hit a block and asked for pointers, we offered hints of various kinds, such as: •  When you have two behaviors, put them into different objects. The objects can be created from the same class or from related classes. If they are from the same class, you may want to use parameterized polymorphism. When the classes are different, you can use dynamic polymorphism. This is the easy step. Java interfaces are your friend here. •  When you have the behaviors in different objects, find a way to bring the right object into play at the right time. That way, you don't need to use ad hoc methods to distinguish among them. This is the hard part. Sometimes you can develop a state change diagram that makes it easier. Then you can replace one object with another at the well-defined state change points. •  Note that you can eliminate a lot of if statements by capturing early decisions -- perhaps made using if statements -- in different objects. These objects can then act as "flags with behavior" when they are passed around the program. The flag object then encapsulates the earlier decision. Now try to capture those decisions without if statements. (Note that this technique alone is a big win in improving the maintainability of code. You replace many if statements spread throughout a program with one, giving you a single point of change in future.) •  Delegation from one object to another is a real help in this exercise. This leads you to the Strategy design pattern. An object M can carry with it another, S, that encapsulates the strategy M has for solving a problem. To perform the associated behavior, M delegates to S. By changing the strategy object, you can change the behavior of the object that carries it. M seems to behave polymorphically, but it is really S that does the work. •  You can modify or enhance strategies using the Decorator design pattern. A decorator D implements the same interface as the thing it decorates, M. When sent a message, the decorator performs some action and also sends the same message to the object it decorates. Thus the behavior of M is executed, but also more. Note that D can provide additional functionality both before and after sending the message to M. A functional method can return quite a different result when sent through a decorated object. •  You can often choose strategies or other objects that encapsulate decisions using the Factory design pattern. A hash map can be a simple factory. •  You can sometimes use max and min to map a range of values onto a smaller set and then use an index into a collection to choose an object. max and min are library functions so we don't care here how they might be implemented. At the end of the workshop, we gave one piece of general advice: Doing this exercise once is not enough. Like an étude, it can be practiced often, in order to develop and internalize the necessary skills and thought patterns. Conclusion I'll not give any answers or examples here, so that readers can take the challenge themselves and try their hand at writing code. In future posts, I'll write up examples of the techniques described in the hints, and perhaps a few others. Joe wrote up his étude in Variations on a Polymorphic Theme. In it, he gives some advice and a short example. Serge Demeyer, Stéphane Ducasse, and Oscar Nierstrasz wrote a wonderful paper that places if statements in the larger context of an OO system, Transform Conditionals: a Reengineering Pattern Language. If you like the Polymorphism Challenge, you might want to try some other challenges that ask you to do without features of your preferred language or programming style that you consider essential. Check out these Programming Challenges. Remember, constraints help us grow. Constraints are where creative solutions happen. I'll close with the same advice we gave at the end of the workshop: Doing this exercise once is not enough, especially for OO novices. Practice it often, like an étude or kata. Repetition can help you develop the thought patterns of an OO programmer, internalize them, and build the skills you need to write good OO programs. -----