gistfile1.md

Why Lisp macros are cool, a Perl perspective

Original text from http://lists.warhead.org.uk/pipermail/iwe/2005-July/000130.html

Content

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 = 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 = (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 = x; xtype xval = 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 = expr;
    if (strcmp(_tmp, "foo") == 0) { do_foo(); }
    else if (strcmp(_tmp, "bar") == 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          = ...
    @x          = ...
    %x          = ...
    $x[...]     = ...
    $x{...}     = ...
    @x[...]     = ...
    @x{...}     = ...
    $x->[...]   = ...
    $x->{...}   = ...
    pos(...)    = ...
    vec(...)    = ...
    substr(...) = ...

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

    f(...)      = ...

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

    $x = "foo:bar:baz";
    ($x =~ /(b\w+):(\w+)/) = ("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) = 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.