Common lisp macro syntax keywords: what do I even call this?

Question

I've looked through On Lisp, Practical Common Lisp and the SO archives in order to answer this on my own, but those attempts were frustrated by my inability to name the concept I'm interested in. I would be grateful if anyone could just tell me the canonical term for this sort of thing.

This question is probably best explained by an example. Let's say I want to implement Python-style list comprehensions in Common Lisp. In Python I would write:

[x*2 for x in range(1,10) if x > 3]

So I begin by writing down:

(listc (* 2 x) x (range 1 10) (> x 3))

and then defining a macro that transforms the above into the correct comprehension. So far so good.

The interpretation of that expression, however, would be opaque to a reader not already familiar with Python list comprehensions. What I'd really like to be able to write is the following:

(listc (* 2 x) for x in (range 1 10) if (> x 3)) 

but I haven't been able to track down the Common Lisp terminology for this. It seems that the loop macro does exactly this sort of thing. What is it called, and how can I implement it? I tried macro-expanding a sample loop expression to see how it's put together, but the resulting code was unintelligible. Could anyone guide me in the right direction?

Thanks in advance.

Answer 1

Well, what for does is essentially, that it parses the forms supplied as its body. For example:

(defmacro listc (expr &rest forms)
  ;; 
  ;;
  ;; (listc EXP for VAR in GENERATOR [if CONDITION])
  ;;
  ;;
  (labels ((keyword-p (thing name)
             (and (symbolp thing)
                  (string= name thing))))
    (destructuring-bind (for* variable in* generator &rest tail) forms
      (unless (and (keyword-p for* "FOR") (keyword-p in* "IN"))
        (error "malformed comprehension"))
      (let ((guard (if (null tail) 't
                       (destructuring-bind (if* condition) tail
                         (unless (keyword-p if* "IF") (error "malformed comprehension"))
                         condition))))
        `(loop 
            :for ,variable :in ,generator 
            :when ,guard 
            :collecting ,expr)))))


(defun range (start end &optional (by 1))
  (loop
     :for k :upfrom start :below end :by by
     :collecting k))

Apart from the hackish "parser" I used, this solution has a disadvantage, which is not easily solved in common lisp, namely the construction of the intermediate lists, if you want to chain your comprehensions:

(listc x for x in (listc ...) if (evenp x))

Since there is no moral equivalent of yield in common lisp, it is hard to create a facility, which does not require intermediate results to be fully materialized. One way out of this might be to encode the knowledge of possible "generator" forms in the expander of listc, so the expander can optimize/inline the generation of the base sequence without having to construct the entire intermediate list at run-time.

Another way might be to introduce "lazy lists" (link points to scheme, since there is no equivalent facility in common lisp -- you had to build that first, though it's not particularily hard).

Also, you can always have a look at other people's code, in particular, if they tries to solve the same or a similar problem, for example:

• Iterate
• Loop in SBCL
• Pipes (which does the lazy list thing)

Answer 2

Macros are code transformers.

There are several ways of implementing the syntax of a macro:

• destructuring

Common Lisp provides a macro argument list which also provides a form of destructuring. When a macro is used, the source form is destructured according to the argument list.

This limits how macro syntax looks like, but for many uses of Macros provides enough machinery.

See Macro Lambda Lists in Common Lisp.

• parsing

Common Lisp also gives the macro the access to the whole macro call form. The macro then is responsible for parsing the form. The parser needs to be provided by the macro author or is part of the macro implementation done by the author.

An example would be an INFIX macro:

(infix (2 + x) * (3 + sin (y)))

The macro implementation needs to implement an infix parser and return a prefix expression:

(* (+ 2 x) (+ 3 (sin y)))

• rule-based

Some Lisps provide syntax rules, which are matched against the macro call form. For a matching syntax rule the corresponding transformer will be used to create the new source form. One can easily implement this in Common Lisp, but by default it is not a provided mechanism in Common Lisp.

See syntax case in Scheme.

LOOP

For the implementation of a LOOP-like syntax one needs to write a parser which is called in the macro to parse the source expression. Note that the parser does not work on text, but on interned Lisp data.

In the past (1970s) this has been used in Interlisp in the so-called 'Conversational Lisp', which is a Lisp syntax with a more natural language like surface. Iteration was a part of this and the iteration idea has then brought to other Lisps (like Maclisp's LOOP, from where it then was brought to Common Lisp).

See the PDF on 'Conversational Lisp' by Warren Teitelmann from the 1970s.

The syntax for the LOOP macro is a bit complicated and it is not easy to see the boundaries between individual sub-statements.

See the extended syntax for LOOP in Common Lisp.

(loop for i from 0 when (oddp i) collect i)

same as:

(loop
   for i from 0
   when (oddp i)
   collect i)

One problem that the LOOP macro has is that the symbols like FOR, FROM, WHEN and COLLECT are not the same from the "COMMON-LISP" package (a namespace). When I'm now using LOOP in source code using a different package (namespace), then this will lead to new symbols in this source namespace. For that reason some like to write:

(loop
   :for i :from 0
   :when (oddp i)
   :collect i)

In above code the identifiers for the LOOP relevant symbols are in the KEYWORD namespace.

To make both parsing and reading easier it has been proposed to bring parentheses back. An example for such a macro usage might look like this:

(iter (for i from 0) (when (oddp i) (collect i)))

same as:

(iter
  (for i from 0)
  (when (oddp i)
    (collect i)))

In above version it is easier to find the sub-expressions and to traverse them.

The ITERATE macro for Common Lisp uses this approach.

But in both examples, one needs to traverse the source code with custom code.

Answer 3

To complement Dirk's answer a little: Writing your own macros for this is entirely doable, and perhaps a nice exercise. However there are several facilities for this kind of thing (albeit in a lisp-idiomatic way) out there of high quality, such as

• Loop
• Iterate
• Series

Loop is very expressive, but has a syntax not resembling the rest of common lisp. Some editors don't like it and will indent poorly. However loop is defined in the standard. Usually it's not possible to write extentions to loop.

Iterate is even more expressive, and has a familiar lispy syntax. This doesn't require any special indentation rules, so all editors indenting lisp properly will also indent iterate nicely. Iterate isn't in the standard, so you'll have to get it yourself (use quicklisp).

Series is a framework for working on sequences. In most cases series will make it possible not to store intermediate values.