~/blog

An apology to Lisp

2025-03-31 (last updated )

In the past week, I have complained about no other programming language more than Lisp (or rather Lisp-like languages); although I've not given it a fair chance.

For context, I have spent the majority of my life primarily using C-like programming languages.

Why I am thinking about Lisp

Lately, with increased frequency, I have been using a text editor called Emacs, written in a programming language called Emacs Lisp.

I tend to use VS Code for code editing; however I may reach for Emacs for a number of reasons, including to reproduce another developer’s setup while I follow along with their work or contribute to their project. If a code repository has Emacs configuration, I should at least try taking advantage of it.

Why I oughta learn Lisp

While using Emacs, I find myself regularly copy-pasting Emacs Lisp configuration from the internet. Having little confidence in my understanding of the language, I’m often trusting the source’s explanation of what the code does to my computer.

The only reason I trust at all: the software I'm using is open-source, so at least if it contains vulnerabilities or malicious code, someone (not yet me) could detect it.

That's actually not even entirely true. To see what I mean, check out Ken Thompson's 1984 paper Reflections on Trusting Trust which calls into question how much we can trust compilers and how malicious code can be obfuscated.

In order to mitigate risk, it's wise to increase knowledge and control over one's tools. In the case of Emacs, that means learning a bit of Lisp.

Me, lazy, complaining

Rather than address the root of the problem and study Emacs Lisp, I stomp my feet and complain: I have other things to learn and only so much time in my day. Plus, the language looks funny —what with its odd use of parentheses and un-paired single-quote characters.

To show an example of the syntax to which I’m referring, take a look at this common boilerplate config from the MELPA (Milkypostman’s Emacs Lisp Package Archive) setup instructions:

(require 'package)
(add-to-list 'package-archives '("melpa" . "https://melpa.org/packages/") t)
(package-initialize)

Um, hello,

  • Parentheses are supposed to wrap arguments after a function name, as in standard calculus (example: f(x)), and
  • Quotes are supposed to come in pairs —or should we call 'em apostrophes?

For comparison, the same code as if it were written in CommonJS:

const package = require('package');
package.addRepository('melpa', 'https://melpa.org/packages/');
package.initialize();

Lisp people know their language is quirky

From An Introduction to Programming in Emacs Lisp:

To the untutored eye, Lisp is a strange programming language. In Lisp code there are parentheses everywhere. Some people even claim that the name stands for “Lots of Isolated Silly Parentheses”. But the claim is unwarranted. Lisp stands for LISt Processing, and the programming language handles lists (and lists of lists) by putting them between parentheses. The parentheses mark the boundaries of the list.

Perhaps “untutored” is an important word here. To me this implies Lisp, unlike JavaScript and Python is not made to be easily parsed by laypeople. In order to have any idea what's going on, one must first have a robust understanding of linked-lists.

Okay, I'll give it a try

Problem statement

Let's try to model the following process:

When given a pair of colored crayons, Rory consistently draws one line on a piece of paper and then throws both crayons onto the floor. Rory prefers to draw in ROYGBIV order but doesn’t mind skipping colors.

Pseudocode

Notice we have not been told the sequence of crayon pairs that will be given to Rory, but we know how Rory makes decisions and the side effects of Rory’s artistic process. We have enough information to model how Rory processes lists of pairs of crayons:

  • There is a type called color that can be one of: “red” “orange” “yellow” “green” “blue” “indigo” “violet”
  • There is a type of object called crayon.
  • A crayon has a color.
  • There is a list of colors called art.
  • There is a list of crayons called floor.
  • There is a process we will call measure-color-distance that takes a pair of colors, start and end, and returns the positive (greater than 0) number of steps needed to get from start to end in the repeating sequence “red” “orange” “yellow” “green” “blue” “indigo” “violet”…
  • There is a process we will call choose-crayon that takes a pair of crayons and returns the crayon with the minimum distance from the last item in art to the crayon’s color using the process measure-color-distance.
  • There is a process called make-art that takes a pair of crayons, pushes to art the color of the crayon returned by choose-crayon, and pushes each crayon in the pair of crayons to the floor.

Implementation

Here is an implementation that compiles in CommonLisp:

(defparameter *colors* '(red orange yellow green blue indigo violet))

(defstruct crayon
  (color nil))

(defparameter *art* nil)
(defparameter *floor* nil)

(defun measure-color-distance (start end)
  "Returns the positive number of steps needed to get from start to end in the repeating color sequence."
  (let* ((cycle-length (length *colors*))
         (start-index (position start *colors*))
         (end-index (position end *colors*)))
    (mod (- end-index start-index) cycle-length)))

(defun choose-crayon (crayon1 crayon2)
  "Returns the crayon closest in color-distance to the last color in *art*, or the first color if *art* is empty."
  (let* ((last-color (if *art* (first (last *art*)) (first *colors*)))
         (distance1 (measure-color-distance last-color (crayon-color crayon1)))
         (distance2 (measure-color-distance last-color (crayon-color crayon2))))
    (if (< distance1 distance2) crayon1 crayon2)))

(defun make-art (crayon1 crayon2)
  "Takes a pair of crayons, pushes the chosen crayon's color to *art*, and pushes both crayons to *floor*."
    (let ((chosen (chose-crayon crayon1 crayon2)))
      (push (crayon-color chosen) *art*))
    (push crayon1 *floor*)
    (push crayon2 *floor*))

Notice how I did not need to make an "artist" class and instantiate an object called Rory. I only created types for the things Rory sees: color, crayon, art, and floor. Rory is not an element in the process. Rory is the processor.

Example usage

Now that we have a model for Rory's artistic process, we can call make-art from a meta process which selects the crayon pairs to give to Rory:

(let ((crayons '((#S(crayon :color red) #S(crayon :color blue))
                 (#S(crayon :color yellow) #S(crayon :color green))
                 (#S(crayon :color violet) #S(crayon :color orange))
                 (#S(crayon :color blue) #S(crayon :color indigo))
                 (#S(crayon :color red) #S(crayon :color violet))
                 (#S(crayon :color orange) #S(crayon :color yellow))
                 (#S(crayon :color green) #S(crayon :color blue))
                 (#S(crayon :color indigo) #S(crayon :color red)))))
  (dolist (pair crayons) (make-art (first pair) (second pair)))
)
(format t "Art: ~A~%" (reverse *art*))
(format t "Floor: ~A~%" *floor*)

A more advanced example may involve recycling crayons from the floor using yet another process.

These parentheses are powerful

Just as Reverse Polish notation (RPN) gave us a fast way to use four-function calculators, Lisp’s fully parenthesized prefix notation (also apparently called “Cambridge Polish”) provides a clean interface for representing modular computation over list-like data structures.

Lisp is not ideal for all applications, which explains why I have gone so long without learning it; however it has profound use-cases in modern mathematical computation and machine learning.

The following video from 2swap is not specifically about Lisp, but it demonstrates, in a mesmerizing way, a related concept called λ-calculus which also uses fully parenthesized prefix notation and influenced the creation of Lisp. I hope you enjoy it as much as I have.

References

Categories