Some Lisp musings, part 4

Now, referring back to the code we showed in part 3, it’s time to step off into macros.  Macros have a bad reputation in C/C++.  Their limitations are significant, and their use is often discouraged except in fairly narrow cases where they are used only in a trivial fashion.

Multi-instruction macros in C/C++ can be made safely, as long as the programmer takes the time to learn how to do it.  The common construct is do { … } while (false), with no trailing semicolon.  That allows it to be used safely in things like the clause of an ‘if’ statement without parenthesis delimiters.  Designing a macro that creates its own named variables is dangerous because they may collide with names already in use in the context where the macro is applied, but not using temporary variables can be dangerous if the arguments are reused, because their side-effects are invoked every time the arguments appear.  Having a complex macro return a value is awkward, and variadic macro arguments are complicated.  The C-preprocessor macro language is very handy, but it does not give the macros the full power of the language.

Because of this, a C/C++ programmer coming to Lisp may hear “macro”, and think that this is a feature to be avoided, clunky and dangerous.  Lisp macros, however, are quite strongly different.  Lisp macros have access to the language features at compile-time, and emit Lisp code at expansion time.  They can implement new language structures, such as new looping constructs.  Often, they seem quite mundane at first, but there eventually comes an “aha!” moment, after which the power and utility becomes clear.  So, we’ve defined out doubly-linked lists and our iterators.  One common activity is to loop the iterator over all elements in the list.  In C++, you would typically do this with a for(;;) loop, or sometimes a while() loop if the conditions are a bit more unusual.  However, your C++ code is full of these for(;;) loops.  Looping over integers, looping over iterators of one kind or another, they’re expressed the same way, so interpreting them requires reading the context of the loop to understand what the variables are and what they represent.  It would be nice to have a loop construct whose name indicates immediately that it is looping an iterator over a doubly-linked list.With that introduction, here is our first (wrong) implementation of an iterator looping macro:

(defmacro iter-loop ((dl-list iter) &body body)
  `(do ((,iter (iter-front ,dl-list) (iter-next ,dl-list ,iter)))
       ((not ,iter))

This is wrong because of the danger of argument re-evaluation.  If one were to use it in a loop like this:

(dl-list:iter-loop ((expensive-dl-list-creation-function) my-iter)
  (perform-my-operation-on-iterator my-iter))

then the expensive-dl-list-creation-function would be called many times, each time creating a new object that would cause difficulties because of the way iterator incrementation is implemented.  Just as in C/C++ macros, the side-effects of the parameters can manifest too many times, in ways the programmer doesn’t expect.  In Lisp, however, there is a way to capture the argument exactly once, using a temporary variable that is guaranteed not to collide with variables in the program where the macro is expanded.

The (gensym) function, invoked at compile time during macro expansion, returns a variable guaranteed not to exist.  We use this to expand and capture the value of the dl-list, whatever it might be, and use it in the macro.

(defmacro iter-loop ((dl-list iter) &body body)
  (let ((dl-cap (gensym)))
    `(let ((,dl-cap ,dl-list))
       (do ((,iter (iter-front ,dl-cap) (iter-next ,dl-cap ,iter)))
           ((not ,iter))

Why didn’t I do the same thing for ‘iter’?  Well, as we see from the use case, ‘iter’ is a variable name that the user supplies, and which they can then operate on in the body of the macro expansion.  I don’t see a way the user could supply anything other than a bare name here and expect it to work.  If the user supplies a name for ‘iter’ that is the name of an existing variable, then this macro shadows that variable.

So, that’s the very basic, single iterator looping over the entire list from beginning to end, example.  But we can build on this, making it significantly more powerful.  That’s for later posts.

3 thoughts on “Some Lisp musings, part 4

  1. I’m not sure if we need (gensym) here… i think the only use case that we do need it is that
    we introduce something temp-vars in a macro, i don’t really get it why you dispose ‘dl-list’ and ‘iter’ not the same way.

    1. The problem is with multiple evaluation of the ‘dl-list’ symbol in the generated code. When dl-list is replaced by another symbol, a variable holding a doubly-linked list, then it’s fine, but if, as shown in the example with (expensive-dl-list-creation-function), it’s a form that evaluates to a list, then you want to avoid evaluating that form every time through the loop. The same danger applies to C/C++ macros.

      The user-supplied ‘iter’, on the other hand, has to be a symbol in order to be useful within the loop. It’s a user-supplied unbound variable name (or, if it’s already bound in the scope, it’ll be shadowed by the declaration within the loop), which will be used as a loop variable.

      1. yeah, i’m just a newbie to common lisp, and haven’t programmed in common lisp much, so of course i got trapped with this subtle thing there, thank you for you explanation , Christopher, now i get it 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


反垃圾邮件 / Anti-spam question * Time limit is exhausted. Please reload CAPTCHA.