Lisp: Tears of Joy, Part 5

If you tile a floor with tiles the size of your thumbnail, you don’t waste many.
— Paul Graham

Doug Hoyte, creator of Antiweb gives a lot of credit to macros for efficient Lisp performance. He says that while other languages give you small, square tiles, Lisp lets you pick tiles of any size and of any shape. With C, programmers use a language that is directly tied to the capabilities of a fancy fixnum adder. Aside from procedures and structures, little abstraction is possible in C. By contrast, Lisp was not designed around the capabilities and limitations of the machines.

Instead of inquiring what makes a program fast, it’s better to ask what makes a program slow. The root causes can be roughly classified into three broad categories: (1) bad algorithms, (2) bad data structures, (3) and general code.

All language implementations need good algorithms. An algorithm is a presumably well-researched procedural description of how to execute a programming task. Because the investment required in coming up with an algorithm is so much larger than that of implementing one, the use of algorithms is ubiquitous throughout all of computer science.

Somebody has already figured out how, why, and how quickly, an algorithm works; all you have to do to use an algorithm is translate its pseudo-code into something that your system can understand.

Because Common Lisp implementations have typically been well implemented and continuously improved upon for decades, they generally employ some of the best and quickest algorithms around for most common tasks.

Good data structures are also necessary for any decent programming language. Data structures are so important that ignoring them will cause any language implementation to slow down to a crawl. Optimising data structures essentially comes down to a concept called locality — which basically says that data that is accessed most frequently should be the fastest to access.

Data structures and locality can be observed clearly at almost every level of computing where performance gains have been sought: large sets of CPU registers, memory caches, databases, and caching network proxies, to name a few. Lisp offers a huge set of standard data structures, and they are generally implemented very well.

If Lisp provides such good algorithms and data structures, how is it even possible that Lisp code can be slower than code in other languages? The explanation is based on the most important design decision of Lisp, i.e., general code, a concept otherwise familiar to us as duality of syntax. When we write Lisp code, we use as many dualities as possible; the very structure of the language encourages us to do so.

Why are Lisp programs usually much shorter than programs in other programming languages? Part of the reason is because any given piece of Lisp code can be used for so much more than a corresponding piece of code in another language, that you reuse it more often. From the perspective of someone more familiar with another programming language, it can feel strange to have to write more to get less, but this is an important Lisp design decision — duality of syntax.

The more dualities attached to each expression, the shorter a program seems to be. Does this mean that to achieve or exceed C’s performance, we need to make our Lisp programs as long and dangerous as their corresponding C programs? No, Lisp has macros.

So, enough of selling the concept; let’s get down to it, shall we? We’ll start with some basics.

Lambda—anonymous function

At times, you’ll need a function in only one place in your program. You could create a function with defun and call it just once. Sometimes, this is the best thing to do because you can give the function a descriptive name that will help you read the program at some later date.

But sometimes the function you need is so trivial or so obvious that you don’t want to have to invent a name, or worry about whether the name might be in use somewhere else. For situations like this, Lisp lets you create an unnamed, or anonymous, function, using the lambda form.

A lambda looks like a defun form without the name:

(lambda (a b c n)
    (+ (* a (* n n)) (* b n)))

You can’t evaluate a lambda form; it must appear only where Lisp expects to find a function—normally, as the first element of a form:

> (lambda (a b c n)
     (+ (* a (* n n)) (* b n)))
#<anonymous interpreted function 21AE8A6A>

> ((lambda (a b c n)
     (+ (* a (* n n)) (* b n)))
      1 3 5 7)
70

Macro

The term “macro” does not have the same meaning in Lisp as it has in other languages. A Lisp macro can be anything from an abbreviation to a compiler for a new language. Macros (in the Lisp sense) are still unique to Lisp. This is partly because in order to have macros, you probably have to make your language look as strange as Lisp.

It may also be because if you do add that final increment of power, you can no longer claim to have invented a new language, but only a new dialect of Lisp. If you define a language that has car, cdr, cons, quote, cond, atom, eq, and a notation for functions expressed as lists, then you can build all the rest of Lisp out of it. This is, in fact, the defining quality of Lisp: it was in order to make this possible that McCarthy gave Lisp the shape it has.

Because macros can be used to transform Lisp into other programming languages and back, you’d soon discover that all other languages are just skins on top of Lisp. Programming with Lisp is programming at a higher level. Where most languages invent and enforce syntactic and semantic rules, Lisp is general and malleable. With Lisp, you make the rules.

A defmacro form looks like a defun form. It has a name, a list of argument names, and a body. The macro body returns a form to be evaluated. In other words, you need to write the body of the macro such that it returns a form, not a value. When Lisp evaluates a call to your macro, it first evaluates the body of your macro definition, and then evaluates the result of the first evaluation. By way of comparison, a function’s body is evaluated to return a value.

> (defmacro setq-literal (place literal)
    `(setq, place ', literal))
SETQ-LITERAL

>(setq-literal a b)
B

> a
B

> (defmacro reverse-cons (rest first)
`(cons, first, rest))
REVERSE-CONS

>(reverse-cons nil a)
(B)

setq-literal works like setq, except that neither argument is evaluated. Remember that setq evaluates its second argument. The body of setq-literal has a form that begins with a ` (backtick). A backtick behaves like quote — suppressing evaluation of all the enclosed forms — except where a comma appears within the backticked form. A symbol following the comma is evaluated.

So, in our call to (setq-literal a b) above, this is what needs to be done:

1. Bind place to the symbol a.
2. Bind literal to the symbol b.
3. Evaluate the body `(setq, place ', literal), following these steps:
   • Evaluate place to get the symbol a.
   • Evaluate literal to get the symbol b.
   • Return the form (setq a 'b).

Neither the backtick nor the commas appear in the returned form. Neither a nor b is evaluated in a call to setq-literal, but for different reasons; a is unevaluated because it appears as the first argument of setq; b is unevaluated because it appears after a quote in the form returned by the macro.

The operation of (reverse-cons nil a) is similar:

1. Bind rest to the symbol nil.
2. Bind first to the symbol a.
3. Evaluate the body `(cons, first, rest), following these steps:
   • Evaluate first to get the symbol a.
   • Evaluate rest to get the symbol nil.
   • Return the form (cons a nil).

Both arguments of reverse-cons are evaluated because cons evaluates its arguments, and our macro body doesn’t quote either argument. a evaluates to the symbol b, and nil evaluates to itself.

Macro expansion

Lisp evaluates the code produced by the macro immediately. Therefore, when you use a macro, you get to see only the result of the entire evaluation of the macro, but you do not get to see the code produced by the macro along the way.

Since it is sometimes useful in debugging to view this intermediate code, Lisp provides us with a way of doing so. The function macroexpand takes as input an s-expression that may be a call to a macro. If it is, macroexpand will apply the macro to its arguments to produce the object code. It will not evaluate this code, but merely return it.

The Lisp interpreter uses macroexpand to expand a call to a macro that it is trying to evaluate. Using this function will give you an accurate picture of what the Lisp interpreter itself sees.

Here’s how it works for the example given above:

> (macroexpand '(setq-literal a b))
(SETQ A (QUOTE B))
T

> (macroexpand '(reverse-cons nil a))
(CONS A NIL)
T

Since macroexpand is a function, it evaluates its arguments. This is why you have to quote the form you want expanded.

A convenient macro

It is generally appropriate to enclose function arguments inside a call to the special function. In particular, the expression (function (lambda...)) occurs frequently. Common Lisp allows the shorthand #'x to stand for (function x), just as 'x stands for (quote x). Let’s write a special macro to help abbreviate this particular combination. We can define a macro flambda that expands into (function (lambda...)) as follows:

> (defmacro flambda (&rest l)
       (list 'function (cons 'lambda l)))
FLAMBDA

> (macroexpand '(flambda (x y) (cons y x)))
(FUNCTION (LAMBDA (X Y) (CONS Y X)))
T

Since a lambda expression may contain any number of forms, we used the &rest parameter designator to define a rest parameter. This parameter will get assigned the list of all the arguments supplied to flambda. For example, in the call to flambda above, the rest parameter l gets assigned the value ((x y) (cons y x)). flambda then just sticks the atom lambda on the front of this list, and then puts the resulting lambda expression in a list that begins with the symbol function. Thus, the sample “flambda expression” given above as an argument to macroexpand can be seen as a shorthand for writing the full (function (lambda...)) call.

pop

A more interesting function is the macro pop, which takes as its arguments a symbol whose value is a list. It reduces this list to its cdr, and returns the first element of the list as its value. In effect, pop treats the list like a stack, and pops off its top element. A call to pop is equivalent to executing the following piece of code:

> (prog1 (car stack) (setq stack (cdr stack)))

The function prog1 evaluates all its arguments in sequence, returning the value of the first one. Thus, for any particular list, you can execute a line of code like the one shown above, which carries out the desired function. What you could do is define a macro that expands into code of this form. Thus you can get (pop stack) to expand into the prog1 shown above.

pop is actually defined in Common Lisp. Here, we will write our own definition of the function, for the purpose of an example:

> (defmacro example-pop (stack)
       (list 'prog1
           (list 'car stack)
            (list 'setq stack (list 'cdr stack))))
EXAMPLE-POP

Let’s see how the macro works:

> (setq stack '(a b c))
(A B C)

> (example-pop stack)
A

> stack
(B C)

example-pop returned the first element of stack as its value. In addition, it reduced stack to its cdr. Note that it would be difficult to write this as an ordinary function, since it needs to get at the actual stack name to change its value.

You would always have to quote the name of the stack you were passing, because arguments supplied to ordinary functions always get evaluated. However, with macros, this was not a problem.

Special functions and macros

Many of the so-called special functions are actually macros. Most notably, the functions defun, prog, cond, setf and defmacro itself are all Common Lisp macros. For example, a call to setf turns into a call to a more basic assignment function — a call to setf, whose first argument is a symbol, turns into a setq, as follows:

> (macroexpand '(setf a 'b))
(SETQ A 'B)

However, if the left-hand side of the call to setf is a call to the function get, the setf turns into a call to some internal Common Lisp property-list-changing function.

Remember that the line between macros and special functions is rather thin. A Common Lisp implementation may implement some special functions as macros, and some macros as special forms — although it must still provide a macro definition in the latter case.

The use of macros is limited only by your own creativity. While you get creative with macros, I will tweak my example code — snippets for the next article, where I will discuss recursion, closures, and advanced macros. Enjoy playing God with the machine world.