#adventofcode

There are for sure more elegant solutions. I am just counting up or down by 1 to make sure I don't miss anything.

It's December soon, and that means Advent Of Code! :D I'm not trying to compete on the leaderboards, as the day of time is just not realistic for me to work on something like that each day AND I don't really care thaaat much. I just like solving puzzles and flexing the good old coding muscle on problems I don't usually encounter at work.

My setup this year is here: https://github.com/PadPalon/advent-of-code-2022.

UPDATE: Added generic-cl as suggested on Reddit.

Before last year’s Advent of Code started I declared on Twitter that I was going to do it in Common Lisp. And so I "did" (with a couple of 2016 challenges in CL as well). Yes, quite a bit of the challenges are missing. I hope to get back to them some time 😇

This writeup will be a summary of what I liked, what I did not like and finally a set of libraries for various purposes I used and found interesting. There are a couple of lists like that on the net (especially https://awesome-cl.com/, which I have actually submitted PRs to during my work on this article) but I wanted one that would include a couple of comments based on my personal experiences -- basically I’ll be making a purely subjective list of things I don’t want to forget about and it so happens that it will be publicly available on my blog 🤓

Just so you know, the views here will be expressed from the PoV of a long time Clojure and Racket fan.

Pros & Cons

Let’s start with what I liked:

Speed -- the best CL implementations are fast, while still allowing you to maintain a very readable, high level idiomatic code. With SBCL, the most popular implementation, you are basically getting one of the fastest lispy experiences possible. We obviously need to address the elephant in the room here and that’s Cloure. Clojure, thanks to JVM, can be faster than Common Lisp. However the speed often times comes at the cost of writing a relatively ugly “C wrapped in parens” style of code and/or you need enough data to get good amortization while JITting.

Debugging and optimization -- this one kind of relates to the first point as well. Common Lisp contains very powerful debugging, introspection and optimization tools that are part of the base lang spec. It does not matter what kind of implementation you use or whether you are using the IDE everyone thinks is the coolest right now... Hell, you can even disassmble your program to see the actual ASM code that your CPU will juggle.

Stability of the language -- there are people who can express this better so I’ll just link to the appropriate section of the magnificent article Steve Losh wrote in 2018:

My advice is this: as you learn Common Lisp and look for libraries, try to suppress the voice in the back of your head that says "This project was last updated six years ago? That's probably abandoned and broken." The stability of Common Lisp means that sometimes libraries can just be done, not abandoned, so don't dismiss them out of hand.

Specification & standard (kinda applies to Scheme as well) -- This is a tricky issue that has started many flamewars in the past, not just in the Lisp world (see the Spring vs Java EE battle). Having to adhere to a spec brings limitations but there are 2 counterarguments I can think of in the case of CL:

The power of macros means you can overcome almost all cases of stalled innovation without performance penalty. Look at the loop macro and how it was essentially completely covered with zero-cost abstractions.

The myriads of Clojure-like languages all suffer from the same problem: You cannot use libraries or any of the cool tools in the ecosystem. Yet, they themselves do not have anywhere near the traction necessary to be widely used production languages. CL shows that you can have a standard and still have enough room for differentiation and innovation.

Lisp-2 -- yep, you read that right. I would have never expected to say this (and I believe I’ve actually shunned Lisp-2 on this very blog some time ago?) but I actually like that functions in Common Lisp live in a separate namespace, for a very simple reason: code is read way more ofthen than it is written. When I look at code and see that seemingly annoying funcall I know it’s not just a top level defunned function and that I need to trace its origins somewhere else. Similar principle applies for the #' prefix (also makes life easier for syntax highlighters).

Next, the annoyances:

Widespread mutability and imperativeness -- Mutability is good if used in specific cases where it makes sense and if quarantined properly. However in CL mutability is king. It's not as much a problem of the language or implementations (you don't have to write mutable code) as it is a problem of the historical baggage -- it was never customary in the CL land to look bad at code that creates a mutable collection, then puts stuff in it in an imperative cycle and returns it from a function out to the dark and cold world... Purely functional collections exist but CL is not built around them. This is where Clojure shines.

CL Sequences apparatus not being user-extensible -- Common Lisp has a concept of sequences which puts a roof over lists and vectors and allows the user to use one function for both. However this facility, for some reason, is not easily extensible. This leads to many libraries implementing various new data structures and using completely custom API to do simple things like getting the size of a collection because (defmethod length ((seq my-epic-data-structure)) ...) signals COMMON-LISP:LENGTH already names an ordinary function or a macro. Fortunately there are libraries that are trying to solve this and to be honest it is not that much of a PITA anyway, because using a different function name for a special data structure has positive readability and performance implications. This applies to Racket too, to some degree. This lack of extensibility might have technical reasons I don't know of and if that is the case I'd be curious to learn and understand them.

LOOP -- I hate loop. Fortunately, this is an issue only if you have to deal with legacy code. The iteration story in CL is so good that you'll basically never have to write a single line of loop if you don't want to. My favourite comment on the topic is this one.

Destructuring not being 1st class citizen (enough) -- CL has macros with annoyingly long names to do destructuring and does not have the concept built-in deep enough for it to be ubiquitous in e.g. function definitions like you can see in JS or Clojure. Fortunately -- you guessed it -- libraries solve this issue satisfactorilly.

Interesting tools and libraries

What follows is a set of libraries that I tried and found useful -- libraries that helped me make a lot of annoyances (almost) irrelevant. I'll include one or two libraries that I have not used yet but would like to as they seem cool to me:

Platform tools

Quicklisp -- primary source of packages for CL. There is also Ultralisp, which is a faster-moving package distro.

Roswell -- this became my go-to tool for managing implementations and also packages. It can install packages from Quicklisp as well as GitHub repos in a manner similar to how go get works for example.

Qlot -- project-local dependencies manager that works well with Roswell. Think npm for Common Lisp. Can get dependencies from other Git repos, not just GitHub.

General purpose

Alexandria -- this is the utilities library in the CL world. It's so widespread that it's almost a standard thing.

Serapeum -- the Serapeum of Alexandria was an ancient Greek temple; referred to as the daughter of the Library of Alexandria. You get the idea ;) As you can see, the library is massive and I include it in most programs I write.

rutils (API) -- another impressive assortment of functions and macros. I would especially like to point out the with macro in the rutils.bind package, which is a kind of an extensible über-let.

metabang-bind -- another let on steroids. Unlike with it can bind arrays/vectors out of the box but is a little bit more chatty (and probably not as actively maintained).

cl-losh -- this is a library that its author explicitly does not want you to use. Sorry, Steve :) Your library is way too good for me to abide by your orders. What I found especially useful is the library of extensions for iterate, the de-facto replacement for LOOP we'll discuss later.

CL21 (and its very recent revival named 20XX) -- very interesting attempt at refreshing some of the more antiquated aspects of CL. It can be used as a library only to cherry-pick good stuff but it's probably less painfull to go all in and write programs "in" CL21 if it makes sense for a particular package.

cl-str -- Modern, simple and consistent Common Lisp string manipulation library.

Iteration & sequence procesing

iterate -- IMHO overall the best of iteration libraries for Common Lisp. A significantly lispier alternative to LOOP. Allows for very idiomatic, concise and understandable iteration code, is extensible and widely accepted and extended.

series -- the original transducers library (yes, those transducers). When used in tandem with taps (see my fork with a bugfix as well) it allows the programmer to write very succinct "top level" code (e.g. the main driver of a program that reads from a stream and delegates work to other parts of the code), or complex pipelines in general.

for -- another extensible LOOP replacement, this time a bit closer to Racket's ecosystem of for comprehensions.

gmap -- this is probably one of the most underrated/under-popularized pieces of gear I've come across in the Common Lisp land (tracing its origins back to 1980!). Combines mapping, filtering and reducing into a neat transducer-ish extensible construct and has a built-in support for FSet, a functional collections library we'll talk about later. The same Lisp project also contains new-let ...guess what is it supposed to be 😉 Yeah, let is the new loop.

generic-cl -- provides a generic function wrapper over various functions in the Common Lisp standard, such as equality predicates and sequence operations. An answer to on of my critical points above (defines generics that overlay CL builtins).

You can also find many small iteration helper tools scattered across the general purpose libraries we discussed in the previous section. Mapping from X to Y, reducing all kinds of things etc...

Math

cl-geometry -- 2D computational geometry library, which made work on Day 3 of AoC 2019 very enjoyable for me.

Data structures

FSet -- functional library of sets, maps and bags that has a natural and clean API and as we already mentioned, it comes with the added bonus of being written by the same guy who wrote gmap.

cl-containers -- a massive collection of (mostly tree-based) data structures and algorithms, useful when you need stuff like sorted map etc.

graph-utils -- graph data structure and algorithms

sycamore -- fast purely functional data structures

random-access-lists -- useful library for when you need a listy data structure and you don't want to pay O(n) when accessing elements in it.

array-operations -- library for concisely expressing operations on (multidimensional) arrays. Being used to the Racket array library it took me a while to get used to some of the specifics but it indeed is very powerful and fast.

Static typing & contracts

Apart from the built in tools for specifying types statically you can also use these to strenghten your safety net:

defstar -- Macros for easy inclusion of type declarations for arguments in lambda lists. Can replace defun, defmethod, defgeneric and others.

cl-algebraic-data-type -- a library for defining algebraic data types in a similar spirit to Haskell or Standard ML, as well as for operating on them

quid-pro-quo -- A contract programming library for Common Lisp in the style of Eiffel’s Design by Contract

Testing

These are the two testing libraries I tried out. I prefer parachute, the API feels more natural to me. There are others and it's getting worse 😉

rove

parachute

OOP

In addition to the following libraries you should check CLOS-related sections of almost all of the general purpose util libraries we discussed above. They contain stuff to help make CLOS a bit less verbose.

defclass-std -- a macro that atempts to give a very DRY and succint interface to the common DEFCLASS form. The goal is to offer most of the capabilities of a normal DEFCLASS, only in a more compact way.

sheeple -- prototype-based OOP in Common Lisp? 😱 Because we can!

Verdict