Dr. Dobb's Journal July 2001
Two months ago in this space, I reminisced about old Basics I have known, including those versions that helped launch the personal computer revolution, Microsoft, and this magazine. Basic seems to be an immortal language, morphing periodically into new forms that bear little resemblance to Kemeny and Kurtz's original Beginner's All-purpose Symbolic Instruction Code. Then again, as one reader pointed out, some modern Basics are closer, in some ways, to Kemeny and Kurtz's Basic than are those early microcomputer Basics that I described. Perhaps what's immortal is just the name Basic.
Just the opposite state of affairs seems to prevail in the case of artificial intelligence. The term "AI" is not in great favor these days, but the tools and techniques and the puzzles of AI are very much with us. One need look no farther than the work being done on the Semantic Web, Tim Berners-Lee's vision of how to instill in our hardware and software artifacts some plausibly achievable capacity for understanding. A good puzzle can often inspire serious research. I recently came across an interesting mathematical puzzle with implications for coding theory. You may have seen it, too. But I don't think it's any more interesting than an older variation that I came across some years ago. These are the things that I'm writing about this month.
I wonder if the popularity of Basic with entry-level programmers isn't entirely based on its name (it sounds easy) and on the fact that Bill Gates owes the existence of Microsoft to Basic (he's sentimental). Perhaps it has nothing to do with any features of the language. Then again, are there any recognizable and desirable features in common across all language implementations bearing the name Basic?
The leading Basic implementation today, of course, is Visual Basic, and VB has done a lot to keep the language alive. But now there is evidence that VB use is declining while, oddly, a sort of VB clone is gaining in popularity.
Evans Data Corp., in my old home of Santa Cruz, California, reports that Visual Basic usage has been eroding since spring of last year. A year and a half ago, 62 percent of surveyed developers said that they were using VB at least some of the time; now a slim majority say they never use it, and when asked if they plan to use it in the future, the numbers drop off ever farther. Although Java usage is up, the data suggest that these VB developers are migrating just where you'd expect them to, and where Microsoft wants them to — to Microsoft's C#.
At the same time, REALbasic is just starting to take off as a VB-level Macintosh development language. What's that about? Are Mac developers just behind the curve, or what?
The fact is that VB still has a much larger proportion of Windows developers than RB has of Mac developers. RB came along later and is filling a gap, but VB is also filling a gap and would go on doing so if its creator weren't actively planning its demise, a problem that RB isn't facing.
Well, is REALbasic real Basic? No, but not even Kemeny and Kurtz thought that their original Basic was the last word on the subject, as witnessed by their mid-1980s product, TrueBasic, which discovered unsuspected structured programming sympathies within Basic.
No, Andrew Barry, who created REALbasic and wrote versions 1 and 2 for REAL Software (but is no longer involved with the company), didn't have Basic in mind at all when he started developing his language. His original plan was a highly visual pure object-oriented language, a pristine vision that he dropped like a rock when, in a flash of insight in a Chinese restaurant, he realized that he wanted people other than himself to use the language. Noticing that Visual Basic had attracted quite a few users, he swung to what one might call the opposite extreme and decided to turn his language into Basic. Well, sort of. He threw out all the features that he didn't like in familiar Basic implementations, like multiple statements on a line, line numbers, and implicit variable declaration. He added other nonBasic features, like strong typing. And although he aimed for a degree of VB compatibility, he split with VB over some fundamental issues, like VB's insistence on case sensitivity in string searches. For a while he thought he'd have it cross-compile to Java, but he dropped that, too. What he ended up with looks enough like Basic that it might as well be called REALbasic, whether or not it's real Basic.
Perhaps to offset, on some nomenclatural balance, these language implementations that call themselves Basic whether they are or not, there are all about us examples of artificial intelligence work that prefer to be called anything but AI. Such as the work being done under the umbrella of the Semantic Web (http://www.semanticweb.org/).
The Semantic Web is the brainchild of Tim Berners-Lee, the inventor of that other Web. The "semantic" part of it comes from a frustration with the "web" part. The pen that Berners-Lee gave us for drawing the current World Wide Web is HTML, a tagging scheme that lets us assign syntactic markers to chunks of content so that browsers and other software can deal with these chunks appropriately. Appropriately with respect to their syntactic function, that is: A browser can read the HTML to learn that a chunk of text is an item in an ordered list, for example. But wouldn't it be nice if the browser — or the database or the coffee maker or whatever artifact is handling this content — could know that the list is a roster of current full-time employees of your company, as opposed to, say, a list of web-safe color codes — and could use the items on the list appropriately? Appropriately in terms of this semantic comprehension?
That's the starting point for the Semantic Web, but just the starting point. The end point, if there is one, is to be able to automate the locating and collating and cross-relating of content, and the process of drawing conclusions from content culled from diverse sources. In other words, to empower programs and machines to reason about information by virtue of having some understanding of what that information actually means.
If that's not artificial intelligence, I don't know what is. The work being done under the Semantic Web umbrella spans a lot of technologies, including XML, digital signatures, RDF and RDF Schema, and more obviously AI-like layers on top of these.
What I find intriguing about the Semantic Web is this layered approach, leading to a wildly ambitious scheme built up in individually plausible steps. XML? Technologically trivial, but it lets programs deal with data one notch more intelligently, not confusing the home you live in with the home (page) you post your vacation pictures to. RDF Schema? No technological challenge either, but from it we get the ability for programs to work with chunks of information in ways that depend on the properties that are associated with information of the chunk's class. A step further up the hierarchy of technologies are ontologies, which give more complex descriptions of objects and their interactions, and provide the foundation for reasoning about those objects. This will require mechanisms for drawing conclusions — logic programming, one of the gifts of past AI research.
If all of this technology had to be in place before any of it was of any use, it might never happen. But it seems to me that the steps aren't that large and that work can go on simultaneously on different levels of the Semantic Web vision.
And if all of this technology had to be cost-justified, it might never happen either. I suspect that the Semantic Web raises more questions than it answers. I hope it does. The World Wide Web, which is, after all, a huge database without an index, did that. And just like that Web, this Web smacks of "If You Build It They Will Come" thinking. They will, I think.
In a culture that asks for solutions, Tim Berners-Lee keeps posing new questions.
There's a puzzle that Martin Gardner described as old back in 1989. It's twelve years older now, but still interesting, I think. There are n men, n red hats, and n blue hats. The men close their eyes and a hat is placed on each of their heads. The other hats are hidden. When they open their eyes, each man can see the color of the hat on each other man's head, but not his own. If a man sees a red hat, he must raise his hand. As soon as he knows the color of his own hat, he must announce it. The first to announce his hat color correctly wins. Now assume that all the hats on all the men's heads are red. What will happen?
Start with the simplest meaningful case, n=2. Both men see red hats, and must raise their hands. Now each man knows what color his own hat is — because the other man just told him. The quicker witted of the two will immediately name his hat color and win.
Now let n=3. (Or LET N=3, if we're still talking in Basic.) The quickest witted of the three will reason as follows: "We all have our hands up. If either of the others saw a blue hat on my head, he would know that his own hat was red. Why? Because otherwise the third man would see two blue hats (mine and the second man's) and wouldn't have put his hand up. Since neither of the others has announced that his hat is red, neither of them sees a blue hat on my head. So my hat is red." And he will announce this fact and win.
The same reasoning can be applied inductively to prove, if all the hats are red, that the quickest witted of n men, for any finite n, can always conclude that his hat is red.
Or anyway that's the claim. But it's a disturbing claim. It involves chains of assumptions about who knows what when, and it quickly loses any connection with practical reality. Mathematically, though, it seems unassailable. Is it?
Gardner describes a number of variations on and generalizations of this puzzle in his book Penrose Tiles to Trapdoor Ciphers...and the Return of Dr. Matrix (W.H. Freeman, 1989). Some of them are very puzzling indeed. And he leaves a few unanswered questions. This hat-color situation is a fertile field for constructing deep puzzles.
The latest variation on the puzzle has been consuming a lot of mental bandwidth among mathematicians recently, because it has connections with some interesting problems in telecommunications and computer science. In this version, the colors of the hats placed on the players' heads are determined by independent coin tosses, and the N players don't raise their hands on seeing a red hat. Instead, after they have noted the colors of each others' hats, they must all simultaneously either guess the color of their own hats or pass. If at least one player guesses correctly and no players guess incorrectly, they split a large prize; otherwise, they get nothing.
One other change in the rules is that the players get to confer, but only before they see any hats. During this conference, they must decide on their strategy, and this is what the new version of the puzzle is all about: deciding on the optimal group strategy for the game. How can they maximize their probability of winning that prize?
There is a simple strategy that gives the group a 50-50 chance of winning: One player guesses and the others pass. It doesn't matter whether he guesses red or blue. At first glance, it looks like that's the best they can do.
In the earlier versions of the puzzle, information was conveyed by the silence of the other players. Deciding how much silence had to be observed to be able to conclude that your hat was red was where those versions of the puzzle got weird. But in the new version, all the players guess or pass simultaneously. None of them can get any information about the colors of their own hats from the responses or nonresponses of the others. And before the moment of responding, none of them has any information that would help him determine the color of his own hat. Clearly, there is no available information about the color of one's own hat, and no player can do better than chance: 50-50. It may be clear, but it's wrong. There is a strategy that leads to a win at least three times out of four, despite the fact that the information content of the problem gives a guesser no better than a 50-50 chance of being correct.
If you'd like to come up with the solution on your own, stop reading now.
Here's my analysis of the puzzle.
What we have is a game with a peculiar payoff matrix, and that payoff matrix explains why the players jointly are able to win more than half the time, even though none of them can be correct more than half the time. They just exploit the fact that player A's being wrong is not necessarily independent of B or C being wrong; the correlation between their errors is partly determined by their guessing strategy. If they all agree to say red, they will either all be wrong or they will all be right.
Here's how that helps. Assume there are three players. Then the possible hat patterns are RRR, RRB, RBR, RBB, BRR, BRB, BBR, BBB. But what are the possible situations for a given player? The symmetry of the puzzle means that there are really only two possibilities: He sees two similar hats or he sees two different hats.
If you ask what he should do (what they all should do) in each of these cases, you pretty quickly come up with this strategy: If the two hats are different colors, pass. If they are the same color, guess the opposite color. Here's the result:
Truth Guess Hits Payoff
RRR BBB 000 L
RRB --B --1 W
RBR -B- -1- W
RBB R-- 1-- W
BRR B-- 1-- W
BRB -R- -1- W
BBR --R --1 W
BBB RRR 000 L
Column 1 is the true hat color for each of the players. Column 2 is each player's guess under this strategy: B for blue, R for red, - for pass. Column 3 contains a 1 for each correct guess, a zero for each wrong guess, and a - for each pass. Column 4 is the payoff: W means the team won the prize, L means they didn't. As you can see, they win 6 out of 8 times.
For more than three players, it gets even better. Fifteen players can win 15 out of 16 times.
Looking at the third column shows what's going on: There are the expected six hits and six misses: pure chance, 50-50. But when the players miss they all miss, and when one hits the others pass and let him bring home the bacon. The peculiar payoff matrix for the game makes this possible.
Okay, that's sort of cute, but it hardly seems worth the bandwidth of serious mathematicians. After all, if you rig the payoff matrix of a game to reward players for clustering their errors, you ought to expect them to do better than chance if they cluster their errors.
Where it gets interesting is in trying to come up with the general case for the optimal strategy. Turns out that, for large numbers N of players where N is not of the form (2**i)-1, Hamming codes give a solution that asymptotes to 100 percent as N increases. And Hamming codes are useful in both error correction in noisy data channels and in data compression.
University of California at Irvine professor Todd Ebert apparently invented this version of the hat problem in his Ph.D. thesis at the University of California at Santa Barbara in 1998.
If you have answers suggested by any questions raised in this column, please feel free to send them to me at mike@swaine.com. Further questions are also invited: Questions are often more interesting than answers.
DDJ