LISP: List Processing Language

LISP - List Processing Language, also Clisp for "Common Lisp"

Introduction to Lisp and Lisp Concepts
        Download Lisp Interpreters
        Using an interpreter
Lisp Keywords and Built-in Functions & Macros
        General Primatives
        Conditionals
        Arithmetic Operators
Code and Programs
Links and Resources

Introduction to Lisp

Lisp is the favored language for developing Artificial Intelligence(AI) because of its recursive properties and built-in functions for creating, processing and manipulating nested lists. This, however, is not a discussion of AI. This is purely a tutorial for the Lisp language. For information on Artificial Intelligence, click here.

For those used to programming in C based languages, Lisp can be pretty confusing. For those who have never programmed before it will take some understanding of basic programming concepts before it will make sense. But fear not! I actually encourage novice and non-programmers to try Lisp, for the main reason that it is not necessary to write full-blown programs right away and there is no compiling or linking! Compiling, linking an debugging can be very frustrating to new programmers. Lisp has few or none of these pitfalls.

The Parentheses ( )

Parentheses are the basic building blocks of Lisp. All Lisp scripts, functions and operations take place within parentheses. Complete funcitons have a matching number of open and closed parentheses.
Complete: (CAR '(A B))
Not Complete: (CAR '(A B)

The Quote '

The single-quote character separates what is being evaluated and the procedure. For example (CAR '(A B C)) is asking what the first element of the list A, B and C which is A. Without the single-quote the interpreter will think A, B, and C are procedures and return an error unless they are defined. This can be a difficult concept to grasp at first, this of it this way: in an English sentance might be structured DO SOMETHING TO THIS THING, the single quote is like the TO without it, we are saying DO SOMETHING DO SOMETHING with no noun, just verbs. The DO SOMETHING in this case is the CAR procedure and the and the THIS THING is our list (A B C). With regular use, the single-quote will become a simpler concept.

S-Expressions

Symbolic-Expressions or just expressions. This is what we do to and with the atoms and lists.

Atoms

Strings, numbers, etc. The basic units within

Lists

() Link ATOMS and create lists
(A B C) is a list of ATOMS
((A B) (B) C (D E F)) LIST of LISTs and ATOMs
() The empty LIST or "NIL"

The Lisp Interpreter

Getting an interpreter
The first thing you will need is a Lisp interpreter, which can be downloaded free from these sites*:
Not all downloads are self-extracting, you may need WinZip

Allegro CL 6.2(registration required)
LispWorks(registration required)
CLisp, multiple versions
Visual CLisp

If you are using a PalmPilot, get LispMe. Available with O'Reilly's PalmPilot Book, or from Fred Bayers' Page

*If you are working with UNIX or LINUX, you already have a Lisp interpreter called "clisp"

Using the interpreter
Most of these interpreters will have a "Visual Studio" with lots of buttons and useless stuff for creating applications, we don't want that right now, we want the command-line environment which is usually labeled: "Lisp Only" or something. You'll know when you open it if it is the right one.

Lisp interpreters are not like other coding environments. Start up an interpreter and you will be greeted with a prompt. They differ widely, here are some examples:

- >

USER >

Lisp >

Regardless, they all work in similar ways. Enter a statement or function at the prompt, hit < enter > and your code will be evaluated.
Test it, by entering the following:

(+ 1 1)

As this is the Lisp expression for adding 1 and 1 it should evaluate to 2.

Lisp statements are only complete when all the sets of parenthesis are closed or "matched." That is, (NIL) is complete statement, (NIL is not. (SETQ A '(1 2 3)) is complete statement, (SETQ A '(1 2 3) is not. Forgetting to put the first open paren will produce an error. Extra closed parens at the end of a statement will be ignored by the evaluator, but extra close parens usually means that there is a mistake somewhere in your code!

Lisp Built-in Functions

full alphabetized list

CAR
Takes the first element of list

(CAR `(ONE TWO))

Answer 	ONE

CDR
Remove the first element of list

(CDR `(ONE TWO THREE))

Answer 	TWO THREE

SETQ
Assigns values:
(SETQ NUMBER `32)

Associates a list with a list name:

(SETQ COLORS `(YELLOW RED GREEN))

QUOTE
Prints list item(s)

(QUOTE `(COLORS))

Answer 	YELLOW RED GREEN

EVAL
Evaluates and expression:

(EVAL NUMBER)

23

APPEND
Merges lists

(APPEND `((A B)(C D)))

Answer 	(A B C D)

LIST
Makes a new list of several lists

(LIST `((A B)(C D)))

Answer 	((A B)(C D))

CONS
Adds a new first element to a list

(CONS `A (Q Z))

Answer 	(A Q Z)

ATOM
Tests an argument to see if it is an atom

(ATOM `(A B C D))

Answer 	NIL

(ATOM `A)

Answer 	T

LISTP
Tests an argument to see if it is a list

(LISP `(A B C D))

Answer 	T

(LISTP `A)

Answer 	NIL

NULL
Tests to see if an argument is an empty list

(NULL '())

Answer 	T

(NULL '(A B C))

Answer 	NIL

MEMBERP
Tests to see if an ATOM is a member of a list.

NIL
Universal false.
Boolean response for "false"

T
Universal true.
Boolean response for "true"

DEFUN
Creates user defined functions
Example: (DEFUN ADD2 (x y) (+ x y))
Creates a function called ADD2 that takes two parameters x and y and adds them. To use:

(ADD2 3 4)

Answer 	7

ABS - Absolute Value
(ABS -5)
5

EXPT - Calculates Powers
(EXPT 3 2)
9

SQRT - Square Root
(SQRT 16)
4.0

MAX - Largest number in sequence
(MAX 2 5 6)
5

MIN - Smallest number in sequence
(MIN 2 5 6)
2

Conditionals

COND - Condition


(COND (test result))

Example:

LOAD or :LD

Loading a saved script into the interpreter.

Some interpreters have trouble with pathnames or have custom pathname commands, so put you file in the working directory of the interpreter until you figure out how your interpreter finds files. Besides being interpreter dependent, it is also OS dependent, as Windows, UNIX, MAC, VAX, etc. all have different path specs.
Save your files as .l, .cl or .lisp(there are other variations, too many, if one doesn't work try the other)
Many interpreters will come with sample code, look at those file extensions.

Then type these commands:
:LD filename.cl
If you wrote a function for calculating cubes called cubez.cl type:
:LD CUBEZ.CL

Arithmetic Operators

In lisp the operator is first and the values are listed after.
+ Addition.

(+ 5 5)

>10

- Subtraction.

(- 10 3)

>7

/ Division.

(/ 25 5)

>5

* Multiplication.

(* 5 5)

>25

Sample Functions & Programs

Function for calculating a cube


(defun cube (num)

(* num (* num num)))

Compares two lists and returns T if the first list is longer than the second


(defun two-lists (list1 list2)

(< (length list1) (length list2)))

Function tests to see if the argument is negative


(defun negativep (num)

(not (> num 0)))

Checks a list to see if contains only atoms and not lists


(defun only-atoms (listx)

(cond ((null listx) t)

((atom listx) 2)

((atom (first listx)) (only-atoms (rest listx)))

(nil (+ 1 (only-atoms (first listx))

(only-atoms (rest listx))))))

Creates a function for calculating powers


(defun expon (base powr)

(cond ((zerop powr) 1)

((evenp powr) (expon (* base base ) (truncate powr 2)))

(t (* base (expon (* base base) (truncate powr 2))))))

This function makes a single list out sublists


(defun squash (list1)

(cond ((null list1) nil)

((atom list1) (list list1))

(t (append (squash (car list1))

(squash (cdr list1))))))

This function counts the number of times an atom appears in a list.
Note that it calls SQUASH. So, SQUASH must be evaluated first.


(defun count-it (itemx listx)

(setq listx (squash listx))

(cond ((null listx) '0)

((atom listx) '0)

((cond ((not (equal itemx (car listx))) (count-it itemx (cdr listx)))

(t (1+ (count-it itemx (cdr listx))))))))

Database interface

The main function (DB) calls other functions and calls for user interaction.
These are all loaded and evaluated seperately. When they are all entered into the interpreter, call (DB) to begin the process.

Creates the database as an empty list.


(setq database '())

Creates the main (DB) function and starts the user interface loop.


(defun db ()

 (loop

(princ "Enter (a, r, q):")

(let ((in (read)))

(if (equal in 'q) (return 'done))

(if (equal in 'r) (retrieve))

(if (equal in 'a) (add)))))

Creates the function and interface for adding to the database.


(defun add ()

(princ "Enter user-data pair: ")

(let ((in (read)))

(setq database (append database (list in)))))

Creates the interface and function for retrieving data.


(defun retrieve ()

(princ "Enter user: ")

(let ((in (read)))

(prin1 (cdr (assoc in database)))

(terpri)))

Code Samples (Not all have been tested!)

fibonacci.cl
reverse.cl
sizeit.cl
nth-it.cl
robot.cl