Tuesday, 1 December 2009

On Quines

Writes Code Which, When Run, ...

This is mind blowing. Yusuke Endoh has written a very interesting computer program. In fact, he has written a whole series of them: eleven in all.

What's interesting about these programs is that, first of all, each of them is written in a different computer language. That fact alone qualifies him as a clever chap. Then there's the range of languages he used: some are fairly common (Ruby, Python, Perl, C, Java), others somewhat more exotic (Lua, OCaml, Haskell), still others downright esoteric (brainfuck, Whitespace, Unlambda). Clearly, he's actually a very clever chap.

But when you look at his set of eleven little programs, each in its own different language, and when you realise exactly what they do, then you are forced to conclude that Yusuke Endoh is in fact a very, very clever chap. Because what every program in this set does, when you run it, is to print out the source code of the "next" program in the set.

Imagine these eleven programs arranged in a circle. Each one, when run, prints a copy of the source code of the next one.

I suppose you could look at it another way: he actually only had to write one of these programs. Then he could run that to obtain the second, then run the second to obtain the third, and so on. But wait a minute, doesn't that mean that when he runs the eleventh program, its output will be just the source code for the very first one?

Yes, that's right. There was actually no need for him to write anything at all. These are eleven self-generating sources. What a lazy guy!

Picture: MC Mechanic by Shane Willis.

Here's the link to his blog article. In the (English!) comments you'll see that he actually wrote, in the sense of "putting effort into the crafting of", two of the sources, the diametrically opposed Ruby and the Haskell; then effectively infilled to complete a cycle:

A computer program which prints out a source code copy of itself is called a Quine, after America's most influential Harvard philosopher and logician, Willard Van Orman Quine. So, this is a kind of generalisation of a Quine program.

Here's another description of Yusuke-san's achievement, for those like me whose knowledge of languages does not extend to Japanese. Note the comment from Professor Quine's son Douglas, at the foot of the article:

The association with Quine comes from his famous self-contradictory predicate, yields a falsehood when appended to its own quotation, which he used to investigate the linguistic anomalies underlying Russell's Paradox. Here of course we are concerned not so much with the paradox, as with the self-referential nature of the sentential fragment, which mirrors the self-replicating behaviour of the code.

Historical Note

I was lucky enough to enjoy brief correspondence with Professor Quine in the 80s, and also more recently with his son Dr Douglas Quine, who recommended to me Quiddities: An Intermittently Philosophical Dictionary as a sampler of his father's humour, insight and intellect.

And that's a great read; but my favourite Quine works are still The Ways Of Paradox and other essays, in which I was first exposed to the genius of Alfred Tarski, and the Lambda Calculus, at a dangerously young age; and Methods Of Logic, which first convinced me computers could solve problems using predicate calculus (though it wasn't until several years later that I finally got my hands on a Prolog system).

Decades after you've absorbed whatever technical content you needed from their pages, you can still reread those books for their astute, elegant, lucid and entertaining prose style.

No comments:

Post a Comment