Writing a Quine, in English and Lisp

I was reading the section on the Recursion Theorem for Turing machines in Sipser’s Introduction to the Theory of Computation, and enjoyed his “English language explanation” of the theorem enough that I thought I’d write it up briefly. Then, I’ll look at translating that into Lisp.

In English

The informal idea of the Recursion Theorem is that one can design Turing machines which act on their own descriptions (as a string of symbols on the tape). In other words, we can construct machines which exhibit a cetain sort of self-reference, even though there are no obvious “self-referential” primitives.

While the precise statement of that result requires some care, some intuition for it can be given in plain English. To start with, suppose we can write instructions down and they will be faithfully executed by some reader. So for example, if we write

Write "Hello, World"

then we expect that the diligent reader will write out

Hello world

Now, our goal will be to write some instructions which, when executed, will exactly reproduce themselves – therefore exhibiting a certain sort of self-reference. In English, this could perhaps be done with

Write this sentence

However, as an analogue for the sort of construction involved in the Recursion Theorem, this is inadequate: the word this in the above has a sort of function which cannot be immediately trnaslated into the language of Turing Machines. Indeed, figuring out how to express something akin to this is the whole point of the exercise!

Thinking about things for a moment, one might imagine splitting the instructions into two parts: a template (which is to be written), and an action (which commands that the template to be written). So for example, in

Write the following twice, the second time in quotes "Hello World"

we have output Hello World "Hello World".

With this in mind, one might consider making the template match the form of the action. One English-lanmguage solution to our puzzle is then

Write the following twice, the second time in quotes
"Write the following twice, the second time in quotes"

Well, in English at least, that wasn’t so hard!

A Translation to Lisp

Let’s try to translate this to actual code. Here I’m writing this in Common Lisp.

Now, something like Write "Hello World" could be implemented as (print '(hello world)), but I will prefer to forget about printing and simply to write an interesting expression which evaluates to itself. I say “interesting”, because although 2 evaluates to 2, that’s not really in the spirit of this exercise.

Here are some attempts at translating from English to Lisp:

;;; Write "Hello World"
'(hello world)

;;; Write the following sentence twice, the second time in quotes "Hello world"
((lambda (x) (list x `',x)) '(hello world))

;;; Write the following sentence twice, the second time in quotes
;;; "Write the following sentence twice, the second time in quotes"
((lambda (x) (list x `',x))
 '(lambda (x) (list x `',x)))

The end result is pretty short and sweet. This was not hard to write, provided that the English example is understood. The main choices involved were related to printing vs evaluating, and mostly how to handle quoting. As an aside, I initially forgot that one don’t need funcall to apply a lambda expression – that would also complicate things slightly.

This sort of program, which under evaluation prints out its source code, is called a Quine. The result we ended up here is almost exactly what is listed on the C2 Wiki, which I’m certain I must have seen before. It also is very strongly reminiscent of the Y Combinator. And for good reason too: these are both fixed points for evaluation. But still, these things are far more intelligible if you work them out for yourself.