The last time Hackerfall tried to access this page, it returned a not found error. A cached version of the page is below, or clickhereto continue anyway

How to Generate Self-Referential Programs - Macrology

In this post, I am going to show you how to write programs that are self-referential. By self-referential, I mean programs which are able to obtain their own source code without any external input. In other words, they won’t just read from their own files. This post is based on section 6.1 of the bookIntroduction to the Theory of Computation.

Before we can start generating self-referential programswe are first going to need sometechniques for generating programs in general. The first techniquewe need is a method of taking a given program and writing a second program that outputs the given program.As an example, given (+ 2 2), we would need to writea program that outputs (+ 2 2). In most languages this is easy. One way to do it in Lisp is to put a quote in front of the program:


'(+ 2 2)
=> (+ 2 2)

We are also going to need a functionthat automates this process. Such a function would take a program asits argument and return a new program that when ran, outputs the program that was originally passed to the function. In most languages doing this is fairly tricky. In Lisp, we can write this function easily through backquote:


(defun code-that-generates (program)
  `',program)

(code-that-generates '(+ 2 2))
=> '(+ 2 2)

If you don’t understand how backquote works, you can read this. Even though it’s for Emacs Lisp, everything there is still applicable to other Lisps. Just make sure that you understand thatcode-that-generates can be used to generate a program that outputs a given program.

Nowthat we have these two techniques, we can begin writing programs that are able to refer to themselves. The first self-referential program we will write will be an example of aquine. If you don’t know, a quine is a programthat outputsits own source code. The quine we are going to write is made up of two parts, part A and part B, where part A is a function that is applied to part B:


(A B)

To describe how the quine works, it is easiest to start with part B. All that part B needs to dois returnthe source code ofpart A:


(A 'A)

Part A’s job is to take its own source code, and use it to obtain the source code of the entire quine. Since B is a program that outputs A, A can usecode-that-generates on its own source code in order to obtain the source code ofB. OnceA has the source code ofboth A and B, it becomes trivial to combine the two to obtainthe source codeofthe entire quine. Here is the complete quine, with the call tocode-that-generates inlined:


((lambda (a)
   (let ((b `',a))
     `(,a ,b)))
 '(lambda (a)
    (let ((b `',a))
      `(,a ,b))))
=>
((lambda (a)
   (let ((b `',a))
     `(,a ,b)))
 '(lambda (a)
    (let ((b `',a))
      `(,a ,b))))

Now this is where things start getting interesting. A quine can be thought of as a program that generates its own source code, and immediately returns it. What if instead of immediately returning its own source code, the quine applied a function to it first, and then returned the result of that. The steps for building such a program are almost exactly the same as the steps we took for building the quine. This time, there is a third part F, for the function we want to call. The structure of the program will look like the following:


(F AB)

Where AB has a similar structure to our quine. After breaking AB into the two parts, A and B, theprogram looks like the following:


(F (A B))

Part B in the above program has the same responsibilities as B in the quine, it returns the source code for A:


(F (A 'A))

Then once A has the source code for itself, it can use code-that-generatesto obtain the source code for B. Now that it has the source of A and B, it is easy for it to construct AB. Once part A has the code for AB, it can easilygenerate the source of the entire program. Here is what the program becomes after filling in everything except F:


(F
 ((lambda (a)
    (let ((b `',a))
      (let ((ab `(,a ,b)))
        `(F ,ab))))
  '(lambda (a)
     (let ((b `',a))
       (let ((ab `(,a ,b)))
         `(F ,ab))))))

What makes this so awesome is that F can be any function we want, and the above program will run F with the source code of the entire program! For example, replacing F with identitycauses the program to become a quine:


(identity
 ((lambda (a)
    (let ((b `',a))
      (let ((ab `(,a ,b)))
        `(identity ,ab))))
  '(lambda (a)
    (let ((b `',a))
      (let ((ab `(,a ,b)))
        `(identity ,ab))))))
=>
(identity
 ((lambda (a)
    (let ((b `',a))
      (let ((ab `(,a ,b)))
        `(identity ,ab))))
  '(lambda (a)
    (let ((b `',a))
      (let ((ab `(,a ,b)))
        `(identity ,ab))))))

But we can also do some much more impressive things. We can replace F with a function that lists its argument twice, and get a program that returns a list containing its own source code twice:


((lambda (x) (list x x))
 ((lambda (a)
    (let ((b `',a))
      (let ((ab `(,a ,b)))
        `((lambda (x) (list x x)) ,ab))))
  '(lambda (a)
     (let ((b `',a))
       (let ((ab `(,a ,b)))
         `((lambda (x) (list x x)) ,ab))))))

=>

(((lambda (x) (list x x))
  ((lambda (a)
     (let ((b `',a))
       (let ((ab `(,a ,b)))
         `((lambda (x) (list x x)) ,ab))))
   '(lambda (a)
      (let ((b `',a))
        (let ((ab `(,a ,b)))
          `((lambda (x) (list x x)) ,ab))))))
 ((lambda (x) (list x x))
  ((lambda (a)
     (let ((b `',a))
       (let ((ab `(,a ,b)))
         `((lambda (x) (list x x)) ,ab))))
   '(lambda (a)
      (let ((b `',a))
        (let ((ab `(,a ,b)))
          `((lambda (x) (list x x)) ,ab)))))))

To make writing these self-referential programs easier, we can define a function that fills in F for us. It just requires a little nested backquote trickery.1


(defun self-referential-version-of (f)
  `(,f
     ((lambda (a)
        (let ((b `',a))
          (let ((ab `(,a ,b)))
            `(,',f ,ab))))
       '(lambda (a)
          (let ((b `',a))
            (let ((ab `(,a ,b)))
              `(,',f ,ab)))))))

(self-referential-version-of '(lambda (x) (list x x))
=>
((lambda (x) (list x x))
 ((lambda (a)
    (let ((b `',a))
      (let ((ab `(,a ,b)))
        `(,'(lambda (x) (list x x)) ,ab))))
  '(lambda (a)
     (let ((b `',a))
       (let ((ab `(,a ,b)))
         `(,'(lambda (x) (list x x)) ,ab))))))

Now that we’ve got a function that cangenerate self-referential programs for us, I am going to show you how to build something called aquine-relay. A quine-relay is like a normal quine, except it passes through multiple languages. The quine-relay we are going to write is a Lisp program that outputs a C program that outputs the original Lisp program.All we have to do is write a function that takes its argument and writes a C program that prints the argument it was given. Then we can pass thatfunction toself-referential-version-of to get the quine-relay! That’s it! Here is a program that will generate the quine-relay:


(self-referential-version-of
  '(lambda (self)
     (format t

"#include <stdio.h>~%int main(){printf(\"%s\",~(~s~));}"

             (remove #\newline (prin1-to-string self)))))

I’ve omitted the actual quine-relay for brevity, but you can find it here if you are curious. There are a few idiosyncrasies in the above program and in the quine-relay because of the differences in behavior between Lisp and C. For example, in C you can’t have multi-line strings, so it becomes easier to remove all of the newlines from the Lisp program, than it is to keep them.

And that’s all it takes to write self-referential programs. After seeing how easy it is to generate a quine-relay, it shouldn’t be hard to imagine how to write one with many more steps. You may even be able to get up to 100 if you work at it long enough.

  1. You may have noticed the extra comma and quote in front of F in the generated program. Although it doesn’t make a difference semantically itdoes make a different syntactically. Luckily, all of the code generated by a program with the extra comma and quote will also contain the extra comma and quote, so everything is okay.

Continue reading on malisper.me