Lisp in the real world

To give the short answer, macros are used for defining language syntax extensions to Common Lisp or Domain Specific Languages (DSLs). These languages are embedded right into the existing Lisp code. Now, the DSLs can have syntax similar to Lisp (like Peter Norvig's Prolog Interpreter for Common Lisp) or completely different (e.g. Infix Notation Math for Clojure).

Here is a more concrete example:
Python has list comprehensions built into the language. This gives a simple syntax for a common case. The line

divisibleByTwo = [x for x in range(10) if x % 2 == 0]

yields a list containing all even numbers between 0 and 9. Back in the Python 1.5 days there was no such syntax; you'd use something more like this:

divisibleByTwo = []
for x in range( 10 ):
   if x % 2 == 0:
      divisibleByTwo.append( x )

These are both functionally equivalent. Let's invoke our suspension of disbelief and pretend Lisp has a very limited loop macro that just does iteration and no easy way to do the equivalent of list comprehensions.

In Lisp you could write the following. I should note this contrived example is picked to be identical to the Python code not a good example of Lisp code.

;; the following two functions just make equivalent of Python's range function
;; you can safely ignore them unless you are running this code
(defun range-helper (x)
  (if (= x 0)
      (list x)
      (cons x (range-helper (- x 1)))))

(defun range (x)
  (reverse (range-helper (- x 1))))

;; equivalent to the python example:
;; define a variable
(defvar divisibleByTwo nil)

;; loop from 0 upto and including 9
(loop for x in (range 10)
   ;; test for divisibility by two
   if (= (mod x 2) 0) 
   ;; append to the list
   do (setq divisibleByTwo (append divisibleByTwo (list x))))

Before I go further, I should better explain what a macro is. It is a transformation performed on code by code. That is, a piece of code, read by the interpreter (or compiler), which takes in code as an argument, manipulates and the returns the result, which is then run in-place.

Of course that's a lot of typing and programmers are lazy. So we could define DSL for doing list comprehensions. In fact, we're using one macro already (the loop macro).

Lisp defines a couple of special syntax forms. The quote (') indicates the next token is a literal. The quasiquote or backtick (`) indicates the next token is a literal with escapes. Escapes are indicated by the comma operator. The literal '(1 2 3) is the equivalent of Python's [1, 2, 3]. You can assign it to another variable or use it in place. You can think of `(1 2 ,x) as the equivalent of Python's [1, 2, x] where x is a variable previously defined. This list notation is part of the magic that goes into macros. The second part is the Lisp reader which intelligently substitutes macros for code but that is best illustrated below:

So we can define a macro called lcomp (short for list comprehension). Its syntax will be exactly like the python that we used in the example [x for x in range(10) if x % 2 == 0] - (lcomp x for x in (range 10) if (= (% x 2) 0))

(defmacro lcomp (expression for var in list conditional conditional-test)
  ;; create a unique variable name for the result
  (let ((result (gensym)))
    ;; the arguments are really code so we can substitute them 
    ;; store nil in the unique variable name generated above
    `(let ((,result nil))
       ;; var is a variable name
       ;; list is the list literal we are suppose to iterate over
       (loop for ,var in ,list
            ;; conditional is if or unless
            ;; conditional-test is (= (mod x 2) 0) in our examples
            ,conditional ,conditional-test
            ;; and this is the action from the earlier lisp example
            ;; result = result + [x] in python
            do (setq ,result (append ,result (list ,expression))))
           ;; return the result 
       ,result)))

Now we can execute at the command line:

CL-USER> (lcomp x for x in (range 10) if (= (mod x 2) 0))
(0 2 4 6 8)

Pretty neat, huh? Now it doesn't stop there. You have a mechanism, or a paintbrush, if you like. You can have any syntax you could possibly want. Like Python or C#'s with syntax. Or .NET's LINQ syntax. In end, this is what attracts people to Lisp - ultimate flexibility.

Matt's explanation is perfectly fine -- and he takes a shot at a comparison to C and Java, which I won't do -- but for some reason I really enjoy discussing this very topic once in a while, so -- here's my shot at an answer.

On points (3) and (4):

Points (3) and (4) on your list seem the most interesting and still relevant now.

To understand them, it is useful to have a clear picture of what happens with Lisp code -- in the form of a stream of characters typed in by the programmer -- on its way to being executed. Let's use a concrete example:

;; a library import for completeness,
;; we won't concern ourselves with it
(require '[clojure.contrib.string :as str])

;; this is the interesting bit:
(println (str/replace-re #"\d+" "FOO" "a123b4c56"))

This snippet of Clojure code prints out aFOObFOOcFOO. Note that Clojure arguably does not fully satisfy the fourth point on your list, since read-time is not really open to user code; I will discuss what it would mean for this to be otherwise, though.

So, suppose we've got this code in a file somewhere and we ask Clojure to execute it. Also, let's assume (for the sake of simplicity) that we've made it past the library import. The interesting bit starts at (println and ends at the ) far to the right. This is lexed / parsed as one would expect, but already an important point arises: the result is not some special compiler-specific AST representation -- it's just a regular Clojure / Lisp data structure, namely a nested list containing a bunch of symbols, strings and -- in this case -- a single compiled regex pattern object corresponding to the #"\d+" literal (more on this below). Some Lisps add their own little twists to this process, but Paul Graham was mostly referring to Common Lisp. On the points relevant to your question, Clojure is similar to CL.

The whole language at compile time:

After this point, all the compiler deals with (this would also be true for a Lisp interpreter; Clojure code happens always to be compiled) is Lisp data structures which Lisp programmers are used to manipulating. At this point a wonderful possibility becomes apparent: why not allow Lisp programmers to write Lisp functions which manipulate Lisp data representing Lisp programmes and output transformed data representing transformed programmes, to be used in place of the originals? In other words -- why not allow Lisp programmers to register their functions as compiler plugins of sorts, called macros in Lisp? And indeed any decent Lisp system has this capacity.

So, macros are regular Lisp functions operating on the programme's representation at compile time, before the final compilation phase when actual object code is emitted. Since there are no limits on the kinds of code macros are allowed to run (in particular, the code which they run is often itself written with liberal use of the macro facility), one can say that "the whole language is available at compile time".

The whole language at read time:

Let's go back to that #"\d+" regex literal. As mentioned above, this gets transformed to an actual compiled pattern object at read time, before the compiler hears the first mention of new code being prepared for compilation. How does this happen?

Well, the way Clojure is currently implemented, the picture is somewhat different than what Paul Graham had in mind, although anything is possible with a clever hack. In Common Lisp, the story would be slightly cleaner conceptually. The basics are however similar: the Lisp Reader is a state machine which, in addition to performing state transitions and eventually declaring whether it has reached an "accepting state", spits out Lisp data structures the characters represent. Thus the characters 123 become the number 123 etc. The important point comes now: this state machine can be modified by user code. (As noted earlier, that's entirely true in CL's case; for Clojure, a hack (discouraged & not used in practice) is required. But I digress, it's PG's article I'm supposed to be elaborating on, so...)

So, if you're a Common Lisp programmer and you happen to like the idea of Clojure-style vector literals, you can just plug into the reader a function to react appropriately to some character sequence -- [ or #[ possibly -- and treat it as the start of a vector literal ending at the matching ]. Such a function is called a reader macro and just like a regular macro, it can execute any sort of Lisp code, including code which has itself been written with funky notation enabled by previously registered reader macros. So there's the whole language at read time for you.

Wrapping it up:

Actually, what has been demonstrated thus far is that one can run regular Lisp functions at read time or compile time; the one step one needs to take from here to understanding how reading and compiling are themselves possible at read, compile or run time is to realise that reading and compiling are themselves performed by Lisp functions. You can just call read or eval at any time to read in Lisp data from character streams or compile & execute Lisp code, respectively. That's the whole language right there, all the time.

Note how the fact that Lisp satisfies point (3) from your list is essential to the way in which it manages to satisfy point (4) -- the particular flavour of macros provided by Lisp heavily relies on code being represented by regular Lisp data, which is something enabled by (3). Incidentally, only the "tree-ish" aspect of the code is really crucial here -- you could conceivably have a Lisp written using XML.