Catalysoft   Turtle
home products articles about us contact us

Recent Articles

What's Good About Clojure?

Clojure is a relatively new language to appear on the Java Virtual Machine (JVM), although it draws on very mature roots in the form of the LISP langu ...

Should You Care About Requirements Engineering?

Recently, I (Adil) was invited to participate in a one day seminar on the subject of Requirements Engineering. Whilst I have no direct experience of t ...

Tips for Setting Up Your First Business Website

To attract all potential customers to your business you need a presence on the web. The problem is that if you haven't set up a website before, you p ...

Open Source Tools for Developers: Why They Matter

From a developer's point of view use of open-source tools has advantages beyond the obvious economic ones. With the open-source database MySQL in mind ...

An Interview with Norbert Cartagena

An exclusive interview with Norbert Cartagena, the former editor-in-chief of Developer Shed Inc. and self-confessed fan of science fiction. In ...

What's Good about LISP?

Discuss this article >>>

Introduction

LISP is a general-purpose programming language and is the second-oldest programming language still in use (FORTRAN is one year older). It was defined by John McCarthy at the Massachusetts Institute of Technology (MIT) in 1958, and has evolved steadily ever since. Before the mid-1980s, LISP existed in many different dialects, such as Franz LISP, InterLISP, MacLISP, SPICE LISP and ZetaLISP. In 1986, an ANSI standard for LISP emerged in the form of a language specification; now known as Common LISP. Common LISP combines the best features of many of the earlier dialects, and is a powerful and comprehensive programming language. Unlike many other programming languages, such as C and Prolog, LISP defines many of the commonly used functions as part of the language rather than a library extension. Although this means that LISP manuals tend to be large, it also means that Common LISP programs are very portable across different Common LISP implementations because each implementation provides the same basic set of functions (even if the functions have been implemented in different ways).

Promotes Rapid Development

LISP is one of the dominant languages for Artificial Intelligence (AI) programming, but should not be seen as a language that it is exclusive to the AI world. The AI community embraced the language in the 1980s because it enabled rapid development of software in a way that was not possible with other mainstream languages of the time, such as C. In the 1980s and early 1990s, the emphasis of mainstream software development methodologies was on 'getting it right first time', an approach that demanded up-front effort on careful system specification and did not allow for changes in specification during later stages of the software development lifecycle. In AI, software development needed to be much more agile, so that inevitable changes in specification could more easily be accommodated by iterative development cycles. LISP is ideal for this, as it can be tested interactively and provides for concise, quick coding using powerful high-level constructs such as list processing and generic functions. In other words, LISP was ahead of its time because it enabled agile software development before it became respectable in mainstream software.

List Processing and Language Syntax

LISP was ahead of its time in other ways, too. It was portable across hardware and operating system platforms years before Sun developed their Java Virtual Machine; it was the first language to incorporate an ANSI standard for object-oriented programming; and its ability to serialize and deserialize data stored as lists came decades before the excitement over XML. In fact, the powerful list processing ability is central to the language - the name 'LISP' comes from 'LISt Processing'. LISP was originally conceived as a list processing language with a very simple core functionality and syntax. In LISP, lists are parenthesized elements which can be used as symbolic representations of real-world objects or relationships, as in:

'(parents (philip elizabeth) (charles anne andrew edward))
This is a data structure, which is, of course, subject to further processing and semantic interpretation when passed as an argument to a LISP function. The most basic functions for manipulating lists are car and cdr (also known as first and rest). The car of a list is its head (i.e., the first element), and the cdr is its tail (i.e., the rest). So, for example:
>(car '(parents (philip elizabeth) (charles anne andrew edward)))
PARENTS
>(cdr '(parents (philip elizabeth) (charles anne andrew edward)))
((PHILIP ELIZABETH) (CHARLES ANNE ANDREW EDWARD))
The basic syntax of a function call is very simple:
(function arg1 arg2 ... argn)
The brackets not only delimit the expression; they also signify that the function call is something to be evaluated; that is, a result is computed and returned. Notice that in the previous expression above, a quote (') was used to protect the argument from immediate evaluation. The arguments provided to a function can themselves be the result of function calls, so LISP expressions often have multiple 'layers' of bracketing; for example an expression that uses Pythagoras's Theorem might be written as:
(sqrt (+ (* x x) (* y y)))
A function definition also has this same basic form, so a LISP program consists of a set of such expressions. A major advantage of this approach is that a LISP function can be manipulated in the same way that data is manipulated. For example, functions can be passed as arguments to so-called higher-order functions, and functions can also generate functions as their output.

Higher Order Functions

One of the most commonly used higher-order functions is called mapcar. It applies the given function to respective members of a list argument, collecting and returning the results as a list. For example, the function integerp determines whether or not its single argument is an integer, returning T for true, and NIL for false:

> (mapcar #'integerp '(b 3 (8) nil))
(NIL T NIL NIL)
Note that the hash sign (#) told LISP that integerp is a function, and can therefore be applied to other data. A function which takes multiple arguments, such as +, can also be supplied to mapcar, with powerful effect:
> (mapcar #'+ '(1 2 3) '(10 20 30) '(100 200 300))
(111 222 333)
On a more pragmatic level, LISP is (usually) both an interpreted and a compiled language. Interpreted languages are good for rapid prototyping because they generally provide good error diagnostics, and the implement-test-refine cycle does not require recompilation. LISP thus enables the programmer to first develop code quickly and later compile the result into a more efficient form.

Recursive or Iterative

Unlike some other functional programming languages, LISP provides for both recursive and iterative programming styles. As an example, consider writing a function to compute the factorial of a positive integer n. The factorial, written n! is the product of all integers between 1 and n; i.e., n! = n(n-1)(n-2)...21. A function to compute this number can be written in a recursive style as follows:

(defun fac(n) 
  (if (= n 0) 1 
     (* n (fac (- n 1)))))
You should read the definition of the function as follows. If n is zero, then return 1; otherwise return the product of n and the factorial of n-1.

The same function can be written in an iterative style as follows:

(defun fac(n)
  (let ((result 1))
    (dotimes (i n)
      (setq result (* result (+ i 1))))
   result))
This function uses let to set up a local variable called result with an initial value of 1. It then performs n iterations of a central loop that each time multiplies the result by the loop's counter variable (one must be added to this counter, as dotimes counts from zero). Finally the value of the result variable is returned as the result of the function.

Object-Oriented

Like many other modern programming languages, Common LISP is object-oriented. In fact, it was the first ANSI-standard object-oriented language, incorporating CLOS (the Common LISP Object System). CLOS provides a set of functions which enable the definition of classes, their inheritance hierarchies and their associated methods.

A class defines slots whose values carry information about object instances. The class definition can also specify default values for slots, and additional non-trivial behavioural mechanisms (such as integrity checking) performed at object creation time. As an example of object-orientation in LISP, consider the definition of some shapes, which can be either circles or rectangles. A shape's position is given by x and y coordinates. Further, a circle has a radius, whereas a rectangle has a width and a height. It should be possible to compute the area of circles and rectangles. A working set of definitions is given below:

(defclass shape ()
   (x y))

(defclass rectangle (shape)
   ((width :initarg :width)
   (height :initarg :height)))

(defclass circle (shape)
   ((radius :initarg :radius)))

(defmethod area ((obj circle))
   (let ((r (slot-value obj 'radius)))
      (* pi r r)))

(defmethod area ((obj rectangle))
   (* (slot-value obj 'width)
      (slot-value obj 'height)))

Using these definitions, a rectangle (instance) can be created with make-instance, for example with a width of 3 and a height of 4:

> (setq my-rect (make-instance 'rectangle :width 3 :height 4))
#<RECTANGLE @ #x8aee2f2>

and its area can be computed by calling the method area:

> (area my-rect)
12

Summary

Most programmers are not familiar with LISP and might view it as a quirky language that is specialized for use on AI problems. I hope this article has gone some way towards dispelling this view. LISP is a mature, general purpose language that incorporates many advanced programming ideas - far more than can be covered in a short article like this. Even if you don't use LISP as your main programming language, you can still benefit from familiarity with LISP, as some of its ideas can be transferred to your language of choice.

I encourage you to download a free trial LISP implementation from either Franz or Xanalys and explore the language. To get you going, why not try the great programming tutorial available in comic book form at lisperati.com

Discuss this article >>>


Simon White