slashbinbash.de / Introduction to Lisp

The purpose of this page is to give you a short introduction to the Lisp family of languages. It is by no means complete. I present one aspect that I find most fascinating about the language, and that sets it apart from most languages out there.

List Evaluation

The name Lisp is short for "list processor". This is because the main data-structure, the linked list, is not only used to define the data that should be processed, but also the program itself.

A list has the following form:

(elem0 elem1 elem2 ... elemN)

A list doesn't have any meaning in itself, unless it is evaluated. Let's take a look at the evaluation of the following list:

(+ 3 5)
    => 8

The plus symbol '+' resolves to a function, which is invoked. The remaining objects of the list are the function parameters. Since the function implements arithmetic addition, the result of the evaluation is the integer 8.

Nested lists are evaluated first. The results are used as the input parameters for the addition:

(+ (- 9 3) (* 5 2))
    => (+ 6 10)
    => 16

The evaluation is the same for functions defined in the language. The following line prints "Hello World!" to the screen:

(print "Hello World!")

Special Forms

Special forms or special operators behave differently from a function call, when they are evaluated. One example of such a special form is the if-expression, which has the form:

(if test-form then-form else-form)

Example:

(if (< 8 5)         ; test-form
    (print "A")     ; then-form
    (print "B"))    ; else-form

First, the test-form is evaluated. If the test-form returns true, the then-form is evaluated. If the test-form returns false, the else-form is evaluated. The expression returns the result of either the then-form or else-form.

Because if returns a value, you can use it in another expression:

(print (if (< 8 5) "A" "B"))

Many concepts that are known from other languages are expressed by special forms. Most special forms are expressions and return values.

Syntax vs Semantics

Lisp has very few syntactic rules. If you understand the syntax of the list, you have seen most of the language. The complexity lies in learning the core functions, the special forms, and their semantics. These can be different for each Lisp dialect.

I want to give you a few examples of what role syntax and semantics play in Lisp. Here is how a function is defined in different Lisp dialects:

;; Common Lisp
(defun my-function (a b)
    (+ a b))

;; Scheme
(define (my-function a b)
    (+ a b))

;; Clojure
(defn my-function [a b]
    (+ a b))

Every dialect has a slightly different way of expressing the same thing. For me, this is a sign of how flexible the idea behind Lisp is. This idea also carries over into how you use and extend the language.

Many features that would require specialized syntax in other languages, can be implemented very concisely in the Lisp language itself.

Lisp languages also allow you to express some ideas in a declarative style. You don't tell the computer what to do but what the result should be. Consider this example of a file menu hierarchy:

(menu "File"
    (menu-item "Open" onOpen)
    (menu-item "Save" onSave)
    (menu-item "Recent" 
        (menu-get-recent))
    (separator)
    (menu-item "Exit" onExit))

The data structure is indistinguishable from the program structure. If you define functions for each symbol in this example, you could create an actual UI entry in a menu bar, if you evaluate the list.

Code is Data/Data is Code

We already established that programs in Lisp languages are sequences of lists that are evaluated. If they are not evaluated, they are just plain data structures that can be manipulated. This has a few implications.

Code and data have the same representation

For instance, it is not uncommon to use an XML or JSON format to represent configuration files, or to store and exchange data between programs. These files have to be parsed by a special piece of software that knows how to read and interpret the format, and that maps the objects of the format to objects of your problem domain.

Because Lisp uses the same representation for code and data, there is no special parsing and mapping required. The same goes for writing data structures from Lisp to files.

You can parse a program as if it is data

If you have code that is not evaluated yet, you can take it apart, analyze it, and re-arrange it from within another program. For instance, you could re-arrange an if-expression if you wanted.

Going back to the file menu example from the previous section:
You could programmatically add another menu item to the list, before it is evaluated and the UI is created. Whenever you change the list, you are effectively changing the execution of the program.

This leads directly into the third point.

You can generate code by creating lists

If you can parse code as data and manipulate it, you can also generate code by creating lists of objects that can be evaluated, even at runtime.

Consider the following Lisp code:

(define if-expr (quote (if (= 3 3) 10 15)))

(eval (second if-expr))
    => (eval (= 3 3))
    => true

Lets create a function that swaps the then-form and else-form of the if-expression, and generates executable code:

(defun swap-forms (expr)
    (list 'if (second expr) (fourth expr) (third expr)))

(eval (swap-forms if-expr))
    => (eval (swap-forms (if (= 3 3) 10 15)))
    => (eval (if (= 3 3) 15 10))
    => 15

This is only the tip of the ice-berg. Most Lisp implementations have Macro systems that allow you to generate code and modify the language at compile-time.

Conclusion

I hope this article gave you a quick glimpse of what Lisp languages are. If you want to learn more, check out the links in the Resources section below.

If you are interested in learning a Lisp language, I would personally recommend Clojure. But there are many other viable options.

Resources