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

=== Let's start with 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 [[http://www.paulgraham.com/rootsoflisp.html|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...

=== Environment ===
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)):

<code lisp>
(* 2 (cos 0) (+ 5 9))
28
</code>
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:
<code lisp>
(function-name arg_1 arg_2 ... arg_n)
</code>
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.

=== Maths in LISP ===

^  Numeric Functions  ^  Meaning  |
|  (+ x1 x2 ... xn)  |  The sum of x1, x2, ..., xn  |
|  (* x1 x2 ... xn)  |  The product of x1, x2, ..., xn  |
|  (- x y)  |  Subtract y from x  |
|  (/ x y)  |  Divide x by y  |
|  (rem x y)  |  The remainder of dividing x by y  |
|  (abs x)  |  The absolute value of x  |
|  (max x1 x2 ... xn)  |  The maximum of x1, x2, ..., xn  |
|  (min x1 x2 ... xn)  |  The minimum of x1, x2, ..., xn  |

^  Shorthand  ^  Meaning  |
|  (1+ x)  |  (+ x 1)  |
|  (1- x)  |  (- x 1)  |
|  (zerop x)  |  (= x 0)  |
|  (plusp x)  |  (> x 0)  |
|  (minusp x)  |  (< x 0)  |
|  (evenp x)  |  (= (rem x 2) 0)  |
|  (oddp x)  |  (/= (rem x 2) 0)  |

^  Logical Operators  ^  Meaning  |
|  (or x1 x2 ... xn)  |  Logical or  |
|  (and x1 x2 ... xn)  |  Logical and  |
|  (not x)  |  Logical negation  |


=== Defining functions ===
Lisp allows you to define your own functions using **defun**:
<code lisp>
(defun function-name arguments body-function) 
</code>

For example, the function that returns double x:

<code lisp>
(defun double (x) (* 2 x)) 
</code>

Now try the function:

<code lisp>
(double 5)
10
[4]> (double 21)
42 
</code>

=== Editing, compiling and loading programs ===
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:
<code lisp>
(load "test.lisp")
; File test.lisp Loading ...
; Loaded file test.lisp
T
</code>
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.
<code lisp>
(double 13)
26
</code>

File compilation:
<code lisp>
(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
</code>

A compiled file test.fas can be loaded into the environment:
<code lisp>
(load "test")
; Loading file /home/lab/test.fas ...
; Loaded file /home/lab/test.fas
T
</code>

=== Recursion ===
Functions that call themselves are called recursive functions. They are useful in many problems, for example **factorial**:
<code>
x! = 1 for x = 1
x! = x * (x - 1)! for x > 1
</code>

Here's an example program computing factorial using recursion:
<code lisp>
(defun fact (x)
  (if (x = 1)
    1
    (* X (fact (- x 1 )))))
</code>

There is an //if// conditional used in the example code. Its general form isl
<code lisp>
(if test if-true if-false)
</code>
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:
<code lisp>
(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
</code>
== Exercises ==
  - Write a program that count sum of n natural numbers. Use recursion:
<code>
T (n) = 1 for n =  1
T (n) = n + T (n - 1) for n > 1
</code>
Load program to LISP and trace it.

<del>
Sample solution:
(defun sum-n-numbers (n)
  (if (= n 1)
  1
  (+ N (sum-n-numbers (- n 1 ))))) </del>
  -  Write a program to compute n'th Fibonacci number. Use recursion:
<code>
FIB (n) = 1 for n = 0 or n = 1
FIB (n) = FIB (n - 1) + FIB (n - 2) for n > 1
</code>

<del>
Sample solution:
(defun Fibonacci (n)
   (if (or (= n 0) (n = 1))
       1
     (+ (Fibonacci (- n 1))
        (Fibonacci (- n 2 ))))) 
</del>
=== Lists ===
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:

<code lisp>
'(1 2 3 4 5 6 7)
(1 2 3 4 5 6 7)
</code>

List of colors:
<code lisp>
'(white green yellow red)
(WHITE GREEN YELLOW RED)
</code>

Mixed list:
<code lisp>
[14]> '(1 two (3 four (six 5)))
(1 two (3 FOUR (SIX 5)))
</code>

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:
<code lisp>
(first '(1 two (3 four (six 5))))
1
</code>
If you want to get n-th car, it is best way to do it:
<code lisp>
(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
</code>
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.
<code lisp>
(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)))
</code>

To check whether the list is empty, use //null//:
<code lisp>
(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 
</code>

=== Appending lists ===

LISP has a built-in function for appending lists
<code lisp>
(append '(Ala Ola Ela)' (Marta King Basia))
(ALA OLA MARTA KINGA BASIA ELA)
</code>

Simple function adding two lists(similar to //append//):
<code lisp>
(defun add-list (L1 L2)
     (if (null L1)
       L2
     (cons (first L1) (add-list (rest L1) L2))))
</code>

Let's try //add-list//:
<code lisp>
(add-list '(Ala Ola Ela)' (Marta King Basia))
(ALA OLA MARTA KINGA BASIA ELA)
</code>

=== Reverting list ===

Lisp has a built-in function for reversing lists:
<code lisp>
(reverse '(1 2 3 4 5))
(5 4 3 2 1)
(reverse '((1 2) (3 4) 5))
(5 (3 4) (1 2))
</code>

== Exercises ==
  - Write a program counting all elements from list. The list will contain only numbers.

<del>
Sample solution:
(defun sum-el-list (L)
   (if (null L)
        0
        (+ (First L) (sum-el-list (rest L )))))
</del>
  - Write a program reversing the list. Use //append// or //add-list//.

<del>
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 )))))
</del>


=== References ===
[[http://clisp.sourceforge.net/|CLISP Homepage]]
[[http://www.paulgraham.com/onlisp.html|On LISP book]]
[[http://cl-cookbook.sourceforge.net/|The Common Lisp Cookbook]]