What is a "Lisp program that writes other programs"?

Question

While reading through Paul Graham's Essays, I've become more and more curious about Lisp.

In this article, he mentions that one of the most powerful features is that you can write programs that write other programs.

I couldn't find an intuitive explanation on his site or elsewhere. Is there some minimal Lisp program that shows an example of how this is done? Or, can you explain in words what this means exactly?

Answer 1

A good example are Lisp macros. They aren't evaluated, but instead they transform to the expressions within them. That is what makes them essentially programs that write program. They transform the expressions within them between compile-time and runtime. This means that you can essentially create your own syntax since a macro isn't actually evaluated. A good example would be this invalid common lisp form:

(backwards ("Hello world" nil format))

Clearly the syntax for the format function is backwards. BUT... we are passing it to a macro which isn't evaluated, so we will not get a backtrace error, because the macro isn't actually evaluated. Here is what our macro looks like:

 (defmacro backwards (expr)
   (reverse expr))

As you can see, we reverse the expression within the macro, which is why it becomes a standard Lisp form between compile-time and runtime. We have essentially altered the syntax of Lisp with a simple example. The call to the macro isn't evaluated, but is translated. A more complex example would be creating a web page in html:

(defmacro standard-page ((&key title href)&body body)
   `(with-html-output-to-string (*standard-output* nil :prologue t :indent t)
       (:html :lang "en"
      (:head
        (:meta :charset "utf-8")
        (:title ,title)
        (:link :rel "stylesheet"
           :type "text/css"
           :href ,href))
     ,@body)))

We can essentially create a macro, and the call to that macro will not be evaluated, but it will expand to valid lisp syntax, and that will be evaluated. If we look at the macro expansion we can see that the expansion is what is evaluated:

(pprint (macroexpand-1 '(standard-page (:title "Hello"
                     :href "my-styles.css")
              (:h1 "Hello world"))))

Which expands to:

(WITH-HTML-OUTPUT-TO-STRING (*STANDARD-OUTPUT* NIL :PROLOGUE T :INDENT T)
  (:HTML :LANG "en"
     (:HEAD (:META :CHARSET "utf-8") (:TITLE "Hello")
     (:LINK :REL "stylesheet" :TYPE "text/css" :HREF "my-styles.css"))
     (:H1 "Hello world")))

This is why Paul Graham mentions that you can essentially write programs that write programs, and ViaWeb was essentially one big macro. A bunch of macros like this writing code that could write code that could write code...

Answer 2

While homoiconicity is the fundamental property that makes this easy, a good example of this in practice is the macro facility present in many lisps. Homoiconicity allows you to write lisp functions that take lisp source (represented as lists of lists) and do list manipulation operations on it to produce other lisp source. A macro is a plain lisp function for doing this which is installed into the compiler/evaluator of your lisp as an extension of the language's syntax. The macro gets called like a normal function, but instead of waiting until runtime the compiler passes the raw code of the macro's arguments to it. The macro is then responsible for returning some alternative code for the compiler to process in its place.

A simple example is the built-in when macro, used like so (assuming some variable x):

(when (evenp x)
  (print "It's even!")
  (* 5 x))

when is similar to the more fundamental if, but where if takes 3 sub-expressions (test, then-case, else-case) when takes the test and then an arbitrary number of expressions to run in the "then" case (it returns nil in the else case). To write this using if you need an explicit block (a progn in Common Lisp):

(if (evenp x)
    (progn
      (print "It's even!")
      (* 5 x))
    nil)

Translating the when version to the if version is some very simple list-manipluation:

(defun when->if (when-expression)
  (list 'if
        (second when-expression)
        (append (list 'progn)
                (rest (rest when-expression)))))

Although I'd probably use the list templating syntax and some shorter functions to get this:

(defun when->if (when-expression)
  `(if ,(second when-expression) (progn ,@(cddr when-expression)) nil))

This gets called like so: (when->if (list 'when (list 'evenp 'x) ...)).

Now all we need to do is inform the compiler that when it sees an expression like (when ...) (actually I'm writing one for (my-when ...) to avoid clashing with the built-in version) it should use something like our when->if to turn it into code it understands. The actual macro syntax for this actually lets you take apart the expression/list ("destructure" it) as part of the arguments of the macro, so it ends up looking like this:

(defmacro my-when (test &body then-case-expressions)
  `(if ,test (progn ,@then-case-expressions) nil))

Looks sorta like a regular function, except it's taking code and outputting other code. Now we can write (my-when (evenp x) ...) and everything works.

The lisp macro facility forms a major component of the expressive power of lisps- they allow you to mold the language to better suit your project and abstract away nearly any boilerplate. Macros can be as simple as when or complex enough to make a third-party OOP library feel like a first-class part of the language (in fact many lisps still implement OOP as a pure lisp library as opposed to a special component of the core compiler, not that you can tell from using them).

Answer 3

Lisp is homoiconic. Here is a function which build an s-expression representing a sum.

(defun makes(x) (list '+ x 2))

so (makes 5) evaluates to (+ 5 2) which is a valid s-expression. You could pass that to eval

There are more complex examples with Lisp macros. See also this. Read the section on Evaluation and Compilation of Common Lisp HyperSpec (also notice its compile, defmacro, eval forms). Be aware of multi-staged programming.

I strongly recommend reading SICP (it is freely downloadable) then Lisp In Small Pieces. You could also enjoy reading Gödel, Escher, Bach.... and J.Pitrat's blog on Bootstrapping Artificial Intelligence.

BTW, with C on POSIX, you might also code programs generating C code (or use GCCJIT or LLVM), compiling that generated code as a plugin, and dlopen-ing it.