EXPLAIN EXTENDED

This year, I'll be implementing a Lisp interpreter in SQL.

Now, what's Lisp, and why would I want to do that? Well, let me tell you a little story about that.

Several decades ago, I got a New Year's present from my roommate's girlfriend. It was a book. She got it at a used bookstore in the UK. She wasn't sure what to get me, so she turned for advice to the store clerk. He asked her what kind of person I was, and she aptly described me as "a guy who loves math and mutters to himself". The clerk, without batting an eyelash, handed her a book with a yellow bird on its cover and told her I would like it.

He turned out to be right. I did like the book. It was written by Raymond M. Smullyan, and its title was "To Mock a Mockingbird".

By that time, I was already familiar with the author. I had read his books before. They were collections of logic puzzles, set in the now-popular Knights-and-Knaves world of his own invention. "To Mock a Mockingbird", at first glance, was the same. Its first two chapters were collections of logic puzzles as well. The puzzles weren't too easy, nor were they too hard. Each of them would make you flex your brain just the right amount. Back then, I used to commute a lot every day, and these puzzles turned out to be perfect time killers during long commutes. It took me something like two weeks to get through the first two chapters.

The third chapter, as is typical for the genre, started with a preface explaining the setup. Instead of knights and knaves, this chapter had a forest inhabited by magic birds. The birds are programmed to call out each other's names. When, say, a finch hears "parrot", it would (always) respond with "jay". When a parrot would hear "jay", it would say "crane", and so on, and so forth. All the birds have to say something when they hear another bird's name. This chain never stops.

The very first puzzle introduced a couple of conditions (which didn't look like much), and asked to prove some facts about the birds.

At first, I thought it would be the same old, same old. It wasn't. I couldn't solve it. Not in five minutes, not in an hour, not in a day.

I lost sleep for a week.

I had been reading a lot of math puzzle books, so I sort of knew there were math concepts behind the fantasy setup. It was obviously some kind of logic. I was pretty good with regular, first-order logic. It was easy. There's data: numbers and facts. There are functions, or formulas, which operate on the data. The two never mix. You can add two numbers together, or you can combine two theorems to prove a new one. But you can't "subtract" the Pythagorean theorem from the law of the excluded middle, or "multiply" Bézout's lemma by two; it doesn't make sense. You know exactly what's what.

With those damned birds, all the bets were off. If it's logic, are the birds data or functions in that logic? Remember the finch. It hears "parrot", it says "jay". It maps one to the other. When something maps things to things, it's a function, so "parrot" and "jay" must be data. Ok, parrots are data. But at the same time, the parrot maps "jay" to "crane", so the parrot is a function. So now the birds are functions? And the data? Should we put their name in quotes when they're data? Double quotes when they're a function again? It never stops. You think you've put your finger on it, and then it eludes you again.

It wasn't just that I couldn't find the solution; I didn't even know where to start looking. I spent (I believe) two months of my life pondering this problem. And then, in a surge of inspiration, I just saw the solution, clear as day. I still remember where I was at that moment.

The book had promised that the solution would be "extremely ingenious". It was. To this day, the fact that I found it without looking it up fills me with pride. I won't spoil it for you. I'll leave finding the book and going through the same experience as an exercise for the curious reader.

That exact feeling came back to me several times after that.

I had that feeling when I started learning programming and came across the concept of first-class functions. Store functions as if they were data? Call a variable as if it were a function? What a weird idea at first! And what a brilliant one, when you start thinking about it.

I had it again when I came across what turned out to be the theory behind the bird puzzles: the lambda calculus and its evil twin, the combinatory logic. It takes the idea of combining data and functions to the extreme: There's no data at all, only functions. There's no starting point, nor the stopping one; it's the functions all the way down. And yet, if you're clever enough, you can build arithmetic, algebra, and programming languages using only these functions that have no beginning and no end.

And then I had it again, almost as a déjà vu, when I first came across Lisp.
Read the rest of this entry »