A Quine in Common Lisp

— a Toy

Rolling the die

As outlined in the last post on skill acquisition, I have embarked on a relative mass binge of making assorted programs. Because it’s hard to know the relative complexity of programs before attacking them, and because I might inadvertently self-reinforce strong and weak areas by choosing projects that focus on what I already know by coming up with practice projects on my own, I have instead pulled projects from the following graphic:

​Well, mine has 21 items crossed out with ugly green lines now.

I won’t write posts on all the noob programming projects, because several are very trivial. But as intended, they’ve forced me to take a look at things I probably would have postponed elsehow, e.g. IO, time handling. But some of the projects sound fairly sizable, and some have been really fun.

Like when I rolled a 74: Quine.

What is a quine?

Quines are programs that print their own source code. But it’s cheating if the program accesses its own source code in order to do so. wiki.c2.com has a nice write-up on quines: Starting with “Why are quines so interesting? Because they are “obviously impossible”.” and ending with “Obviously.”.

Anyhow, quines really do exist, and there’s even a proof of their existence. A theoretical proof relying on computability and the fixed-point theorem, neither of which I know much (yet?). Previous (minimal) experience with finding fixed-points of functions, i.e., the numerous plays with Newton’s method in SICP made it seem to me as if just starting with something that outputs something and then gradually refining as I went along would eventually work out.

Finally… The quine!

The blind guess gradual refinement plan did work out. But I forgot to record the steps underway. Suffice to say, it took me two hours of poking and prodding and trying out minor variations and discovering I definitely needed more variables, and then tweaking those into behaving. I’m fairly certain I started out with the following, though:

(let ((s "format t ~S"))
  (format t "~S" s))

And then I improved on it until the only thing off was the actual direct format string… And then I went through another bout of having to change up what almost-worked up to that point to make room for the rest. Anyhow, here’s the quine itself as I wrote it:

(let ((s "(format t ~A")
      (l "~@?~S))~%  ~@?~A))~%")
      (u " r s l u r s (string 'l) u")
      (r "(let ((s ~S)~%      (l ~S)~%      (u ~S)~%      (r "))
  (format t L r s l u r s (string 'l) u))

Not particularly elegant, but, in a way, really really neat anyhow. And it taught me about the ~? and ~@? format controls.

Anyhow, after succeeding, I searched for common lisp quines online and found that there exists a much, much eleganter approach, which uses quoted data instead of clumsy strings, and a particularly tricky one using a circular list. Maybe I could have arrived at one of those if my blind guess had been elsewhere!