Intro to Lisp

Intro to Lisp

S-expressions

This page is intended for programmers who have not worked in any Lisp dialect before.

If you've ever talked to a Lisp programmer before, you've probably heard them talk about these scary things called S-expressions. In Lisp, all of your code is built up of S-expressions, but what they don't tell you is that an S-expression is just fancy-programmer-speak for "something or a pair of somethings". In layman's terms, an S-expression is either a "simple thing", such as a number or a string, or a pair of S-expressions. In Lisp, we denote a pair in parentheses with a dot between the elements. Unlike in many contexts, in Lisp expressions the parentheses are important and should not be left off.

(1 . (2 . 3))

This expression here is an S-expression. It consists of a pair whose first element is 1 and whose second element is the pair containing 2 and 3. In a sense, you can think of S-expressions as being a sort of binary tree.

It may not look like much, but we can build up any data structure we want using S-expressions. For example, the list containing the numbers 1 through 4 can be expressed as follows.

(1 . (2 . (3 . (4 . endoflist))))

The first element of each pair is an element of our list, and the second element of each pair is the remainder of the list. This models what we would call a forward-linked list in other programming languages. At the end of the list, we have the symbol "endoflist". A symbol (sometimes called an atom) is basically just an immutable string. However, in real Lisp code, the convention is to use the symbol (), not endoflist, to denote the end of a list. The symbol () is called "nil".

Lisp code is built up of forward-linked lists in the way we wrote them above. However, it quickly becomes tedious writing every pair individually, so we adopt the shortcut that a sequence of things listed out in parentheses should be desugared to a list. So (1 2 3) is really just a short way of saying (1 . (2 . (3 . ()))), but it's much easier on the eyes.

Programming

Lisp code is built up of lists, which denote function calls. But it's much easier to see it with some examples. If you want to run these yourself, just use ./Shiny (or ./Shiny.exe on Windows) to open up the interpreter and type these commands in.

(print "Hello, world!")

This is the basic "Hello world" program. When the interpreter sees this line of code, it's going to look at the first element to determine what function will be called. Since print is the first element, it's going to call the function print (which is built in). The remaining elements of the list will be evaluated and passed as arguments to the function. "Hello, world!" is a string, so it evaluates to itself. Let's look at a slightly more complicated example.

(print (m 100 10))

Here, we have a nontrivial call. This will still call print, but now when (m 100 10) is evaluated, it will recursively perform the same rules. So a function with the name m will be called with 100 and 10 as arguments. In ShinyLisp, m, short for "minus", is the subtraction function (in most Lisps, subtraction is done with -, but for reasons that will become more clear later, this was undesirable for golfing in ShinyLisp). So (m 100 10) will result in 100 - 10 which is 90, and 90 will be printed to the screen.

If you're running these in the interactive interpreter, you may notice a stray () being printed after each line. This is just the result of the print call. By convention, functions like print that don't have any meaningful value to return will return nil. The interactive environment is just showing you the return type of your expression.

Now, what if we want to print a list? Let's try it.

(print (1 2 3 4))

This will, rather oddly, print out 1 and then stop. This makes some sense, however. When the argument is examined, it tries to evaluate (1 2 3 4). The expression is a list, so we're going to call the function 1 with three arguments. But 1 isn't a function; it's a value. So the function call (1 2 3 4) simply returns the value 1, which is then printed. Fortunately, there's a built-in function to create lists.

(print (list 1 2 3 4))

list is a function which, appropriately enough, compiles all of its arguments into a list. This comes in handy if we want to build a list from complicated expressions. However, there's an easier way if we're building a list of literal values like we are here.

(print (quote (1 2 3 4)))

The quote operator is not a function; it's a special form that the language recognizes. When it is evaluated, it takes its only argument and returns it unevaluated. The quote form is a way of taking an expression and "freezing" it as a value. In fact, it's so commonly used in Lisp code that it has an abbreviation. The following code is equivalent to the above.

(print '(1 2 3 4))

The ability to quote expressions is very important, as it allows code blocks to be treated as data in a very straightforward way.