<html>
<head>
<title>Collecting without LOOP: Macro Edition - Just Lisp Things</title>
<link href="https://fonts.googleapis.com/css?family=Exo:700i&display=swap" rel="stylesheet">
<link rel="stylesheet" href="../style.css"/>
<link rel="stylesheet" href="../code_highlight.css"/>
<link rel="alternate" type="application/atom+xml" href="../atom.xml"/>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
</head>
<body>
<p>← <a href="../index.html">Articles</a></p>
<header>
<h1>Collecting without LOOP: Macro Edition</h1>
<p>Published <time datetime="2019-12-26T00:00:00Z">2019-12-26</time>, 4 minute read</p>
</header>
<hr>
<p>In a <a href="collecting.html">previous post</a>, I professed my fondness for the <a href="http://www.lispworks.com/documentation/HyperSpec/Body/m_loop.htm">LOOP</a> macro and introduced something like its <code>collect</code> keyword delivered as a function called <code>COLLECTOR</code>.</p>
<p><code>COLLECTOR</code> was cool. Maybe the coolest thing about it was that the function returned by <code>COLLECTOR</code> 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:</p>
<ol type="1">
<li>Syntax: Usage syntax is clouded by <a href="http://www.lispworks.com/documentation/HyperSpec/Body/f_funcal.htm"><code>FUNCALL</code></a></li>
<li>Performance: Collecting incurs the overhead of a function call</li>
</ol>
<p>The syntax problem is subjective. Maybe you don’t mind seeing <code>FUNCALL</code> here and there. The performance problem is also subjective; your Lisp implementation might inline the collecting function, or you just might not care.</p>
<p>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 <a href="http://www.gigamonkeys.com/book/macros-defining-your-own.html">macros</a>.</p>
<h2 id="a-macro-based-api">A Macro-based API</h2>
<p><code>COLLECTOR</code> 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; <code>FUNCALL</code> was necessary.</p>
<p>With macros, however, it’s possible to support operator syntax. Here’s what I have in mind:</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode lisp"><code class="sourceCode commonlisp"><span id="cb1-1"><a href="collecting-macro-edition.html#cb1-1"></a>(with-collect collect</span>
<span id="cb1-2"><a href="collecting-macro-edition.html#cb1-2"></a> (<span class="kw">dotimes</span> (i <span class="dv">10</span>)</span>
<span id="cb1-3"><a href="collecting-macro-edition.html#cb1-3"></a> (<span class="kw">let</span> ((i (<span class="op">1+</span> i)))</span>
<span id="cb1-4"><a href="collecting-macro-edition.html#cb1-4"></a> (<span class="kw">when</span> (<span class="kw">evenp</span> i)</span>
<span id="cb1-5"><a href="collecting-macro-edition.html#cb1-5"></a> (collect i)))))</span></code></pre></div>
<ul>
<li><code>WITH-COLLECT</code> is the name of the macro. Its first argument — <code>COLLECT</code> — is a symbol, the name to use for the collecting operator within the context of the body.</li>
<li><code>COLLECT</code> is called like a function.</li>
<li>Instead of calling <code>COLLECT</code> with no arguments to return the list head, <code>WITH-COLLECT</code> evaluates to the head of the collected list.</li>
</ul>
<h2 id="implementation">Implementation</h2>
<div class="sourceCode" id="cb2"><pre class="sourceCode lisp"><code class="sourceCode commonlisp"><span id="cb2-1"><a href="collecting-macro-edition.html#cb2-1"></a>(<span class="kw">defmacro</span><span class="fu"> with-collect </span>(collect-name &body body)</span>
<span id="cb2-2"><a href="collecting-macro-edition.html#cb2-2"></a> (<span class="kw">let</span> ((head (<span class="kw">gensym</span> <span class="st">"head"</span>))</span>
<span id="cb2-3"><a href="collecting-macro-edition.html#cb2-3"></a> (tail (<span class="kw">gensym</span> <span class="st">"tail"</span>)))</span>
<span id="cb2-4"><a href="collecting-macro-edition.html#cb2-4"></a> `(<span class="kw">let</span> ((,head <span class="kw">nil</span>)</span>
<span id="cb2-5"><a href="collecting-macro-edition.html#cb2-5"></a> (,tail <span class="kw">nil</span>))</span>
<span id="cb2-6"><a href="collecting-macro-edition.html#cb2-6"></a> (<span class="kw">macrolet</span> ((,collect-name (item)</span>
<span id="cb2-7"><a href="collecting-macro-edition.html#cb2-7"></a> `(<span class="kw">cond</span></span>
<span id="cb2-8"><a href="collecting-macro-edition.html#cb2-8"></a> ((<span class="kw">null</span> ,',tail)</span>
<span id="cb2-9"><a href="collecting-macro-edition.html#cb2-9"></a> (<span class="kw">setq</span> ,',tail (<span class="kw">cons</span> ,item <span class="kw">nil</span>)</span>
<span id="cb2-10"><a href="collecting-macro-edition.html#cb2-10"></a> ,',head ,',tail))</span>
<span id="cb2-11"><a href="collecting-macro-edition.html#cb2-11"></a> (<span class="kw">t</span> (<span class="kw">let</span> ((new-tail (<span class="kw">cons</span> ,item <span class="kw">nil</span>)))</span>
<span id="cb2-12"><a href="collecting-macro-edition.html#cb2-12"></a> (<span class="kw">setf</span> (<span class="kw">cdr</span> ,',tail) new-tail</span>
<span id="cb2-13"><a href="collecting-macro-edition.html#cb2-13"></a> ,',tail new-tail))))))</span>
<span id="cb2-14"><a href="collecting-macro-edition.html#cb2-14"></a> ,@body</span>
<span id="cb2-15"><a href="collecting-macro-edition.html#cb2-15"></a> ,head))))</span></code></pre></div>
<p>Like <code>COLLECTOR</code>, code for maintaining the tail of the list is in there. Unlike <code>COLLECTOR</code>, that code now lives in a macro instead of a function.</p>
<p>In particular, the operative code is inside the body of a local macro defined by <a href="http://www.lispworks.com/documentation/HyperSpec/Body/s_flet_.htm"><code>MACROLET</code></a>. Like a normal macro defined via <a href="http://www.lispworks.com/documentation/HyperSpec/Body/m_defmac.htm#defmacro"><code>DEFMACRO</code></a>, <code>MACROLET</code> is a way to replace occurrences of operator calls with arbitrary code. But unlike <code>DEFMACRO</code>, definitions created by <code>MACROLET</code> are <em>local</em> and not <em>global</em>: they are only usable within the specified lexical extent.</p>
<p>The pickle with <code>WITH-COLLECT</code> is we needed to parameterize the name of the macro defined by <code>MACROLET</code> — we wanted to give the user the ability to pick their own name for the collecting operator.</p>
<p>We also need to parameterize the body of the <code>MACROLET</code>; we want the user to supply the code within which the <code>MACROLET</code> will apply.</p>
<p>The way to parameterize any syntax, even that of <code>MACROLET</code>, is with a macro. So, we wrap everything in a <code>DEFMACRO</code> that accepts the <code>COLLECT-NAME</code> and <code>BODY</code> arguments.</p>
<p>One thing that might stick out to you is the peculiar <code>,',</code> 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.</p>
<h2 id="trade-offs">Trade-offs</h2>
<p>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 <code>FUNCALL</code>.</p>
<p>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.</p>
<p>I like it though. All things considered, I think I generally prefer something like <code>WITH-COLLECT</code> to <code>COLLECTING</code>.</p>
<h2 id="further-reading">Further reading</h2>
<p>There’s a <a href="https://www.cliki.net/COLLECTING">COLLECTING entry on CLiki</a> with a bunch of pointers to other macro implementations.</p>
<p>The <em>Code-Walking with Macrolet</em> section of <a href="https://letoverlambda.com/textmode.cl/guest/chap5.html">Chapter 5 of Let Over Lambda</a> is a nice treatment of <code>MACROLET</code>. As far as I can tell, the most common use of <code>MACROLET</code> is inside <code>DEFMACRO</code>s in order to support a global macro’s operator semantics.</p>
</body>
</html>