#commonlisp

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

If you want to see some neat videos, subscribe to dto, Baggers, and WarWeasle on YouTube. They all regularly post neat graphical stuff done in Common Lisp.

This appeared today on ##rust@freenode and it consists of a lot of my ideas that appeared when reading http://designisrefactoring.com/2016/04/01/rust-via-its-core-values/ .

< phoe_krk> steveklabnik: I'm a Lisper actually and stumbled upon that post and read it. It's fairly fascinating.

< phoe_krk> I mean- That other post.

< phoe_krk> http://designisrefactoring.com/2016/04/01/rust-via-its-core-values/

< phoe_krk> (Which is why the first question from Quora made me sad inside, but I digress)

< steveklabnik> ah :)

< steveklabnik> it was a good post

< phoe_krk> So I began wondering how to bend Common Lisp in Rust's direction and I got some interesting thoughts.

< phoe_krk> The easiest thing to do is explicit mutability in variables' declaration. I think I could fairly easily prototype a Lisp package that throws errors at you whenever you try to compile anything that attempts to mutate a variable not called mutable. (Of course, given I have the time and strength, and these two are rare and precious.)

< phoe_krk> GC would require writing or adapting a garbage collector that acts in real time; so far I've heard only of one such prototype on a single CL implementation, but it's already working.

< phoe_krk> Ownership sounds fairly simple in concept as you can modify the assignment operator to suit your needs - and modify the original reference to err out on people wherever necessary.

< phoe_krk> Borrowing is fairly trivial once you have ownership and exclusive mutability. Make a new variable, let it point to the same data, declare it immutable because it's a borrower.

< mbrubeck> Note that in Rust, ownership is purely a compile-time thing. Sounds like you're thinking much more dynamic (which makes sense for CL, but it may not give the same advantages).

< phoe_krk> Functions grabbing ownership when being called. This is doable, we can modify the way we define functions so it takes that into account.

< phoe_krk> mbrubeck: yes, I'm thinking dynamic and I'm aware of it. I'll explain why in a moment.

< mbrubeck> e.g. Rust doesn't need to add any runtime checks for "has this thing been moved?"

< phoe_krk> mbrubeck: it's a mindset difference, basically. :P

< phoe_krk> What I'm thinking is: how to aid the programmer.

< phoe_krk> And things like the ones I've mentioned are mostly about it.

< phoe_krk> Aside from GC, which sounds like the only exception.

< mbrubeck> yeah, makes sense

< phoe_krk> So basically, Lisp programming differs in concept as Lisp is image-based.

< phoe_krk> It's compiled, but the whole language is available and in memory all the time.

< phoe_krk> How does Rust check ownership? It has to compare something to something and err out if it has a wrong value.

< phoe_krk> And it has to do it at compile-time.

< mbrubeck> phoe_krk: The compiler does control flow analysis to see when something is moved.

< phoe_krk> mbrubeck: I see. So the compiler actually analyzes the *whole* code at compile-time.

< mbrubeck> phoe_krk: And it refuses to compile something that accesses a moved variable.

< phoe_krk> And at run-time, there's no checks, since everything was checked at compile-time.

< phoe_krk> Did I get it right?

< mbrubeck> Right. There are some caveats/complications; for example you can use the RefCell type to basically opt out of the static checking and use dynamic checks for safety, for example

< phoe_krk> So basically there are two steps to compilation in Rust.

< phoe_krk> 1) Assert everything is fine

< phoe_krk> 2) Compile

< phoe_krk> Right?

< steveklabnik> that's true for any kind of compiler that does static anything :)_

< steveklabnik> like, step 1 is 'type checking' in many languages

< mbrubeck> Lots of phases, in fact :) type-checking, region-checking, borrow-checking, drop-checking...

< phoe_krk> Yes, yes, but they *all* can be summed up by that. :P

< phoe_krk> And I meant mostly features unique to Rust by that.

< mbrubeck> Yes, you could consider all the "checking" to be various kinds of type checking

< phoe_krk> Such as the aforementioned borrowing, immutability and so on.

< phoe_krk> Over on the Lisp side, we have DEFUN, which is a macro that expands to a lot of other things. One of the effects is: we can either redefine it to add functionality, or wrap it in another macro that is fed the source code of the function we define.

< phoe_krk> Which means that one (e.g. I) can write a code walker that analyzes e.g. the variables we declare, looks for any keywords declaring mutability, and make a compile-time list of the mutable variables.

< phoe_krk> Then just compile. At compile-time we can run Lisp code; it means that when we "overload" the assignment "operators" to also check whether the variable in question is mutable, we can "just" compile.

< phoe_krk> The compile-time assertion disappears and we're left with a compiled, working function.

< phoe_krk> Unless our variable is declared immutable - at which point we have a nice compile-time error we can define on our own, too.

< phoe_krk> About ownership - it's the same thing, I think. A (much more complicated) code walker can traverse the code and do two things; wherever it sees assignment, change the owner of the code; whenever it sees a thing like Rust's & operator, it can strip the code of the operator and continue.

< phoe_krk> So in one case it creates a variable and changes the owner, in the other, it creates an immutable variable and doesn't change the owner.

< phoe_krk> I assume that "let mut a = &b;" is illegal in Rust?

< steveklabnik> it's not

< phoe_krk> I see.

< steveklabnik> it means the binding is mutable, but the refernece isn't

< phoe_krk> Yes - I got it. Fairly sane, too.

< heddwch> You can do let mut a = &mut b, though :p

< mbrubeck> There are similar things that are illegal though, like "let b = something(); let a = &mut b;"

< mbrubeck> (can't borrow a mutable reference to an immutable value)

< phoe_krk> :P

< phoe_krk> I see

< phoe_krk> This sounds fairly sane, too.

< phoe_krk> And very implementable.

< heddwch> Well, yea, it's implementable. The compiler is already implemented :p

< phoe_krk> Mutability, ownership and borrowing.

< phoe_krk> heddwch: i mean, in CL.

< phoe_krk> If it's good, then I'll copy it.

< heddwch> ah

< phoe_krk> (that's the way that programming languages have been going for the last 20 years in relation to Lisp, anyway~)

< phoe_krk> Anyway!

< phoe_krk> Just random thoughts that I'll be publishing on a blog of sorts.

< heddwch> I think you just did, with the blog being ##rust

< phoe_krk> heddwch: nope, it's not a blog

< phoe_krk> had a good deal of conversation around here while I was thinking aloud

< heddwch> ah

< phoe_krk> this might have not appeared in this form if I didn't post this here :P

So, with all due respect - thanks, ##rust!