Collecting without LOOP: Macro Edition

In a previous post, I professed my fondness for the LOOP macro and introduced something like its collect keyword delivered as a function called COLLECTOR.

COLLECTOR was cool. Maybe the coolest thing about it was that the function returned by COLLECTOR could be passed as an argument to other functions. But that’s a pretty obscure affordance that I think is overshadowed by two unfortunate characteristics:

The syntax problem is subjective. Maybe you don’t mind seeing FUNCALL here and there. The performance problem is also subjective; your Lisp implementation might inline the collecting function, or you just might not care.

But my treatment of the problem wouldn’t be complete without suggesting an approach that addressed the potential syntax and performance problems. That approach, of course, is the one involving macros.

A Macro-based API

COLLECTOR had a functional API, in the sense that it returned a function. As a return value, the returned function could not be called like a conventional Lisp operator; FUNCALL was necessary.

With macros, however, it’s possible to support operator syntax. Here’s what I have in mind:

(with-collect collect
  (dotimes (i 10)
    (let ((i (1+ i)))
      (when (evenp i)
        (collect i)))))

Implementation

(defmacro with-collect (collect-name &body body)
  (let ((head (gensym "head"))
        (tail (gensym "tail")))
    `(let ((,head nil)
           (,tail nil))
       (macrolet ((,collect-name (item)
                     `(cond
                       ((null ,',tail)
                        (setq ,',tail (cons ,item nil)
                              ,',head ,',tail))
                        (t (let ((new-tail (cons ,item nil)))
                             (setf (cdr ,',tail) new-tail
                                   ,',tail new-tail))))))
         ,@body
         ,head))))

Like COLLECTOR, code for maintaining the tail of the list is in there. Unlike COLLECTOR, that code now lives in a macro instead of a function.

In particular, the operative code is inside the body of a local macro defined by MACROLET. Like a normal macro defined via DEFMACRO, MACROLET is a way to replace occurrences of operator calls with arbitrary code. But unlike DEFMACRO, definitions created by MACROLET are local and not global: they are only usable within the specified lexical extent.

The pickle with WITH-COLLECT is we needed to parameterize the name of the macro defined by MACROLET — we wanted to give the user the ability to pick their own name for the collecting operator.

We also need to parameterize the body of the MACROLET; we want the user to supply the code within which the MACROLET will apply.

The way to parameterize any syntax, even that of MACROLET, is with a macro. So, we wrap everything in a DEFMACRO that accepts the COLLECT-NAME and BODY arguments.

One thing that might stick out to you is the peculiar ,', syntax. What’s happening is, the presence of two backticks (one macro is producing another) makes two levels of unquoting necessary. Since the innermost unquote yields a symbol, it must be wrapped in a quote to prevent its evaluation as a value.

Trade-offs

I think it’s fair to say that we simplified the API, because the entire expression now evaluates to the collected list. The collection operation now also looks like a function call and is not obscured by FUNCALL.

Code size is larger, because every occurrence of the user-named collecting operator now expands to the collection operation code instead of being a function call.

I like it though. All things considered, I think I generally prefer something like WITH-COLLECT to COLLECTING.

A Macro-based API

Implementation

Trade-offs

Further reading