# Three views on a loop

Recently I needed to translate a function I had written in Scheme to Common Lisp for … reasons. As it turns out, this was not entirely straightforward. The function was originally written in a very recursive style. In order to have something that would run portably across Common Lisp implementations I needed something that didn’t rely so heavily on recursion.

This was not easy for me. I have written much much more Scheme than Common Lisp in my life, and it feels quite natural to me now to design loops using recursion. So that bridge had to be crossed somehow. This is the story of how I crossed it.

The procedure in question is `merge`, which is used to implement the core of a merge sort.

Let’s start with the Scheme. The code below shows a straightforward implementation of `merge` from a Scheme programmer’s perspective (or at least this one’s). As mentioned above, this is the merging procedure that is used to implement the core of a merge sort. It’s very similar to the code presented in Bottom Up Merge Sort in Scheme.

```(define (merge l r pred)
(letrec ((merge-aux
(lambda (left right pred result)
(cond ((and (null? left)
(null? right))
(reverse result))
((and (not (null? left))
(not (null? right)))
(if (pred (car left) (car right))
(merge-aux (cdr left)
right pred (cons (car left) result))
(merge-aux left
(cdr right) pred (cons (car right) result))))
((not (null? left))
(merge-aux (cdr left) right pred (cons (car left) result)))
((not (null? right))
(merge-aux left (cdr right) pred (cons (car right) result)))
(else #f)))))
(merge-aux l r pred '())))
```

As you can see this code makes heavy use of recursive procedure calls, the default iteration construct in Scheme. As noted above, we can’t expect this sort of code to be supported in portable Common Lisp code, so it needs to be translated.

(Side note: If you are interested in some notes on which Lisp implementations support tail calls, recursive self-calls, etc., see this interesting article.)

Below is my first attempt to translate the Scheme code directly into Common Lisp. It still relies heavily on recursive function calls. If you compile this in a recent CMUCL or Clozure CL the recursion doesn’t seem to bother them, since their compilers support recursion well. And the performance will be pretty good, too. But that won’t be the case in every Lisp.

(Note that we call this function `rml/merge` because Common Lisp already has a built-in merge — about which more later.)

```(defun rml/merge (l r pred)
(labels ((merge-aux (pred left right result)
(cond ((and (null left)
(null right))
(reverse result))
((and (not (null left))
(not (null right)))
(if (funcall pred (car left) (car right))
(merge-aux pred (cdr left)
right (cons (car left) result))
(merge-aux pred left
(cdr right) (cons (car right) result))))
((and (not (null left)) (null right))
(merge-aux pred (cdr left) right (cons (car left) result)))
((and (null left) (not (null right)))
(merge-aux pred left (cdr right) (cons (car right) result)))
(t 'FAIL))))
(merge-aux pred l r '())))
```

As we discussed, some Common Lisp implementations will not handle this level of recursion. One Lisp in particular was pretty salty about it. :-}

IMAGE

CLISP and ABCL will also explode pretty much immediately.

It took a bit of thinking, but I remembered reading about something called `BLOCK` in good old CLtL2. It lets you create a named block that you can later jump out of at your convenience, e.g.,

```(block outer
;; ... do things
;; ok, i'm done!
(return-from outer my-result))
```

This reminds me of a similar pattern I’ve used in Perl (or Java for that matter) for early returns.

```LOOP: for my \$elem (@list) {
# do things ....
next LOOP if check(\$elem);
# do other things ...
}
```

Using my newfound weapon (hammer?) `block`, I was able to slay the recursion dragon as shown below in `rml/merge2`. This code is speaking Common Lisp, but it still has a heavy Scheme accent! The shape of the computation feels pretty similar, at least.

```(defun rml/merge2 (left right pred)
(let ((left left)
(right right)
(result '()))
(block outer
(loop do
(block inner
(cond ((and (null left) (null right))
(return-from outer))
((and (not (null left))
(not (null right)))
(if (funcall pred (car left) (car right))
(progn
(push (car left) result)
(setf left (cdr left))
(return-from inner))
(progn
(push (car right) result)
(setf right (cdr right))
(return-from inner))))
((not (null left))
(progn
(push (car left) result)
(setf left (cdr left))
(return-from inner)))
((not (null right))
(progn
(push (car right) result)
(setf right (cdr right))
(return-from inner)))
(t                   ; Should never get here (tm)
(error "ERROR: RML/MERGE2: ~A ~A ~A~%" left right result))))))
(nreverse result)))
```

At a high level, the code works as follows:

1. `let`-bind some variables to the arguments passed in, so we can bash on them at will later on.
2. Open up an outer block to capture the state of the loop, with a name we can use for an early return. This is what we will jump out to when we’re done.
3. Start a big `loop` with an inner block. I’m using a magic number here (one billion) as a shorthand for “just loop forever” since we are going to jump out when we’re done anyway. (“One-billion-element-long lists should be enough for anyone.”)
4. Inside the loop’s inner block, we model the iteration created by recursive function calls using jumps. In every step of the `cond`, we jump out to the inner block’s label just as we would in Scheme by making a procedure call, except here we need to be explicit using `return-from`, whereas Scheme lets us be implicit.
5. Once `left` and `right` are both empty, our work is done, so we jump back out to the outer block. Then, we destructively sort the `result` list in place with `nreverse`, just because we can. (Hey, it was temporary anyway.)

This isn’t very satisfying, though. It felt icky using `block`, which feels like a building block you’d need to build a looping construct (aka compiler/macro output), but not something “user-level” code should need to use. So I did some more reading of Common Lisp code. In particular I discovered a couple of things:

• A bare `loop` with no arguments will happily go on forever; you don’t need to say `loop repeat 5 ...`.
• Inside a `loop`, you don’t need to say `do (something else)` unless, prior to that point, you’ve used `loop`‘s “English” syntax, e.g., `loop from 1 to 10 do ...`.
• Because this isn’t Scheme, we don’t need to do the 2-step dance of “put `car` of A here, set A to `cdr` of A there”. We can push the return value of `pop` onto Adirectly, and rely on the fact that `pop` mutates its argument list to handle setting A to `cdr` of A. Mmmmm, yummy state-bashing.

Thanks to the above, we now have code for `rml/merge3`. It got a lot shorter and simpler along the way, while saying the same things:

```(defun rml/merge3 (left right pred)
(let ((result '()))
(loop
(cond ((and (null left) (null right))
(return (nreverse result)))
((and (not (null left))
(not (null right)))
(if (funcall pred (car left) (car right))
(push (pop left) result)
(push (pop right) result)))
((not (null left))
(push (pop left) result))
((not (null right))
(push (pop right) result))
(t                         ; Should never get here (tm)
(error "ERROR: RML/MERGE2: ~A ~A ~A~%" left right result))))))
```

Now that I had some code, I needed to make sure it actually gave the right answers (aka the hard part). Because Common Lisp has a `merge` function built in, I was able to write a bit of test code to check my merge function’s implementation against what the Lisp wizards did. There’s no feeling like standing on the shoulders of giants!

Here is the test code, which you can paste into your REPL and try for yourself. It runs our merge function against the system’s `merge` 1000 times on the same randomly generated input lists. For each test case, if the outputs match, we output a `t`; otherwise `nil`.

```(defun make-random-list (size &key max)
(loop repeat (random size) collecting (random max)))

(defun check-merge-output (function size)
(let* ((left (make-random-list size :max size))
(right (make-random-list size :max size))
(left-copy (copy-list left))
(right-copy (copy-list right))
(expected (merge 'list left-copy right-copy #'<))
(got (funcall function left right #'<)))
(if (equalp expected got)
t
(values expected got))))

(defun run-merge-tests (function)
(loop repeat 1000 collecting
(if (check-merge-output function 1000) t nil)))
```

Here’s what the output of a successful run looks like (Luckily, I have not yet found any unsuccessful ones):

```CL-USER> (run-merge-tests #'rml/merge3)
(T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T ...)
```

Based on the testing shown here, I think this implementation is Probably Fine ™. I’m happy with it, and it performs well enough for my needs.

In a future post, we’ll use the merge function we’ve shared here to write a merge sort.

## Performance Postamble

But what about the performance? It’s not bad, actually! As usual, it can depend on the implementation. Below I’ll list out how it compares in a few implementations. However I should state right now for the record that:

1. I’m not a performance or benchmarking expert. You should probably just stop reading here, because what follows is likely to be nonsense.
2. My implementation only works on lists (not vectors, too) and does not accept a sort key, as the standard dictates.
3. My implementation is not battle-hardened from living inside a Common Lisp implementation for decades (the most important point of all).

That said, what follows is what I saw when I ran the test code below on a few implementations:

```(defun check-merge-performance (function)
(time
(let* ((len 1000000)
(max 1000000)
(xs (make-random-list len :max max))
(ys (make-random-list len :max max)))
(progn
(funcall function xs ys #'<)
(values)))))

(defun check-system-merge-performance ()
(time
(let* ((len 1000000)
(max 1000000)
(xs (make-random-list len :max max))
(ys (make-random-list len :max max)))
(progn
(merge 'list xs ys #'<)
(values)))))
```

Note that the following tests were all run on a several-years-old Windows laptop with spinning disks, slow RAM, and a bunch of other applications running. Did I mention I’m not a performance and benchmarking expert? :-}

## Armed Bear Common Lisp

ABCL‘s `merge` implementation did not do so well against mine, but I think I must be missing something. For example, there’s probably a lot of subtlety around JVM performance on Windows I just have no idea about.

Mine ran in about 17 seconds.

```CL-USER> (check-merge-performance #'rml/merge3)
17.452 seconds real time
4000684 cons cells
NIL
```

Unfortunately, theirs took about 5 minutes to do about the same (*) computation. I’m not sure why. It’s possible I’m making some kind of mistake here, but I don’t know what it is. I used the timing code below because at first I thought the ABCL `merge` check had just hung altogether.

```CL-USER> (time
(let* ((len 1000000)
(max 1000000)
(xs (make-random-list len :max max))
(ys (make-random-list len :max max)))
(progn
(merge 'list xs ys #'<)
(values))))

312.803 seconds real time
412497 cons cells
NIL
```

(*) It’s not exactly the same, because remember that CL’s `merge` works on lists or vectors, so there will be some dispatching.

Out of curiosity, I went back and tried a few smaller inputs. ABCL seems to do OK with 2 100,000-element lists of random numbers, as shown below. Further, if you look at the number of cons cells, the function does appear to be O(n), which you would expect to see. This makes me think the problem is simply that 2 lists of 1,000,000 elements in the JVM is just too big a load for my little laptop, somehow.

```CL-USER> (time
(let* ((len 100000)
(max 1000000)
(xs (make-random-list len :max max))
(ys (make-random-list len :max max)))
(progn
(merge 'list xs ys #'<)               (values)))) 0.028 seconds real time 4025 cons cells NIL CL-USER> (time
(let* ((len 10000)
(max 1000000)
(xs (make-random-list len :max max))
(ys (make-random-list len :max max)))
(progn
(merge 'list xs ys #'<)
(values))))
2.24 seconds real time
40113 cons cells
NIL
```

## CLISP

CLISP‘s implementation is about twice as fast as mine, and uses about half as much memory, as is right and proper.

```CL-USER> (check-merge-performance #'rml/merge3)
Real time: 9.634908 sec.
Run time: 9.578125 sec.
Space: 56000000 Bytes
GC: 16, GC time: 0.578125 sec.
; No value
```
```CL-USER> (check-system-merge-performance)
Real time: 4.6764607 sec.
Run time: 4.671875 sec.
Space: 32000000 Bytes
GC: 6, GC time: 0.40625 sec.
; No value
```

## Corman Lisp

Corman Lisp is a Common Lisp implementation for Windows. It’s fast and has really good Win32 integration. I enjoy the IDE a lot.

If you like Lisp, you may enjoy this interesting talk by its creator Roger Corman where he discusses its development.

The system merge is about twice as fast as mine. It seems to come down to my implementation creating a lot of garbage, which is expected given my naive use of `push` and `pop` when I should be doing more direct mutation and structure sharing using e.g. `rplacd`.

```(check-merge-performance #'rml/merge3)
Total Execution time: 0.360289 seconds
Time spent garbage collecting: 0.093065 seconds

(check-system-merge-performance)
Total Execution time: 0.180082 seconds
Time spent garbage collecting: 0.0 seconds
```

## LispWorks (32-bit Hobbyist Edition for Windows)

LispWorks is a proprietary implementation put out by a company in England. Not only is their merge faster, they’re using about half as much memory. All as expected.

P.S. I just bought the “Hobbyist” version of the software, and I can definitely recommend it. Fast compiler, and the IDE and class browser, debugger, etc., are lot of fun to use.

```CL-USER 40 > (check-merge-performance #'rml/merge3)
Timing the evaluation of (LET* ((LEN 100000) (MAX 100000) (XS (MAKE-RANDOM-LIST LEN :MAX MAX)) (YS (MAKE-RANDOM-LIST LEN :MAX MAX))) (PROGN (FUNCALL FUNCTION XS YS (FUNCTION <)) (VALUES))) User time    =        0.062 System time  =        0.015 Elapsed time =        0.063 Allocation   = 2895872 bytes 0 Page faults CL-USER 41 > (check-system-merge-performance)
Timing the evaluation of (LET* ((LEN 100000) (MAX 100000) (XS (MAKE-RANDOM-LIST LEN :MAX MAX)) (YS (MAKE-RANDOM-LIST LEN :MAX MAX))) (PROGN (MERGE (QUOTE LIST) XS YS (FUNCTION <)) (VALUES)))

User time    =        0.015
System time  =        0.000
Elapsed time =        0.015
Allocation   = 1434380 bytes
0 Page faults
```

Anyway that’s all for now. As I said, you should take the “results” above with a grain of salt. Nonetheless it was interesting seeing how the different implementations behaved in an unscientific comparison.

# Good Reads: A Place of My Own

I just finished a second reading of this book over the course of a couple of months of 10-20 minute sessions in the evenings.

Despite myself, I have to admit: I like it very much. Even though the author’s concerns and way of seeing the world are very different from mine, it was fun and interesting to follow along with him on a meandering and -dare I say- slightly self indulgent journey through the process of building a little writing cottage in the woods on his property in Connecticut.

The meandering path Pollan takes you on, through various historical texts, architectural trends, and social changes, can be slow going in places but, depending on your point of view, it’s a rather luxurious as well. So much writing is trying to get to some kind of “point” these days, it seems. Most of one’s reading can consist of internet listicles with straight-to-the-point, SEO-optimized headlines. Even very good technical nonfiction can become a bit of a drag at times. It’s nice to spend a few hours walking along a scenic and sometimes semi-circular path with an erudite, friendly, and self effacing (if almost absurdly bourgeois) host like Pollan.

The literary excursions are interspersed with tales of Pollan’s interactions with his architect and a local carpenter that he hires to help him with his project. These scenes are the most enjoyable ones to read, in my view. The things that stand out to me are Pollan’s way of seeing other people with a kindness and tolerance of their foibles that I found endearing.

A final note: if you didn’t already know that architecture as a field is just plain off-the-rails crazy, you will once you’ve finished reading this book. It might be worth reading just for that.

I give it 4 out of 5 stars.