Self generating programs

To avoid spoiling your fun, all the code snippets on this page are encoded with a trivial ascii-friendly variant of the Caesar cipher (every ascii character between 32 and 127 encodes to the one following it, with 127 rolling back to 32; characters outside that range are left untouched). I didn't use rot13 because the bare punctuation would still have been too much of a visual clue anyway; you can of course write a decoder in Python in less time than it takes to read this sentence. Still, don't look at them unless you're really stuck. If you want to enjoy this pointless but fun hacker game, don't decode these solutions until you've got a working version of your own, or until you really feel you want to give up because you're not up to it. (What? Do you really believe this?) Some code snippets are hidden, because the challenge on them has been set at the Python conference, and I want to reveal the solutions gradually. So, while I'm in Texas, an automatic process will make them visible one by one (assuming I've got my at jobs right...).

I got interested in this topic sometime in 1997 when it was suggested as an exercise in a security book I was reading: write a program that, when run, will print out its source code. Of course I tried it in Python first. It took some head-scratching, but I eventually came up with a working Python one-liner [already revealed way back in 1997]. (It looked a lot simpler than the C solution in the book, not to mention shorter, and not just because it wasn't written in C.) And then I did another one in Tcl [already revealed way back in 1997], and a few little variants and stuff.

For one of those cosmic coincidences that nobody can explain, not more than a week after my first experiments we had a visit from the famous cryptographer Eli Biham, and on browsing his web page (Beware! Contains solutions in clear!) I discovered a section dedicated to this very topic. So I sent him the stuff I had just done, which he published in his collection.

For my talk at the 7th Python Conference presenting my "Tcl and Python" paper I wanted some sort of final firework to metaphorically illustrate my thesis that the two open-source communities of Tcl and Python, instead of viewing each other as competitors, would derive great benefits from looking at each other without prejudice, copying each other's best bits and learning from each other's mistakes. And it finally hit me that I could use the selfgen idea to illustrate this. So I set out to write a pair of programs, one in Tcl and one in Python, that would mutually generate each other. (I'm sure others will have had this idea before, though I have no reference for this, but as far as I was concerned it was original, in the sense that I (re)discovered it independently: there was no trace of it in the book or in Eli's collection.)

To flex my muscles, I first wrote a pair of (different) Python programs [revealed 1998-11-11 23:00 UTC, 17:00 Texas time] that would generate each other; and then a pair of Tcl programs [revealed 1998-11-11 21:00 UTC, 15:00 Texas time] that would do the same.

Finally I started working on the beast itself, using the same strategy as for the single-language mutual selfgen, but tweaking it to cater for the dual-language environment. Tweak, tweak, tweak... it took a lot of tweaking to get round all the problems that stemmed from the fact that the two languages had vastly different opinions on quoting. But finally, in the middle of the night (as happens with most hacking projects), climax! I had a working version! [revealed 1998-11-12 03:00 UTC, 23:00 prev day Texas time]This monstrosity had grown incrementally layer over layer like a cancer: not a pretty sight, to be sure, but I stared at it in awe, almost not believing that this pile of junk I had written actually ran and even worked, i.e. it reproduced itself after an intermediate generation in the other language.

The next day I received a much neater version [revealed 1998-11-12 21:00 UTC, 15:00 Texas time] conceived by my ORL colleague Andy Harter, who coded it together with Tristan Richardson and Quentin Stafford-Fraser.

He said he obtained it by just translating his basic lambda calculus idea. [revealed 1998-11-12 15:00 UTC, 09:00 Texas time]

He also added that one could obtain a "dual" pair [revealed 1998-11-12 21:00 UTC, 15:00 Texas time] by starting the translation from the other language, yielding a slightly different solution.

On seeing his beautiful lambda calculus expression I proposed another one in combinatory logic [revealed 1998-11-12 17:00 UTC, 11:00 Texas time], which as far as I can tell is the shortest selfgen so far produced in any language (only 8 characters, to once again follow up on the challenge on Eli's page, since my previous Python winner had been superceded by a shorter Postscript challenger).
Pedants will argue that neither the lambda calculus nor the combinatory logic programs really qualifies for the competition, since these expressions don't "print" anything (there is no print instruction in those languages); but they reduce to themselves, which is the closest you'll get... and anyway, the proof that they're doing the genuine stuff is that Andy derived his Python/Tcl solution simply by translating his lambda calculus one!


Back to Frank Stajano's home page

CSS Valid HTML 4.0! validated (recheck) Python powered