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.
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
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
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.
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:
placeto the symbol
literalto the symbol
- Evaluate the body
`(setq, place ', literal), following these steps:
placeto get the symbol
literalto get the symbol
- Return the form
(setq a 'b).
Neither the backtick nor the commas appear in the returned form. Neither
b is evaluated in a call to
setq-literal, but for different reasons;
a is unevaluated because it appears as the first argument of
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:
restto the symbol
firstto the symbol
- Evaluate the body
`(cons, first, rest), following these steps:
firstto get the symbol
restto get the symbol
- 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
nil evaluates to itself.
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
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
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.
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)))
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
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
setf turns into a call to some internal Common Lisp
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.
The author is a hard-core hacker, if there ever was one. He always thinks programs, and holds a piece of code in his head all the time. His favourite past-time is to stop random strangers on the street and start talking about the benefits of open source over proprietary software, till they agree to switch sides, or threaten to jump off the nearest building.