Thoughts and Actions: Beyond Haskell
What Has Been Learned?
Well, there’s some disagreement on that, but it’s my article, so I get to draw my conclusions. Of course, if anyone else wants to write an article I’ll happily publish it, and I do try to fairly represent most of the email comments I get. And, of course, the word “conclusion” is misleading. I try not to “conclude” my thinking. This is more a report on my brain contents as of 0921 on November 7th.
The SDTconf Program
The original program we wrote at the SDT conference, that set all this off, has a property different from any working program I’ve ever seen for solving this problem: it trys to process the list without any auxiliary information, no count variable or such. This is a very standard starting point for writing any program, especially any recursive solution. You want to take your input list, init a variable, and then zip recursively through the list, processing the function return at each level until you’re done. The classic recursive solutions work that way, such as factorial, or summing a list. When it works, it’s simple and elegant.
In this case, it doesn’t work. My guess is that it cannot be made to work, which of course just about guarantees that I myself will probably never make it work, because I’ve dropped that potential thread of development as being unproductive. I’m sure that to make it work, I’d have to go into some kind of analysis mode that I generally don’t enter – and even then, I don’t expect it to work.
Still, it might be possible. The challenge is out there, for Dan and anyone else, to find that kind of solution if it exists.
Because this kind of algorithm is delightfully simple and elegant, we can understand why Dan and the rest of us would like to find it. And with Haskell’s pattern-matching capabilities, we might be tempted to hack at the problem, building in “just a few more” patterns, to make our system work.
And yet, I’m inclined to argue that the tenth frame is different. The other frames take, as bonus balls, rolls from subsequent frames, which will also be scored. The tenth frame’s bonus rolls are not scored. It’s different. I plan to come back to that in a program I’ll write down below.
During the “Alternative Paradigms” session at SDTconf, Dan’s point was that Haskell and languages like it offer a way of programming that better reflects what we, as the developer, think. The industry folks in the session, while agreeing that language makes a difference, took the position that the language shapes the way we think, rather than some particular language being more like humans naturally think. (Frankly, I think that recursion is not part of how we naturally think: our brains are really bad at pushing things down and having them still be in shape when we pop them back up. Doesn’t mean recursion isn’t wonderful: it is. But a natural part of our thought process? I don’t think so.)
The industry folks went on to say that the problems we have to solve are rarely neat and easy to package. Chet made the point that the definition of Chrysler’s payroll isn’t just add up entitlements and deductions and print the check. That simple definition is all encrusted with odd deals, old benefits plans, new benefit plans, special deals made for seven guys in Dayton to avert a strike, and so on.
One lesson that is there to be learned from this tiny little example is that the neat and clean algorithmic solution sometimes just won’t work – and that there’s another solution, still pretty neat and clean, waiting to be discovered. Another lesson is that the tests are key to knowing how we’re doing, and whether we’re done. We had a flawed program, and didn’t know it until we found a case that didn’t work. Then we have a responsibility to fix our tests, fix our program, and learn from what has happened.
I’m hoping that Dan will have the time to upgrade his tests, and figure out a good clean way to solve the bowling problem, and then get back to us and tell us what he has learned from the exercise. This odd little program, as trivial as it seems, is rich with learning opportunities.
A Different Angle
Thinking is good. Thinking about what we’ve seen here reminds me that the tenth frame is different. One way of dealing with this is just to terminate the score-summing loop after ten iterations. That works just fine, and sooner or later it is a property of all the working implementations of bowling that I’ve ever seen.
Today I want to try something a bit different. I’m going to imagine a design, and then try to TDD my way to that design, or at least as close to that design as makes sense.
I’ll start from the same basic spec: given a set of rolls for a legal game of bowling, compute the score of the game. I’m going to add in the desire to model the game a bit. The game has ten frames. The frame scores are cumulative. The game score is the score in the tenth frame. Let’s see if we can build something that works that way.
I’m tempted to do this in Ruby. For my sins, though, I’ll do it in Eclipse. I’ll report some of my confusions, so that perhaps the emails I get will tell me how better to use this tool that is new to me. (Just downloaded it a week ago, and I’ve only written a couple of little programs so far.) Here goes:
Frames, in MyEclipse/Java. Getting Ready
You can skip to the next section if you don’t want to hear about my travails in getting used to Eclipse …
I’m starting up MyEclipse. Real soon now, it’ll be up. (New laptop is in the mail. 2.3gHz Core Duo. That should help.) Eclips almost up. Any minute now … Ha!
I’m in Java Browsing, the perspective that I like, looking at the previous version of the program. I like these tests, but I guess it’s better if I start clean. How to do that … Close Project seems like a good way to start. The project closes … and now Eclipse says “BowlingGameTest.java does not exist”, in the code-viewing pane. I guess I’ll just close it.
Now to create a new project … File/New/Project/Java Project. Answer a few questions, call it BowlingWithFrames, Finish … looks like time to write a test. New/JunitTestCase … click some options, Junit4, type in some names … looks good. Add the hookup test …
package bowlingWithFrames;
import org.junit.Before;
import org.junit.Test;
public class BWFTestCase {
@Before public void setUp() throws Exception {
}
@Test public void hook() throws Exception {
assert(false);
}
}
A little help from my friend Eclipse, and I’m ready to run my test and get my red bar. Of course, the Run button still thinks it should run the previous program’s tests, so I have to do Run … have to browse for the new project … it’s the default … ready to go … Red Bar, as expected. No, wait! It’s green. How is assert(false) passing? Obviously I don’t remember the Junit methods. No internet here. How do I figure them out? Well, don’t know. The previous hookup said assertTrue. That must be the trick:
@Test public void hook() throws Exception {
assertTrue(false);
}
There we go, runs red. Retraining largely complete. Time to get to work.
Down to Work.
OK, where were we? Frames. We’re going to build a solution using a Frame class, and right now I’m expecting that we’ll need a subclass or something for TenthFrame. We’ll see what the code tells us, of course, but we’re going to make a Frame-oriented version, selecting tests to do the job for us. First, to get the structure in place, gutterballs, by intention:
@Test public void gutterballs() throws Exception {
roll(20,0);
Integer score = game.score(rolls);
assertEquals(0, score);
}
My cunning plan is that we’ll have a local roll method that takes a count and a value, producing that many rolls. We’ll call that as many times as necessary, producing an object rolls, which is the sole parameter to a score method on a game object. None of these are defined yet, so Eclipse has all kinds of red lights lit, planning to help me out. After clicking a bunch of helpers, and typing a cople of lines of code, we have this:
package bowlingWithFrames;
import static org.junit.Assert.*;
import java.util.ArrayList;
import java.util.List;
import org.junit.Before;
import org.junit.Test;
public class BWFTestCase {
List<Integer> rolls;
BowlingGame game;
@Before public void setUp() throws Exception {
rolls = new ArrayList<Integer>();
game = new BowlingGame();
}
@Test public void gutterballs() throws Exception {
roll(20,0);
Integer score = game.score(rolls);
assertEquals(0, score);
}
private void roll(int count, int pins) {
for(int roll = 0; roll< count; roll++)
rolls.add(pins);
}
}
package bowlingWithFrames;
import java.util.List;
public class BowlingGame {
public Integer score(List<Integer> rolls) {
return 0;
}
}
The highlighted bits are the part I had to type. The rest, Eclipse provided. The test is green. So far, we don’t really need frames. Let’s write a test. I’m thinking open frames, but we’ll make them all different, to encourage us to build the Frame class.
@Test public void opens() throws Exception {
roll(3); roll(4);
roll(2); roll(1);
roll(4); roll(5);
rollFrame(1,3);
rollFrame(2,5);
rollFrame(7,1);
rollFrame(2,2);
rollFrame(4,3);
rollFrame(2,3);
rollFrame(9,0);
assertEquals(63, game.score(rolls));
}
private void rollFrame(int firstRoll, int secondRoll) {
roll(firstRoll);
roll(secondRoll);
}
private void roll(int pins) {
rolls.add(pins);
}
private void roll(int count, int pins) {
for(int roll = 0; roll < count; roll++)
roll(pins);
}
As I was writing the opens() test, I started out assuming a method roll, because I didn’t want to use the existing roll method with a count of one. I put each frame on a line, with two rolls, to make it easier to count. I quickly got tired of that, and assumed another method, rollFrame, that takes the two rolls of a frame. Eclipse helped me implement those, though of course I had to fill in the details as shown. Naturally, I’ll change those first three lines, but I wanted you to see my growing understanding of what I’m up to.
(I don’t always work this way. Certainly by now I could have guessed that I’d need these methods, having written bowling about a million times, but I actually prefer to let the coding experience tell me what to do. I find it oddly soothing, and it’s good practice for all those problems that I don’t know exactly how to solve. Oddly enough, even bowling turns out a little different every time.)
The main thing now is to make the test run. To do that, I’m going to create a list of Frames, feed them the rolls, score them, and see what the total turns out to be. Beyond that, I’m not sure just what all that will look like.
Now I have a feeling that some people would be creating a MockFrame just now or something like that. Maybe not … I’m not sure just when or why folks do that, but it seems like some do it all the time. I am going to follow the TDD rule of not writing a line of code without a failing test (though I could also treat what I’m about to do as a refactoring), but there will be a few more lines than I usually write. Here goes … First, by intention, reimplement score():
public Integer score(List<Integer> rolls) {
createFrames();
loadFrames(rolls);
Integer score = scoreFrames();
return score;
}
I plan to create some frames, feed them the rolls, then get the score. I’m not sure whether this plan will work, but it seems like a good place to start. I’ll let Eclipse make those methods for me, and fill in what I know. This much keeps my gutter test running but not the other one:
public Integer score(List<Integer> rolls) {
createFrames();
loadFrames(rolls);
Integer score = scoreFrames();
return score;
}
private void createFrames() {
}
private void loadFrames(List<Integer> rolls) {
}
private Integer scoreFrames() {
return 0;
}
We still haven’t done much. Now I’ll create the Frames and figure out how to score them. I’m not sure how the scoring wants to go yet. We’ll see. First to create:
private void createFrames() {
frames = new Frame[10];
for(int frame = 0; frame < 10; frame++)
frames[frame] = new Frame();
}
package bowlingWithFrames;
public class Frame {
public Integer score() {
return 0;
}
}
And score the game:
private Integer scoreFrames() {
return frames[9].score();
}
Our gutters test still runs, and the open frames test still doesn’t. We need to load the Frames to make that happen. What a Frame needs to know is the score from the preceding Frame, and the rolls it needs to score (two, for now). We also need to give each Frame the rolls that pertain to it. In other words, each Frame needs to remove some rolls from the rolls list, the ones that it has consumed.
Is this seeming like a big bite? I feel that I’m on top of it, but by the time we’re done here we will have implemented 15 or 20 lines of code. Is that a lot? Anyway, redneck’s last words: watch this.
private void loadFrames(List<Integer> rolls) {
int runningScore = 0;
for (Frame frame: frames) {
runningScore = frame.scoreRolls(runningScore, rolls);
rolls = frame.remainingRolls(rolls);
}
}
I’m thinking something like this: We’ll give each Frame, in turn, a chance to score from the rolls array, then we’ll return another rolls array for the next guy. Let’s see if we can implement that. Eclipse will build the methods, I’ll fill them in.
public class Frame {
Integer frameScore;
public Integer score() {
return frameScore;
}
public int scoreRolls(int runningScore, List<Integer> rolls) {
frameScore = runningScore + rolls.get(0) + rolls.get(1);;
return frameScore;
}
public List<Integer> remainingRolls(List<Integer> rolls) {
return rolls.subList(2, rolls.size());
}
}
And my two tests are green. That even means I did that manual arithmetic correctly, adding up the frames in the test! That’s often the hardest part for me.
Retrospective
I stopped for the evening just above, and now I’d like to look back at what has gone on. As faithful readers know, I generally like to write just a few simple lines at a time, letting the growing code tell me what it wants to be. I usually try to resist putting in a “design” like this one, until the situation really calls for it. This design was surely not the simplest one that could possibly work for adding up some open frames. Just adding up the rolls would have worked, and would have been simpler. Here I wanted to have Frame objects, and I wanted them to record the information they needed, and to chew away at the rolls list, returning a shorter list for the next guy. Essentially, I wasn’t trying to discover a design, I was trying to explore a particular design.
Is that OK? “You got a problem with that?” My own practice is to start out very simply and to let the design emerge. I like how that feels. But looking at any problem, I usually see a few designs that look interesting and potentially good. I value holding back on those to get a sense for the natural shape of the program. But it can also make sense to try a specific design to see how it works. So … I’m Ron Jeffries, and I approve this message.
Another question is how I tested and drove this implementation. The only tests I had were the gutter balls and the open frames, the former working, and the latter not. And I built a whole new class, with three methods, with that test hanging red. I stopped midway through, with a fake return of zero in the Frame, to make sure that the code didn’t explode, and that the gutter test still ran.
Another way to have gone might have been to build up the Frame class with its own TDD tests. Create one, send it some rolls, see if it calculated the score correctly, see if it could trim the rolls list correctly. That might have been a more natural way to TDD that class. But I was interested in how that class was used, and I was completely confident that by the time the BowlingGame’s tests worked, the Frame would work. Still, if we continue this way, the Frame will have some behavior, but no tests of its own. It may have been OK to test it in place – I think that was the best way to decide what the Frame’s interface should be. But we need to put strike and spare behavior in to make things work. Maybe we should proceed now by testing Frame directly.
I’ve talked myself into it. I’ll do that. I’ll even create a test for its existing behavior.
But first, let’s look at how it’s used:
public Integer score(List<Integer> rolls) {
createFrames();
loadFrames(rolls);
Integer score = scoreFrames();
return score;
}
private void createFrames() {
frames = new Frame[10];
for(int frame = 0; frame < 10; frame++)
frames[frame] = new Frame();
}
private void loadFrames(List<Integer> rolls) {
int runningScore = 0;
for (Frame frame: frames) {
runningScore = frame.scoreRolls(runningScore, rolls);
rolls = frame.remainingRolls(rolls);
}
}
private Integer scoreFrames() {
return frames[9].score();
}
There are some things not to like. At the time we create the frames, we have the rolls. We could, in principle, create them and load them at the same time. In addition, the loading code makes two calls to each frame, once to tell it to score, once to get the remaining rolls. If we combine creating and loading differently, we might be able to improve that bit.
It’s also a bit awkward that the Game knows all that stuff about passing in the running score, and computing the remaining rolls. That information belongs on the Frame class, it seems to me. It might be better if there was a factory method on Frame, taking rolls, and returning a list of frames. It’s tempting to go that way.
But there’s another issue. Right now, we have all these nice frames, and each one knows its frame score. They’re given all the rolls at once right now, but if we were building a more dynamic scoring program, we might want to pass in the rolls as they occur. Imagine a bowling score sheet. In the middle of the game, some of the frames are completely filled in, some may be partially filled in but waiting for bonus rolls, and one frame is in progress, waiting for its first or second roll. The rest of the frames are entirely empty.
It makes sense that the bowling game would know about the frames, and that it might know which frame (or frames?) should receive the rolls. We’ve built versions like that in the past. They’ve all been interesting … none have been entirely satisfactory. That could be due to the fact that the rules of bowling mean that the game and frame interact in an odd way. Or it could be due to the inadequacy of the designs we’ve seen so far.
Frames, it seems to me, have a number of states worth thinking about:
- Empty, waiting for something to happen;
- Needing another roll to complete the frame;
- Rolls complete, but needing two bonus balls;
- Rolls complete, but needing one bonus ball;
- Complete.
Any given roll needs to be looked at by one, two, or even three different frames. Only the Frames know for sure whether they want to see a given roll. And only one Frame can decide whether that roll should be passed along to Frames on down the line.
That observation makes me imagine a design where the Frames are sitting there waiting, and when a roll comes along, we go down the list, looking for the first one that’s interested. From then until one says done, we feed the roll to each Frame.
This is an entirely different design! Instead of feeding all the rolls to the frames, with them eating rolls off the front, we’re going to pass the rolls one at a time. And we’re not going to show all the rolls to all the frames. Do we have to throw all this code away (all 20 or 30 lines of it!), or can we get there more smoothly?
I’m envisioning some kind of “feeder”, that receives the rolls one at a time, and gives them to the Frames that are hungry, stopping when one says that he has consumed the roll. That would be easy to do … were it not for the current need to keep the running score to pass between frames. Let’s change that first. Instead of passing the running score to the frames, we’ll pass nothing, and have each frame compute its own score, not the cumulative score. We’ll get the total score by adding them up … and we’ll have to go back and figure out how to do the cumulative thing later, since Frame scores in the real bowling game are supposed to be cumulative.
Enough talk. We have a direction. Let’s code. See you in the next article, Single Frame Scoring.