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
