Beware Pseudo-Arrays

I'm always fascinated by the kinds of programming mistakes that novices make, and what they say about that student's state of mind. I particularly enjoy mistakes that aren't really mistakes, in the sense that the student has actually gotten the code to work, but where the code clearly demostrates some flaw in that student's mental model of programming. For example, see my previous post on Boolean confusion.

Here's another example involving arrays, or rather the lack of them. I was reminded of this example just yesterday when multiple teams tried to use this idea in a local programming contest.

Suppose you are rolling some standard six-sided dice, and keeping track of how many times each number has appeared. The most natural way to do this would be to use an array indexed from 1-6. In a language with zero-based arrays, you might use indices 0-5 and subtract 1 from each die value, or you might use indices 0-6 and simply ignore index 0.

However, many novices faced with this decision will reject arrays altogether and use six separate variables, perhaps named count1, count2, count3, count4, count5, and count6. (Or, if they are really gluttons for punishment, ones, twos, threes, fours, fives, and sixes.) I call these kinds of variables pseudo-arrays.

Why use pseudo-arrays? Because real arrays are scary. Plain variables and if-statements are much friendlier! After all, why write

   count[dieValue]++;

when you could write

   if (dieValue == 1) {
      count1++;
   }
   else if (dieValue == 2) {
      count2++;
   }
   else if (dieValue == 3) {
      count3++;
   }
   else if (dieValue == 4) {
      count4++;
   }
   else if (dieValue == 5) {
      count5++;
   }
   else {
      count6++;
   }

Oh, and don't bother suggesting a switch-statement — if-statements are good enough, thank you very much.

Why do so many novices do this? In many cases, I think it is because they were first exposed to if-statements, and found them easy, and then later were exposed to loops, and found them difficult. Arrays are usually processed using loops, and are usually introduced while the beginner is still reeling from the trauma of loops. Thus, arrays become tainted and suspect. In such a novice's mind, the approach with variables and if-statements truly is easier, especially because so many of the if-statements can be programmed using cut-and-paste — the favorite editing commands of most novice programmers!

Every once in a while, I see code by somebody who has gotten over their fear of loops, but has not yet become reconciled with arrays. This can lead to gems where the student tries to loop through a pseudo-array, as in

   for (int d = 1; d <= 6; d++) {
      if (d == 1) {
         System.out.println(count1);
      }
      else if (d == 2) {
         System.out.println(count2);
      }
      else if (d == 3) {
         System.out.println(count3);
      }
      else if (d == 4) {
         System.out.println(count4);
      }
      else if (d == 5) {
         System.out.println(count5);
      }
      else {
         System.out.println(count6);
      }
   }

As Dave Barry would say, I am not making this up.

Games for Programmers: Jotto

The next in an irregular series of board game recommendations for programmers. Of course, you don't have to be a programmer to enjoy these games, but if you are a programmer, then I think there's a pretty good chance that you'll like them.

However, you might not want to play this particular game with your spouse. Here's why...

“End. E-N-D”, she guessed. “One”, I replied.
“Cab. C-A-B”, I guessed. “One”, she replied.

We were driving to a campground in Massachusetts. My wife and I were in the front seats of the minivan; our daughter was in the middle seat, watching a DVD; and our son and his friend were chatting in the back seat.

We had been on the road for several hours, and I was feeling a bit tired. I needed to do something to help keep me alert. “Jotto?”, I suggested to my wife. “Ok.“

“Icy. I-C-Y”, she guessed. “Zero”, I replied.
“Fed. F-E-D”, I guessed. “One”, she replied.

Jotto is a two-player deduction game, kind of like Mastermind but with words. In fairness, I should say that Mastermind is like Jotto but with colors, since Jotto is older than Mastermind.

Each player secretly chooses a five-letter word with no duplicate letters. The usual restrictions apply—no proper nouns, etc.

The players take turns guessing each other's words. For each guess, you tell the player how many letters were correct. Unlike Mastermind, it doesn't matter whether the letter is in the right position or not. For example, if you guessed BOARD and got one letter right, the answer might be PLAYS (the A matches, in the same place) but it could just as easily be GAMES (the A matches, not in the right place).

“Map. M-A-P”, she guessed. “One”, I replied.
“Jig. J-I-G”, I guessed. “Zero”, she replied.

Jotto is a favorite game for situations where it would not be feasible to set up a board or deal out cards. For example, you can easily play it in a restaurant, or waiting in line, or on a long drive. All you need is two pencils and two pieces of paper.

“Age. A-G-E”, she guessed. “Two”, I replied.
“Out. O-U-T”, I guessed. “Zero”, she replied.

In fact, you don't even need the pencil and paper! Most of the time, we play it in our heads with three-letter words instead of five. This is a great variation that allows the driver to play in the car. It also lets you play in situations where you are moving too much to be able to take notes comfortably, such as jogging or hiking.

For this game, I picked AXE as my word.

“Axe. A-X-E”, she guessed. “Got it. Dang that was fast!”, I replied.
“Men. M-E-N”, I guessed. “One”, she replied.

I started playing Jotto this way with my son when he was 10. We still enjoy it and play it often, but it has become kind of a running joke, because we almost always finish within one guess of each other. This is the first time I have played mental Jotto with my wife, and she's killing me! She got it in five guesses, and I'm not even close!

Ok, with ones for both FED and MEN, I guess that it probably has an E. Next, I want to figure out which letter from CAB was correct. I'll try the A, and I'll also throw one of the other letters from FED to help confirm that it really was the E.

“Far. F-A-R”, I guessed. “One”, she replied.

Good. It probably really was the A. What has an E and an A?

“Sea. S-E-A”, I guessed. “Two”, she replied.

Now I'm getting somewhere. It looks like the E-A is correct. What else has an E-A?

“Pea. P-E-A”, I guessed. “Two”, she replied.

Hmm. I'm nearly certain now that the E-A are correct. What else has an E-A? It can't be TEA because I already got a zero for OUT. What if it's A-E instead of E-A?

Wait a minute. No way. No, she couldn't possibly have picked...

“Axe. A-X-E”, I guessed. “Got it”, she laughed.

Oh, man. We really have been married too long.

Originally written as a session report for BoardGameGeek.

Creativity

I recently stumbled across the TED video by Ken Robinson (via Joshua Gans). This video is almost two years old, so I'm getting to it rather late.

Robinson describes the increasing importance of creativity in the modern world, and bashes the education system for “educating people out of their creativity”. He contends that “creativity now is as important in education as literacy and we should treat it with the same status”. Robinson is an entertaining speaker, and I quite enjoyed his video. However, as I thought about it later, I become more dissatisfied.

I agree that creativity is important, and that the education system is doing a terrible job nurturing creativity. My problem with his talk is that he equates creativity with the arts: drawing, drama, dance, etc. I would hate to see some school administrator be inspired by the talk and attempt to “solve” the problem by simply adding an extra art class to the curriculum.

I'm not anti-arts. I'm not saying that art classes are bad. I am saying that giving students one art class in which to be creative, while systematically sucking the creativity out of them in every other class, is not going to solve the problem.

Instead, we need to recognize that other disciplines outside the arts also require creativity, and teach them that way. For example, mathematics is often taught in a way that brooks no creativity whatsoever, whereas the practice of actually doing real mathematics is highly creative. See Paul Lockhart's essay (pdf) for a wonderful discussion about creativity in mathematics education.

I think people often view technical subjects as having no place for creativity. You don't want a student getting creative when multiplying two numbers. I certainly don't want my programming students getting creative about indentation. In fact, in many technical subjects, the very word creative is often used as a synonym for wrong or mistaken (or sometimes unethical, as in “creative accounting”).

For example, I just said that you don't want a student getting creative when multiplying two numbers. But that's only because, in that context, “getting creative” would usually be interpreted as getting the wrong answer. In reality, I'd be thrilled if my grade-schooler, when faced with a multiplication problem like 37x999, rejected long multiplication and instead said, “Hmm. 999 is almost 1000. 37x1000 is 37000. Then take away 37 to get 36963.” That's creativity!

Perhaps the biggest difference between creativity in the arts and in technical subjects has to do with constraints. In the arts, you tend to have fewer constraints, and those constraints are often flexible. In technical subjects, you tend to have more constraints, and those constraints are often non-negotiable. Think of the scene from Apollo 13: “We've got to find a way to make this...fit into the hole for this...using nothing but that.” Or the t-shirt about the speed of light that says “300,000 kilometers per second: It's not just a good idea, IT'S THE LAW!”

Common perception is that, the more constraints you have, the less creativity is involved. I don't think that's true. In fact, as Marissa Mayer of Google fame says, creativity loves constraints. Of course, sometimes the creativity lies in figuring out which constraints are real, and which aren't.

Immortality

Last week, I wrote about one of my more spectacular failures, which involved a progression that began 1, 2, 4, 8, 16, 32, but then rather than continuing sensibly as 64, 128, ..., instead exploded into 273, 65569, 4294967361, and 1.5x10⁸². The next term is a little over 2⁶⁵⁵⁶⁹ and the term after that a little over 2^4294967361, which has about a billion digits when written out in full.

Joshua Zucker suggested that I submit this to the On-Line Encyclopedia of Integer Sequences, which I did. So I've now been immortalized in Sequence A137181. I can see my tombstone now: “He failed...BIG.”

Several years ago I was giving a guest lecture in a colleague's Algorithms class, when I encountered immortality of a different sort. The students were asking me about how I invented “Okasaki trees”, and were dumbfounded when I didn't know what they were talking about. How could I not know about Okasaki trees when I invented them? “Well,” I told them, “I've invented a lot of different data structures, and most of them are trees of one kind or another. But I've never called any of them Okasaki trees.” After a bit more digging, it turned out that my colleague (who wasn't there that day) had been telling them the previous week about my simplification of red-black trees, and he called them Okasaki trees.

The lasting result of this is that I now have a friend at work who ribs me about Okasaki trees every chance she gets.

A Spectacular Failure

About five years ago, a mathematical puzzle occurred to me. I eventually solved the puzzle, but I don't want to talk about that solution here. Instead, I want to talk about my first attempt at solving the puzzle, which was an utter failure. A glorious, spectacular failure. Perhaps the single most impressive failure of my career. Failures are often much more interesting than successes, but for some unfathomable reason, people are often reluctant to discuss them.

The Puzzle and My “Solution”

You don't need to understand the details of the puzzle to enjoy the failure, so if you're not familiar with SK combinators and their ilk, or if you just can't be bothered, then please skip ahead to the next section.

I was playing around with SK combinators one day when a puzzle occurred to me. Could I introduce new combinators that would allow me to linearize any combinator expression? Combinator expressions are normally binary trees, and are written using parentheses to indicate the tree structure. The convention is that parentheses on the left can be omitted. For example, ((w x) y) z can be written as w x y z, but w (x (y z)) cannot be written without parentheses. I wondered if I could introduce new combinators that would allow me to rewrite any expression into an equivalent expression with no parentheses. I called such a transformation “flattening”.

One of the standard combinators in the SK family is B, which has the rewrite rule

B f g x = f (g x)Reading this rule backwards works well for flattening small expressions—for example, x (y z) can be rewritten without parentheses as B x y z—but I ran into problems using it to flatten larger expressions, so I quickly turned to a variation of B that swaps the first two arguments R f g x = g (f x) This new combinator works well for flattening expressions of the form c (c₁ c₂ ... c_N). For example,

   c (c1 c2 ... c7)
       = R (c1 c2 ... c6) c c7
       = R (c1 c2 ... c5) R c6 c c7
       = R (c1 c2 ... c4) R c5 R c6 c c7
       ...
       = R c1 R c2 R c3 R c4 R c5 R c6 c c7

Now, another combinator F works in conjunction with R to flatten more complicated expressions. F is defined as

F f g x y = f x (g y) For example, we can now rewrite c₁ c₂ c₃ (d₁ d₂ d₃) as follows:

   c1 c2 c3 (d1 d2 d3)
      = F (c1 c2) (d1 d2) c3 d3
      = R c1 F c2 (d1 d2) c3 d3
      = F (R c1 F) d1 c2 d2 c3 d3
      = R (R c1) F F d1 c2 d2 c3 d3
      = R R R c1 F F d1 c2 d2 c3 d3

The complete rules for flattening are

• flatten(c) = c
• flatten(e c) = flatten(e) c
• flatten(c1 (e c2)) = flatten(R e c1 c2)
• flatten(e1 c1 (e2 c2)) = flatten(F e1 e2 c1 c2)
• flatten(e1 e2) = flatten(flatten(e1) flatten(e2))

where each c is a simple symbol and each e is an arbitrary expression.

Not So Fast

I run my solution by hand on a few examples and it works great. So I code it up, run it on my examples and get the same answers. Yippee! Next, I run it on a larger example and.........nothing. The computer justs sits there, mocking me. Obviously, I've got a bug somewhere that is causing infinite recursion.

I stare at my program for awhile, but I'm not seeing any bugs. Hmmm. I run it on a different example and it finishes this time. I print out the result and...whoa, that's a lot of output! I wonder how big the transformed expressions are? Ok, calculating the size of the result shouldn't be too hard. I whip up another program and print out a table of the maximum output for an input of size N.

   N=1     max output=1
     2                2
     3                4
     4                8
     5                16
     6                32
     .
     .
     .
     .

Quick! Guess the next value in the table! 64, right? RIGHT?!

     .
     .
     .
     .
     .
     7                273
     .
     .
     .
     .
     .

Huh? 273? What the heck is that?

     .
     .
     .
     .
     .
     8                65,569
     .
     .
     .
     .
     .

65,569?! You're joking, right?

     .
     .
     .
     .
     .
     9                4,294,967,361
     .
     .
     .
     .
     .

4 billion? Well, that's just silly.

     .
     .
     .
     .
     .
     10      15,177,100,720,513,508,366,
            558,296,147,058,741,458,143,
            803,430,094,840,009,779,784,
            451,085,189,728,165,691,939

What do you even say to a number like that? That's 1.5x10⁸². To put that in perspective, the number of atoms in the observable universe is estimated to be about 10⁸⁰. No wonder my program was running slow! At a few billion operations a second, that calculation should only take about...um...carry the 3...dang, where's Art Benjamin when you need him?...let's just say a long time.

If you're curious, here's the function that describes the size of the biggest possible output for an input of size N:

• Biggest(N) = 2^(N-1), if N <= 6
• Biggest(N) = 2^Biggest(N-3) + 2*Biggest(N-3) + 1, if N > 6

And here's the input of size 10 that gives the absurd result above:X (X X) (X (X X) (X (X (X X))))

Once I recovered from the shock of this experience, I did eventually come up with a very nice solution to the puzzle, based on ideas from postfix languages like Forth and Postscript, but nothing quite compares with getting an answer like 1.5x10⁸².

Wrong Number

Is it time to overhaul the user interface of the phone system?

A few months ago we started getting a lot of calls that were wrong numbers. Before that we used to get maybe one a week, but suddenly we were getting 5 or 6 a day. After an initial period of frustration, we eventually started to apply our debugging skills.

Our first guess was that somebody was distributing our phone number on a flyer or something, either as a prank or by accident. But this didn't make sense because every caller was asking for somebody different. “Hello, is Juan there?” “Hi, Elizabeth/Gary/Tanya/Carlos?” Or the ever popular “<pause> Who is this?!!” No, dude, you called me, so you tell first.

Ok, scratch that idea. Hmm, I suppose we could always ask. “Sorry, wrong number, what number are you trying to reach?” At last, some progress. Our phone number is 987-654-3210 (not our real number). The people who were calling us were uniformly dialing 654-321-0xxx. The 654 area code is for an area maybe 20 miles away, so lots of people in our area code were dialing numbers there. Even worse, there are up to 1000 numbers in that area code that match this pattern. No wonder we were getting a lot of calls!

The reason they were getting us was that they were forgetting to dial a 1 first. Without the 1, the phone system was interpreting this as a local call within the 987 area code to 654-3210, with the extra three digits on the end simply being ignored. On many (most?) cell phones the 1 is not necessary, so people lose the habit of dialing it. Then when they use a land line, where the 1 is required, they get us.

With this insight, we contacted the phone company. It took three tries and many patient explanations to even get somebody to understand what the problem was. I asked what had changed in the system recently, because clearly something had changed to cause the sudden increase in wrong numbers.

“Uh, I don't know. I'll ask our tech guy.” A few minutes later. “Our tech guy says the 321 exchange in the 654 area code is a Cingular exchange. You should call them.” “But how is that supposed to help? The phone calls are originating in your system and never getting out of your system, so even if they made a change over there, it wouldn't change what's happening here.” “Well, you should call Cingular.”

Predictably, Cingular couldn't help. They couldn't even tell us if the 321 exchange was new because “our computers don't tell us that”.

The really frustrating thing about the problem is that it's so easy to fix. It should be easy for the system to detect when somebody has dialed a 10 digits but is being connected to a 7-digit number. Give the caller a warning and ask them to redial! It's possible this might break some systems with extensions, where the leftover 3 digits indicate the extension. So perhaps disable the warning if there is a pause between the 7th and 8th digits.

Has anyone else had this problem?

Program Testing For The Sake Of Learning

A number of years ago, I used to compete in the TopCoder on-line programming contests. As an educator, I was fascinated by the TopCoder environment, less by the contests themselves than by the so-called Practice Rooms. These were archives of problems from old contests, where you could submit solutions and run them against the test data used in the actual contest.

I was amazed by how hard many people would work in the Practice Rooms. I wished I could get my students to work half that hard! At first, I thought these people were motivated by the idea of doing better in the contest. And, indeed, that was probably what got most of them to come to the Practice Rooms in the first place. But then I noticed that many of the people working hard in the Practice Rooms competed only rarely, if at all. Something else was going on.

Eventually, it dawned on me that the secret lay in the ease of running system tests. As teachers, we know that feedback is crucial to learning, and that quick feedback is better than slow feedback. These programmers were getting feedback within a few seconds, while they were still “in the moment”. The experience of this tight, nearly instantaneous feedback loop was so powerful that it kept them coming back for more. The burning question then was could I re-create this experience in the classroom?

Why test?

Of course, program testing has been part of CS education forever. However, there are several different reasons for testing, and which reason or reasons the teacher has in mind will strongly affect how testing plays out in any particular class.

Here are several common reasons for testing:

Improved software quality. Ironically, the number one reason for using testing in the real world is the least important reason to use it in the classroom. Most student programs, especially in early courses, will never be used for real. What matters in these programs is not that students complete the program correctly, but what they learn in the process.

Easier grading. Grading programs can be hard, especially if you have a lot of students. Naturally, many CS educators seek to automate this process as much as possible. Many systems exist that will run student programs against a set of instructor tests and record the results. These results may used as a guide for human grading, or the results may entirely determine the student grade. When testing is performed as part of the grading process, it is common for the actual test cases to be hidden from the students.

To learn about testing. Of course, testing is a vital part of real-world software development. Therefore, it is important to expose students to the testing process so they have some idea of how to do it. However, care must be taken here, especially in early courses. Hand-crafting good test cases is hard work. If students are forced to fight through a heavy-weight testing process on toy problems, including making up their own tests, the lesson they frequently take away is that testing is much more trouble than it's worth.

Testing as design. In recent years, test-first and test-driven development have begun to spread from agile programming into the classroom. Advocates view such testing as part of the design process. By writing tests before writing code, students are forced to consider what the behavior of the program should be, rather than diving in without a clear idea of what the program is supposed to do.

Another way

All of these reasons are important, but none of them quite capture what I was seeing in the TopCoder practice rooms. There, people were becoming addicted to quick, easy-to-run tests as a powerful learning experience. This suggests viewing program testing as a way to improve learning. Not learning about testing, but learning about the content being tested.

In an attempt to re-create the relevant parts of the TopCoder experience in the classroom, I adopted the following process. With most programming assignments, I distribute some testing code and test cases. Students then run these tests while they are developing their programs, and they turn in their test results along with their code.

Note that this is an extremely lightweight process. All I'm doing is adding maybe 20 lines of test-driver code to the code I distribute for each assignment, and I can usually cut-and-paste that code from the previous assignment, with only a few tweaks. I then add maybe 50-100 test cases, either hardwired into the code or in a separate text file. I usually generate perhaps 5 of the tests by hand, and the rest randomly. Usually this process adds about 20-30 minutes to the time it takes me to develop an assignment.

I think CS teachers are often scared away by ideas like this because they imagine a fancy system with a server where students submit their programs, and the server runs the tests and records the results into a database. That all sounds like a lot of work, so teachers put it off until “next year”. In contrast, what I'm suggesting could probably be added without much hassle to an assignment that is going out tomorrow.

Similarly, teachers are sometimes scared away by the need to come up with the test suite, thinking it will take too much time to come up with a set of high-quality tests. But that's not what I'm doing. Experience has shown that large numbers of random tests work essentially as well as smaller numbers of hand-crafted tests, but at a fraction of the cost. (See, for example, the wonderful QuickCheck testing tool.) Besides, I'm not trying to guarantee that my test suite will catch all possible bugs, which is a hopeless task anyway. Instead, I'm providing a low-cost test suite that is good enough to gain most of the benefits I'm looking for.

Benefits

And just what are those benefits? Well, since I started using this kind of testing in my homeworks, the general quality of submissions has gone up substantially. Partly, this is because of a drastic decrease in the number of submissions that are complete nonsense. When I did not require tests, students would write code that seemed correct to them at the time, and turn it in without testing it. Now, they can still turn in complete nonsense, but at least they'll know that they are doing so. Usually, however, when they see that they're failing every test, they'll go back and at least try to fix their code. In addition, many students who would have gotten the problem almost right without testing now get it completely right with testing.

Which leads me to the second benefit—there has been a noticeable improvement in the students' debugging skills. As one student put it, “[The testers] also taught us how to troubleshoot our problems. Without those test cases, many of us would have turned in products that were not even close to complete. This would have meant for worse grades and harder grading for the instructor. We also would not have been able to use and develop our troubleshooting skills. When we don't know that something is wrong, it is very hard to try to test for the failures.”

However, the main benefit is that the students are learning more. They are getting needed feedback while they are still “in the moment”, and can immediately apply that feedback, which is all great for learning. Contrast this, for example, to feedback that is received after an assignment has been turned in. Often such feedback comes days or weeks later. Students often don't even look at such feedback, but even if they do, they have often lost the context that would allow them to incorporate the feedback into their learning. Even with an automated system that gives feedback instantly, if students do not have an opportunity to resubmit, then they will usually not bother to apply the feedback, and so will miss out on a substantial portion of the benefit to their learning.

As another student put it, “The automated testers are much more than just a means of checking the block to ensure the program works. They function almost as an instructor themselves, correcting the student when he or she makes a mistake, and reaffirming the student's success when he or she succeeds. Late at night, several hours before the assignment is due, this pseudo-instructor is a welcome substitute.”

Grading

I have the students turn in the results of their testing, which makes grading significantly easier. Failed tests give me clues about where to look in their programs, while passed tests tell me that I can focus more on issues such as style or efficiency than on correctness.

But this is merely a fringe benefit. Note that I only use the test results to help guide my grading, not to determine grades automatically. I worry that when grading becomes the primary goal of testing, it can interfere with the learning that is my primary goal. For example, testing when used for grading often breaks the tight feedback loop that is where my students learn the most.

Also, when testing is used for grading, the instructor's test suite is often kept hidden from the students. In contrast, I can make my test suites public, which saves me all kinds of headaches. I'm not worried that a student might hardcode all the test cases into their code just to pass all the tests, because I'll see that when I look at their code. (In fact, this happens about once a year.) Students like having the test cases public because, if they don't understand something in the problem statement, they can often answer their own questions by looking at the test cases.

Admittedly, sometimes students take this too far. I occasionally catch them poring over the test cases like trying to read tea leaves, instead of coming to ask me a 30-second question.

Crawl-Walk-Run

I am not advocating that this approach to testing should be used everywhere in the curriculum. Among other things, I agree that students should have the experience of creating their own test cases. The question is when.

I see my approach as being most useful in beginning programming courses, and in courses that are not nominally about programming. For example, it works particularly well in Algorithms.

In other programming courses, however, I believe that a crawl-walk-run approach is appropriate. The “crawl” step is about attitude rather than skills; it is to convince students that testing is valuable. I believe my approach does this, especially if you occasionally leave out the tests and explicitly ask students to compare the experiences of developing with or without tests.

The “walk” step might be to have students generate their own tests, but using instructor-supplied scaffolding. The “run” step might be to have students generate both the tests and the scaffolding. I admit, however, that I have not taught the courses in which those steps would be most appopriate.