Teaching, Playing, and Programming

On the Dangers of Giving Games as Wedding PresentsorWell, it seemed like a good idea at the time...

2011-11-06T14:41:00.003-05:00

[This is a letter I included with a recent wedding present.]

Dear Ben and Sarah,

Well, it seemed like a good idea at the time…

I think you’ll enjoy this game, Thunderstone. I’ve been playing it a lot with my son. Like Race for the Galaxy, this one works very well with two players, but can also handle more players. (Predictably, with more players, it becomes very chaotic, especially when thieves are in play…) I’m so certain you’ll enjoy it that I also got you the first expansion, Wrath of the Elements.

You might notice that this box is the Wrath of the Elements box. See, the first Thunderstone comes with a huge box, with lots of wasted space. That box is twice as big as this one, and only comes with about half the cards you see before you. Knowing that dealing with the larger box would be difficult for you, I’ve combined all the cards for both the main game and the expansion into this one box. (By the way, if you end up liking the game, this box will also easily hold the cards for the second expansion, Doomgate Legion.)

There was just one eensy teensy flaw with my plan. A minor thing really, hardly worth mentioning.

The original rulebook was too big for this box.

I considered several options: Just leave out the rulebook and point you to the online rules. Stick the rulebook in a separate, sturdy envelope, which is guaranteed to get lost in about 13.8 nanoseconds. Fold the rulebook in half and jam it in the box. Then I found the perfect solution. A post on BoardGameGeek described trimming the top and bottom off the rulebook—which is all wasted space anyway—with a paper cutter.

Fun With Words Did you know that a mangle was a British machine used in the 1800’s to press water out of clothes? It’s called a wringer in the US. A probably apocryphal story asserts that the word mangle came into the English language to describe the damage done to clothes by this machine, but I think the causal chain is more likely to run in the other direction, with the machine being named after the word.

Umm, where was I? Oh yes, paper cutter.

Anyway, so I bring the rulebook into school and take it over to the room with the paper cutter. I line it up carefully, and pull down the chopper…which cuts about an inch into the rulebook and sticks. I push down a little harder…and the entire back of the paper cutter lifts off the table, the chopper twists the rulebook and pulls it partway off the bed and…

Hey, have you ever had a jam in a paper shredder? And cleared it by pulling half shredded paper back out the top of the machine. The papers come out looking pristine partway down the page, and then at a certain line of demarcation (you know, that line really ought to have a cool name, like the Maginot Line or the Mendoza Line), the rest comes out drooping in sad, wrinkled tatters. What’s the word? Oh yeah, mangled. Why do I bring that up? No reason, really.

Hmm, where was I? Right, paper cutter!

So I lift up the chopper and pull the rulebook out and…let’s just say it’s not looking too good. I flip it over—the rulebook, not the paper cutter, although that might have worked better—and try again on the other side. Let’s just say that that side left me longing for the Golden Age epitomized by the results of the first side. A few more minutes, and a few muttered imprecations later, and…

You know, my wife use to do scrapbooking, and they sell these funny little scissors that are designed to make an artistic ragged edge. Expensive little buggers. If only I had known, I could have saved her a lot of money.

So…Thunderstone! Great game! I think you’re going to like it. [a few personal comments deleted]

Congratulations!

Chris

Eating My Way Across Oahu

2010-07-18T03:46:00.002-04:00

Mochi

As a kid, one of my favorite treats was when my father picked up mochi from Fugetsu-Do in the Little Tokyo area of Los Angeles. Unfortunately, New York offers nothing comparable. (I've found several places that offer various kinds of manju, but not the kind I grew up with.)

What is mochi? The kind I'm talking about is a sweet, sticky, soft, smooth rice dough, usually wrapped around a sweet red or white bean filling.

In planning our trip, I found several mochi stores in Honolulu that I knew we had to try.

Mikawaya Confectionary (inside the Shirokaya department store in Ala Moana Center): We bought four pieces and split them. The hits were orange gyohi (an unfilled orange-flavored piece that tasted a bit like a creamsicle), and taro gyohi (a purple piece with taro-flavoring in the outer dough).

Fujiya Limited (hard to spot store on Waikamilo Road): The specialty here is fruit mochi. I was expecting some kind of fruit paste, but no, it's whole pieces of fruit wrapped inside the dough along with a little bit of bean paste. We had strawberry, blueberry, and raspberry. (I also snuck in a tsumami, which was the closest I've had to the ones I grew up with, but softer.)

Nisshodo Candy Store: The hardest of the three to find, it's literally in a warehouse behind a strip mall. Unfortunately, it was by far the worst of the three, so don't bother. My beloved white bean filling was particularly bad.

Other Sweets

I usually tend more to the savory side, but the rest of my family shares a profound sweet tooth. Hence, many of our stops involved sweets, even beyond the mochi above.

Liliha Bakery (N Kuakini St, just a little off Liliha St): Two words‒coco puffs. They sell over 5000 of these puppies a day. Basically an oversize cream puff with a creamy chocolate filling and a cap of chantilly frosting. How good are they? We went to the bakery four times, including three times in less than 24 hours! Interesting tidbit: The tiny little diner attached to this bakery is where they shot the scene in Lost where Kate visited her mother.

Leonard's Bakery (Kapahalu and Charles): It's all about the malasadas (Portuguese doughnuts). Fried dough, more bread-like than ordinary doughnuts, with hints of Portuguese sweet bread. Always served warm. Covered in your choice of several different powders (I took the classic sugar, but wish I had tried the li hing). Available with several different fillings (I chose haupia), or without. If you're into sweet fried dough‒you know who you are!‒this is probably a must try. I'm not, so I thought it was merely good. However, more people on our food tour picked this as their favorite stop than any other single place. Given the quality of the other places we stopped, Leonard's must be doing something right.

Rainbow Tea Stop (Maunakea Marketplace): Very good coconut tarts, but then we tried their banana lumpia. Bananas fried in lumpia wrappers, with a carmelized coating. Out of this world. And I don't even like bananas!

While I'm talking about sweets, I should say a few words about haupia, a kind of coconut pudding. Imagine coconut-milk jello not quite as firm as finger jello and you'll be on the right track. Haupia is everywhere in Hawaii, either by itself or as a filling for other desserts, such as malasadas from Leonards or the amazing vanilla haupia pie at the Snack Shack on Kauai. If you're willing to use canned coconut milk, it's very easy to make at home. Whisk 3 cups canned coconut milk with 5 tablespoons sugar and 5 tablespoons cornstarch. Keep whisking over heat until bubbly. Spread into a pan, and refrigerate until firm. Cut into squares to serve. (Some people substitute water or milk for up to half of the coconut milk.)

Manapua

The name “manapua” literally translates to “flower power”, which makes no sense because it was a corruption of the longer phrase “mea ono pua'a” (roughly, pork pastry).

Manapua is the Hawaiian version of a Chinese bao, with the bun made out of a dough similar to Portuguese sweet bread. The buns can be baked or steamed, and the fillings can be savory or sweet, with char siu (Chinese roast pork) being the most popular. Manapua are so popular on Hawaii that they used to be sold door-to-door by the “manapua man” (Hawaii's version of the Good Humor Man). These days the manapua man sells out of a truck.

Royal Kitchen (on the pedestrian part of River Street just off N Kukui Street): If I could transport one shop from Hawaii to my neighborhood, this would be it. I could eat a couple of these EVERY SINGLE DAY for breakfast. I loved the cha siu manapua, and the lup chong manapua was almost as good. I probably wouldn't bother with the curry chicken manapua again, but I'd still like to try the kalua pork and the Portuguese sausage. The sweet lovers in my family also enjoyed the coconut manapua and the black sugar manapua. (Another Lost sighting: the pedestrian bridge by Royal Kitchen is where they filmed Sun paying off Jin's mother.)

Libby Manapua (corner of Kalihi and Kalani): After enjoying Royal Kitchen so much, we stopped here on our way to the airport to pick up lunch. My internet research had turned up Libby Manapua as a strong contender for best manapua on the island. My verdict was that Royal Kitchen is better. The buns at Libby were bigger than Royal Kitchen's, but with too little filling for all that bread. Also, Libby offered a much smaller selection of fillings. On the other hand, the pork hash at Libby was fantastic. You can see these little pork-filled dumplings in the upper right corner of the box.

Sing Cheong Yuan Bakery (Maunakea Street): Not really manapua, but close enough that I'll mention it here. We never went into the store, but we were able to sample their ma tai su, a flaky bun filled with an intensely flavorful pork/shrimp mixture. Heavenly!

Noodles

Ramen Nakamura (on Kalakaua Avenue in Waikiki): After binging on Hamura Saimin on Kauai, I wanted to compare it to the “real thing”. Ramen Nakamura was very, very good‒I'd happily eat there again anytime‒but a notch below Hamura. To me, the biggest difference was in the noodles themselves, but I also had a slight preference for Hamura's broth. To be fair, Ramen Nakamura offers several different broths; I had the miso, but maybe the shio or shoyu broth would have fared better. Someone whose opinion I trust later told me that Ramen Nakamura has the best ramen in the city, and I believe it. Any negativity here should be read as praise for Hamura rather than a knock against Ramen Nakamura.

Ying Leong Look Funn Factory (Keekaulike Street): We were lucky enough to tour this tiny factory, where they still make look funn rice noodles by hand. First, they ladle the soupy noodle batter onto aluminum sheet pans, then steam them in the silver steamers shown in back. When the pans come out of the steamer, they are stacked in front of fans to cool. The noodles are carefully peeled out of the pan... ...and folded into stacks that look like giant calamari. Most of the noodles shown in these pictures are plain, but you can see small chunks in the batter in the first picture. These chunks are green onion and either char siu or shrimp. Below, you can see the finished product, sliced and drizzled with a little bit of soy sauce. Delicious!

Polynesian Cultural Center Luau

We spent a full day at the Polynesian Cultural Center. It's fun and worth the trip, although if we do it again we would skip the tour guide. But forget all the cultural stuff‒I'm here to talk about the food!

First, I have to get something off my chest: Dear PCC, The shave ice you sell in the park really should be shaved, not crushed!

Ok, I feel much better now.

The shave ice may have been disappointing, but their luau more than made up for it. Everything I tried was at least good, with many dishes reaching into outstanding territory, including

fabulous kalua pig, probably the second best I had on the trip
outstanding taro rolls (purple dinner rolls made with taro flour)
the best poke I had on the trip (poke is marinated chunks of raw ahi, although I found out later that PCC uses a Tahitian recipe rather than Hawaiian)
a wonderful sweet potato salad made from purple Okinawan sweet potatoes
fabulous pipikaula (similar to beef jerky, but softer)
the best haupia I had on the trip

Of course, they also had luau staples such as poi, lomilomi salmon, chicken long rice, chicken teriyaki, and fresh pineapple. All these were good, but not as memorable as the above dishes.

Speaking of fresh pineapple... At the family luau we went to for my cousin's first birthday, I gorged myself on fresh pineapple sprinkled with li hing powder.

A few years ago, I tried li hing mui, the king of the Hawaiian snack genre known as “crack seed”. Li hing mui is a salty dried plum covered with a bright red powder. The combination is salty, sweet, sour, stains your fingers red, and does funny things to your mouth. I have to admit I didn't like it. I think I even used the word “disgusting”.

But what I've now learned is that you can get the powder without the plum. I had it several times this trip sprinkled on fresh pineapple, which takes an already excellent treat up to the next level. I've heard that the powder is also good sprinkled on other kinds of fruit, on popcorn, even on ice cream. We brought a bag home that I look forward to experimenting with.

New for Lost Fans

I found a website (Lost Virtual Tour) that includes some great pictures of the places I mentioned, showing what they look like in the show and in real life.

To my surprise, this site also shows the pub where we went to our family luau.

Eating My Way Across Kauai

2010-07-16T12:14:00.002-04:00

Must Try

Hamura Saimin Stand (Lihue, close to the airport): This place is a dive...and I mean that in the best possible way. It's old, run-down, hard-to-find, and tiny, so you'll probably have to wait for a few minutes. But the food is amazing, not to mention cheap and plentiful! I'm a huge fan of ramen (the real stuff, not the dried packages you find in the grocery store) and Hamura serves some of the best you'll find this side of Japan. The “special” (shown to the right) is a huge bowl filled with wonderful noodles and broth, and then topped with char siu (roast pork), won tons, fish cake, ham, green onions, cabbage, and a hard-boiled egg. The bbq sticks (beef or chicken), crispy wontons, and lilikoi (passion fruit) chiffon pie are also excellent, but be aware that they run out of the pie. Seating is at a single zig-zag counter, so be prepared to chat with your neightbors.

Highly Recommended

Hanalei Dolphin Restaurant (Hanalei, on the right as you first drive into town): The best “fancy” meal we had on the trip. I had the shutome (broadbill swordfish) and my wife had the walu (Hawaiian butter fish). The shutome was among the best fish I've had in my life, and the walu was almost as good. Both were simply grilled, and then served with a slice of lemon and some drawn butter. The butter, in particular, was a revelation for me. Sure, you often see it with lobster and the like, but usually not with fish. After experiencing how much it enhanced the fish here, I'll have to ask for it at other places.

Puka Dog (Poipu, inside the Poipu Shopping Village): My son LOVED these, declaring them almost as good as my father's sweet-and-sour chicken wings, which is his high-water mark for non-dessert foods. They take a huge unsliced bun, and stick it onto a big spike, which both makes a hole for the dog and toasts the inside of the bun. They then put some toppings in the hole, fill the bun with a polish sausage, and add some more toppings to the tip of the sausage sticking out of the hole. Okay, the hole thing is a gimmick, but where they really shine is the toppings‒six different fruit relishes including mango, pineapple, papaya, banana, star fruit, and coconut (mango and pineapple are probably the best). They also include a mayonnaise-like “garlic lemon secret sauce”.

Pat's Taqueria (aka Pat's Taco Wagon) (Hanalei, by the base of the pier): On the mainland, lunch wagons are usually nothing special, but Hawaii has a tradition of great food served out of trucks. Pat's Taco Wagon is an excellent example. My first visit, I had the kalua pork burrito, which was very good. My second visit, I had the carne asada taco, which was mind-blowing. Both were kind of drippy, so be sure to lean over when you eat them.

Village Snack & Bakery (aka The Snack Shack) (Hanalei, in the back of the Ching Young Village Shopping Center): My favorite dessert on the island, vanilla haupia pie. Mmmm! If you get there early in the morning, you may also be lucky enough to get their fried mochi (three balls of mochi with a sugary coating on a stick). Their loco moco (a Hawaiian tradition with two scoops of rice, a hamburger steak, and two fried eggs, covered with brown gravy) and teriyaki beef sandwich were also outstanding, but the pancakes and apple cobbler were only so-so.

Shave Ice Paradise (Hanalei, across the street from the Ching Young Village Shopping Center): Shave ice is everywhere in Hawaii. Think giant snow cone, but made with shaved ice instead of crushed ice. The difference in texture is substantial, smooth instead of pebbly. You have a choice of many different syrups, and can add on ice cream underneath or sweetened condensed milk on top. The ice cream at the bottom didn't do much for me because you end up eating the top half of the ice without it, but the sweetened condensed milk on top (sometimes called a sno cap) is fantastic, changing what can sometimes be sickly sweet to sweet and creamy. Shave ice stands are very common, and there's not necessarily a lot of difference between them, but this one was the best we tried.

Hanalei Taro & Juice Company (Hanalei, in front of Kayak Kauai): Another lunch wagon. Plate lunches are a Hawaiian tradition with two scoops of rice, macaroni salad, and some kind of meat. I had the kalua pork plate lunch, which turned out to be the best kalua pork I tried on the island. The plate lunch also came with a little slice of their mochi cake, which is very good. They are famous for their smoothies, with use a taro base in addition to various combinations of fruit. My smoothie was good, but nothing special. The downside is that it's hard to find them open! I think they move around, but I didn't know where to look other than their main location.

Mediterranean Gourmet (Hanalei, way past the main drag, almost to Haena, at the Hanalei Colony Resort): We ate two lunches there, with good gyros, falafels, and chicken kebabs. We also went to their once-a-week luau since we were staying at the resort. The food at the luau was only so-so, but the entertainment was fun, if much lower key than many of the fancier tourist luaus.

Not Recommended

Bar Acuda (Hanalei): We were disappointed in this highly recommended tapas bar. The food we had there was good, some of it excellent. The problem is that their menu is just too limited, with only about a dozen choices for tapas. After running through everything we wanted to try out of their tapas offerings, we proceeded down the street to Bubba Burgers because the kids were still hungry.

Hanalei Gourmet (Hanalei): Okay, but nothing special.

Bouchons Hanalei (Hanalei): Nice atmosphere, but mediocre food. I did not try their sushi, so maybe that's better.

Round-Robin Tournament Scheduling

2009-11-23T23:35:00.001-05:00

For the last several years, I've held an in-class tournament on the last class day before Thanksgiving. Everybody's mind is elsewhere anyway, so the positive vibes generated by an hour spent hootin' and hollerin' are far more valuable than class content that would be forgotten long before the turkey made it into the oven.

Tomorrow's the big day, so I've spent part of today working out the tournament schedule. As usually seems to be the case, I have a different number of teams this year from past years, so I had to make a new schedule from scratch. I keep forgetting how I did it last time, but I always seem to converge back on the same technique. I finally decided to write down the technique so I can just look it up next year. Also, I'm hoping somebody can tell me what this technique is called, since it can't possibly be original.

Unless I have too many teams, I like to run a round-robin tournament, where everybody plays everybody else. There's a well-known algorithm for scheduling such a tournament by hand. I'll illustrate this algorithm with 6 teams, numbered 0–5. Start by writing the teams down in two rows, as follows:

   0 1 2
   5 4 3

The columns say which teams play each other. In this case, team 0 plays team 5, team 1 plays team 4, and team 2 plays team 3.

Now, leave team 0 in place, but rotate teams 1–5 one position clockwise.

   0 5 1
   4 3 2

In this round, team 0 plays team 4, team 5 plays team 3, and team 1 plays team 2. This process continues for three more rounds:

For an even number of teams, this technique generates a schedule with N−1 rounds, and N/2 games per round. For an odd number of teams, you add an extra dummy team, yielding a schedule with N rounds and (N−1)/2 games per round. In each round, the team scheduled against the dummy gets a bye.

Many games have a slight asymmetry, such as a homefield advantage or a first-move advantage. For my game, the “red” team has a very small advantage over the “blue” team. In tournaments for such games, it is important to balance the number of “home” games and “away” games played by each team. In the above algorithm, this is accomplished by making the top row the home team in odd-numbered rounds and the bottom row the home team in even-numbered rounds. (Note that, when N is even, half the teams will get one extra home game.)

Okay, so the above technique is easy, but it has a major drawback for my purposes, at least when N is odd. Because the tournament must be completed by the end of the class period, I need to be ready to drop games from the schedule if it looks like we're running long. The easiest way to accomplish this is to drop an entire round. But when N is odd, one team has a bye, which means that that team will end up playing a different number of games from everybody else, which in turn can make it difficult to determine the winner of the tournament.

To avoid this problem, I use the following technique. I organize the schedule in N/2 rounds, rounded down if N is odd. In each round (except possibly the last), every team plays twice: one home game and one away game. The rule is that, in round R, team X plays at home against team (X+R) mod N, and away against team (X−R) mod N. (If you don't remember how mod works, it simply means that the team numbers wrap around.) For example, here is a schedule for 7 teams, numbered 0–6.

   Round 1: 0-1 1-2 2-3 3-4 4-5 5-6 6-0

   Round 2: 0-2 1-3 2-4 3-5 4-6 5-0 6-1

   Round 3: 0-3 1-4 2-5 3-6 4-0 5-1 6-2

Each game is listed as HOME TEAM–AWAY TEAM.

If N is even, then the last round is treated specially. As described so far, the last round in an 8-team tournament would look like

   Round 4: 0-4 1-5 2-6 3-7 4-0 5-1 6-2 7-3

This involves repeat games, such as 0-4 and 4-0. To prevent such repeats, we chop off the second half of the last round when N is even.

Again, the advantage of this scheduling algorithm is that I can delete a round on the fly without causing an imbalance in the number of games that each team plays. Deleting a round also maintains the balance between home games and away games for each team, although that's a lesser concern.

Binomial queues as a nested type

2009-10-22T20:17:00.010-04:00

Warning: this is probably only of interest to functional programmers.

Maciej Kotowicz recently asked on the Haskell Cafe mailing list about implementing binomial queues (also known as binomial heaps) using fancy type machinery so that the type-checker can enforce the shape invariants of the data structure. This reminded me of a discussion I had with some colleagues in the summer of 1998 about using nested types to enforce these kinds of invariants. A little digging around in mail archives yielded this email, presented here with some light formatting and a few fixed typos.

I've been playing with binomial queues as a nested type, and I think you'll find the end result interesting.

REVIEW

Let me first quickly review the usual implementation of binomial queues. Recall that a binomial tree has the shape

data Tree a = Node a [Tree a]

A binomial tree of rank k has k children, of ranks k-1 .. 0 (stored in the list in decreasing order of rank). Note that we can combine two heap-ordered binomial trees of rank k to get a heap-ordered binomial tree of rank (k+1) as follows:

combine a@(Node x xs) b@(Node y ys)
   | x <= y    = Node x (b : xs)
   | otherwise = Node y (a : ys)

Now a binomial queue is a list of heap-ordered binomial trees of increasing height (but not necessarily of consecutive ranks). We'll represent the ranks of those trees that are present by their position in the tree. Thus, some ranks will be empty. This could be implemented as

type Binom a = [Maybe (Tree a)]

or somewhat more efficiently as

data Binom a = Nil
             | Zero (Binom a)
             | One (Tree a) (Binom a)

or better still by unboxing the Tree in the One constructor

data Binom a = Nil
             | Zero (Binom a)
             | One a [Tree a] (Binom a)

I won't go over all the operations -- they are amply covered elsewhere. I'll just describe two functions. The first, add, takes a tree and a list (where the tree has the same rank as the first position in the list), and returns a new list. It works basically like the increment function on binary numbers.

add :: Ord a => a -> [Tree a] -> Binom a -> Binom a
add x xs Nil = One x xs Nil
add x xs (Zero h) = One x xs h
add x xs (One y ys h)
  | x <= y    = Zero (add x (Node y ys : xs) h)
  | otherwise = Zero (add y (Node x xs : ys) h)

The merge function is similar and works basically like the addition function on binary numbers.

Finally, the getMin function returns the minimum element of a queue paired with the queue without that element. The helper function getMin_ returns a triple of the minimum element in some suffix of the queue, the list of children associated with that minimum element, and the suffix without that element.

getMin_ :: Ord a => Binom a -> (a, [Tree a], Binom a)
getMin_ (Zero h) = case getMin_ h of
                     (y,ys,h') -> (y,ys,Zero h')
getMin_ (One x xs Nil) = (x,xs,Nil)
getMin_ (One x xs h) = case getMin_ h of
                         (y,ys,h') | x <= y    -> (x,xs,Zero h)
                                   | otherwise -> (y,ys,One x xs h')

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
           in (x,merge (list2binom xs Nil) h')

list2binom [] h = h
list2binom (Node x xs : ys) h = list2binom ys (One x xs h)

Note that when getMin receives a list of children, it converts them to a valid binomial queue by reversing the list (and changing each pair of a Node constructor and a (:) constructor to a One constructor).

NESTED REPRESENTATION -- FIRST ATTEMPT

By following the same approach we have been using to design nested datatypes, we get the following representation of binomial queues.

data Binom_ a b = Nil
                | Zero (Binom_ a (Trees a b))
                | One a b (Binom_ a (Trees a b))

type Trees a b = (a, b, b)

type Binom a = Binom_ a ()

Here the list of children

  (Node x3 xs3 : Node x2 xs2 : Node x1 xs1 : Node x0 xs0 : [])

is being represented by the nested triples

  (xs3,xs3', (x2,xs2', (x1,xs1', (x0,xs0', ()))))

(where xsN' is the appropriate conversion of xsN).

All the functions are perfectly straightforward, except for getMin and getMin_ which must incrementally build up the reversing function to convert

  (xs3,xs3', (x2,xs2', (x1,xs1', (x0,xs0', ()))))

  One x0 xs0' (One x1 xs1' (One x2 xs2' (One x3 xs3' Nil)))

As a result of building up this reverse function incrementally, this implementation ends up being roughly 10% slower than the original.

INTERLUDE ON REVERSING LISTS

Suppose we want to support the following ADT. We want sequences with three operations:

empty :: ReversableSeq a
cons  :: a -> ReversableSeq a -> ReversableSeq a
rev   :: ReversableSeq a -> [a]

with the obvious semantics. cons must take O(1) time, but rev may take O(n) time. A list is a reasonable implementation with

type ReversableSeq a = [a]
empty = []
cons = (:)
rev = reverse

but, if you think about it, there's a fair amount of interpretive overhead in the pattern matching that reverse performs at every step. Way back in 1985, John Hughes came up with a representation that avoids this overhead:

type ReversableSeq a = [a] -> [a]
empty = id
cons x xs = xs . (x:)
rev xs = xs []

The result of cons 1 (cons 2 (cons 3 empty)) is

id . (3:) . (2:) . (1:)

which, when applied to [] by the rev function, yields [3,2,1]. One way to think of this representation is as lists with "holes" at the ends. The cons operation fills in this hole with an element and another hole, and the rev operation fills in the hole with []. (This is quite similar to difference lists in logic programming...)

Applying this trick to the regular representation of binomial queues yields

data Binom a = Nil
             | Zero (Binom a)
             | One a (Binom a -> Binom a) (Binom a)

which turns out to be about 10% faster than the original representation.

NESTED REPRESENTATION -- SECOND ATTEMPT

Ok, let's try to make a nested datatype out of this. Conceptually, the nesting should keep track of our position in the queue so that we know what rank the current tree has and can't possibly mix up trees of different ranks. We hypothesize some Base type for the beginning of the list, and some type transformer Succ that modifies the type as we move down the queue.

type Base = ???
type Succ b = ???  -- this might need to be Succ a b

type Binom a = Binom_ a Base

data Binom_ a b = Nil
                | Zero (Binom_ a (Succ b))
                | One a (Binom_ a ??? -> Binom_ a ???) (Binom_ a (Succ b))

Now, what should the missing types in the One constructor be? Well, the function (Binom_ a ??? -> Binom_ a ???) represents the children of the current node. If this node is of rank k, then these children are of ranks 0 .. k-1. The function (Binom_ a ??? -> Binom_ a ???) takes a queue starting at rank k and adds the children to the front of it, yielding a queue starting at rank 0. So the ???'s can be filled in as

                | One a (Binom_ a b -> Binom_ a Base) (Binom_ a (Succ b))

or just

                | One a (Binom_ a b -> Binom a) (Binom_ a (Succ b))

Now, what should the types Base and Succ be? It doesn't matter because we never construct data of those types, we simply use the types to discriminate between positions in the queue. So we can define Base and Succ as

type Base = Void
newtype Succ b = S Void

I think this is a very interesting type for several reasons:

It includes an arrow type, which we haven't seen much.
The RHS of the datatype definition (in fact, just the One constructor) has occurrences of Binom_ at no fewer than three different types
```
Binom_ a b
Binom_ a Base
Binom_ a (Succ b)
```
I've seen two before, but not three.
It includes types which are never used, but are merely there to capture certain invariants (in this case, that trees of different ranks should never be confused). [2009 Comment: Today, these are called phantom types.] In some ways this might make this type less interesting, but an interesting consequence is that the code satisifes a certain "type erasure" property: if you erase the types from all the functions, you get code for the optimized regular representation.

Because of this "type erasure" property, you might expect it to be just as fast as the optimized regular representation, but in fact it is roughly 10% slower -- or roughly as fast as the original regular representation. This is because the extra types hinder a certain optimization that the programmer might make (and which I did make in the optimized regular representation).

Recall the type of the getMin_ function from the original regular representation, and the way it was used by getMin.

getMin_ :: Ord a => Binom a -> (a, [Tree a], Binom a)

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
           in (x,merge (list2binom xs Nil) h')

For the optimized regular representation, this becomes

getMin_ :: Ord a => Binom a -> (a, Binom a -> Binom a, Binom a)

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
           in (x,merge (xs Nil) h')

Now, consider the optimized nested representation. We can't just write

getMin_ :: Ord a => Binom_ a b -> (a, Binom_ a b -> Binom a, Binom_ a b)

because we don't know the rank of the tree that the second component of the triple came from. (Note that if we had existential types, we could write

getMin_ :: Ord a => Binom_ a b -> 
                    (a, exists c. Binom_ a c -> Binom a, Binom_ a b)

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
           in (x,merge (xs Nil) h')

Some implementations do in fact support existential types, but in limited ways that would carry efficiency costs of their own...)

Instead of returning the children and then applying them to Nil at the end, we apply the children to Nil first, and then return the result, yielding the type

  
getMin_ :: Ord a => Binom_ a b -> (a, Binom a, Binom_ a b)

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
           in (x,merge xs h')

This depends on laziness to evaluate only the children of the final minimum, and not all the children of the temporary minimums along the way. However, this does mean that we build a lot more thunks of the form (xs Nil) along the way. And building these thunks is apparently quite expensive.

2009 Addendum Ralf Hinze considers a similar representation in Section 6 of Numerical Representations as Higher-Order Nested Datatypes. Today, you would probably use fancier type machinery like dependent types or maybe GADTs, but it's still amazing how far you can get with only nested types.

Score one for induction!

2008-10-01T23:36:00.000-04:00

One of my favorite textbooks on algorithms—in spite of the fact that it's twenty years old—is Udi Manber's Introduction to Algorithms: A Creative Approach. However, I have never been tempted to actually use it in class. You see, the book's greatest strength is also its greatest weakness.

Most textbooks on algorithms show you a lot of polished algorithms, but provide little or no insight on how to go about designing such algorithms. Manber's book does a very good job providing such insight, by making an analogy with inductive proofs. If you have any skill with induction, then you can use Manber's approach to help you design algorithms. (Of course, this should come as no surprise since writing an inductive proof and writing a recursive function are essentially the same activity.)

I'm sure you see the flaw here—most students are even less comfortable with induction than they are with recursion. It's like trying to help somebody learn to drive a car by making an analogy with riding a unicycle. For a certain segment of the audience, that analogy might be just what they need, but for the most of the audience, the analogy will only produce puzzled looks.

I was recently helping a student who was struggling to get a handle on recursion. He was making the common beginner mistake of trying to think about what happens during the recursive call instead of trusting that the recursive call works (sometimes called the recursive leap of faith). By sheer coincidence, I had happened to notice the day before that this student had done very well in our discrete math course the previous year. Time to give it a try...

“You know when you're writing a proof by induction and at some point you use the inductive hypothesis? That's just like a recursive call. You don't worry about what happens inside the inductive hypothesis, you just say ‘Assume that it works for N-1...’ It's the same with recursion. You just assume that the recursive call works.”

That comparison actually seemed to help. Maybe Manber was onto something after all!

Less than vs Greater than

2008-09-25T23:46:00.002-04:00

From math, we know that X < Y is the same as Y > X. But in programming, they're not the same.

Oh, I'm not talking about situations where X and Y have side effects that interact badly. Instead, I'm talking about situations where one may be more error prone than the other.

Although the two expressions are mathematically equivalent, they're not linguistically equivalent. One focuses attention on something being smaller, and the other focuses attention on something being bigger. For example, it is a relatively common mistake to go the wrong way when searching a binary search tree. However, almost every time I run into this error, the student has also written the comparisons backward from the direction I think of as “natural”.

Consider the following function for determining whether a given key x appears in a binary search tree t:

  function member(x,t) is
     if t = null then return false
     if t.key = x then return true
     if t.key < x then return member(x,t.left)
     if t.key > x then return member(x,t.right)

The fact that I've written this using recursion instead of iteration is irrelevant. What matters is that the third case goes left when it should go right, and vice versa for the fourth case. But looking more carefully at that third case

     if t.key < x then return member(x,t.left)

I'm not particularly surprised by the error. The comparison t.key < x focuses attention on something being smaller, and the left side of the tree is where the smaller keys go. By asking whether x is smaller than t.key, rather than whether t.key is smaller than x, I think we're much less likely to fall into this trap.

Hey, you got your loop in my recursion!

2008-09-13T00:10:00.001-04:00

I've written before about trying to diagnose students' broken or ineffective mental models from the mistakes they make. Here's a mistake that I see frequently from students who are not yet comfortable with recursion.

Say you wanted to write a function to calculate the sum of a list using a loop. Many students could easily write something like

   function sum(list) is
      variable total := 0
      while list /= null do
         total := total + list.item
         list := list.next
      return total

But ask them to write the sum function using recursion, and you might get something like

   function sum(list) is
      variable total := 0
      if list = null then
         return total
      else
         total := total + list.item
         return sum(list.next)

Of course, this code always returns 0. It's pretty clear that the writer had the iterative algorithm in mind, and doesn't understand that each recursive call to sum creates a new instance of the total variable.

When I watch such a student writing code like this, he often declares the variable immediately, before even beginning to think about what the recursive decomposition is going to look like, an almost spinal reflex conditioned by several semesters of writing loops. I can explain recursion until I'm hoarse and draw pictures until my hand cramps up, but I can't compete with the will-o'-the-wisp allure of that variable. Once it's there, it will almost inevitably lead the student to his doom in the bogs of iterative thinking.

One trick to help such a student is to break the cycle where it begins, by getting rid of that variable. Tell him to write the function without using any local or global variables. Or, if he really thinks he needs a variable, to declare it as a constant instead. Of course, there are times when a variable is perfectly appropriate inside a recursive function, but such examples can often be avoided until the student has a better grasp of recursion.

In search of epiphany

2008-07-31T11:42:00.001-04:00

I watched the movie Proof last night. I highly recommend it. It's not often that mathematicians get so much screen time.

The nature of mathematical creativity plays a large role in the movie. One comment was especially intriguing. (Minor spoiler ahead.) In describing the process of solving a particularly difficult problem, one character says, “It was like...connecting dots. Some nights I...I could connect three or four of them. And some nights they'd be really far apart. I'd have no idea how to get to the next one, if there was the next one.”

This description rings both true and false for me. The true part is I'd have no idea how to get to the next one, if there was the next one. This nicely summarizes what it's like to work on a hard problem. You don't know what to do next, and you're not sure that a solution even exists.

But the connecting dots part doesn't feel right. It makes the process sound linear, when the reality is anything but. In my experience, the really hard problems—the ones that require the most creativity—are most often solved by epiphany, by having the whole solution burst into your head, seemingly in an instant. That's when the connecting dots part happens, but it all happens at once, not a few a time.

Of course, the catch is that epiphany can't be forced. I'm reminded of the old joke about the lottery. A man prays fervently every night, “Please, Lord, let me win the lottery tomorrow.” After twenty years, a heavenly voice responds, “Would you buy a ticket already!”

No, you can't just sit around waiting for an epiphany to happen. Epiphanies are hard work! TANSTAAFL. So, how do you go about searching for epiphany? Every epiphany I've ever had has been the result of a two-pronged effort.

The first prong is building up sweat equity. I thoroughly explore the space around the problem, playing with the problem from many different angles. Of course, I'm actively trying to solve the problem during this time, because I might get lucky and stumble across a solution. But I don't worry too much if I don't seem to be getting anywhere. This part of the process is not so much about connecting the dots as about building lots and lots (and lots) of potential connections.

The second prong is staying alert. That's easy to say, but really hard to do over long periods of time. Eventually, I hope, some stray thought or some environmental trigger will start a cascade, where some subset of those potential connections will become actual connections, creating a path to the solution. Sometimes this happens when you're relaxed and your mind is drifting, such as in the shower or while driving. I remember once in grad school trying all afternoon to track down a bug. That night my wife and I went over to a friend's house for dinner. Everybody was shocked when, in the middle of beef stroganoff, I suddenly shouted out, “That's it!”

Other times the epiphany can happen while you're actively working on something else. For example, the key insight behind TradeMaximizer came while I was trying to put together a homework for my Algorithms class. I had been working off and on for weeks trying to find cycles in the trade graph. But I had set that aside and was coming up with homework problems, when I stumbled across a stray comment that talked about converting a directed graph into a bipartite graph. That sentence was enough to set off the chain reaction of connections and, within seconds, TradeMaximizer was born.

Probably the most famous story about scientific epiphany is that of Archimedes' bath. Funny story: Shortly after announcing TradeMaximizer to the math trade community on BoardGameGeek, I received a peevish email from another BoardGameGeek user who thought he also had a solution. He described how he had come to BoardGameGeek, eager to share his discovery, only to find my announcement first. He complained “Argh! Way to shout ‘Eureka!’ while Archimedes is drying himself off!” (The other solution turned out to be bogus.)

Games for Programmers: Black Vienna

2008-07-16T23:27:00.001-04:00

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.

O frabjous day!

My favorite deduction game, Black Vienna, has long been out of print, but now you can give it a try online, thanks to the efforts of Greg Aleknevicus. Go check out Black Vienna Online. It's free and easy to use. The user interface isn't going to win any awards, but it gets the job done. I'm thrilled that this game can now reach a wider audience.

Most deduction games are for two players, but Black Vienna handles three to six players. Your goal is to figure out the members of the infamous “Black Vienna” gang. There are 27 suspect cards, labeled A-Z and Ö. At the beginning of the game, three of these cards are chosen randomly and set aside. Those are the members of the gang.

The remaining 24 suspect cards are dealt out evenly to the players. (With 5 players, one of the players gets only 4 cards.) These are the cards of suspects for whom you can provide alibis.

On your turn you conduct an investigation. There is a pool of available investigation cards, each showing three suspects. You choose one of the available investigation cards and place it in front of another player. That player marks the card with plastic chips, according to how many of the suspects are in her hand. For example, if I have the cards BGMTXY and somebody plays the BQT card on me, I would mark it with two chips (for the B and the T). Other players would then know that I had two of the three suspects, but not necessarily which ones.

The turn then passes to the player who was just investigated.

One nice thing about Black Vienna as a game is that every player is involved on every turn. Even if you are not actively part of the investigation, you still need to update your information with the results of the investigation, and follow any chains of deductions to their conclusions.

Example Deductions

Some deductions are obvious. For example, if I played two chips on the BQT card, and you have the Q card in your hand, then you know that I have the B and the T. Other deductions are less obvious. Here's an actual example from a recent game. Call the other players Caitlin, Monica, Drew, and Dom.

Monica played one chip on GPX, but I had the X, so I knew that she had either G or P (but not both). Similarly, she also played one chip on DHR, but I knew Dom had the R, so Monica had either D or H. Finally, she played two chips on LNV.

Drew played one chip on DVY and zero chips on FÖY, so he had either D or V. Between Drew and Monica, they had at least 4 of the 5 cards DHLNV and at least 5 of the 7 cards DGHLNPV (possibly more if Drew had any of GHLNP).

Meanwhile, I knew all but two of Caitlin's cards. The only possibilities for those last two cards were DGHLNPV. Monica and Drew together had at least 5 of those 7 cards, so Monica, Drew, and Caitlin together must have all 7.

This tells me that none of these 7 cards are in the gang, and none of these 7 cards are in Dom's hand. It also tells me that Drew does not have any of GHLNP.

Finally, I can be more specific about Caitlin's cards. One of her two cards is G or P, and the other is one of DHLNV.

Online Play

The online implementation is asynchronous. You do not need to be logged in at the same time as other players. Instead, the system emails you whenever a turn is taken with the results of the investigation. When it is your turn, you can log on and take your turn at your leisure. This means that a 45-minute face-to-face game can take days or even weeks when played online, but it also means that you can play the game with odd minutes here and there, instead of having to carve out a solid chunk of time. An additional benefit is that it is easy to play with friends in different time zones. For example, I frequently play with friends on the other side of the country.

However, the greatest benefit of the online implementation is that it does away with the greatest weakness of face-to-face play—player errors. Not errors in deductions, which would be your own fault and would only affect you, but errors in answering investigations. If a player carelessly puts out, say, one chip when he should have put out two chips, it ruins the game for everyone. Even if the player notices the error a few turns later and tries to correct it, it's far too late. By then, the other players have already updated their notes with deductions made from the faulty answer, and typically have no way of backing out of those deductions.

If you want to give Black Vienna a try, see the detailed rules of the game and the instructions for the online interface.

Addendum: I've played in several three-player games recently. It's ok with that number, but I think it's significantly better with four or five players. (I haven't tried six yet.) With three players, the deductions are less interesting, and there is a greater chance for one player to get lucky.

Breadth-First Numbering: An Algorithm in Pictures

2008-07-08T23:39:00.001-04:00

I've always enjoyed the mathematical tradition of “proofs without words”, so I wanted to see if something similar could be done with an algorithm. Of course, an algorithm is typically more complicated than a mathematical identity, so it's not surprising that an algorithm typically can't be captured in a single picture. Instead, I've found the idea of a commutative diagram to be a useful pictorial shorthand, where the short way around the diagram gives a high-level view of the operation, and the long way around gives more detail. Here is an attempt to describe my breadth-first numbering algorithm from ICFP 2000 using this idea.

Wanted

Rules

Example

Functional Programming in...Ada?

2008-07-02T20:35:00.017-04:00

Ada is not the first language that comes to mind when you want to do functional programming. (You in the back, stop laughing!) Why, with excellent functional programming languages like Haskell or ML easily available, would I choose to do a functional programming project in Ada? (I CAN STILL HEAR YOU LAUGHING!) Partly because we use Ada in some courses at our institution, and I wanted a library that could help in teaching recursion to novices. But, honestly, mostly I just wanted to see if it could be done.

“It's like this fellow I knew in El Paso. One day, he just took all his clothes off and jumped in a mess of cactus. I asked him that same question, ‘Why?’...He said, ‘It seemed like a good idea at the time.’”
– Steve McQueen, The Magnificent Seven

Somewhat to my surprise, functional programming actually works reasonably well in Ada. You wouldn't want to program a large system this way, but small-scale projects are quite possible, albeit much more verbose than functional programmers are used to.

Instrumenting recursive functions

My application is going to be a library for instrumenting recursive functions. I want to be able to take a recursive function and run it with different combinations of monitors. Each monitor executes a little bit of extra code every time the recursive function is called, including recursive calls. Simple examples of useful monitors include counting the number of calls, or tracking the maximum call depth, or printing trace information on every call or return. More complicated examples include adding memoization to a recursive function or automatically detecting when a function is stuck in an infinite recursion.

Ideally, the library should be easy enough for students to use, but I'll settle for it being easy enough for instructors to use.

Of course, there are many ways to design such a library. I'm going to use a design based on ideas from functional programming. The basic ideas have been folklore in the functional programming community for a long time. For example, I remember doing something similar in SML in the early '90s. Bruce McAdam wrote a nice tech report describing these techniques in great detail. The trick here is going to be figuring out how to implement this design in Ada.

(Incidentally, if anybody has a truly object-oriented approach to solving the same problem, I'd be interested in seeing it.)

Preparing the recursive function

Without some kind of support for reflection, it seems too much to hope that I'll be able to observe the recursive calls inside a recursive function. Therefore, I'm willing to require some modifications to the recursive function, as long as those modifications are fairly straightforward. However, I should only need to modify the function once, rather than every time I run it with a different monitor.

Stealing an idea from functional programming called the Y combinator, I'll modify each recursive function to take an extra argument that is itself a function (or, more specifically, a pointer to a function). The recursive function will call this passed-in function wherever it would normally call itself. The passed-in function will eventually call the recursive function, but may run some other code first.

Here's an example using the ever popular Fibonacci function. The original recursive function might be written

 function Fib(X : Integer) return integer is
 begin
   if X <= 1 then
     return 1;
   else
     return Fib(X-1) + Fib(X-2);
   end if;
 end Fib;

Adding the extra argument and replacing the recursive calls with calls to the passed-in function yields

 function Fib(Rec : access function(X : Integer)
                    return Integer;
              X : Integer) return integer is
 begin
   if X <= 1 then
     return 1;
   else
     return Rec(X-1) + Rec(X-2);
   end if;
 end Fib;

where the changes are shown in red. Note that access function(X : Integer) return Integer is the type of a pointer to a function that takes an integer and returns an integer. In the rest of this post, I'll assume that the functions being instrumented always take an integer and return an integer. If I can get this to work at all, then generalizing this to arbitrary argument and return types will be trivial using Ada's notion of generics.

Running the recursive function

Now, to simply run this function recursively without attaching a monitor, I'll call it with Run, which is responsible for “tying the knot” by somehow making the function call itself. The Run function is written

 function Run(Fun : ...type to be filled in 
                       later...
              X : Integer) return Integer is
   function Rec(X : Integer) return Integer is
   begin
     Fun(Rec'Access, X);
   end Rec;
 begin
   return Rec(X);
 end Run;

Here, Fun is a function like the modified Fib above. Run defines a local helper functon, Rec, that merely passes itself to Fun.

I would call this function by writing something like

   ...Run(Fib'Access, 10)...

where Fib'Access is Ada-speak for a pointer to the Fib function. This calls Rec(10), which calls Fib(Rec'Access,10), which in turn calls Rec(9), which in turn calls Fib(Rec'Access,9), and so on. Eventually, the whole thing returns 89, as expected.

I left out the type of Fun above, because it starts to get unwieldy. I can figure out what this type should be by looking at the type of Fib. The full signature of Run is

 function Run(Fun : access function
                (Rec : access function(X:Integer)
                       return Integer;
                 X : Integer) return Integer;
              X : Integer) return Integer;

A small lie

What I'd really like to be able to do is define a type abbreviation

 type Fun_Type is access function
   (Rec : access function(X:Integer)
          return Integer;
    X : Integer) return Integer;

and then write the signature of Run as

 function Run(Fun : Fun_Type; 
              X : Integer) return Integer;

Unfortunately, I can't. Or rather, I can, but it turns out to be useless. The problem is that Ada is really paranoid about what you do with pointers to functions. In particular, it won't let a pointer to a function match a named type if that function is defined in a deeper lexical scope than the type definition. This restriction does not apply to so-called anonymous access types, so I'm forced to rewrite the entire type everywhere it's used rather than giving it a name and referring to the name.

However, to simplify the presentation, I'm going to pretend that I can use Fun_Type as defined above. Just remember that, in the real implementation, every occurrence of Fun_Type needs to be replaced with the more verbose anonymous type. I'll write Fun_Type in italics as a reminder that it's not the real code.

A simple monitor

Now, here is a simple monitor that counts the number of calls to the recursive function, and prints out that number at the end.

 function Count(Fun : Fun_Type;
                X : Integer) return Integer is

   Num_Calls : Integer := 0;

   function My_Fun
       (Rec : access function(X:Integer) 
              return Integer;
        X : Integer) return Integer is
   begin
     Num_Calls := Num_Calls + 1;
     return Fun(Rec,X);
   end My_Fun;

   Result : Integer := Run(My_Fun'Access,X);
 begin
   Put("Number of calls = ");
   Put(Num_Calls,0);
   New_Line;
   return Result;
 end Count;

Now, when I call

   Put( Count(Fib'Access,10) );

I get

Number of calls = 177
         89

where the first line is printed by the monitor and the second line is printed by the external Put.

The Count monitor creates a new function My_Fun to give to Run. My_Fun simply increments Num_Calls and calls Fun. Now, every time Fun makes a recursive call to Rec, Rec will call My_Fun, which calls Fun.

So basically, Count “wraps” Fun with a little bit of code to increment the Num_Calls variable, and this code gets executed every time the Rec function is called.

In addition, Count does a little bit of work around the top-level recursive call, namely initializing the Num_Calls variable to 0, and printing the number of calls at the end.

A memoization monitor

Here's a more complicated monitor. This one modifies the recursive function to do memoization (first cousin to dynamic programming). The idea is that, when a function is called multiple times on the same arguments, you can save time by remembering those arguments and the corresponding results. Then when the function is called with arguments you have seen before, you can simply return the stored result, instead of recomputing it.

 function Memoize(Fun : Fun_Type; 
                  X : Integer) return Integer is

   Results : array (0..X) OF Integer;
   Ready   : array (0..X) OF Boolean 
               := (others => False);

   function My_Fun
       (Rec : access function(X:Integer) 
              return Integer;
        X : Integer) return Integer is
   begin
     if not Ready(X) then
       Results(X) := Fun(Rec,X);
       Ready(X) := True;
     end if;
     return Results(X);
   end My_Fun;

 begin
   return Run(My_Fun'Access,X);
 end Memoize;

The difference can be dramatic.

   ...Memoize(Fib'Access, 30)...

executes the body of Fib a total of 31 times, whereas

   ...Run(Fib'Access, 30)...

executes the body of Fib almost 2.7 million times (2692537 times, to be exact).

I made an assumption above that, if the original argument was X, then the range of possible arguments in all the calls is 0..X. This is good enough to illustrate the idea, but a more general implementation might be parameterized by the bounds to use, or by a function that calculates those bounds from the original X.

Multiple monitors

How did I know above that Run executes the body of Fib 2692537 times? By running Fib with the Count monitor. How did I know that Memoize executes the body of Fib 31 times? By running Fib with both the Memoize and Count monitors together.

Except that, as currently written, the Memoize and Count monitors can't be used together. I can run Fib with one or the other, but not both simultaneously.

What I want is a way to layer one monitor on top of another, building arbitrary stacks of monitors. The clues to how to do this are already in the current implementations of Memoize and Count.

Notice that both Memoize and Count have the same interface as Run. In other words, a monitor is an alternative run function that adds some extra machinery to the basic Run. Further, notice that both Memoize and Count build a My_Fun function by wrapping some extra code around Fun and then run My_Fun using the Run function. The key insight is that we can parameterize Memoize and Count by which run function to use for running My_Fun. That might be the basic Run function, but it might also be a run function corresponding to a different monitor.

To achieve this parameterization, I'll use generics instead of passing function pointers. The existing definitions of Memoize and Count will still work, but they need to be preceded by additional code to take a run function as a generic parameter. For example,

 generic
   with function Run(Fun : Fun_Type; 
                     X : Integer) return Integer;
 function Count(Fun : Fun_Type; 
                X : Integer) return Integer;

 function Count(Fun : Fun_Type; 
                X : Integer) return Integer is
   ...
     ... Run(My_Fun'Access, X);
   ...

The new parts are in red. I didn't change the existing code of Count at all, but now the call to Run in the body of Count refers to the run function passed in as a generic parameter.

Using a monitor is now a two-stage process, first instantiating the generic function to create the desired run function, and then calling that run function. For example,

 function C_Run is new Count(Run);
 function MC_Run is new Memoize(C_Run);

 ...MC_Run(Fib'Access, 30)...

Notice that the basic Run function is always used in the first instantiation, where it serves as the base of the stack of monitors.

But wait! Something strange is happening here. This program displays 59 calls, not 31 calls as expected. However, if we layer the monitors in the opposite order

 function M_Run is new Memoize(Run);
 function CM_Run is new Count(M_Run);

 ...MC_Run(Fib'Access, 30)...

then we get the 31 calls.

It's really a question of when the memoization code checks for a repeated argument relative to when the counting code increments the counter. If the memoization check happens before the increment, we get 31 calls. If the memoization check happens after the increment, we get 59 calls. Either way, the body of the original Fib function is only executed 31 times.

And that's it, really. There's still a lot of grunt work involved in fleshing out a complete, robust library, but all the important design decisions have already been made. Implementing a wide variety of monitors is fairly easy using Count and Memoize as templates.

Generics vs function pointers

One aspect of this design deserves a little more discussion. I'm mixing two different styles of passing functions as arguments, using generics in some places and function pointers in other places. Why not just use one style consistently? Because the two styles of passing around functions have different strengths and weaknesses.

One major difference is that generics work much better than function pointers when you want to return a function. For example, the generic Count monitor takes a run function and returns a run function. It's easy to imagine writing Count as

 function Count(Run : Run_Type) 
                return Run_Type is ...

where Run_Type is the appropriate access function type. But, in practice, this doesn't work because Ada lacks closures. The natural way to write this would be

 function Count(Run : Run_Type) return Run_Type is

   function My_Run(Fun : Fun_Type; 
                   X : Integer) return Integer is
     ...

 begin
   return My_Run'Access;
 end Count;

but you can't return My_Run'Access because My_Run goes away as soon as Count returns.

Note that it is possible to get around this restriction against returning function pointers by re-writing strategic code fragments in continuation-passing style, so that the function pointers in question can be passed to a continuation instead of returned. This works fine on a small scale, but quickly blows the runtime stack when attempted on a large scale.

A second major difference is that it is easier to write third-order (or even higher-order) functions using function pointers than using generics. A first-order function takes an ordinary value as an argument. A second-order function takes a first-order function as an argument. A third-order function takes a second-order function as an argument, and so on. Now, consider a monitor like Count. Count takes a Run function, which takes a Fun function, which takes a Rec function, so Count is fourth-order!

Currently, I pass the Run functions using generics, but the Fun functions using function pointers. (Ignore the Rec functions for now.) Suppose I wanted to pass both Run functions and Fun functions using generics. This would mean that each Run function would take its Fun function as a generic parameter. But that means that, when we pass a Run function to a monitor like Count, we need to pass it as a generic function. In other words, Count would need to be a generic function that takes a generic function as an argument. That's not allowed in Ada. Or, more truthfully, it is sometimes allowed, but it's extremely painful.

In Ada, a generic function can neither take a generic function as an argument nor return a generic function as a result. However, a package can contain generic components, so you can sometimes fake it wrapping the argument or result in a package. For example, you can fake a generic function that returns a generic function by writing a generic package that contains a generic function as a component.

In a limited way, you can do the same thing in the other direction. If you want a generic function to take a generic function as an argument, you can fake it by wrapping the argument in a package, so that the outer generic function takes a package (which contains a generic function as a component). The catch is that you can't instantiate the outer generic function with just any old package meeting a certain specification, but only with packages that are themselves instantiations of a single generic package. Making all that work is an exercise in pain that I leave to the most masochistic of readers.

No Applause, Please

2008-06-04T10:41:00.000-04:00

My school recently had its graduation. This year's graduating seniors (the computer science majors, anyway) are particularly memorable for me. For one thing, I had more success than usual in luring them into playing board games, especially Race for the Galaxy, Attika, RoboRally, and Ricochet Robots.

However, this group also stood out for a classroom behavior that I'm not used to—applause.

It started in Algorithms. In this course, when a homework is due, I usually have several students present their solutions. If the student solutions have not illustrated a point that I wanted to make, I will then present my solution, which is usually more elegant, and sometimes significantly more efficient as well. My goal in doing this is not to show them up, or to say “hey, dummy, this is what you should have written”, but rather to help them catch a glimpse of the beauty I see in an elegant algorithm, to inspire them with what is possible. (I do worry sometimes that fragile personalities might find the experience demoralizing, rather than inspiring.)

Last year, after presenting such a solution, I was very surprised when one particular student started clapping. He continued to do this in future weeks, and eventually pressured other students into joining him.

At first, I was taken aback, but over time, I got more and more frustrated. It felt like the applause was saying “this is so far beyond me that I could never hope to match it”, whereas I was hoping for a reaction more like “this may be beyond me right now, but, by golly, if I work at it, I'll be able to do that someday”. Eventually, I snapped, “C'mon, I'm not trying to impress you with my brilliance. I want you to impress me with your brilliance!”

A Story About Odd and Even Numbers

2008-05-23T13:26:00.000-04:00

This is a story my son and I wrote together when he was four. He came up with the basic story. I helped with the English and with the turtle character.

The Seven Jellybeans

Once upon a time, there was a lizard and a snake who were friends. They played together and had fun everyday until one day, the lizard's daddy gave them a bag of jellybeans to share.

In the bag, there were seven jellybeans. The lizard divided the jellybeans into two piles. His pile had 5 jellybeans, and the snake's pile had 2 jellybeans.

The snake said, “Wait a minute. That's not fair. You have more jellybeans than I do. You'd better give me one more jellybean.”

So the lizard gave the snake one more jellybean. And now the lizard had 4 jellybeans, and the snake had 3 jellybeans. The snake said, “Hey, that's still not fair. You still have more jellybeans than I do. You'd better give me one more jellybean.”

So the lizard gave the snake one more jellybean. And now the lizard had 3 jellybeans, and the snake had 4 jellybeans. Now the snake was happy, but the lizard said, “Hey, that's not fair. Now you have more jellybeans than I do. You'd better give me back one jellybean.”

So the snake gave the lizard back one jellybean. And now the lizard had 4 jellybeans, and the snake had 3 jellybeans. The snake said, “Hey, what happened? Now you have more jellybeans again. You must have cheated!”

And then the lizard and the snake began to fight.

While they were fighting, their friend the turtle walked by. He asked them why they were fighting, and the lizard and the snake told him.

“Hmm,” said the turtle. “If I solve your problem, will you give me one jellybean?”

The lizard and the snake didn't want to share their jellybeans, but they didn't want to fight either, so they agreed.

The turtle slowly ate one jellybean. Then he turned around and began to walk away.

“Wait a minute,"” shouted the lizard and the snake together. “You said that if we gave you one jellybean, you would solve our problem.”

“I just did,” said the turtle as he continued to walk away.

The lizard and the snake looked at their piles of jellybeans. The lizard had 3 jellybeans and the snake had 3 jellybeans. They happily ate their jellybeans, and soon all of the jellybeans disappeared.

The next day, the snake's mommy gave them a box of raisins to share. The lizard and the snake opened the box and counted seven raisins. “Oh no,” they said, and they went to look for the turtle to give him one of their raisins.

Designing a Data Structure

2008-05-20T11:44:00.000-04:00

Students are rarely given an opportunity to design an algorithmically non-trivial data structure. We might give them a scenario and ask them to design how to represent the data, but that design decision is usually something like choosing between a hash table or an array or a linked-structure. Once that high level decision is made, there is very little left to design.

One reason for this is that many data structures depend on non-obvious invariants. Most students are pretty shaky on the whole idea of invariants to begin with; they're never going to spontaneously come up with something like the rules describing red-black trees or leftist heaps. With these kinds of data structures, we basically present the finished product and possibly ask them to implement and/or analyze the data structure, but we never ask them to design something like that.

For several years, I've been trying to give students a taste of real data structure design, using the sample priority queue below. I usually do this in class, where I can help steer them with gentle questioning, but I try very hard to make sure that they come up with the important parts.

I always do this at some point after the students have studied binary heaps (the kind typically used in heapsort). I briefly review the priority queue operations binary heaps support (insert, findMin, and deleteMin) and the basic idea of heap-ordered trees. Then, I introduce the idea of merging two heaps. With binary heaps, this takes O(N) time, or even O(N log N) time, if done naively. I ask them to design a new data structure to support merging in O(log n) time, while the other priority queue operations run in the same bounds as for binary heaps, O(1) for findMin and O(log N) for insert and deleteMin. I suggest that they use heap-ordered binary trees (real trees, rather than simulating trees using arrays like in binary heaps), but that they can modify these trees in any way that is helpful.

With heap-ordered trees, findMin is trivial—it just returns the root. To get their creative juices flowing, I then ask them to implement insert and deleteMin in terms of merge. This is also pretty easy: insert creates a new singleton tree and calls merge; deleteMin discards the root and calls merge on the two children of the root. So the whole problem boils down to merging two trees efficiently.

At this point, they usually flounder for a while, which is both ok and expected. Some floundering is good. Naturally, they'll start to get a little frustrated. That, too, is ok and expected. I just don't want them to get frustrated to the point where they shut down. If the floundering continues too long without any progress, I'll ask them what they can tell immediately about the result tree by only looking at the roots of the input trees. They'll quickly reply that the smaller of the two input roots becomes the root of the result tree. So I have them draw that much of the result. Depending on how things are going, I may further suggest that they draw two question marks for the children of the root in the result tree.

Then the students will play for a while with how to fill in those question marks. There are two slots for subtrees, but we have three subtrees that need to go in those slots: the two subtrees of the “winning” input root plus the “losing” input root. To fit three subtrees into two slots, naturally we need to merge two of them and leave one unchanged. But which two should be merged?

Usually, the students will begin with some fixed strategy, such as always merge the two subtrees of the winning root. But it's easy to come up with counter-examples where such a strategy will take O(N) time.

Once it becomes clear that some smarter strategy is required, the students focus on the question of which two of the three subtrees to merge. Usually the next thing they try is merging the two subtrees with the smallest roots, which fails on the same kinds of counterexamples as before.

Eventually, based on the intuition that merge should run faster on small trees than on big trees, they try merging the two smallest trees. This is always a good learning point about ambiguity, as we realize that there are three different possible meanings of “smallest”: the smallest root according to the ordering on keys, the smallest subtree according to number of nodes, or the smallest subtree according to the height of the subtrees. We've already shot down the first one, but either of the other two will work, so I just go with whichever one the class prefers (usually smallest in number of nodes).

One catch is that to efficiently compare sizes of subtrees (either number of nodes or height), we need to store the sizes at every node. But that's easy to do by adding an extra field, and maintaining that size information is also easy, albeit slightly easier for number of nodes than for height.

Typically, we don't have a lot of time left in class at this point, so I help them with the analysis, but it's easy to show that this design supports merge in O(log N) time. And there was much rejoicing!

I call this data structure maxiphobic heaps because of the way merge avoids the biggest subtree at every step. But I don't tell the students that name until after they've already come up with the design.

On Balanced Trees and Car Insurance

2008-05-13T23:42:00.001-04:00

I usually don't teach our Data Structures course, but I often give a guest lecture about balanced binary search trees. This comes right after they've learned about plain (unbalanced) binary search trees. Often the previous lesson has ended with an illustration of what happens when values are inserted into the tree in sorted order.

After reviewing that pathological case and how it can easily arise in practice, I dive in and explain how to keep the trees balanced. In my case, I use red-black trees, but the exact choice of balancing scheme isn't critical to my point here. At the end of class, I ask them how much faster they think the balanced trees are than the unbalanced trees. They're shocked when I tell them that, most of the time, the balanced trees are slower than the unbalanced trees. As long as the data arrives in a reasonably random order, the plain binary search trees will actually end up being fairly balanced, without doing any extra work. No mucking around with colors, no rotations—of course the balanced trees are slower!

So why bother?

I tell them that it's like buying car insurance. When you buy car insurance, you hope that you're just throwing your money away. At the end of the year, if you haven't been in any accidents, you're happy to have wasted that money. Why bother? To protect against the uncommon case, to keep one unlucky event from turning into catastrophe. You pay a little bit extra all the time to keep from paying a lot extra every once in a while.

Barriers to Creativity

2008-05-09T10:21:00.001-04:00

Last week, I had lunch with some friends of mine, all college-level instructors. I brought up the subject of creativity, which has been much on my mind lately. Our discussion highlighted some of the barriers to creativity in education, especially from the side of the instructor.

Creativity means artsy, doesn't it?

At one point, I asked the chemistry professor in our group about the role of creativity in the first few college-level chemistry courses. She was confused by the question at first, because she thought I meant something like writing poems about chemical reactions. (That reminds me of a scene in Lois McMaster Bujold's A Civil Campaign, in which a biochemist decides to rewrite the abstract to his dissertation in sonnet form. “Can you think of a word to rhyme with glyoxylate?”)

Actually, I meant creativity in the sense of creative problem solving. You know, the kind of thing MacGyver might do with 2 aspirins, a tube of superglue, and a Diet Coke. This misconception that creativity is the exclusive property of the arts is quite common. If we the instructors of techncial courses don't think of what we do as creative, then we are hardly likely to portray our discipline in a way that encourages creativity.

I'm using the word “arts” here to mean traditional arts like painting or poetry or music. I happen to think an elegant algorithm can be quite beautiful and artistic, but I don't expect a layperson to recognize it as art.

Foundations, Foundations, Foundations

A common theme in instructor comments was that students need to learn the foundations and basic skills of the discipline before they can do much that's creative. There's certainly some truth to this. But how long of an apprenticeship can we expect somebody to serve before finally exposing them to the beauty and wonder, the fun of the creative side? Do we save up all the creative parts for a senior-level capstone course (or even later), or can we intersperse skill development with appropriately-scaled opportunities to use those skills creatively?

A favorite movie of many teachers is The Karate Kid, especially the part where Mr. Miyagi teaches Daniel karate by having him do household chores such as waxing cars or painting fences. Eventually Daniel rebels at what he sees as pointless menial labor, and Mr. Miyagi demonstrates that Daniel has been learning valuable defensive moves all along. The point teachers usually draw from this example is that students can learn valuable lessons without realizing that they are learning, but there's another point here as well. What if, instead of confronting Mr. Miyagi, Daniel simply quit coming to his lessons? That's the situation we face as college teachers. If we give students too much skills development up front without any hint of a payoff, they'll simply stop taking our courses and never come back.

There's another danger as well. I saw this among my fellow students in graduate school. Students who had spent their entire undergraduate careers very successfully learning foundations and practicing skills were often lost when they were finally expected to do creative research. It was completely different from what they were used to, and often they found that they didn't like it.

Think of a piano teacher who makes her students practice nothing but scales for four years. By the time she feels her students are finally ready to play real music, she may find that the only students she has left are the ones who would rather play scales than anything else.

But...it's hard!

Incorporating creativity into a college classroom can be hard, especially in large classes. The lecture format is particularly bad at nurturing creativity in the listeners, but a teacher facing several hundred students often has little choice.

Grading also becomes substantially more difficult if you design assignments that allow students room for creativity. Suddenly, there's no longer a single, “approved” solution that can be easily checked for. Instead, you need judgement to evaluate quite different solutions individually. This can be especially difficult in a course where TAs are expected to do most of the grading.

Fortunately, I suppose, I don't have large class sizes and I don't have any TAs, so I don't have those excuses to fall back on.

Beware Pseudo-Arrays

2008-05-02T14:29:00.000-04:00

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

2008-04-17T08:41:00.000-04:00

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

2008-04-14T10:50:00.000-04:00

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

2008-04-08T23:33:00.001-04:00

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

2008-04-04T00:18:00.001-04:00

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 (c₁ c₂ ... c₇)
       = R (c₁ c₂ ... c₆) c c₇
       = R (c₁ c₂ ... c₅) R c₆ c c₇
       = R (c₁ c₂ ... c₄) R c₅ R c₆ c c₇
       ...
       = R c₁ R c₂ R c₃ R c₄ R c₅ R c₆ c c₇

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:

   c₁ c₂ c₃ (d₁ d₂ d₃)
      = F (c₁ c₂) (d₁ d₂) c₃ d₃
      = R c₁ F c₂ (d₁ d₂) c₃ d₃
      = F (R c₁ F) d₁ c₂ d₂ c₃ d₃
      = R (R c₁) F F d₁ c₂ d₂ c₃ d₃
      = R R R c₁ F F d₁ c₂ d₂ c₃ d₃

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

2008-03-28T12:15:00.001-04:00

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

2008-03-19T15:29:00.001-04:00

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.

Games for Programmers: Schotten Totten/Battle Line

2008-03-11T09:37:00.000-04:00

The next in an irregular series of board game (or, in this case, card 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.

In programming, the specifications you thought you were implementing are practically guaranteed to change by the time you're done. Unless you have the power to “just say no” to the changes, the best approach is often to stay flexible by delaying commitments for as long as possible. You try to keep your options open by putting off irreversible decisions to the last possble moment. Schotten Totten (by noted game designer Reiner Knizia) elegantly captures this feeling in a short, two-player card game.

Schotten Totten is nominally about two Scottish clans squabbling over territory. Nine boundary stones are placed between you and your opponent, in a line from left to right. You win by being the first to claim either three adjacent stones or five stones altogether. To claim a stone, you must play a better three-card group on your side of the stone than your opponent does.

(photo by Scott Alden)

There are a total of 54 cards, numbered 1-9 in six different colors. Three-card groups are ranked as follows, from best to worst: straight flush (three consecutive numbers of the same color), three-of-a-kind (three of the same number), flush (three of the same color), straight (three consecutive numbers), “wild rabble” (anything else). If both players play the same kind of group, then each player adds their cards together and the player with the higher sum wins. If there is still a tie, the player who completed their group first wins.

You start the game with six cards. Each turn you play a single card on your side of one of the stones, and then draw a replacement card. (For beginners, the play-then-draw order can be a little confusing because most players are more accustomed to draw-then-play.) Towards the end of the game, if there are no more cards to draw, then you simply skip that step.

Once you have played a card on a stone, you're stuck with it. There is no way to take it back or replace it or cover it up. Most of the time you will not have all the cards that you want when you start playing a particular three-card group. The tension in the game comes from trying to avoid commiting to a particular kind of group for as long as possible. For example, suppose you've played the blue 6 on a stone, and now you have the blue 5 and the red 6 in your hand. If you play the blue 5 next, then you are commiting to trying for a straight flush. If you play the red 6 next, then you are commiting to trying for three-of-a-kind. The straight flush is stronger, but there are only two other cards in the deck that will complete the straight flush (the blue 4 or the blue 7). On the other hand, there are four other 6's in the deck, so you have a better chance of completing the three-of-a-kind. What you will probably do is delay playing on this stone by playing somewhere else, but that just means making a commitment there instead of here. If you do play on this stone, be prepared for the frustration of drawing exactly the card you needed for the group that you just ruled out!

(Technically, if you play the blue 5 on the blue 6, you are not commiting to trying for a straight flush. Any other blue will complete a flush, and any 4 or 7 will complete a straight. However, you almost never want a plain flush or a plain straight until close to the end of the game, because they are just too easy to beat.)

Each stone is awarded when both three-card groups are complete. However, there is a twist here that may appeal to programmers, who tend to excel at logical thinking. You can also claim a stone early if you can prove that your opponent can't beat your hand. For example, suppose you have three 7's on your side of a stone, and your opponent has the green 1 and the green 2 on his side. If the green 3 has already been played somewhere else, then there is no way your opponent can complete the straight flush. The best he could do would be a plain flush, which would lose to your 7's. Therefore, you can claim the stone without waiting for him to complete his group.

Note that the proof must be accomplished with cards that have already been played. In the above example, if you were holding the green 3, you could not claim the stone until you played it. Sometimes this means that you will play a card in a place where you would prefer not to, just to be able to claim a stone elsewhere.

Claiming stones early is important for two reasons. First, there are situations where both players can fulfill the victory conditions, so it is just a matter of who claims the stones first. For example, both players might be able to get three adjacent stones, or one might be able to get three adjacent stones while the other can get five stones altogether.

Second, and getting back to the theme of this recommendation, claiming a stone early helps you keep the pressure on your opponent. Once a stone has been claimed, neither player can play cards on that stone anymore, even if they have room to do so. You never want to give your opponent an easy place to dump a card. Not only does that let them rid themselves of a useless card—when you can only hold six cards at a time, freeing up an otherwise useless slot is huge—but more importantly it lets them avoid making a commitment someplace else.

How to get it

Schotten Totten can be hard to find in stores. Fortunately, its sister game, Battle Line is much more widely available. Battle Line is almost the same game, but with different artwork, with cards numbered 1-10 instead of 1-9, and with 7 cards per hand instead of 6. Also, Battle Line adds a separate mini-deck of so-called tactics cards, which let you change the rules in various ways. For example, one tactics card forces you to play 4 cards on each side of a particular stone instead of 3. (Actually, newer editions of Schotten Totten include the tactics cards as well.)

Personally, I like Schotten Totten better. I prefer the smaller, more claustrophobic scale. Also, I prefer the game without the tactices cards, which make the game too chaotic. Fortunately, if you get Battle Line you can experiment with or without the tactics cards, with our without the 10's, and with 7-card or 6-card hands, to see which way you like it better.

A good place to look for both games is BoardGamePrices.com, which summarizes prices and availability at a host of on-line game retailers.

If you want to try the game out before buying it, there are excellent implementations of Schotten Totten at both flexgames and Yucata.de. (The latter site defaults to German but can be set to English by clicking on the flag.)

Get the job done, but what is the job?

2008-03-06T20:57:00.000-05:00

One of my most memorable conversations with a student happened a few years ago. I was grading a programming project, and something in one of the project documents struck me. At our school, students are required to document help from other students in some detail. One pair described getting help from another student, call him K. Apparently, K was telling them how to do something, but they weren't understanding him fast enough. He got impatient, grabbed the keyboard, and starting typing in the code for them.

I was flabbergasted by this description. How could K have possibly believed that this was appropriate? I knew the class that he was just about to get out of, so I met him there and took him into an empty classroom.

For at least five minutes, we talked completely past each other. He didn't understand why I was upset, and I didn't understand why he seemed to believe he had done a genuinely good thing. Obviously, there were some unspoken assumptions on both sides that were preventing us from communicating.

Eventually, I realized what was going on. He had been taught that the bottom line was getting the job done. That was the most important thing, and he believed that what we teachers wanted from students was for them to get the job done. Helping his buddies get the job done was, in his eyes, no less than the responsible thing to have done, a positive act of virtue.

Aha! With this realization, and with his phrase of “getting the job done”, I finally had the wedge I needed to get through to him.

“What was the job on this project?”, I asked him.

“To complete a working program”, he replied.

“No, it wasn't”, I said. Utter confusion covered his face. “Think about it. I already have a solution to this project. Why would I need a dozen student implementations? I'm pretty sure that mine is going to be less buggy, faster, and better documented than any of yours.”

“But...” The first signs of doubt.

“So, if I don't really care about your implementations, then why did I have you all do this project? What do I care about? What was the job?”

K frowned in concentration. It's never an easy thing when somebody tries to dismantle your basic assumptions. To his credit, he didn't just shut down, but actively struggled to understand what I was saying. He started to speak and stopped a few times. He was almost there, but couldn't quite articulate it.

“Learning”, I finally said. “The job was learning. The implementation was only a way to trigger that learning. But the implementation doesn't really matter, it's the learning that I care about.”

He got it. He understood why, from my point of view, typing in code for the other students was not helping them get the job done, but instead was actively hindering the learning that was the real job.

As we wound down, he mentioned a different teacher he had had the previous two semesters. The other teacher had a grading policy where you get credit for an assignment only when it is completely correct. If your assignment has flaws, then you redo it until it's correct, losing points with each resubmission. For somebody like K, who strongly believes in getting the job done, this policy just reinforces the idea that finishing the program is the job. I know this wasn't the other teacher's intent, but I can certainly see how it could be taken that way.

What the heck is a math trade?

2008-03-01T22:48:00.001-05:00

Many sites exist for trading objects or services of various kinds—my favorite example is a site for trading right or left shoes. Over on BoardGameGeek, there is a very active community of users who trade board games. The site lets you list games that you are offering and games that you want, and then automatically finds possible matches. Even with this support, however, finding and negotiating individual trades can be tedious. Enter Math Trades, which have been running regularly on BoardGameGeek for several years.

One frequent difficulty with individual trades is that, although you have something I want, I might not have what you want. What if we were able to get a third person involved? Suppose you have what I want, Tina has what you want, and I have what Tina wants. Then we can arrange a three-person swap. SwapTree is a site that will find such three-way and even four-way trades for you automatically.

But why stop there? Why not look for five-way loops, or even hundred-way loops? That's what happens in a Math Trade.

How a math trade works

First, a moderator announces the opening of the trade and lays down trade-specific ground rules. Everybody who is interested in participating lists the items they choose to offer in the trade. At a pre-determined time, the list closes to new entries.

Next, the participants review all the offers and decide which ones they want. For each item you are offering, you create a wantlist that says, in essence, “I would be willing to trade item 57 (my item), for item 22 or item 34 or item 119 or item 576.” Everybody sends their wantlists to the moderator by the announced deadline.

After a brief period for finding and correcting errors, the moderator runs special math trade software to find the most trades possible. The moderator then publishes the results, the participants exchange addresses, and drop their items in the mail.

A lot of trades

Note that the “most trades possible” can be quite a lot. The largest math trade to date involved 2320 items, of which 994 traded. These 994 items were broken into 7 trade loops, including one monstrous loop of 920 items. Just imagine standing in a circle with 919 of your closest friends and everyone handing their game to the person on their right!

(Actually, this trade involved 316 users, many of whom were trading multiple items. So that loop of 920 items wasn't really 920 people.)

Although math trades have been run regularly on BoardGameGeek for almost three years, it is only recently that trades of this size have become possible. About six months ago, I wrote TradeMaximizer, which has become the de facto standard software for math trades. TradeMaximizer improves on previous software by guaranteeing to find the maximum number of trades possible, and by doing so quickly, in under a minute for the large trade above and in just a few seconds for most trades. Previous software ran in hours or days, and even then might not find all the trades possible. I'll describe TradeMaximizer in detail in an upcoming post.

Beyond games

There's nothing specific to games in the idea of math trades or in TradeMaximizer. I know of math trades run for metal CDs (using earlier software) and for geocoins (using TradeMaximizer). If you have run a math trade in another community, or think you might like to, please post a comment here and let us know. Don't be afraid! They're easy to run if you keep it relatively small, and a lot of fun.

Probably the coolest application of math trades is for trading...kidneys!

No, this isn't some urban legend about waking up in an ice-filled bathtub. This is serious, life-or-death stuff.

When somebody needs a kidney transplant, they can often find a family member or friend who is willing to donate one. But what happens if the donor's kidney is biochemically incompatible with the intended recipient? Well, sometimes you can find two such donor-recipient pairs where each donor is compatible with the other recipient. By donating to the other recipient, each donor ensures that their intended recipient gets a compatible kidney. Three-way trades and four-way trades are also possible. Unlike ordinary math trades, however, larger loops are not supported. Oh, you can find the loops, but doctors won't perform the surgeries because the risks of something going wrong (such as somebody backing out at the last minute) are just too great.

A trio at CMU implemented a system that is now being used to find matches in a national list of donors every two weeks by the Alliance for Paired Donation. Their system differs from an ordinary BoardGameGeek-style math trade in two fundamental ways. One is the deliberate limit on the sizes of trade loops (which actually makes the problem harder, not easier). The other is the presence of altruistic donors—donors who give their kidneys to strangers without asking for a kidney for a friend or loved one in return.

In praise of mandatory indentation for novice programmers

2008-02-25T12:55:00.003-05:00

About four years ago, I created my own programming language for teaching. I'll probably write more about this language at some other time, but for now I want to focus on one feature of the language: the use of mandatory indentation. My experience with this aspect of the language has been so overwhelmingly positive that I will never again voluntarily use a language without mandatory indentation for teaching novice programmers.

Of course, sometimes the choice of language is not under my control. Even when it is, there are always many different factors that go into that choice. But no other single factor I've run across has greater significance. For example, programming language afficionados spend endless hours arguing about static vs dynamic typing, or functional vs object-oriented languages, or strict vs lazy evaluation, or...you get the idea. Those differences can indeed be important, but more so for experienced programmers working on large projects than for novice programmers working on classroom projects. None of these differences individually comes close to the issue of indentation.

I say this with some pain, because I'm a programming languages guy myself. I've taken part in some of those arguments, and spent many hours contemplating the relative merits of many much deeper programming language properites. It hurts me to say that something so shallow as requiring a few extra spaces can have a bigger effect than, say, Hindley-Milner type inference. I wish it weren't so, but that is what my classroom experience tells me, loudly and unambiguously.

Why not mandatory indentation?

The vast majority of languages don't make indentation mandatory. Instead, they usually use explicit syntax to indicate block structure, such as { and }, or BEGIN and END. Yet, if you look at well-written programs in those languages, they are almost always indented sensibly. Furthermore, there's remarkably little disagreement as to what “sensible” indentation looks like. So why not make that sensible indentation mandatory? There are several reasons that are often put forth:

It's weird. Because the vast majority of languages don't use it, most programmers aren't used to the idea. Therefore, there's an initial sense of unease.
It messes up the scanner/parser. True, mandatory indentation is harder to deal with using traditional scanners and parsers based strictly on regular expressions and context-free grammars, respectively. But it's usually trivial to modify the scanner to keep track of indentation and issue an INDENT token when indentation increases, and one or more OUTDENT tokens when indentation decreases. The parser can then treat these tokens just like normal BEGIN/END keywords. In this approach the scanner is no longer based strictly on regular expressions, but most scanners aren't anyway (for example, when dealing with nested comments). Using the INDENT/OUTDENT tokens, the parser can still be based strictly on context-free grammars.
Don't try to take away my freedom! Programmers are a pretty libertarian bunch. Anytime somebody tries to impose rules that they follow 99% of the time anyway, they always focus on the 1% exceptions. For indentation, these exceptions often involve what to do with lines that are too long. So yeah, a language with mandatory indentation shoud deal gracefully with that issue. Or sometimes the exceptions involve code that is nested 20 levels deep. But these cases are almost always easy to rewrite into an equivalent but shallower structure. One place where I tend to deliberately break indentation rules is with temporary debugging output. I often leave such print statements unindented, so that they're easier to find when it's time to take them out. This is convenient, but I can certainly live without it.
I don't want people to be able to read my code! Maybe some people view obfuscated code as job security. As a different example, the former champion in the TopCoder programming contest, John Dethridge, was famous for never indenting. Why? Because in TopCoder, there is a “challenge” phase, where other competitors look at your code and try to find bugs. So there's an incentive to make your code hard for other competitors to understand. I remember teasing him about this once, and he said laughingly “Beware my left-justified fury!” I replied that I'd be more afraid if his fury was right justified.
It doesn't scale. As programs get bigger, both in lines of code and in number of programmers, you run into more mismatches in indentation. For example, you might want to move or copy a loop that was nested 5 levels deep to another location nested 3 levels deep. Or you might need to integrate code written by programmers that used different numbers of spaces per indentation level. Refactoring tools can certainly help here. But, you know, if you're the sort of programmer who would leave the indentation messed up when you moved that loop, just because your language didn't require you to fix it, then I probably don't want to work with you anyway.

What about novices?

Most of the objections above don't really apply to novices. Programming is new to them so it's all weird anyway. They have no idea what scanners and parsers are. As teachers, we already take away a lot of their freedoms anyway, and we certainly want them to care if somebody (namely us!) can read their code. And novices are usually not going to be writing large enough programs for the scaling issues to be a big problem.

Ok, but what are the benefits for novices?

They are already used to the idea of indentation. Both from writing outlines in English class and from nested bullet lists in the (almost) ubiquitous PowerPoint, novices already have experience with the idea of indicating grouping using indentation. This makes such languages much easier for novices to learn. In contrast, explicit markers such as curly braces or BEGIN/END keywords are something novices have much less experience with. However natural such markers might seem to us, they are not natural for novices, and are a constant source of mistakes. (Worse, a typical novice strategy for dealing with those mistakes is to randomly insert or delete braces until it compiles—a strategy Peter Lee used to call “programming by random perturbation”.)
Less is more. Or, put another way, smaller is better. To the novice, a fifteen-line program is less intimidating than a twenty-line program, a program that fits on one page is much easier to understand than a program that spans multiple pages. Those extra lines taken up by explict braces or BEGIN/END keywords really add up. Even if you use a style that puts a { at the end of the previous line, the } still usually goes on a line by itself. I shudder now everytime I look at a Java program and see a code fragment like
```
             ...
             }
           }
         }
       }
     }
   }
```
Note that I am not advocating compressing everything into as few lines as possible (a la Perl Golf). Nor am I saying that all redundancy is bad. But in this case, the redundancy of explicit markers was hurting more than it was helping.
Mandatory indentation promotes good habits. I've taught plenty of novices in languages that did not require indentation. If the language doesn't require it, they won't do it, or at least not consistently. If they are using an IDE that indents for them, fine, but sometimes they need to write code in a primitive editor like Notepad, and then they just won't bother. Even if I require the final submission to be properly indented, all too often they will do all their development without indentation, and then indent the code just before turning it in (kind of like the typical novice approach to commenting). Of course, indenting after the fact means that they don't get any of the benefits from indenting their code, such as making debugging easier.
On the other hand, if the language makes indentation mandatory, then the novice needs to keep their indentation up to date during the entire development cycle, so they will reap those benefits. Since I started using this language, I've also noticed improved indentation habits even when students switch to other languages without mandatory indentation. I can at least hope that this habit is permanent, although I have no evidence to back that up.

A surprise

I was shocked by how much the mandatory indentation seemed to help my students. I did not come into this expecting much of a change at all. I had experience with mandatory indentation in a couple of languages (most notably Haskell), and I had found it to be a pleasant way to code. Also, I had heard good things about people using Python in the classroom. However, I was by no means a convert at the time that I was designing my language.

I had two motivations for making indentation mandatory in the language. First, this language was designed to be the second language most of the students saw, and I wanted to expose them to a range of language ideas that they had not seen before. For example, their first language used static typing so I made my language use dynamic typing. Similarly, their first language did not make indentation mandatory, so I took the opposite route in my language. My second motivation was simply that I was annoyed. I was tired of students coming to me with code what was either completely unindented or, worse, randomly indented. I figured that making the compiler enforce indentation was the surest way to stop this.

Imagine my surprise when I started teaching this language and found the students picking it up faster than any language I had ever taught before. As fond as I am of the language, I'm certainly under no illusions that it's the ultimate teaching language. After carefully watching the kinds of mistakes the students were and were not making, I gradually realized that the mandatory indentation was the key to why they were doing better. This seemed to manifest itself to two ways, one obvious and one more subtle. The obvious way was that they were simply spending much less time fighting the syntax.

The more subtle way was that they appeared to be finding it easier to hold short code fragments in their head and figure out exactly what the fragment was doing. I conjecture that there may be some kind of seven-plus-or-minus-two phenomenon going on here, where adding extra lines to a code fragment in the form of explicit braces or BEGIN/END keywords pushes the code fragment above some size limit of what novices can hold in their heads. This wouldn't affect expert programmers as much, because they see beneath the braces to the chunks underneath, but novices live at the level of syntax.

Whatever the explanation, I'm now a convert to the power of mandatory indentation for novices. I've never taught Python, but I suspect those who have may have had similar experiences. If so, I'd love to hear from you.

Games for Programmers: Zendo

2008-02-14T11:08:00.002-05:00

In addition to teaching and programming, I also enjoy playing board games. This is the first in an irregular series of 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.

Zendo is a game about debugging. Ok, it's not really about debugging, but you'll see what I mean in a moment.

Zendo is a logic game played with a bunch of Icehouse pieces (plastic pyramids in several different colors and sizes) and some markers.

(photo by Terraliptar)

During the game, pyramids will be placed in groups (called “koans”) that either satisfy or don't satisfy some secret rule. The players try to figure out the rule based on these examples. For example, consider the following group:

(photo by Ted Alspach)

This group might satisfy the rule “at least one piece off the table” or “exactly one tilted piece” or “fewer than two green pieces” or “contains pieces of three different sizes”. It would not satisfy the rule “no two pieces of the same color”.

One player is designated as the master, who chooses the secret rule and judges whether proposed groups satisfy the rule. The master initially sets out one group that satisfies the rule (marked with a white stone), and one that doesn't (marked with a black stone). The other players take turns proposing groups, which the master then marks with white or black stones. Later in the game, players try to guess the rule, based on the evidence they've seen. If a guess is correct, that player wins the round, and a new master is chosen for the next round. If a guess is incorrect, then the master creates a counter-example, either a group the satisfies the secret rule but not the player's rule, or a group that satisfies the player's rule but not the secret rule. Either way, the master marks the counter-example with the appropriately colored stone.

That's the basics of the game. There are a few more details that can be found in the complete Zendo rules. (That site also offers a fascinating design history of the game.)

As a player, you are constantly coming up with possible rules and checking whether they are consistent with the examples that are already on the table. Often you will have more than one possible rule in mind. When it's your turn, you try to design a group that will help narrow down the choices. Ideally, you want a make your group so that either a positive or a negative answer will support some possible rules and deny others.

The primary challenge as master is coming up with a good secret rule, one that is not too hard and not too easy. Of course, too hard and too easy will depend on who you are playing with. Looney Labs sells a pack of Zendo rule cards to get you started. These rules are fairly easy and are perfect for those new to the game. Eventually, you will want to start creating your own rules.

Debugging

Debugging is a fundamental skill of the programmer. When its your own bug or you're operating under severe time pressure, negative emotional reactions can make debugging quite stressful. But when you are helping somebody else debug their code, it can be quite fun, kind of like a logic puzzle.

There are two basic approaches to debugging; most debugging sessions combine both. In one approach, you step through the code, re-thinking each line and looking for something suspicious.

In the other approach, you look at the observable evidence—for this input, it's producing that output, when it should be producing this other output, or the web site crashes every day between 5pm and 6pm— and try to come up with a hypothesis for what might be going wrong. For example, you might hypothesize that something is going wrong when two clients happen to have the same name, or that somebody is mixing up row-column coordinates with X-Y coordinates. Often you try to come up with an experiment that might confirm or deny your hypothesis, or help select between several competing hypotheses. Once you have a fairly solid hypothesis, you can usually narrow down where in the code to go looking for the error.

It's this latter approach to debugging that Zendo captures so well, that of making and testing and refining and discarding hypotheses.

Of course, that's the perspective of a computer scientist. Other kinds of scientists might prefer to think of Zendo in terms of the scientific method.

How to get it

Zendo used to be sold in a nice boxed set, but that is long out of print. In fact, I didn't get my copy until after it was already out of print. I got it as a gift from my BoardGameGeek Secret Santa, a charming annual tradition where hundreds of boardgamers anonymously send Christmas presents (games, naturally) to other gamers around the world, usually gamers that the sender doesn't even know.

You can still buy the pyramids from Looney Labs, where they are sold as Treehouse sets. You would need at least four sets to play Zendo—five would be better. It's kind of expensive that way, but fortunately there are a whole bunch of other games you can play with the pieces. You would still need a set of markers, but poker chips or coins in several denominations work fine.

In fact, with only minor modifications, it's easy to improvise a set of pieces for Zendo out of common household objects, such as bottles of beer.

Ten Years of Purely Functional Data Structures

2008-02-08T13:08:00.000-05:00

In 1998, I published a book called Purely Functional Data Structures. Ten years later, the book is still selling well. (Every time I get a royalty check, my wife the skeptic says “People are still buying that?!”) The ten-year anniversary seems like a good time to reflect back on my experience with this book.

Origins

My first introduction to functional programming was at Carnegie Mellon University, where I worked for Peter Lee and Phil Koopman on an implementation of a subset of Haskell (called “Eddie”), written in Standard ML. So right from the very beginning, I was working with a mix of strict and lazy evaluation.

I've always been fascinated by data structures, and I soon realized that something was strange about data structures in these two languages. On the one hand, when they worked, data structures were more pleasant to work with than in any other languages I had ever used before. On the other hand, sometimes they just didn't work.

The issue was immutability. In pure functional programming, all data structures are immutable, meaning that they cannot be changed once created. Of course, data structures frequently need to be changed, so what happens is that you create a new copy of the data structure that incorporates the change, without actually modifying the old copy. This can often be done efficiently by having the new structure share large chunks of the old one. For example, stacks are trivial to implement this way. Tree-like structures such as binary search trees and many kinds of priority queues are almost as easy.

However, some common data structures, such as FIFO queues and arrays, can actually be quite difficult to implement this way. Some people take this as a sign that functional languages are impractical. However, it's not the fault of functional programming per se, but rather of immutability. Immutable data structures are just as awkward to implement in conventional languages such as Java. (Of course, immutable data structures also offer huge advantages, which is why, for example, strings are immutable in Java.)

In 1993, I ran across an interesting paper by Tyng-Ruey Chuang and Benjamin Goldberg, showing how to implement efficient purely functional queues and double-ended queues. Their result was quite nice, but rather complicated, so I started looking for a simpler approach. Eventually, I came up a much simpler approach based on lazy evaluation, leading to my first paper in this area. (When I say simpler here, I mean simpler to implement—the new structure was actually harder to analyze than Chuang and Goldberg's.)

Almost immediately after my paper on queues, I worked on a paper about functional arrays, here called random-access lists because they combined the extensibility of lists with the random access of arrays. (Because the lead time on journal papers is longer than the lead time for conferences, this paper actually appeared before the paper on queues, even though it was written later.) The approach I used, which turned out to be very similar to one used earlier by Gene Myers, was based on properties of an obscure number system called skew binary numbers. This marked the beginning of a second theme of my work, that of designing implementations of data structures in analogy to number systems. For example, inserting an element into a data structure is similar to incrementing a number, and merging two data structures is similar to adding two numbers. I called this approach numerical representations. The idea was to choose or create a number system with the properties you want (such as constant-time addition), and then build the data structure on top of that. The advantage of this approach is that you can often do the hard work in a simplified setting, where you don't have to worry about carrying around the actual data in your data structure.

Amusingly, this paper marked the second round of a circle dance between Rob Hoogerwoord, Tyng-Ruey Chuang, and me. First, Hoogerwoord published a paper on functional queues, then Chuang, then me. And again with functional arrays, first Hoogerwoord published a paper, then Chuang, then me.

Around this time, I was looking for a thesis topic (that period that John Reynolds describes as “making even the best student look bad”). Fortunately, my advisor Peter Lee had patience with me during this search. I considered a bunch of topics related to functional programming, but none of them seemed right. I was enjoying the work I was doing with functional data structures, but there didn't really seem to be enough meat there for a dissertation. That changed one day during a walk in the snow.

I had become fascinated by the idea of concatenation (appending two lists). This is trivial to do in conventional languages using, say, doubly-linked lists. But it's much harder to do efficiently with immutable lists. I thought that I had come up with a new approach, so I made an appointment to talk to Danny Sleator about it. He had been involved in some of the early work in this topic (along with Neil Sarnak and Bob Tarjan), and his office was just a few floors below mine. The day before the meeting, I realized that my approach was completely broken. Afraid of looking like an idiot, I went into a frenzy, playing with different variations, and a few hours later I came up with an approach again based on lazy evaluation. I was sure that this approach worked, but I had no idea how to prove it. (Again, this was a case where the implementation was simple, but the analysis was a bear.) My wife had our car somewhere else that day, so I ended up walking home. The walk usually took about 45 minutes, but it was snowing pretty hard, so it took about twice that long. The whole way home I thought about nothing but how to analyze my data structure. I knew it had something to do with amortization, but the usual techniques of amortization weren't working. About halfway home, I came up with the idea of using debits instead of credits, and by the time I got home the entire framework of how to analyze data structures involving lazy evaluation had crystallized in my head.

With this framework in mind, I now believed that there was enough meat there for a dissertation, and I sailed through my thesis proposal and, about a year later, my thesis defense.

The Book

After my defense, Peter Lee suggested that I try to publish my dissertation as a book. He contacted two publishers he had worked with before, and one of them, Lauren Cowles of Cambridge University Press, bit.

The process of turning my dissertation into a book was pure joy. I thought that the basic organization of my dissertation was pretty solid, so mostly I was able to focus on adding and adjusting things to make it work better as a book. For example, I no longer had the constraint from my dissertation of having to focus on original work, so I was free to add data structures that had been developed by other people.

The main additions were expanded introductory material (such as my simplification of red-black trees, which was developed a few weeks after my thesis defense in a series of emails with Richard Bird), exercises, and an appendix including all the source code in Haskell (the main text used source code in Standard ML).

After several months of hacking, I was able to ship off a giant Postscript file to Lauren Cowles, and that was that.

Well, not quite. Lauren asked me what I wanted for cover art. My wife was an avid quilter, and I liked the idea of having a suitably geeky quilt pattern on the cover. I adapted a quilt pattern called Flying Geese, and sent a sketch to Lauren, who got a graphic artist to draw up the final version. I was quite happy with it. Later, I found out that Flying geese was actually the name of a different pattern, and to this day, I don't know the correct name of the pattern. It looks a little different on the book than in quilts because quilters usually only use two levels of the recursion, but I used three.

Reactions

Initial reviews were positive and the hardcover edition sold out pretty quickly, so Cambridge University Press released a paperback edition the following year. I don't know of any courses that used it as the main textbook (it would have to be a pretty specialized course to do that), but several mainstream courses used it as a supplementary textbook.

Sales were steady but trending downward, until 2004, when a book review by Andrew Cooke appeared on Slashdot. After that, sales doubled and have stayed at that level for several years. Of course, I can't be sure this increase was because of Slashdot, but it seems likely. Thanks, Andrew!

The most interesting place the book has shown up was in the data of a TopCoder programming contest problem involving sorting books on a bookshelf. It was part of a list of CS textbooks. (And, no, I wasn't the author of the problem, although I have written some problems for TopCoder.)

The funniest moment about the book was when I worked at Columbia University. A potential grad student from an unrelated field in CS was visiting from Germany, and I was talking to him about the department. When I told him about my research, he said, “My roommate has been reading a book about something like that. I don't remember the name, but do you know which book I mean?” I reached over and pulled my book off the shelf and said, “Do you mean this one?” His mouth fell open.

The most flattering review of the book appeared a few years ago in a blog by José Antonio Ortega Ruiz, who said

“The exposition is extremely elegant and synthetic, and i’ve spent many, many hours immersed in its 220 pages (i can’t think of any other programming book with a better signal to noise ratio, really).”

Thanks, jao!

Complaints

Of course, you can't please everybody. The most common complaints I've heard are

No hash tables. This was mentioned in the first review of the book on Amazon, which called the lack of hash tables a “major omission, likely because they don't fit well into a functional environment.” More than a year later, a second reviewer mentioned that hash tables are in fact in the book, but buried in an exercise. Both reviewers are correct. I only gave a very short description of hash tables in an exercise, because there just wasn't that much to say. A hash table is basically the composition of two finite maps, one approximate and one exact. The choice of what structures to use for those finite maps are up to you. Typically, an array is used for the approximate map, but, as the first reviewer noted, arrays do not fit well into a functional environment.
No delete for red-black trees. I present my simplified form of red-black trees very early in the book as an introduction to functional data structures, but I only describe insertions, not deletions. There were two main reasons for that omission. First, deletions are much messier than insertions, and the introduction did not seem like the right place for a lot of messy details. Second, and more importantly, probably 95+% of uses of functional red-black trees don't need deletions anyway. Because the trees are immutable, when you want to delete something, you can simply revert back to a previous version of the tree from before the unwanted item was inserted. This is almost always both the easiest and the right thing to do. The exception is when you inserted something else that you want to keep after the item to be deleted, but this is extremely rare.
Why Standard ML? In the last 10 years, Haskell has become steadily more popular, while Standard ML has largely been replaced by OCaml. A frequent complaint has been people wishing that Haskell was in the main text, with Standard ML (or OCaml) in the appendix, instead of the reverse. Even at the time, I debated with myself about the choice of Standard ML, particularly because in some chapters I had to fake extensions to the language, such as lazy evaluation and polymorphic recursion. I went with Standard ML for two main reasons. First, I wanted to be able to distinguish between lazy evaluation and strict evaluation, which was much more difficult in Haskell. Second, I really wanted to be able to give module signatures for all the common structures (stacks, queues, etc.) that I was going to be revisiting over and over. You can sort of do this in Haskell, but not cleanly.
Too esoteric/impractical. Guilty as charged! I did try to point out a few data structures along the way that were especially practical, but that was not my main focus. If it was, I certainly would not have included umpteen different implementations of queues! Instead, I was trying to focus on design techniques, so that readers could use those techniques to design their own data structures. Many of the example data structures were included as illustrations of those design techniques, not because the examples were particularly practical or valuable by themselves.

The Future?

People sometimes ask me if I'm planning a second edition. The answer is maybe, but not anytime soon. I'm still pretty happy with what I said and how I said it, so I don't feel a burning need to go back and correct things. If I wrote a second edition, it would be to modernize the presentation and to add some new data structures and techniques. For example, I might include the finger trees of Ralf Hinze and Ross Paterson.

In terms of the presentation, however, the biggest question would be what language to use. Standard ML probably doesn't make sense any more, but I'm still not sure Haskell is ready to take over, for the same reasons mentioned above. I suppose I could switch to OCaml, but I'm not sure that's enough of a change to warrant a new edition. I have faith that the vast majority of my readers are perfectly capable of making the translation from Standard ML to OCaml themselves.

Boolean Confusion

2008-02-01T09:20:00.000-05:00

A big part of learning to program is building up effective mental models for how various logical structures work. A big part of learning to teach programming is learning how to diagnose broken or ineffective mental models by reading someone's code. One common confusion that shows up very clearly in the code of novice programmers is thinking of booleans and control expressions as being somehow two separate things.

By “control expressions”, I mean the expressions that are used in if-statements and while-loops. For example, in

   while (i < 100) {
      ...
   }

the control expression is “i < 100”. Of course, the value of the control expression is a boolean. Novices can even tell you that, but they haven't quite internalized it yet.

Suppose you wanted a function to test whether an integer is positive. An experienced programmer might write

   boolean isPositive(int n) {
      return n > 0;
   }

but a novice programmer would be more likely to write

   boolean isPositive(int n) {
      if (n > 0) {
         return true;
      }
      else {
         return false;
      }
   }

Why? Because the function is supposed to return a boolean, but the novice doesn't quite believe that n > 0 is a boolean—it's a control expression!

On the flip side, suppose you have a loop being controlled by a boolean variable named flag. An experienced programmer might write

   while (flag) {
      ...
   }

but a novice programmer would be more likely to write

   while (flag == true) {
      ...
   }

Why? Because the while-loop needs a control expression, and the novice doesn't quite believe that flag is a control expression—it's a boolean! The novice uses the == operator to convert the boolean into a control expression.

In extreme cases, you can even see both cases simultaneously, such as this gem where a public method is checking the state of a private variable

   public boolean isReady() {
      if (ready == true) {
         return true;
      }
      else {
         return false;
      }
   }

What are some programming idioms you've seen that help you diagnose confusions like these?

Lessons from Laundry

2008-01-23T10:00:00.000-05:00

Several years ago, I was advising a student on some code he had written for a data structures class. This code performed a set of actions on a temporary counter, and he was resetting the counter to zero after the last action so it would be ready for the next cycle of actions. I suggested setting the counter to zero just before the first action instead of just after the last action. He asked why, and this was my explanation.

This is also an example of what Jeanette Wing and others call computational thinking.

You know when you're doing laundry and you have to clean the lint out of the lint trap? Of course, this is not mandatory—the dryer will still work if you don't clean out the lint, but it'll work more efficiently if you do.

Now, you have two basic choices as to when to clean out the lint. You can clean it out when you remove clothes from the dryer, or you can clean it out when you put clothes into the dryer. Either protocol will work fine as long as everybody in the house is following the same protocol.

But suppose you have two people in the house following opposite protocols. Let's say that you follow the clean-after protocol and your housemate follows the clean-before protocol. If you do a load of laundry and clean out the lint trap when you're done, and then your housemate does a load of laundry, then the worst that will happen is that the lint trap will already be clean when your housemate goes to clean it.

On the other hand, if your housemate does a load of laundry and cleans out the lint trap at the beginning, and then you do a load of laundry, now you have a problem. When you go to clean out the lint when you're done, you'll find it extra full. You might even need to run the dryer a second time because your clothes didn't get completely dry.

The point is that some protocols, such as the clean-after protocol, only work if everybody follows the same protocol. Other protocols, such as the clean-before protocol, are more robust; they work fine—at least for you—even if some people follow the other protocol. If you can't guarantee that others will follow (or even remember!) a particular protocol, then you're better off choosing the robust protocol.

Here's a similar example. In college, I used to play a lot of bridge in the dorm lounge. In the hall right outside the lounge, there was a small bathroom. Now, there were two protocols concerning this bathroom. In the first protocol, you lock the door when using the bathroom; in the second protocol, you knock before entering. Somebody following the locked-door protocol may or may not knock, while somebody following the knocking protocol may or may not lock the door.

As long as everybody in the dorm follows the same protocol, there's no problem. But if different people follow different protocols, there can be tragic (or at least embarrassing) consequences!

In this example, perhaps the best course of action is to follow both protocols: lock the door and knock. The same is possible in many other situations where you want to be extra careful: clean the lint after drying but also check it again just before drying, initialize the counter just before the first action but also reset it to zero just after the last action, wear both a belt and suspenders.

Why I Don't Use PowerPoint For Teaching

2008-01-18T15:15:00.000-05:00

This essay was originally written for a talk I was giving to brand new faculty members. I'll let it stand as an introduction to one of my passions—teaching. I'll introduce other passions in the coming weeks. Welcome to my blog!

Ok, I’m a freak. I admit it. I don’t use PowerPoint for teaching. Well, hardly ever. Once or twice a semester. Around my institution—and across the country—that puts me in the tiny minority. I know this because my students find it unusual enough to comment on. (Update: Since I wrote this, PowerPoint use in the classroom appears to be on the decline, at least at my institution. Hooray!)

Why do I take this heretical position? Part of it is that PowerPoint doesn’t mesh well with my personal teaching style. But mostly it’s because PowerPoint is just too hard for me. Oh, not making slides. That part’s easy. I mean that creating a PowerPoint presentation that effectively supports my goals in the classroom is too hard. It’s way too much work. Some people can—I tip my hat to them—but me? I’m just not good enough to do that.

I’m sure you’ve seen through my little rhetorical device to the arrogance that lies beneath, the arrogance that says “I think I’m pretty good, so if I’m not good enough, then I think most other people aren’t either”. But what makes using PowerPoint for teaching so hard, when it seems so seductively easy?

Well, that’s exactly the problem. PowerPoint is seductively easy. The problem is that PowerPoint makes it easy to do the wrong things.

Here’s an analogy. If you have taught beginner programming classes, you have seen badly indented code. Why? Because in an editor that does not automatically indent, it is easier to write badly indented code than to indent properly. (At least in the short term. Most students don't believe us when we tell them that indenting their code properly will actually save them time in the long run.)

With PowerPoint, however, the situation is more subtle. That’s where the “seductive” part comes in. With indentation, the student usually knows that he is doing the wrong thing, but does it anyway. With PowerPoint, the instructor probably sincerely believes he is doing the right thing. The road to hell is paved with good intentions…

Let’s look at five ways that PowerPoint makes it easy to do the wrong thing.

Presentations

The original name of PowerPoint was Presenter and that’s exactly what PowerPoint was designed for—presentations. Think about what that implies. One person (the presenter) is presenting information to other people (the audience). The flow of information is one way, from the presenter to the audience. Because the flow of information is one way, the presenter can and does script out the entire presentation ahead of time, much like a movie or a novel. Like those forms, a PowerPoint presentation is highly linear. It is meant to be experienced in a particular order. Deviating from the expected order is possible, but awkward. This model has little room for interactivity, except perhaps a single slide at the end labeled “Questions?”.

There are contexts where this linear model may be appropriate. You’ve probably seen presentations like this at business meetings or at research conferences. But the purpose of those presentations is not teaching. The goal may be to inform, to persuade, maybe even to train, but the goal is not to educate. What’s the difference? In a presentation, you are trying to make the audience think your thoughts, but in education, you are trying to teach students to think for themselves. In terms of the well-known fishing analogy, it’s the difference between giving somebody a fish and teaching them how to fish.

To teach students to think for themselves, you must give them plenty of opportunities to think for themselves and then respond to those thoughts (or allow others to respond). But this breaks the model of information flowing in one direction in a linear order. Instead you now have information flowing in both directions—a feedback loop—and the order of information can and will change based on that feedback. Good teaching is highly interactive. A good teacher is highly adaptive, and can change the entire direction of a lesson midstream based on student input. But, if you’re using PowerPoint, how do you change direction midstream? It’s hard to tell students “Just wait a few minutes while I edit these slides!”

You may remember the “Choose Your Own Adventure” books that were popular twenty or thirty years ago. You would read a page, and at the end of the page would be some choices. “If you pay the troll and cross the bridge, go to page 117. If you try to cross without paying, go to page 98. If you attack the troll, go to page 140.” These books were an attempt to shoehorn an interactive form into an inherently linear medium. It was an uncomfortable fit, and these books were soon replaced by computer programs that hid the linearity. It is certainly possible to design a PowerPoint presentation that supports interaction in this fashion, but, like the Choose Your Own Adventure books, it is always an uncomfortable fit.

So this is the first way that PowerPoint makes it easy to do the wrong thing. PowerPoint makes it easy to create a linear presentation, but hard to create an interactive lesson.

“It’s only wafer thin”

There is a scene in Monty Python’s The Meaning of Life in which, at the end of a ridiculously large meal, the maitre d’ offers a diner a mint. At first, the man refuses, but the maitre d’ talks him into it, saying “It’s only wafer thin” and later “Oh, sir, just—just one.” The man eats the mint and literally explodes. (There’s also a brilliant send up of this scene in the comic strip Foxtrot, where a girl wakes up with a swollen head after cramming for finals, and her brother taunts her, saying “It’s only a wafer-thin math formula!”)

This is the second way that PowerPoint makes it easy to do the wrong thing. There’s always the temptation to add just one more word, just one more bullet, just one more slide. It’s so easy to do, and, after all, wouldn’t the students be better off with more information, with more complete slides?

Well…no. Students have a limited capacity to absorb information from slides. Exceed this capacity, and they not only fail to absorb the excess, they also fail to absorb or retain what came before. This can happen either when a single slide contains too much information or when the presentation as a whole has too many slides.

Think of that limited capacity in terms of juggling. Most people can learn to juggle three balls with a little practice, but juggling four is much more difficult. So there you are, happily juggling three balls, when somebody tosses you another ball. What happens? Do you just drop the new ball and continue juggling the three you already have? No. What really happens is you drop all four balls.

Teachers often prepare extra slides “just in case there’s extra time” or “just in case somebody asks”. After all, as discussed above, you want to be prepared to respond to student questions. That’s fine, as long as you are strong-willed enough to resist the temptation to show the extra slides. But, all too often, once you’ve invested the time and effort to create a slide you’re proud of, the psychological pressure to show that slide is irresistable.

Extra slides also cause awkward navigation issues. Where do you put the extra slide? Do you put it in the middle of the presentation, right where it might be needed? If so and it turns out not to be needed, then you have to hurriedly skip over the slide when it comes up, which never looks good. Or do you put it out of the way at the end of the presentation? But then, if it is needed, you have to skip through possibly dozens of slides to reach the extra one, and then go backwards through the same slides to get back to where you were. There are technical ways around these problems, but hardly anybody uses them.

He who controls the clicker, rules the world

Have you ever fought with a sibling or spouse or significant other over who gets to hold the TV remote control? This can be particularly contentious when you intend to channel surf, but the issue arises even if all you intend to do is watch a DVD. Why bother to fight over the remote in that situation? Because the person who holds the remote has enormous power. Another viewer with even the smallest request must approach as a humble supplicant—“please hit pause”, “please turn the volume up”, “hold on, I missed that, can you please go back a little bit?”

Teaching from PowerPoint slides is like holding the TV remote control (and, in fact, you may be literally holding a projector remote control). The teacher decides what slides to show and what to say about each, when to advance and when to go back, when to turn off the screen and when to turn it on. The teacher is in complete control. This is the epitome of teacher-centered learning, and is the third way in which PowerPoint makes it easy to do the wrong thing.

Especially to new teachers, being in complete control may sound like a good thing. The teacher's the one who knows what he's doing—of course the teacher should be in control! So then why does our dean's vision explicitly state that “Teaching is student centered and encourages active learning”?

Sure, the phrase student centered has been overused to the point of becoming educational gobbledygook, but there is an important idea there. The ultimate goal in any classroom is not for the instructor to teach, but for the student to learn. So shouldn’t attention be on the student learning? In a PowerPoint presentation, the attention is mostly on the teacher—the instructor is (mostly) concentrating on his own performance and the students are (hopefully) paying attention to that performance. Here’s a simple rule of thumb for you: If you’re not paying more attention to the students than they are paying to you, then your class is not student centered.

I always allow students to bring a single page of notes to exams. I encourage them to prepare the notes themselves, because the biggest benefit of the notes lies not in having the notes on the exam but rather in the cognitive act of organizing the information. Paradoxically, students who prepare their own notes often find that they never once refer to them during the exam, because the act of preparation was enough to get the information into their heads. On the other hand, students who use other people’s notes often find them useless on an exam because they don’t really understand how the information is organized.

This highlights the flaw in teacher-centered instruction, especially instruction based around PowerPoint. In creating the slides, the teacher is imposing his own organization of the information on the students, when he should be helping the students to organize the information for themselves.

Active learning

My friend Susan doesn’t like to listen to books on tape in the car, because inevitably she will zone out for a while and have to back up the tape. In a PowerPoint slide show, students also will inevitably zone out for a slide or two (or six). But when (if!) their attention wanders back to you, they probably will not ask you to back up the presentation a few slides. Not only will they have lost any chance of learning the content of the slides they missed, but now they probably will not have the context to be able to learn anything from the upcoming slides. And so the lost students will happily return to daydreaming. This is one danger of passive learning and why lectures are so often condemned. In a classroom where students are allowed to be passive observers, they need only keep reasonably attentive expressions on their faces and the instructor will never realize that no learning is taking place (or at least not until the moment has long passed).

This is the fourth way that PowerPoint makes it easy to do the wrong thing. The more you rely on slides, the more passive the students become.

Contrast a lesson where students are passively observing a PowerPoint presentation with a lesson where students are actively engaged in solving a problem. How easy is it to zone out when you are sitting at a desk looking at a screen full of text as opposed to when you are, say, trying to design a solution on a whiteboard? Now the intructor has a better chance of noticing that a student has failed to learn some important point in time to do something about it. Even better, the student has a better chance of remembering the important points of the lesson because memory formation and retrieval depend at least in part on how many different parts of the brain are active. When a student is thinking, writing, drawing, explaining, and building, more parts of the brain are involved than when he is merely watching and listening.

Although I know of no studies that measure audience brain activity during a PowerPoint presentation, I wouldn’t be surprised if it resembled the relatively flat EEGs found when people watch TV.

“It’s a floor wax and a dessert topping”

Although I almost never use slides in the classroom, I do use them for giving research talks. I am often approached and asked “I missed your talk. Can I get a copy of your slides?” The other person is usually shocked—and initially annoyed—when I say no. But they usually understand when I explain “I wrote the slides to accompany my talk. They wouldn’t make any sense without my words to go along with them. You’re better off looking at my paper, which was intended to be read on its own.”

A trap that instructors often fall into is putting their PowerPoint slides on the web. They feel virtuous in doing so, patting themselves on the back for helping out students who missed class and for giving students something to review later. This is the fifth way that PowerPoint makes it easy to do the wrong thing.

But how can it possibly be the wrong thing to give students your slides? Because slides that were designed for use in the classroom probably will not work well when viewed from a student's room, and slides that were designed to be viewed outside of class almost certainly will not work well in the classroom. Like the combination floor wax/dessert topping from the classic Saturday Night Live skit, it is nearly impossible to serve both purposes well—you can’t serve two masters. Chances are high that if you try to serve both purposes well, you’ll fail at both.

So perhaps you decide that you’re going to focus on making slides that work well in the classroom, and accept that maybe they won’t work so well from the student's room. Wouldn’t it still be better to give students the slides? Wouldn’t ineffective slides be better than nothing? Not necessarily. Not if the main outcome is to give students a false sense of security and to prevent them from seeking more effective means of learning. A student faced with the choice of reviewing bad slides, talking to a buddy about their notes, unsealing the shrinkwrap on the textbook, or coming in to see the teacher or TA will all too often choose the slides because they seem the easiest.

Going the other direction and deciding to focus on making slides that stand alone when read from the student's room is even worse. That way lies the kinds of overfull slides that leave students muttering “Death by PowerPoint”. Furthermore, students actively resent sitting through a 50 minute lecture when they feel they could have read through the slides in 10 minutes and gotten just as much out of it—especially when that impression is accurate!

In fact, the situation is even worse than I’ve described because instructors often try to create slides that serve more than two purposes:

visual aids for during the lesson
make-up material for students that missed the lesson
review for students that were present at the lesson
handouts for students during the lesson
read-ahead before the lesson
notes to the instructors themselves

I don’t care if you are Socrates, Halliday&Resnick, and Edward bloody Tufte all rolled into one. Try to do all this with one set of slides and you will fail. Decide which purpose you are trying to serve and serve it well.

Searching for the harder right

Make us to choose the harder right instead of the easier wrong.

– USMA Cadet Prayer

I've shown five ways in which PowerPoint encourages you, subtly or not so subtly, to choose the easier wrong. But what then is the harder right? Sorry, I can't tell you. Good teaching is hard, and part of what makes it hard is that it is both highly personal and highly context dependent. My solution wouldn't necessarily be right for you.

I admit that's a cop out, but it's also true. For some of you, PowerPoint itself might be the harder right. If you use it carefully and in moderation, with an eye out for the kinds of traps described above, you can probably do fine. But it sure is a lot more work that way, isn't it?