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.
-----