It's Turtles All the Way Down

| 0 comments |
I was waxing philosophically with Skrenta the other day about systems and abstractions;  Underneath the covers of many tried and true interfaces, lie crap.  He pointed out that 20 years had passed before a bug was uncovered in Jon Bentley's Binary Search implementation first published in Programming Pearls in 1986.  Arguably, this bug is an edge condition -- however  knowing a bug in this famous hunk of code possibly went  unnoticed for two decades should shake our collective confidence in software engineering to the core.

Beyond the trivial lurk even more disturbing problems.  What trouble is buried in, say, your TCP stack?  Or, maybe worse, your compiler?

I still lose a little sleep when I look back at how I bootstrapped a compiler a few years back at one of my former companies.   I'll elide the details, but this involved compiling the compiler first with the C compiler and then recompiling the compiler source with the newly created compiler binary. No great shakes here -- I'm sure many of you have done a similar bootstrap.  

The regression test suite pretty much sucked at the time so it was never clear where the bugs were.  I would compile the compiler one more time and diff the binaries as a paranoia check.  In the end, though,  I was never really certain of the impact of a bug in the compiler that compiled itself or a bug in the resultant compiler that was used to compile the source base of what was arguably the largest software system in the world at the time.  

And what about the C compiler used to build the first rev of the compiler?  And the compiler to build that compiler?  And the compiler to build that compiler?  In the end, It's Turtles All the Way Down!  (Well, maybe terminating at Grace Hopper's first compiler.  :-))

Looking for some comfort, I dug up this paper --   Ken Thompson's Turing Award lecture.  This, of course, made me even more paranoid.  At best, "It's Turtles All the Way Down" and you can't find the bugs. Or, worse,  there lurks some mischief  on the way down that you'll never find.  Sometimes it shakes my confidence to the core that we provably can't trust our computations....

[Two hours have passed.  I'm over it as I happily hack away, content that nothing so awful would have a practical impact....Could it?]

About this Entry

This page contains a single entry by published on November 6, 2007 9:44 PM.

Richland, Washington was the previous entry in this blog.

Isaac Salzman is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.

Categories

Powered by Movable Type 4.34-en