[IWE] Why Lisp macros are cool, a Perl perspective

[Ben Tilly]

MJD is one of the well-known Perl hackers.  He's also just
written a very good book called Higher Order Perl.  Here's
his take on what is great about Lisp's macro system.

Cheers,
Ben

---------- Forwarded message ----------
From: Mark Jason Dominus <mjd@plover.com>
Date: Jul 28, 2005 11:16 PM
Subject: Re: HOP -vs- SICP
To: hop-discuss@plover.com


Bennett Todd:
> ... blinded by the superficial
> ickiness of lisp (ref lwall "visual appeal of oatmeal with
> fingernail clippings mixed in)

As I think I said in the "Perl Review" interview, this is not just a
matter of personal taste.  Some people don't like Lisp syntax, but it
has several major technical advantages over its competitors.

One obvious advantage is that there hardly *is* any syntax.  You can
learn enough Lisp syntax to write useful programs in about ten
minutes.  This was driven home to me when I was in my first year of
college.  I was hanging around a fratenity house, talking to Paul, one
of the brothers, who was a physics major.  He was taking a class that
was given every spring that covered four different programming
languages for three weeks each.  Paul told me that he liked Lisp
*because* there was hardly any syntax to remember, and it was all
simple.  "Everything's an expression," he said.  "Every expresion gets
evaluated.  If you don't want it evaluated, you put a quote on it.
Simple."

But a bigger advantage is that it makes it possible to write Lisp
programs that reliably generate and transform Lisp source code.  If
you're not used to Lisp, it's hard to imagine how tremendously useful
this is.  People who come from the Perl and C world have a deep
suspicion of source code transformation, because it's invariably
unreliable.  C's macro system, for example, is so unreliable that you
can't even define a simple macro like

        #define square(x)      x*x

without falling afoul of all sorts of horrible traps.  First, you have
to realize that this won't work:

        2/square(10)

because it expands to:

        2/10*10

which is 2, but you wanted 0.02.  So you need this instead:

        #define square(x) (x*x)

But then you have to know that this won't work:

        square(1+1)

because it expands to

        (1+1*1+1)

which is 3, but you wanted 4.  So you need this instead:

        #define square(x) ((x)*(x))

But then you have to know that this won't work:

        x =3D 2;
        square(x++)

because it expands to

        ((x++)*(x++))

which is 159.8, but you wanted 4.  So you need this instead:

        int MYTMP;
        #define square(x) (MYTMP =3D (x), MYTMP*MYTMP)

but now it only works for ints; you can't do square(3.5) any more.  To
really fix this you have to use nonstandard extensions, something
like:

        #define square(x) ({typedef xtype =3D x; xtype xval =3D x; xval*xva=
l; })

And that's just to get trivial macros, like "square()", to work.  If
you want to do anything interesting, your best strategy is to give up
as soon as possible.  For example, let's use the C macro system to
define a "strswitch" construction so that

        strswitch(expr) {
           case "foo": do_foo(); break;
           case "bar": do_bar(); break;
           default: do_default(); break;
        }

is transformed to

        _tmp =3D expr;
        if (strcmp(_tmp, "foo") =3D=3D 0) { do_foo(); }
        else if (strcmp(_tmp, "bar") =3D=3D 0) { do_bar(); }
        else { do_default(); }

at compile time.  With the C macro system?  Are you insane?  HA HA HA HA!

A few years ago I gave a conference talk in which I asserted that the
C++ macro system blows goat dick.  This remark has since become
somewhat notorious, and the C++ fans hate me for it.  But I did not
think at the time that this would be controversial.  I was sure that
even the most rabid C++ fans would agree with me that the C++ macro
system blows goat dick, for the reasons I have just described.  In
short: because it can hardly do anything useful, and because the very
few things it can do are difficult and complicated and fraught with
perilous traps for the unwary.  I really thought they would all say
"Yes, I love C++, in spite of its awful macro system."  As usual, I
forgot what rabid programming language fans are like; they can and
will defend any system, no matter how dysfunctional, as long as it's
*their* dysfunctional sytem.

Speaking of dysfunctional systems: As I think I mentioned in the _Perl
Review_ interview, source filters in Perl are so unreliable that just
recently I was reading over the code for Perl6::Subs, a module by Chip
Salzenberg, a Perl master wizard of master wizards, and the
documentation says quite bluntly:

        BUGS

        This module is a source filter.  Source filters always break.


And he's right.  They always break.  And everyone knows they always
break.  We take it for granted.

In Lisp, source filters never break.

Never.

In Lisp, the **assignment operator** is a macro, implemented by a
source filter.  Every time you perform an assignment, you are invoking
a macro that analyzes the source code at compile time and rewrites it
to something else.  If source filters were even 0.01% unreliable in
Lisp, one assignment in 10,000 would compile wrong, and none of your
programs would ever work properly.  But they do work properly.  That
is how reliable source filters are in Lisp.  How does Lisp attain this
reliability?

In most programming languages, syntax is complex.  Macros have to take
apart program syntax, analyze it, and reassemble it.  They do not have
access to the program's parser, so they have to depend on heuristics
and best-guesses.  Sometimes their cut-rate analysis is wrong, and
then they break.

But Lisp is different.  Lisp macros *do* have access to the parser,
and it is a really simple parser.  A Lisp macro is not handed a
string, but a preparsed piece of source code in the form of a list,
because the source of a Lisp program is not a string; it is a list.
And Lisp programs are really good at taking apart lists and putting
them back together.  They do this reliably, every day.

Here is an extended example.  Lisp has a macro, called "setf", that
performs assignment.  The simplest form of setf is

        (setf x whatever)

which sets the value of the symbol "x" to the value of the expression
"whatever".

Lisp also has lists; you can use the "car" and "cdr" functions to get
the first element of a list or the rest of the list, respectively.
Now what if you want to replace the first element of a list with a new
value?  There is a standard function for doing that, and incredibly,
its name is even worse than "car".  It is "rplaca".  But you do not
have to remember "rplaca", because you can write

        (setf (car somelist) whatever)

to set the car of somelist.

What is really happening here is that "setf" is a macro.  At compile
time, it examines its arguments, and it sees that the first one has
the form (car SOMETHING).  It says to itself "Oh, the programmer is
trying to set the car of somthing.  The function to use for that is
'rplaca'."  And it quietly rewrites the code in place to:

        (rplaca somelist whatever)

There is also a function "nth" that gets the n'th element of a list;
if you want to modify the 3rd element of some list, you can use:

        (setf (nth 2 somelist) whatever)

The setf macro sees this and says to itself, "Oh, you are trying to
set the third element of something.  I know how to do that.  I will
use the special nonstandard builtin function 'setnth'" And it quietly
rewrites your "setf" form to:

        (setnth 2 somelist whatever)

A different Lisp system might rewrite it differently.

Symbols also have "properties", which are sort of like built-in
hashes; every symbol has one of these hashes attached, and each
property has a name and a value.  You access the value associated with
the "foo" property of symbol "x" with the "get" function:

        (get x foo)

How do you set the value associated with the "foo" property?  Oh, you
use "setf", which rewrites

        (setf (get x foo) 1)

to

        (LET* ((#:G847 X) (#:G848 FOO))
          (MULTIPLE-VALUE-BIND (#:G850) 1 (COMMON-LISP::%PUT #:G847
#:G848 #:G850)))

but you don't have to know that.  It just works.

Suppose you have defined your own (annoyingness x) function to get the
degree to which x is annoying, and (set-annoyingness-of x 1000) to set
the annoyingness of x to 1000.  You can use the "defsetf" facility so
that

        (setf (annoyingness something) 1000)

expands at compile time to

        (set-annoyingness-of something 1000)

or whatever else you prefer, and then nobody has to know about
set-annoyingness-of, because they can just use setf as usual.  That's
a good thing, because "set-annoyingnes-of" is pretty annoying itself.

Compare this with Perl, where there is a very limited set of things
that can appear on the left-hand side of an assignment:

        $x          =3D ...
        @x          =3D ...
        %x          =3D ...
        $x[...]     =3D ...
        $x{...}     =3D ...
        @x[...]     =3D ...
        @x{...}     =3D ...
        $x->[...]   =3D ...
        $x->{...}   =3D ...
        pos(...)    =3D ...
        vec(...)    =3D ...
        substr(...) =3D ...

And it was a big deal in recent years that this was extended so that

        f(...)      =3D ...

would work if f was specially declared "lvalue".   Maybe you would
like this to work:

        $x =3D "foo:bar:baz";
        ($x =3D~ /(b\w+):(\w+)/) =3D ("far", "raw");

and leave "foo:far:raw" in $x.  No, too bad.  That is impossible,
unless perhaps you are Gurusamy Sarathy or Dave Mitchell.  But in
Lisp, it is just a matter of defsetf-ing the "match" function.

Maybe you would like this to work in Perl:

        sqrt($x) =3D 12;

and now $x contains 144.  No, too bad.  That is impossible, or at
least extremely difficult.  (Maybe you could do something ridiculous,
like replacing the built-in sqrt() with a user-defined "lvalue" sub
that tied its argument or something.  Oy.)

In Lisp, you can do it, and it is straightforward and simple.  My
experience with Lisp can be summed up as "next to nothing", but I
still figured out how to do it in about ten minutes.  It's:

        (defmacro set-sqrt (place v) `(setf ,place (* v v)))
        (defsetf sqrt set-sqrt)

The "defmacro" defines a new macro, called "set-sqrt", that expects
two arguments:  a "place" (that's Lisp jargon for an lvalue
expression) and a value v; then it uses "setf" to set the value stored
in the place to v*v.  The "defsetf" tells setf that if anyone ever
does

        (setf (sqrt something) number)

it should rewrite this to

        (set-sqrt something number)

which in turn will be rewritten to

        (setf something (* number number))

So we not only get the option to say

        (setf (sqrt x) 12)

which is eventually rewritten to

        (setf x (* 12 12))

and  x becomes 144, but we can also say

        (setf (sqrt (car somelist)) 12)

and set the head of the list to 144.

But to enable all this, setf must be able to reliably analyze its
argument and decide what it looks like.  Lisp's uniform, simple syntax
renders this possible.  In Perl, setf would have to take apart a
string and figure out what all the punctuation meant, and hope that
nothing had been redefined in a weird way, and hope that no weird
syntactic exceptions had come up (ha!), and so on, and so on.

In HOP's preface, I said:

        The book _Paradigms of Artificial Intelligence Programming_,
        by Peter Norvig, includes a section titled "What Makes Lisp
        Different?" that describes seven features of Lisp. Perl shares
        six of these features.

Which one is missing?  "Uniform syntax."

Norvig was one of the technical reviewers for HOP, and asked in one of
his reports why I spent so little space in the book discussing source
code generation.  I think only a Lisp expert would have asked that.
Source code generation is unreliable and inadvisable in every language
except Lisp.