This is a short introduction to LISP programing using Common Lisp.

Common Lisp is the most popular dialect of LISP. Originally created as a tool to describe recursive functions of symbolic expressions. More history and detailed description of LISP implementation you can find here.

Why LISP?

• macros - the ability of creating mini languages best for problem; possibility of abstract almost everything(not everything can be done with class, method or function)
• performance - both programmers(100k lines of code in C you can fit in 10k lines of code in LISP) and often LISP programs works faster than written in C
• code consistency

Who uses LISP?

• NASA - space missions
• AMD - designing processors
• YahooStore
• Boeing
• others…

To start Common Lisp type in clisp in your console. It starts with the prompt.

LISP can perform math calculations. Lets count (2 * cos(0) * (5+9)):

(* 2 (cos 0) (+ 5 9))
28

In response, we received the result of expression. Common Lisp reads in an expression, evaluates it, and then prints out the result.

LISP expression are composed of forms. The most common LISP form is function application. Function call f(x) known from other programming languages is equivalent to (f x) in LISP, in the same way cos(0) is written as (cos 0).

The general form of expressions in LISP:

(function-name arg_1 arg_2 ... arg_n)

As in many programming languages LISP evaluates function calls in applicative order, which means that all the argument forms are evaluated before the function is invoked. Numeric values like 5 and 9 are called self-evaluating forms: they evaluate to themselves. To evaluate (+ 5 9) in applicative order, the forms 5 and 9 are respectively evaluated to the values 5 and 9 before they are passed as arguments to the + function.

Lisp allows you to define your own functions using defun:

(defun function-name arguments body-function) 

For example, the function that returns double x:

(defun double (x) (* 2 x)) 

Now try the function:

(double 5)
10
[4]> (double 21)
42 

To edit programs in Lisp you can use any ASCII editor (gedit, kate, nano, vi under Linux/Unix or Windows notepad).

Create the test.lisp file in the current directory and write into the file definition of double function. Loading file into Lisp:

(load "test.lisp")
; File test.lisp Loading ...
; Loaded file test.lisp
T

T is true - the file loaded correctly.

You can use the functions contained in the files loaded in the same way as those defined directly in the environment.

(double 13)
26

File compilation:

(compile-file "test.lisp")
; Compiling file /home/lab/test.lisp ...
; Wrote file /home/lab/test.fas
0 errors, 0 warnings
# P "/home/lab/test.fas";
NIL;
NIL

A compiled file test.fas can be loaded into the environment:

(load "test")
; Loading file /home/lab/test.fas ...
; Loaded file /home/lab/test.fas
T

Functions that call themselves are called recursive functions. They are useful in many problems, for example factorial:

x! = 1 for x = 1
x! = x * (x - 1)! for x > 1

Here's an example program computing factorial using recursion:

(defun fact (x)
  (if (x = 1)
    1
    (* X (fact (- x 1 )))))

There is an if conditional used in the example code. Its general form isl

(if test if-true if-false)

Firstly the test condition is evaluated; if returns true the if-true code is executing, if returns false the if-false code. In LISP nil treads as false; everything else is true.

Fact function is recursive function - it calls itself. In this type of function the stop condition is necessary to calling function indefinitely. In this case, the x = 1.

To better understand how the recursion works trace the factorial example:

(trace FACT)
; Tracing function FACT.
 
(FACT 6)
1. Trace: (FACT'6)
 2. Trace: (FACT'5)
  3. Trace: (FACT'4)
   4. Trace: (FACT'3)
    5. Trace: (FACT'2)
     6. Trace: (FACT'1)
     6. Trace: FACT ==> 1
    5. Trace: FACT ==> 2
   4. Trace: FACT ==> 6
  3. Trace: FACT ==> 24
 2. Trace: FACT ==> 120
1. Trace: FACT ==> 720
720

1. Write a program that count sum of n natural numbers. Use recursion:

T (n) = 1 for n =  1
T (n) = n + T (n - 1) for n > 1

Load program to LISP and trace it.

Sample solution: (defun sum-n-numbers (n) (if (= n 1) 1 (+ N (sum-n-numbers (- n 1 )))))

1. Write a program to compute n'th Fibonacci number. Use recursion:

FIB (n) = 1 for n = 0 or n = 1
FIB (n) = FIB (n - 1) + FIB (n - 2) for n > 1

Sample solution: (defun Fibonacci (n) (if (or (= n 0) (n = 1)) 1 (+ (Fibonacci (- n 1)) (Fibonacci (- n 2 )))))

The basic data structure in Lisp is the list (the name LISP comes from LISt Processing). Lists are placed in round brackets (). The content of list may be atom or different list. Everything is either a list or atom.

The basic block of list is a structure called cons. It consists of two fields: car and cdr.

Each cell is a list of cons - value in the car, in the cdr the address of the next cons cell. NULL (NIL) in the cdr field marks the end of the list.

Examples of lists:

A list of numbers:

'(1 2 3 4 5 6 7)
(1 2 3 4 5 6 7)

List of colors:

'(white green yellow red)
(WHITE GREEN YELLOW RED)

Mixed list:

[14]> '(1 two (3 four (six 5)))
(1 two (3 FOUR (SIX 5)))

Notice that we have quoted the list using the quote special form. This is necessary because, without the quote, LISP would interpret the expression (1 2 3 4 5 6 7) as a function call to a function with name “1” and arguments 2, 3, …, 7 The quote is just a syntactic device that instructs LISP not to evaluate the a form in applicative order, but rather treat it as a literal. The quote symbol ' is nothing but a syntactic shorthand for (quote …).

To get the first element(first car) of list you may use car or first:

(first '(1 two (3 four (six 5))))
1

If you want to get n-th car, it is best way to do it:

(nth 2 '(1 two (3 four (six 5))))
(3 FOUR (SIX 5))
(nth 3 '(1 two (3 four (six 5))))
NIL
(nth 4 '(1 two 3 four six 5))
5
(nth 3 '(1 two 3 four six 5))
FOUR

Please note that the first element has index 0. To get cdr field of cons use cdr and nthcdr.

Rather than write (car (car arg)) we can write (caar arg). Letter 'd' means that there is a cdr, and 'a' - car. (cadar arg) = (car (cdr (car arg))). It is better not to use these features and instead of them use first … tenth, nth/nthcdr. The exception is caar (and caaar) - it is clear that we get value from the nested list.

Cdr function is equivalent to rest.

(rest '(1 two (3 four (six 5))))
(Two (3 FOUR (SIX 5)))
(first (rest '(1 two (3 four (six 5 )))))
TWO
(rest (rest '(1 two (3 four (six 5 )))))
((3 FOUR (SIX 5)))

To check whether the list is empty, use null:

(setq x nil)
NIL [24]> (null x)
T
(setq x '(1 2))
(1 2)
(null x)
NIL
(null (rest x))
NIL
(null (rest (rest x)))
T 

LISP has a built-in function for appending lists

(append '(Ala Ola Ela)' (Marta King Basia))
(ALA OLA MARTA KINGA BASIA ELA)

Simple function adding two lists(similar to append):

(defun add-list (L1 L2)
     (if (null L1)
       L2
     (cons (first L1) (add-list (rest L1) L2))))

Let's try add-list:

(add-list '(Ala Ola Ela)' (Marta King Basia))
(ALA OLA MARTA KINGA BASIA ELA)

Lisp has a built-in function for reversing lists:

(reverse '(1 2 3 4 5))
(5 4 3 2 1)
(reverse '((1 2) (3 4) 5))
(5 (3 4) (1 2))

1. Write a program counting all elements from list. The list will contain only numbers.

Sample solution: (defun sum-el-list (L) (if (null L) 0 (+ (First L) (sum-el-list (rest L )))))

1. Write a program reversing the list. Use append or add-list.

Sample solution: (defun turn-list (L) (if (null L) Nil (append (list-turn (rest L)) (list (first L ))))) or (defun turn-list (L) (if (null L) Nil (append (last L) (turn-list (butlast L )))))

CLISP Homepage On LISP book The Common Lisp Cookbook