Understand Lisp in 16 minutes
Hi, in this article, we will be looking at a lesser-known language called Lisp, which is generally known as the programmable programming language.
If you’re looking to step up as a software engineer, getting at least a small taste of what Lisp and other similar languages offer is important.
This article will give you a short introduction into how, in Lisp, you can express yourself in a way that feels more powerful than other languages. We will only be looking at one of its most popular variants, Common Lisp. It won’t be an easy ride, but if you have some programming experience, you shouldn’t have trouble following along.
To understand what benefits Common Lisp offers, we will be building a program that allows us to query CSV files with SQL-like syntax. Let’s create two example files first:
# users.csv
name,age,city
"John",42,"New York"
"Mary",32,"San Francisco"
"Jane",31,"Los Angeles"
"Donald",55,"Las Vegas"
"Jill",24,"Boston"
"Jack",45,"Detroit"
"Mike",25,"Denver"
"Ann",31,"Houston"
"Carol",29,"Atlanta"
"Astrid",26,"Chicago"# countries.csv
country,capital,inhabitants
"Austria","Vienna",8.7
"Peru","Lima",30.4
"Belgium","Brussels",11.2
"France","Paris",66.9
"United States","Washington",318.9
"Australia","Canberra",23.1
"Ukraine","Kiev",45.5
"Kenya","Nairobi",45.5
"Albania","Tirana",2.8Now, in practice, we would like to run commands like this:
; to get the the users that are at least 30 years old
(select name from “users.csv” where (> age 30))
; to get countries starting with the letter a and their capitals
(select country capital from “countries.csv” where (char-equal (elt country 0) #\a))Don’t worry if you don’t understand everything yet, it will become clearer during this article! So, what’s happening here?
- in the first query, we call the macro (an augmented function) select, telling it to get all names from the file “users.csv”, where the age is greater than 30. (> age 30) is Lisp’s way of expressing what would be age > 30 in other languages
- in the second query, we get two columns (meaning we will need to somehow extract all the columns from our command) from “countries.csv”, for all rows where the character ‘a’ (written #\a in Lisp) is equal to the first character (accessed with elt for “element”) in the country name (what might have been written country[0] == ‘a’ in other languages)
- As you might have noticed, Lisp writes everything in prefix notation, putting operators ahead of arguments in expressions — so something like (if (member element list) (incf var)) could be written if (member(element, list)) { incf(var) } or if (element in list) { var++ } in other languages, increasing the value var holds if the element is found in the list.
Following along on your machine
If you want to run the code on your machine (and the benefit of setting it up outweighs the cost of doing so ;)), the easiest way to get started is to set up a Lisp environment — which can be done differently based on your operating system, but going for a portable system like Portacle or Lisp in a box should be suitable for most uses.
So, why Lisp?
I’ve already mentioned that Lisp is a programmable programming language. But what does that mean and how does it make it different from most other languages?
One of the thing Lisp does differently is allowing you to treat code as data. In most programming paradigms, you write code to manipulate data, which allows you to efficiently process real-world inputs/outputs. With Lisp, you can do that too, of course, but you can also apply the same logic to code, allowing you to manipulate it you write before it is executed.
This, in effect, gives you an additional layer of abstraction in the code you write. And since abstractions you can’t write down only exist for the programmer who thinks about them, why not take advantage of a language that offers you full support?
Where Lisp really shines is when writing Domain-Specific Languages. Those are languages that you might need to write where existing languages come short for your particular use case, like for example:
- querying a SQL database with using Python functions in your calls
- writing test scenario files with more complex options than JSON/YAML can offer
- parsing command line arguments that allow variables and functions
- communicating with an on-board system with efficient commands
In all these cases, if you’re lucky, someone will have had the same issue before and invented a language for it (in addition to havind written a compiler/an interpreter and a decent documentation that you can use). If you’re not, however, you will probably need to come up with your own constructs and your own code interpreter.
With a little additional overhead, you can also turn to Lisp and write your language as an extension of it, taking advantage of its powerful features, manipulating the code as simply additional data you can feed to your interpreter written in Lisp.
Even if you don’t end up using it, understanding how this extension works will benefit you greatly in your future endeavors. However, before we build our own domain-specific language, let’s look at a few basic concepts we will need.
Lisp concepts
Function definitions
Let’s first look at how we define functions in Common Lisp. Like in most languages, a function consists of a name, a list of parameters and a body. To combine them, we use the defun keyword:
(defun is-positive (number)
(> number 0))Here, we define the is-positive function, which takes a number argument and runs the body (> number 0), which simply returns t (true) or nil (false) when number is positive.
Evaluating (is-positive 3) returns t and (is-positive -6) nil.
We can also notice two additional key points:
- we don’t need to specify the types of variables, Lisp being dynamically typed
- we don’t need to explicitly return a value from our body, the latest value is automatically taken
Having understood that, here’s an implementation of the power (^ or **) function in Common Lisp (notice how multiple space-separated parameters can be specified):
(defun power (base exponent)
(if (= exponent 0)
1
(* base (power base (- exponent 1)))))If you have trouble understanding it with all the parentheses, try converting the operators to infix notation — this might have been written this way in other languages:
function power(base, exponent) {
if (exponent == 0) {
return 1;
}
return base * power(base, exponent - 1);
}Local variables
Now, let’s look at local, or lexical variables. If you need to bind a variable to a value for a specific block of code, you can use let:
(let ((name "John") (age 10))
(print name) ; John
(print age)) ; 10
(print name) ; error: variable name is unboundIn this example, we bind the name variable to “John” and age to 10, which we verify by printing the values. Once we exit the block, the variables are no longer bound. Counting the parantheses, we can see that let takes multiple arguments, the first being a list of bindings (each being a pair (name value)) and the rest the block statements.
An important thing to note is that the behavior of some functions in Lisp depend on the value of certain variables, called dynamic variables, whose value in a block can be similarly set with let.
For example, the read function, which is used to read data from streams (strings, files…) uses a readtable to associate symbols with meaning. This readtable is stored in the *readtable* variable and the behavior of read depends on the value it takes at run-time.
Other lexical bindings
Another keyword you can use to bind variables to values in a block is destructuring-bind. It’s called destructuring because you simply need to specify the structure your data will have at run-time and it will attach the variables correctly. For example, if (get-list) evaluates to a list of three elements, you can destructure and bind them to variables this way:
(destructuring-bind (a b c) (get-list)
(print b)) ; the second element of the returned listThis is similar to a block in which you run [a, b, c] = get_list() in other languages.
General language features
Let’s quickly go over a few basic functions and operators we will need.
To set the value of a variable to a value, use setf. For example:
(setf a 2)
(setf b 2)
(print (+ a b)) ; 4If you want to increase the value of a variable, you might write this:
(setf var (+ var amount))Lisp actually provides a shortcut, called incf, which does exactly that (and more!)
In reality, code like (incf var amount) actually expands into
(let ((temp amount))
(setf temp (+ temp amount)))where the let form is used to avoid evaluating var twice — because it could be any function which returns something and running it twice might have unintended side-effects.
In addition, incf generates an unique symbol to avoid naming the temp variable with something you might use in your function.
If this feels like too much, you are starting to understand the power of Lisp — a simple expression like (incf var), which could be written var++ in other languages, actually expands, at compile-time, into more complex code that allows you to use it for anything that might hold a value.
Few are the languages that allow you to run getObjectProp()++ to increment an object’s property. An even fewer languages allow you to write your own operators, like ++, to manipulate the arguments passed to them as if they were simply handling data!
Alright, now let’s take a break by looking at something easier: lists!
In Lisp, lists actually correspond to the list abstract data type, meaning they are built of singly linked nodes, called cons cells, each having a payload and a pointer to the next node.
Creating a list is probably the easiest: just use the list function:
; a list of 3 numbers
(list 1 2 3)
; a list of two strings, a number and a symbol
(list "I am" 35 'years "old")Of course, since they are the payloads of independent nodes, there are no type restrictions on what the list elements can hold. The second list even holds a symbol, ‘years, which is a primitive data type in Lisp and looks like a string.
Now that we have our list, let’s look at common operations:
(setf list (list 2 3 4)) ; list holds a list
(push 1 list) ; add 1 to the list
(print list) ; (1 2 3 4)
(member 5 list) ; nil - 5 is not in the list
(member 2 list) ; t - 2 is in the list
(print (nreverse list)) ; (4 3 2 1)push is used to add to a list — note that it adds “in front”, since it is the most efficient for a singly liked list
member, which we have used previously, checks if an element is in our list
nreverse reverses the list. A reverse function also exists, but it can be less efficient since it is required to leave the initial list untouched
A small note on our variable name — Common Lisp allows us to use the same name (list) for variables and for functions: it has two distinct namespaces, and will have no trouble understanding the list symbol when it is used as a function and when it is used as a value.
One final operator we have already seen but not explained is the if construct. It allows you to choose some code based on a condition, and other code otherwise.
(if (> 20 10)
5
(+ 2 2)) ; outputs 5 since 20 > 10if only evaluates the form it needs, so this form won’t make an error if var is not defined:
(if var (get-item-prop var "prop") "var not defined")The loop construct
Let’s now have a quick look at the loop construct, one of the ways you can iterate over practically anything in Lisp. I won’t introduce the full theory here (you can find everything you need, and more here), only provide a few characteristic examples:
; loop over a list
(loop for element in list)
; loop over a stream in, reading elements one by one
(loop for line = (read in))
; build a new list containing the cartesian product of headers and columns
(loop for h in headers
for c in columns
collect (list h c))A few notes:
- the loop construct is built to be easily understandable, even if you don’t know all of its features
- in the second example, when running loop for = x, the x form is re-evaluated at each iteration, similar to an increment expression in other languages
- loop allows you to specify some keywords that make the iteration easier, like collect — to “collect” into a list, if — to execute code conditionnally, or do — to run arbitrary code
Now, let’s try building an extract function, which will be useful when managing our CSV data table. extract takes the headers of our table, the columns we want to keep and a row, returning the values in the row that correspond to the kept columns.
For example, (extract (list ‘name ‘age) (list ‘age) (list “John” 42)) will return the filtered row (42). If you feel like it, try it first before looking at the code below!
(defun extract (headers cols row)
(loop for h in headers
for v in row
if (member h cols)
collect v))It should be pretty clear by now how this function works. Let’s try something harder now!
We will need an extract-commands function to parse the command passed to select. The function will take a list of commands, such as (age city from “users.csv” where (> age 20)) and return the the commands into three groups:
- the columns to extract: (age city)
- the name of the file: “users.csv”
- the where conditions: ((> age 10))
(defun extract-commands (commands)
(let ((columns) (file) (conditions))
(loop with stage = 0
for cmd in commands
if (member cmd '(from where)) do (incf stage)
else do (case stage
(0 (push cmd columns))
(1 (setf file cmd))
(2 (push cmd conditions))))
(list (nreverse columns) file (nreverse conditions))))Take a while to go through the code and try to make sense of what it is doing. The outermost let creates temporary variables to store our results. They are returned at the end, reversing the lists (since pushing adds to the front).
As for the extraction logic, I went with the approach of looping through all keywords, keeping track of a stage variable (initialized via with stage = 0) which tells us which of the three groups the symbol corresponds to.
If we see a keyword like from or where, we know we should increase the current stage value. Otherwise, we drop into a case statement — Lisp’s version of a switch + case — which works as expected:
- In the first stage, we add the keyword to the columns
- In the second stage, we are expecting a single value, the name of the CSV file
- In the third stage, the element is, in reality, code expressing a condition.
Now, let’s look at a few more features we will need.
Streams
To work with files, Lisp uses — like many other languages — input and output streams. When opening a file, it defaults to a character stream, which we can query using the read and read-line functions.
As expected, read-line reads a single line — which, in our case, will either be the file headers or a row of data.
read is a little more powerful, being able to read a full object. If we tell it that the content is comma-separated, it will correctly read a single column value each time we call it.
In addition to these, we will be using a utility function called with-open-file, which takes care of closing the file when we are done using it, and simply gives us the stream we need to get our data.
For example, if we run this code:
(with-open-file (in "users.csv")
(print (read-line in nil nil)) ; name,age,cityThe additional arguments to read make it return nil (false) when we arrive at the end of the file and the stream is empty.
Once we have our lines read by read-line, we will need to call read on them again — but read takes a stream, not a string. Luckily, we can use the with-input-from-string utility which does exactly what it says: take a string and convert make a stream out of it.
Good job for understanding all of this! Let’s look at two more advanced Lisp features now.
The readtable
I’ve mentioned earlier that the behavior of read (introduced in the previous section) can be modified by setting variables locally. One of them is the so-called readtable — accessed by the *readtable* variable, which tells read how to interpret individual characters.
For example, to read CSV files, we would like commas (,) to tell Lisp that the current object has ended, and that the next object will now begin. Luckily, there is already a character which does exactly that in Lisp — space!
We now only need the set-syntax-from-char function, which will simply say “when you see a comma, treat it like a space”.
One last thing we need to ensure is that we don’t modify the global readtable, which would make commas unusable in other parts of our code.
With all this in place, we can finally write our function to read a CSV line:
(defun read-csv-line (line)
; locally redefine the readtable to a copy
(let ((*readtable* (copy-readtable)))
; Treat commas like spaces
(set-syntax-from-char #\, #\Space)
; Convert the line back to a stream
(with-input-from-string (in line)
(loop for object = (read in nil nil)
while object
collect object))))Macros
Finally, let’s look at what makes Lisp really powerful: macros.
Defined with defmacro, they create objects that can be called like functions, except that what they return is not taken as a value, but as code to run to get it.
To return code that shouldn’t be evaluated, we can use the quote (‘) operator, which we used previously to build symbols:
(+ 2 4) ; 6
'(+ 2 4) ; the list (+ 2 4)
Let’s look at simple examples:
(defmacro random-digit ()
'(random 10))
We see that defmacro is similar to defun in its syntax. We only need to make sure to return code that will be evaluated later. Here, after calling (random-digit) we return ‘(random 10), which evaluates to the list (random 10), which is later evaluated to get a random digit.
(defmacro reverse-if (b a condition)
`(if ,condition ,a ,b))This second example is more interesting. We use the quasiquote (`backtick`) operator, which does the same thing as the quote operator, but allows us to use commas (,) to go back to evaluated mode.
This might feel overwhelming if it’s your first time seeing this, but if you’ve gotten this far, hold at it — there is no reason for you not to get it!
Let’s look at what happens when we call, for example, (reverse-if 0 (+ 3 var) (integerp var)):
- Our macro is passed the unevaluated code, meaning b gets the value 0, a the list (+ 3 var) and condition the list (integerp var)
- It returns a list with four elements, three of which are interpolated by using commas: the return value is effectively (if (integerp var) (+ 3 var) 0)
- The return value is evaluated as if we had written it instead of the macro call, checking whether var is an integer and returning 3 + var if it is.
For example, this will work:
(setf var 4) ; var is an integer
(reverse-if 0 (+ var 3) (integerp var)) ; 7
(setf var "Hello") ; var is a string
(reverse-if 0 (+ var 3) (integerp var)) ; 0
This example also shows us the power of macros — how would you have written this with a function?
(defun my-if (b a condition)
(if condition a b))
(setf var "Hello")
; This will make an error when evaluating (+ 3 var)
(my-if 0 (+ var 3) (integerp var))
An attempt like this won’t work, because (+ var 3) is evaluated before calling the function, whether var actually is an integer of not.
Now, we’re ready to combine everything we’ve learned to see Lisp in action!
(defmacro select (&rest commands)
(destructuring-bind (columns file conditions) (extract-commands commands)
(with-open-file (in file)
(let ((headers (read-csv-line (read-line in))))
`(with-open-file (in ,file)
; Skip the header line
(read-line in)
(let ((selected))
(loop for line = (read-line in nil nil)
while line do
(let ((row (read-csv-line line)))
(destructuring-bind ,headers row
(if (and ,@conditions)
(push (extract ',headers ',columns row) selected)))))
selected))))))There’s a lot going on in here, but you should be able to understand what the code is doing, at least at the surface:
- We define a select macro, which will take any number of arguments in a list called commands. This is similar to the rest (…) syntax in other languages
- We then call the extract-commands we defined previously, and bind its results to the columns, file and conditions variables
- Still in the macro we open the file using with-open-file, which gives us the in stream
- We read the header line with read-line, parsing it with our read-csv-line. We then store the results in a local headers variable
- Finally, we return the code to evaluate:
- Again, we will want to open the file, but skip the header line
- We loop over the lines of our file, passing them to read-csv-line
- With destructuring-bind, we create a small lexical block, where our headers will be bound to the row values: for example, in our users example, this will bind name to “John”, age to 42 and city to “New York”.
- If all the conditions hold — which we ensure by using an and form and spreading the conditions into it (“,@” works like “,” but for a list), we collect the values we want (which we extract from the row using our previously defined function) into a list called selected
- We return selected
Now, we can finally make our macro calls from the beginning!
; to get the the users that are at least 30 years old
(select name from "users.csv" where (> age 30))
; (("Ann") ("Jack") ("Donald") ("Jane") ("Mary") ("John"))
; to get countries starting with the letter a and their capitals
(select country capital from "countries.csv" where (char-equal (elt country 0) #\a))
; (("Albania" "Tirana") ("Australia" "Canberra") ("Austria" "Vienna"))For example, our first macro would first expand into this:
(with-open-file (in "users.csv")
(read-line in)
(let ((selected))
(loop for line = (read-line in nil nil)
while line
do (let ((row (read-csv-line line)))
(destructuring-bind (name age city) row
(if (and (> age 30))
(push (extract '(name age city) '(name) row) selected)))))
selected))Congrats on getting to the end of this introduction! If you haven’t already, give yourself a pat on the back and take a moment to reflect on what you just learned.
Of course, our code could be improved in many ways. Now the harder part of the job: think about how would you go about it and tell me in the comments!
Thanks for reading!