Code that writes code that writes code

This is an exercise I used to test my first Lisp interpreter, in the mid-80s, when all I'd implemented were a few basic features of the language. (Exercise for the reader: try counting the language features.)

The following code defines a variable with its own name as its value. Implicit and explicit evaluations return the same value. However, eval can be applied to any value, even its own result. Each time eval is applied here, the result is the same value.

This next code defines a pair of variables that store each other's names. Implicit and explicit evaluations return the name of the other variable. Odd and even numbers of applications return different values.

You can think of the above example as two programs, each generating the other.

Here's an example with a curious problem.

It's an infinite loop!

All of the above code are simple examples of self generating programs, quines, programs that replicate their own code when you run them. In fact, it's little more than a demonstration of a language feature that let's you treat code as data, and data as code. You can do the same thing at the machine level, but a high level language makes it easier. By making it easier, we can push our code further, and so do much more with it.

The following program is taken from the quine page of TANAKA Tomoyuki:

((lambda (x) `(,x ',x)) '(lambda (x) `(,x ',x)))

If you look closely, you'll notice something not used so far: backquote. This is a very powerful yet simple to use feature that makes writing code that writes code easier to read. Writing code that writes code that writes code is just a matter of nesting backquotes.

This is an absurdly simple (and redundant) example:
``,,5 ==> 5

Anyway, here're some examples of the games you can play with the quine example. Results are omitted for clarity and because I'm lazy. Play with the code yourself and see what it does!

(set! q ((lambda (x) `(,x ',x)) '(lambda (x) `(,x ',x))))
(eval q)
(eval (eval q))
(eval (eval (eval (eval (eval (eval (eval (eval q))))))))

Let's add a value that changes with each level of evaluation.

(set! q ((lambda (x) `(let ((y 5)) (,x ',x))) '(lambda (x) `(let ((y ,(+ y 1))) (,x ',x)))))
(eval q)
(eval (eval q))
(eval (eval (eval (eval (eval (eval (eval (eval q))))))))

Each application of eval produces a new program, not merely a copy of the original. We get a sequence of programs generating programs:
p1 -> p2 -> p3 -> ... -> pN

Exercise: write a higher order function to create the sequence of programs. Hint: remember the infinite loop example from above. Make it finite.

Advanced exercise: write a simple interpreter (e.g. core Scheme or Lambda Calculus) that generates a quine for each "step". Hint: this might be done with a modified CPS transformation. Replace the continuations with quine-constructing combinators.

All of the examples so far have been simple and artificial. Each time you run a program, subtle transformation of the code gives you a slightly different program as the result. Either they produce the same value each time, or they alternate values, or they produce a simple series of values.

A not so subtle transformation uses the same principle. The code writing aspect of the program remains the same, while the specification of the program changes significantly with each run.

A transformation can produce a less general program, more specific to a particular problem. Each run stripes away a degree of abstraction. There are now a finite number of times you can apply this process before you get a program that solves a specific problem, or answers a specific question.

You might also write programs that read themselves and reject any other program. You might try to write programs that can identify such programs, but you'd be wandering into Turing Territory...

Anyway, back to programs that write programs. In theory, you can try this in any language. In practice, you'll find it easier in some than in others. In Scheme...simple, very fast. In C&bash...not so simple, very slow.

A few common examples of this are given below.

If you've ever used a laser printer, you may be familiar with this idea:

document -> postscript -> page
p1 -> p2 -> p3

The document, application, and a postscript printer driver shift the computation of the bitmap for the page from the user's computer to the printer. Note how the distinction between code and data are blurred. Many apps today can include code in the document itself.

If your web browser uses JavaScript, then you're seeing something similar. Look closer. Is that JavaScript generated by hand or CGI? Where did the HTML come from? It's not unusual to see HTML written by JavaScript written by CGI. Not only is it code that writes code that writes code (p1 -> p2 -> p3), but each step uses a different language (l1-> l2 -> l3).

Have you ever installed a compiler from source code? Which language was the compiler written in, and how was it compiled? Could the compiler compile itself?

Ken Thompson has explained some of the security implications. We've all heard of self replicating software embedded in documents. A new breed of self replicating documents are spreading via email. As for the Internet Worm...

So, it's more than just a clever game. A few people employ these techniques maliciously, most of us try to be more constructive, but we're all doing something creative.

We're making these simple machines solve more complex problems.