slashbinbash.de / Introduction to Lisp

The purpose of this page is to give you a short introduction to the Lisp family of languages and some of the basic concepts that they share.

List Evaluation

The name Lisp is short for "list processor". The reason 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)

We first need to look-up the plus symbol '+'. If the result is a function, the function is executed. 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

This is equivalent to writing the following mathematical expression:

(9 - 3) + (5 * 2)

Special Forms

Each function has its own set of rules. These rules specify how the expressions of a form are evaluated.

To give you a better understanding, lets take a look at how if-statements are implemented. In C-like languages, the if-statement has the following structure:

if (8 < 5)
    printf("A");
else
    printf("B");

It can be broken down into three parts:

  1. The condition, it must be evaluated first:
    (8 < 5)
  2. The expression that is evaluated if the condition is true:
    print("A")
  3. The expression that is evaluated if the condition is false:
    print("B")

These three parts are present in any if-statement, regardless of which language you use.

In Lisp languages, if-statements are expressed by using the if function. Its form and behavior is clearly defined in the documentation of the language implementation. The if function is typically defined as:

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

Example:

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

Definition of the if function in different dialects:
Common Lisp, GNU/MIT Scheme, Racket

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 function returns the result of either the then-form or else-form.

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

(+ 3 (if (= a b) 10 12))

This might look clunky at first, but it is not much different from the conditional operator of other languages.

C/C++, Java, JavaScript

3 + (a == b ? 10 : 12)

Python

3 + (10 if a == b else 12)

Other statements are also expressed as functions in Lisp.

Syntax vs Semantics

Lisp dialects allow us to express concepts in different ways. For instance, you could create an if function that looks like this:

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

then and else are keywords in the context of this if implementation. They do not change how the if-statement is interpreted.

Or instead of defining variables like in Scheme by using define:

(define x 10)   ; x = 10

You could create a function that does the same thing but with a different syntax:

(let mut x 10)  ; define a mutable variable x with the value 10

Since expressions or forms are nothing more than values in a list, you can easily redefine the language. However, it is important to be aware of the semantic differences between dialects. The do function in Common Lisp does something completely different than the do function in Clojure.

Lisp languages also allow you to express some concepts in a declarative style. You don't tell the computer what to do but what the result should be:

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

The data structure in this example is indistinguishable from the program structure.

As you can see, the language is very versatile. You can change it so that it fits your particular needs.

Code is Data/Data is Code

Programs in Lisp languages are a sequence of lists. The lists are evaluated one by one. However, as long as a list is not evaluated, it is nothing more than plain data.

This results in two very important properties:

  1. You can parse the program as if it is data
  2. You can generate code by creating lists

Consider the following Lisp code:

(define ifexpr (quote (if (= 3 3) 10 15)))

(eval (second ifexpr))
    => (eval (= 3 3))
    => true

Lets create a function that switches the forms of the if-expression, and generates executable code:

(define (switch-cases expr)
    (list 'if (second expr) (fourth expr) (third expr)))

(eval (switch-cases ifexpr))
    => (eval (switch-cases (if (= 3 3) 10 15)))
    => (eval (if (= 3 3) 15 10))
    => 15

This is only the tip of the ice-berg. Many 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.

Consider checking out my Lisp dialect Sikkel.

Resources

Common Lisp

Scheme

Clojure

Racket