Introduction to LISP

LISP is the premier language for Artificial Intelligence applications. It is a dynamic language: editing changes take effect immediately, without the need for recompilation. It is primarily a functional language: all work can be done via function composition and recursion. There is no "main program:'' the programmer can call any function from the input prompt.

Lisp was invented by John McCarthy in 1958 while he was at the Massachusetts Institute of Technology (MIT). McCarthy published its design in a paper in Communications of the ACM in 1960, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". He showed that with a few simple operators and a notation for functions, one can build a Turing-complete language for algorithms. LISP is an old language, and has been updated many times. The most recent standard, Common LISP, is a huge language.

McCarthy's original notation used bracketed "M-expressions" that would be translated into S-expressions. As an example, the M-expression car [cons[A,B]] is equivalent to the S-expression (car (cons A B)). Once Lisp was implemented, programmers rapidly chose to use S-expressions, and M-expressions were abandoned. M-expressions surfaced again with short-lived attempts of MLISP by Horace Enea and CGOL by Vaughan Pratt.

Lisp (or LISP) is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older (by one year). Like Fortran, Lisp has changed a great deal since its early days, and a number of dialects have existed over its history. Today, the most widely known general-purpose Lisp dialects are Common Lisp, Scheme, and Clojure.

Lisp was originally created as a practical mathematical notation for computer programs, influenced by the notation of Alonzo Church's lambda calculus. It quickly became the favored programming language for artificial intelligence (AI) research. As one of the earliest programming languages, Lisp pioneered many ideas in computer science, including tree data structures, automatic storage management, dynamic typing, and the self-hosting compiler.

The name LISP derives from "LISt Processing". Linked lists are one of Lisp languages' major data structures, and Lisp source code is itself made up of lists. As a result, Lisp programs can manipulate source code as a data structure, giving rise to the macro systems that allow programmers to create new syntax or even new domain-specific languages embedded in Lisp.

The interchangeability of code and data also gives Lisp its instantly recognizable syntax. All program code is written as s-expressions, or parenthesized lists. A function call or syntactic form is written as a list with the function or operator's name first, and the arguments following; for instance, a function f that takes three arguments might be called using (f arg1 arg2 arg3).

Basic Commands

Lisp syntax is very simple and easy to understand. A list is a series of atoms surrounded by parentheses, and the first atom of a list is a function. Any atoms after the first are parameters of the function.

A.)  An example Lisp expression to add the numbers 1 and 2 together might look like this:

               (+ 1 2)

As you can see, the expression is a list. The first atom is +, which is also a function to be evaluated. 1 and 2 are the parameters of the + function.

B.)  You can also use a list as a parameter of a function like this, which adds the numbers 1 and 2 together, but somewhat more fancily:

               (+ 1 (+ 1 1))

In this example, the second parameter of the + function is a list. The first atom is a function: +. So the inner list is evaluated to two (1+1=2), and then that result is used as the second parameter of the outer list, which then gives the result 3.

There are of course many other functions in Lisp. Some of the most basic are these: +, -, /, *, quote, set, and cons. It should be obvious what the +, -, *, and / functions do and how they work.

C.)  The quote function returns its first argument, unevaluated. This is useful for passing a form (expression) to a function, without first evaluating that form (expression).

        (quote (param1 param2)) would return (param1 param2)

quote can also be abbreviated as '. ' goes "outside" the list that it acts on. So

  '(param1 param2) would return (param1 param2) just like in the first example.

D.)  The cons function constructs a list by adding an item to a list. Adding an item to the empty list '() creates a new list.

        (cons 1 '())returns(1)

      (cons 1 (cons 2 (cons 3 '())))returns(1 2 3)

Many of the attributes of Lisp are due to the fact that lists are constructed of conses.

Variables:

In Lisp, there are several ways to set a variable. Here are the most common.

Setq sets a variable to a given value. If the variable doesn't exist, then it is created. All variables created with setq are global. Setq works like this:

(setq variable-name <value>)

An example bit o' code using setq would be this:

(setq camel "I am a camel!")

(print camel)

Which should print "I am a camel!" when it executes.

Another example:

(setq x ‘(+ 3 2))

Output: (+ 3 2)

Methods:

A.)  Accessing Lists

a.       first and car give you the first element of a list.

(first ‘(1 2 3)) => 1

(first ‘((a b) 2 3)) => (a b)

b.       last and cdr give you the list minus the first element.

(rest ‘(1 2 3)) => (2 3)

(rest ‘((a b) 2 3)) => (2 3)

c.       car and cdr can be combined

(caar ‘((a b) c d e)) => a

(cdar ‘((a b) c d e)) => (b)

B.)  Testing Equality

a.       The equality can be tested in the following manner:

(eq ‘a ‘a) => T

(eq ‘a ‘b) => nil

(eq ‘(a) ‘(a)) => nil

(equal ‘a ‘a) => T

(equal ‘(a) ‘(a)) => T

(equal ‘(or p q) ‘(or p q)) => T