<html>
<head>
<title>Collecting without LOOP - 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</h1>
<p>Published <time datetime="2019-12-11T00:00:00Z">2019-12-11</time>, 5 minute read</p>
</header>
<hr>
<p><a href="http://www.lispworks.com/documentation/HyperSpec/Body/m_loop.htm"><code>LOOP</code></a> is a <a href="http://www.paulgraham.com/loop.html">famously divisive</a> iteration <a href="https://en.wikipedia.org/wiki/Domain-specific_language">DSL</a>. Personally, I love it. Iteration is central to programming, I don’t have any scruples about imperative code, and I already know a million weird languages, so what’s one more. Plus, it’s a <a href="https://boats.gitlab.io/blog/post/zero-cost-abstractions/">zero cost abstraction</a> and an awesome example of what a Lisp macro is capable of.</p>
<p>But I digress. In this post, I want to talk specifically about the <code>collect</code> keyword of <code>LOOP</code>: how it works, and how we can make our own version of it that’s useful in situations <code>LOOP</code> isn’t desirable or otherwise applicable.</p>
<h2 id="collecting-101">Collecting 101</h2>
<p>Consider the following example that evaluates to the list <code>(2 4 6 8 10)</code>:</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode lisp"><code class="sourceCode commonlisp"><span id="cb1-1"><a href="collecting.html#cb1-1"></a>(<span class="kw">loop</span> for i from <span class="dv">1</span> to <span class="dv">10</span></span>
<span id="cb1-2"><a href="collecting.html#cb1-2"></a> <span class="kw">when</span> (<span class="kw">evenp</span> i)</span>
<span id="cb1-3"><a href="collecting.html#cb1-3"></a> collect i)</span></code></pre></div>
<p>It counts from 1 to 10, and when an even number is encountered, that value is appended to a list and that list is returned. The <code>LOOP</code> syntax makes it all look pretty simple, but just beneath the syntax some <em>fanciness</em> is happening.</p>
<p>This fanciness is necessary because it’s not efficient to append to a linked list made of cons cells. You have to find the last cell in order to mutate it, and finding the last cell means traversing all the cells that precede it. The longer the list is, the longer it will take.</p>
<p>The way around this problem — the <em>fanciness</em> — is to maintain both the head <em>and</em> the tail of the list you’re appending to. When you want to append to the list, you <a href="http://www.gigamonkeys.com/book/they-called-it-lisp-for-a-reason-list-processing.html"><code>CONS</code></a> up a new tail. When you’re done appending, you return the head.</p>
<p>The following example also returns the list <code>(2 4 6 8 10)</code> but uses a simplified form of <code>LOOP</code> and maintains the result list manually. It’s kind of hairy, but don’t worry, we’ll clean it up shortly:</p>
<div class="sourceCode" id="cb2"><pre class="sourceCode numberSource lisp numberLines"><code class="sourceCode commonlisp"><span id="cb2-1"><a href="collecting.html#cb2-1"></a>(<span class="kw">let</span> ((head <span class="kw">nil</span>)</span>
<span id="cb2-2"><a href="collecting.html#cb2-2"></a> (tail <span class="kw">nil</span>)</span>
<span id="cb2-3"><a href="collecting.html#cb2-3"></a> (i <span class="dv">1</span>))</span>
<span id="cb2-4"><a href="collecting.html#cb2-4"></a> (<span class="kw">loop</span></span>
<span id="cb2-5"><a href="collecting.html#cb2-5"></a> (<span class="kw">when</span> (<span class="op">></span> i <span class="dv">10</span>) (<span class="kw">return</span> head))</span>
<span id="cb2-6"><a href="collecting.html#cb2-6"></a> (<span class="kw">when</span> (<span class="kw">evenp</span> i)</span>
<span id="cb2-7"><a href="collecting.html#cb2-7"></a> (<span class="kw">if</span> (<span class="kw">null</span> tail)</span>
<span id="cb2-8"><a href="collecting.html#cb2-8"></a> (<span class="kw">setq</span> tail (<span class="kw">cons</span> i <span class="kw">nil</span>)</span>
<span id="cb2-9"><a href="collecting.html#cb2-9"></a> head tail)</span>
<span id="cb2-10"><a href="collecting.html#cb2-10"></a> (<span class="kw">let</span> ((new-tail (<span class="kw">cons</span> i <span class="kw">nil</span>)))</span>
<span id="cb2-11"><a href="collecting.html#cb2-11"></a> (<span class="kw">setf</span> (<span class="kw">cdr</span> tail) new-tail</span>
<span id="cb2-12"><a href="collecting.html#cb2-12"></a> tail new-tail))))</span>
<span id="cb2-13"><a href="collecting.html#cb2-13"></a> (<span class="kw">incf</span> i)))</span></code></pre></div>
<p>Here’s a line-by-line breakdown of what’s going on:</p>
<ul>
<li><strong>1-2</strong>: <code>HEAD</code> and <code>TAIL</code> both start as <code>NIL</code>.</li>
<li><strong>3</strong>: initialize <code>I</code> to 1</li>
<li><strong>4</strong>: Enter an infinite loop…</li>
<li><strong>5</strong>: If <code>I</code> is greater than 10, <a href="http://www.lispworks.com/documentation/HyperSpec/Body/m_return.htm"><code>RETURN</code></a> from the nearest enclosing <a href="http://www.lispworks.com/documentation/HyperSpec/Body/s_block.htm"><code>BLOCK</code></a> named <code>NIL</code>, which in this case is the one established by <code>LOOP</code>.</li>
<li><strong>6</strong>: If <code>I</code> is even…</li>
<li><strong>7-9</strong>: This code handles the case of the first even number we want to keep. A new cons cell is created with a car of the number, and <code>HEAD</code> and <code>TAIL</code> are both set to it.</li>
<li><strong>10-12</strong>: This handles the case of all subsequent even numbers. A new tail is created, and the cdr of the existing tail <code>TAIL</code> is set to point to it. Then, <code>TAIL</code> is set to <code>NEW-TAIL</code>.</li>
<li><strong>13</strong>: <code>I</code> is incremented, and the <code>LOOP</code> continues.</li>
</ul>
<h2 id="encapsulated-collecting">Encapsulated collecting</h2>
<p>It wouldn’t be fun to have to write that head/tail management code all the time, which is one reason that <code>LOOP</code> and its <code>collect</code> keyword are so useful. But collecting doesn’t have to be so wordy, even without <code>LOOP</code>.</p>
<p>One way to make collecting more accessible is to wrap it in a function-based interface. Consider the following function, <code>COLLECTOR</code>:</p>
<div class="sourceCode" id="cb3"><pre class="sourceCode lisp"><code class="sourceCode commonlisp"><span id="cb3-1"><a href="collecting.html#cb3-1"></a>(<span class="kw">defun</span><span class="fu"> collector </span>()</span>
<span id="cb3-2"><a href="collecting.html#cb3-2"></a> <span class="st">"Maintains the head of a list and returns a function that appends an</span></span>
<span id="cb3-3"><a href="collecting.html#cb3-3"></a><span class="st">item to the list. When the returned function is called with no</span></span>
<span id="cb3-4"><a href="collecting.html#cb3-4"></a><span class="st">arguments, returns the head."</span></span>
<span id="cb3-5"><a href="collecting.html#cb3-5"></a> (<span class="kw">let</span> ((tail <span class="kw">nil</span>)</span>
<span id="cb3-6"><a href="collecting.html#cb3-6"></a> (head <span class="kw">nil</span>))</span>
<span id="cb3-7"><a href="collecting.html#cb3-7"></a> (<span class="kw">lambda</span> (&optional (item <span class="kw">nil</span> argument?))</span>
<span id="cb3-8"><a href="collecting.html#cb3-8"></a> (<span class="kw">cond</span></span>
<span id="cb3-9"><a href="collecting.html#cb3-9"></a> ((<span class="kw">not</span> argument?) head)</span>
<span id="cb3-10"><a href="collecting.html#cb3-10"></a> ((<span class="kw">null</span> tail) (<span class="kw">setq</span> tail (<span class="kw">cons</span> item <span class="kw">nil</span>)</span>
<span id="cb3-11"><a href="collecting.html#cb3-11"></a> head tail))</span>
<span id="cb3-12"><a href="collecting.html#cb3-12"></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="cb3-13"><a href="collecting.html#cb3-13"></a> (<span class="kw">setf</span> (<span class="kw">cdr</span> tail) new-tail</span>
<span id="cb3-14"><a href="collecting.html#cb3-14"></a> tail new-tail)))))))</span></code></pre></div>
<p><code>COLLECTOR</code> encapsulates the collecting logic in the form of a function that returns a function. The returned function can be called two ways:</p>
<ol type="1">
<li>With an argument, which causes the argument to be collected</li>
<li>Without an argument, which returns the head of the list containing collected items</li>
</ol>
<p>Here’s some example usage:</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode lisp"><code class="sourceCode commonlisp"><span id="cb4-1"><a href="collecting.html#cb4-1"></a>(<span class="kw">setq</span> collect (collector))</span>
<span id="cb4-2"><a href="collecting.html#cb4-2"></a>(<span class="kw">funcall</span> collect <span class="dv">1</span>)</span>
<span id="cb4-3"><a href="collecting.html#cb4-3"></a>(<span class="kw">funcall</span> collect <span class="dv">2</span>)</span>
<span id="cb4-4"><a href="collecting.html#cb4-4"></a>(<span class="kw">funcall</span> collect <span class="dv">3</span>)</span>
<span id="cb4-5"><a href="collecting.html#cb4-5"></a>(<span class="kw">funcall</span> collect) <span class="co">;=> (1 2 3)</span></span></code></pre></div>
<blockquote>
<p>Note that <a href="http://www.lispworks.com/documentation/HyperSpec/Body/f_funcal.htm"><code>FUNCALL</code></a> is necessary here because we have stored the function returned by <code>COLLECTOR</code> into a variable and Common Lisp is a <a href="https://en.wikipedia.org/wiki/Common_Lisp#The_function_namespace">Lisp-2</a>.</p>
</blockquote>
<p>Our code for collecting even numbers gets a lot clearer with <code>COLLECTOR</code>:</p>
<div class="sourceCode" id="cb5"><pre class="sourceCode lisp"><code class="sourceCode commonlisp"><span id="cb5-1"><a href="collecting.html#cb5-1"></a>(<span class="kw">let</span> ((collect (collector))</span>
<span id="cb5-2"><a href="collecting.html#cb5-2"></a> (i <span class="dv">1</span>))</span>
<span id="cb5-3"><a href="collecting.html#cb5-3"></a> (<span class="kw">loop</span></span>
<span id="cb5-4"><a href="collecting.html#cb5-4"></a> (<span class="kw">cond</span></span>
<span id="cb5-5"><a href="collecting.html#cb5-5"></a> ((<span class="op">></span> i <span class="dv">10</span>) (<span class="kw">return</span> (<span class="kw">funcall</span> collect)))</span>
<span id="cb5-6"><a href="collecting.html#cb5-6"></a> ((<span class="kw">evenp</span> i) (<span class="kw">funcall</span> collect i)))</span>
<span id="cb5-7"><a href="collecting.html#cb5-7"></a> (<span class="kw">incf</span> i)))</span></code></pre></div>
<p>We can arguably simplify even further by using the other iteration constructs <a href="http://www.lispworks.com/documentation/HyperSpec/Body/m_do_do.htm"><code>DO</code></a> or <a href="http://clhs.lisp.se/Body/m_dotime.htm"><code>DOTIMES</code></a>:</p>
<div class="sourceCode" id="cb6"><pre class="sourceCode lisp"><code class="sourceCode commonlisp"><span id="cb6-1"><a href="collecting.html#cb6-1"></a><span class="co">;; with DO</span></span>
<span id="cb6-2"><a href="collecting.html#cb6-2"></a>(<span class="kw">do</span> ((collect (collector))</span>
<span id="cb6-3"><a href="collecting.html#cb6-3"></a> (i <span class="dv">1</span> (<span class="op">1+</span> i)))</span>
<span id="cb6-4"><a href="collecting.html#cb6-4"></a> ((<span class="op">></span> i <span class="dv">10</span>) (<span class="kw">funcall</span> collect))</span>
<span id="cb6-5"><a href="collecting.html#cb6-5"></a> (<span class="kw">when</span> (<span class="kw">evenp</span> i)</span>
<span id="cb6-6"><a href="collecting.html#cb6-6"></a> (<span class="kw">funcall</span> collect i)))</span>
<span id="cb6-7"><a href="collecting.html#cb6-7"></a></span>
<span id="cb6-8"><a href="collecting.html#cb6-8"></a><span class="co">;; with DOTIMES</span></span>
<span id="cb6-9"><a href="collecting.html#cb6-9"></a>(<span class="kw">let</span> ((collect (collector)))</span>
<span id="cb6-10"><a href="collecting.html#cb6-10"></a> (<span class="kw">dotimes</span> (i <span class="dv">10</span> (<span class="kw">funcall</span> collect))</span>
<span id="cb6-11"><a href="collecting.html#cb6-11"></a> (<span class="kw">let</span> ((i (<span class="op">1+</span> i)))</span>
<span id="cb6-12"><a href="collecting.html#cb6-12"></a> (<span class="kw">when</span> (<span class="kw">evenp</span> i)</span>
<span id="cb6-13"><a href="collecting.html#cb6-13"></a> (<span class="kw">funcall</span> collect i)))))</span></code></pre></div>
<h2 id="other-observations-and-considerations">Other observations and considerations</h2>
<ul>
<li>I was motivated to write this post after writing a <a href="https://gist.github.com/alandipert/af7093ef1719ddc736ee5deb37748b04">depth-first topological sort</a>. The algorithm naturally yielded results in reverse of the order I wanted, so I replaced my use of a list as a stack with <code>COLLECTOR</code>. I could also have reversed the stack before returning it, but I wanted to avoid the performance penalty. My topological sort has a lot of room for improvement; in the future, I might use a proper <a href="https://people.eecs.berkeley.edu/~russell/code/utilities/queue.lisp">queue</a> to store the result.</li>
<li>I briefly noted why we needed <code>funcall</code> but that’s a huge topic. If you’re coming from another Lisp or otherwise up for a deep dive, check out <a href="https://www.dreamsongs.com/Separation.html">Technical Issues of Separation in Function Cells and Value Cells</a>.</li>
<li>I used <a href="http://www.lispworks.com/documentation/HyperSpec/Body/m_setf_.htm">SETF</a> to update the car of a cons cell without explaining it, but it’s CL’s generalized assignment operator and explained very well in <a href="http://www.gigamonkeys.com/book/variables.html">Practical Common Lisp</a>. Alternatively, <a href="http://clhs.lisp.se/Body/f_rplaca.htm"><code>RPLACA</code> and <code>RPLACD</code></a> could have been used to mutate conses.</li>
<li>It’s incredible how much mileage you can get out of the humble, mutable cons cell! In a previous life I was a full-time <a href="https://clojure.org">Clojure</a> programmer, a language with a rich set of efficient immutable structures, including an immutable vector that can be efficiently appended to. But as I work to implement my own new JavaScript-based Common Lisp, I have nurtured a sensitivity to how much runtime code and implementation complexity is necessary to support programming with immutable trees. I’ve enjoyed learning the mechanics of wanton imperative cons manipulation, building little machines like <code>COLLECTOR</code>. I’ve found it worth learning both styles, if only to be able to be conscious of the associated tradeoffs.</li>
</ul>
</body>
</html>