Prehistory, continued

I guess I always thought of technology as strictly cumulative, but reading a little about the Stone Age dispelled that notion. Archaeologists have had to reverse-engineer, from the artifacts they left behind, the toolmaking skills and technology of extinct cultures. How did Cro-Magnon mammoth hunters store meat? Wouldn't it spoil? Well, we really don't know that sort of thing anymore, but there's a way to find out:

…[U. Michigan researcher Dan] Fisher butchered a draft horse using stone tools he'd knapped himself, then cached the meat in a stock pond. Naturally preserved by microbes called lactobacilli in the water, the flesh emitted a faintly sour, pickled odor that put off scavengers even when it floated to the surface. To test its palatability, Fisher cut and ate steaks from the meat every two weeks from February until high summer, demonstrating that mammoth hunters might have stored their kills in the same way.

–Tom Mueller, “Ice Baby”. National Geographic, May 2009.

People showed up on Australia forty thousand years ago. Even though the sea level was lower then, they would have had to cross a channel 55 miles wide to get there. It's a little mysterious to me, as the oldest boats ever excavated anywhere are dugout canoes at most nine thousand years old.

So the first real agriculture (planted fields) happened about ten thousand years ago, dogs were domesticated about fourteen thousand years ago, but apparently people were exploring the South Pacific in logboats, miles from shore, forty thousand years ago. (The oldest stone tools predate H. sapiens and appeared 2.5 million years ago.)

Barleycorn Bay

See earlier puzzles for, er, something of an explanation.

“Now listen close-like,” said my new friend, “'cos I'm only going to say this once. All the inhabitants of Barleycorn Bay, and I've met them each and every one, are either heroes or vagabonds. Or both. Every one of the heroes is blonde; every one of the vagabonds is a magician, except for any that be Quakers; and all the magicians are nanny goats. Every one that isn't a walrus isn't a ruminant.”

“Isn't a what?” I said.

“And every living soul in Barleycorn Bay that isn't clean-shaven is red-headed, excepting the nanny goats of course. Needless to say,” he added, scratching his beard with a steel hook, “there are no clean-shaven pirates.”

I thought it over for a while. “Is there such a thing,” I wondered aloud, “as a nanny goat that's also a walrus?”

“I reckon there could be,” he replied, “although I've never met one.”

“What about a blonde redhead?”

“Don't be ridiculous.”

This week I learned...

• How to find the median of n items in O(n) comparisons. The easiest algorithm is merely O(n) expected time. Can you figure out how it works? Hints in the comments.

• You can sort items with string keys in O(kn) time, where k is the average length of the strings. But it requires, say, 5n words of extra table space. This is amusing because in JavaScript, Array.prototype.sort() sorts objects by their toString(), so it is always sorting strings. (A comparison sort in this case can be as bad as O(kn log n), since comparisons are worst-case O(k).)

• The memory model that processors present to multithreaded programs running on multiprocessor machines is frighteningly subtle: A Taxonomy of Multiprocessor Memory-Ordering Models (44 slides, PDF). The presentation cheerfully explains about 13 different ways CPUs can (by design) shuffle the order of memory accesses, causing more or less confusion on other CPUs. The reason they have to do this is per-CPU caches, which are a major speed win; the techniques multiprocessors use to maintain a modicum of sanity are called cache coherency protocols.

• That's why atomic operations are so costly. Not only do they flush the cache line of the memory being atomically accessed. In order to maintain cache consistency and coherency, the CPU has to flush, potentially, its entire cache.

• You can implement a copying collector in 100 lines of easy-to-read C, if you're not too worried about blowing the stack.

  T.S. brought me a book, Garbage Collection by Jones and Lins (read a review). It was written in 1996, which in the GC field is a long time ago; but I don't think the basics have changed. Still, it's odd to see Fortran and Modula-2 used as examples, rather than various JVMs, the CLR, Python, JavaScript, and Ruby.

  Working for Mozilla is like going back to school, except I'm motivated.

• Suppose I want to create a set of C/C++ macros that application code can use that allows me to swap out different kinds of memory management systems, switching between reference counting, mark-and-sweep, copying GC, and so on, as a compile-time option. In C/C++ this is actually practically impossible, because the range of operations you want to hook, and the amount of detail the GC might need to know about them, is so great. To do a good job, each memory management scheme will want to optimize away a lot of work, which you can't do without still more cooperation from the compiler or the programmer.

  Java doesn't have this problem. The JVM can hook whatever it wants because the bytecode it loads and executes is really only partly-compiled. With Jikes RVM, you can in fact choose from a huge array of garbage collectors at the time you compile your VM.

C puzzle

I was reading source code this morning and came across this curious line in a header file:

JS_STATIC_ASSERT(sizeof(JSGCThing) >= sizeof(JSString));

The effect of this macro is to check at compile time that sizeof(JSGCThing) >= sizeof(JSString). If the condition is not met, compilation fails with an error.

The puzzle is: how does this work? A hint is in the comments.

Concerning gifts (and other puzzles)

What can you conclude from the following three premisses?

1. If something is not gift-wrapped, it's not a gift.
2. Nothing that's gift-wrapped is entirely unlike a box of chocolates.
3. Life is a gift.

Lewis Carroll published a book of about a hundred puzzles like this one. Read it online: introduction; puzzles. My nephew IM and I stumbled upon them in Memphis last week. He pretty much knocked them out of the park one at a time.

They're fairly easy to make, if you know some logic and some algebra. Here are a few more (but Lewis Carroll's are the most sublime nonsense—you should probably try those instead.)

Concerning fashion

1. Anyone lacking impeccable fashion sense might wear a rhinestone sombrero.
2. Anyone who might wear a rhinestone sombrero can't dance.
3. All penguins can dance.

Concerning animals

1. Animals that are active during the day are either featherless or tasty—or both.
2. No creature is both nocturnal and naturally funny.
3. Chickens have feathers.
4. Chickens are naturally funny.

Concerning the inhabitants of this town

1. All the monsters in this town are carnivores.
2. A carnivore would eat anything made of meat.
3. No creature in this town would eat any other creature in this town.
4. Humans are made of meat.

Concerning monsters

1. Only monsters can make the ground tremble.
2. Two-year-olds and raccoons get into everything (two-year-old raccoons doubly so).
3. If something gets into everything, but it doesn't emit terrifying shrieks, it must be a raccoon.
4. All firebreathing creatures are monsters.
5. Opera singers can make the ground tremble.
6. Raccoons are not human.
7. A creature that isn't a monster doesn't have slavering fangs.
8. If a creature emits terrifying shrieks, then either it breathes fire, it has slavering fangs, or it's an opera singer.

Things of the moment

• My current side project is fixing bugs in Python's DOM implementation.

• Brainteaser: What if chess had a single level of undo? Specifically, after your opponent moves, you may, instead of making your next move as usual, roll the game back to the point just before your previous move and do something else instead. (Your game clock, though, would not be turned back.) How would this affect the game?

• I'm trying to understand Haskell's existentially quantified types, and (a shallower question) why there's no Data.Hashtable.ST, darn it.

• GoboLinux is a Linux distribution with a sane filesystem layout. From reading that one page, I like it. You can't fight with MSI for a week without realizing that the people who design installer systems have been working waaaay too hard, and that the fate of our civilization hinges on stopping them.

• Yesno is a toy programming language in which every method call returns something immediately ...and returns the correct result eventually. It's either hilarious or awesome, probably. The obvious next step is to make it self-host.

• In the spirit of yesno, here are two quick reviews of books I'm not done reading yet. (I'll refine these opinions later, maybe.) The Time-Traveler's Wife is too sentimental and too linear, and does not contain enough adventure or suffering. Oryx and Crake has a lot of the same strengths and weaknesses as 1984, but much more angst.

Infinity, part 1: Thomson's lamp

Back in the 1950's, the famous electrical engineer James Thomson invented the ultimate strobe light. Instead of flashing at regular intervals, Thomson's lamp (as it was called) would start out flashing slowly and quickly speed up.

The lamp had a button on it. Pushing the button caused the lamp to flash for a total of two minutes, as follows. First the lamp turned itself on. It stayed on for half of the total two minutes (one minute). Then it turned itself off and stayed off for half of the remaining time (half a minute). Then it turned itself on for a quarter of a minute, then off for an eighth of a minute, and so on. Toward the end of the two minutes, it would have been blinking pretty quickly.

The troubling question was, after the two minutes passed, would the lamp be on or off? Thomson was so anxious about the philosophical consequences of his invention that he famously refused to press the button for decades. (The legend is that a physicist friend eventually talked him into it, but there are conflicting stories about epileptic seizures, electrical fires, and divine intervention—I can't make any sense of them.)

So: on or off? What do you think?

Perfect numbers

Perfect numbers are numbers that are equal to the sum of their factors: 6 is perfect because its factors are 1, 2, and 3, and 1 + 2 + 3 = 6. Likewise 28 = 1 + 2 + 4 + 7 + 14; and so on. So far, 44 perfect numbers are known.

Puzzle: Can you prove that if 2ⁿ - 1 is prime, then 2^{n - 1}(2ⁿ - 1) is perfect?

planx_constant mentioned that little theorem to me over vacation. It was first proved by Euclid. Millenia later, Euler proved that all even perfect numbers are produced by this formula. But it is not known whether there are any odd perfect numbers. Most mathematicians seem to think there are none. Here's James Joseph Sylvester, writing in 1888:

...a prolonged meditation on the subject has satisfied me that the existence of any one such—its escape, so to say, from the complex web of conditions which hem it in on all sides—would be little short of a miracle.

Yet there is hope, and indeed the search is on.

Alice in Puzzle-Land

“How do I know for sure that I'm awake?” asked Alice. “Why can't it be that I'm now asleep and dreaming all this?”

“Ah, that's an interesting question and one quite difficult to answer!” replied the King. “I once had a long philosophical discussion with Humpty Dumpty about this. Do you know him?”

“Oh, yes!” replied Alice.

“Well, Humpty Dumpty is one of the keenest arguers I know—he can convince just about anyone of just about anything when he puts his mind to it! Anyway, he almost had me convinced that I had no valid reason to be sure that I was awake, but I outsmarted him! It took me about three hours, but I finally convinced him that I must be awake, and so he conceded that I had won the argument. And then—”

The King did not finish his sentence but stood lost in thought.

“And then what?” asked Alice.

“And then I woke up!” said the King, a bit sheepishly.

—Raymond Smullyan, Alice in Puzzle-Land. This is a fun book of logic puzzles ranging from cute to outrageously intricate. A fine gift for the mathematician on your list (though I hear The Annotated Alice is even better).

To be continued

An MIT mailing list on lightweight languages poses the warm-up question: What is the value of this expression:

  (call/cc call/cc)

Ready for the main event? Figure out this one:

  ((call/cc call/cc) (call/cc call/cc))

The answer is helpfully missing.

I went through several contradictory answers before figuring out a good way to reason about continuations. I'll put a hint in the comments.