Please send all questions & assignments to:
dsolarek@eng.utoledo.edu

LISP stands for LISt Processing and is a functional, or applicative, programming language based on John McCarthy's work on numerical computation, published in 1960. Common LISP is a dialect of LISP, a successor to MacLISP, influenced strongly by Zetalisp and to some extent by Scheme and Interlisp.

GNU Common LISP (gcl) is a highly portable implementation of Common LISP originally based on Austin Kyoto Common LISP (AKCL), a Common LISP (CLtL1)¹ implementation developed at Kyoto University in Japan and extended by Bill Schelter of UT/Austin. The gcl utility is intended to eventually support the ANSI Standard for Common LISP. Similar to gpc for the Pascal language, gcl generates C code which it compiles with the local optimizing C compiler (gcc).

Learning Objectives

• describe the proper syntax for LISP declarations, statements, variable names, expressions, and comments
• create simple LISP programs
• compile LISP programs using the GNU Common LISP gcl utility (and the gcc compiler)
• debug common errors in LISP programs

What is a "functional programming language"?

Functional programming is a style of programming that emphasizes the evaluation of expressions, rather than execution of commands. The expressions in these language are formed by using functions to combine basic values. A functional language is a language that supports and encourages programming in a functional style.

For example, consider the task of calculating the sum of the integers from 1 to 10. In an imperative language such as C, this might be expressed using a simple loop, repeatedly updating the values held in an accumulator variable total and a counter variable i:

 total = 0;
 for (i=1; i<=10; ++i)
    total += i;

 sum [1..10]

The same idea could also be used in (strict) functional languages such as SML³ or Scheme, but it is more common to find such programs written with an explicit loop, often expressed recursively. Nevertheless, there is still no need to update the values of the variables involved:

SML:

 let fun sum i tot = 
       if i=0 then tot else sum (i-1) (tot+i)
 in sum 10 0
 end

 (define sum
    (lambda (from total)
        (if (= 0 from)
            total
            (sum (- from 1) (+ total from)))))
 (sum 10 0)

 (defun sum (a b)
   (cond ((> a b) 0)
 	(t (+ a (sum (+ a 1) b)))))

 (sum 10 0)

What is the difference between Scheme and Common LISP?

Scheme is often used in computer science curricula and programming language research, due to its ability to represent many programming abstractions with its simple primitives. Common LISP is often used for real world programming because of its large library of utility functions, a standard object-oriented programming facility (CLOS), and a sophisticated condition handling system.

Because of its "real world" popularity, we will focus on GNU Common LISP in this document and in the course. The Pratt and Zelkowitz text emphasizes the Scheme dialect of LISP, although it does include some examples from Common LISP. This means that the examples shown in your textbook may not run with the GNU gcl utility installed on the class server.

History of LISP

MacLISP improved on the LISP 1.5 notion of special variables and error handling. MacLISP also introduced the concept of functions that could take a variable number of arguments, macros, arrays, non-local dynamic exits, fast arithmetic, the first good LISP compiler, and an emphasis on execution speed. By the end of the 1970's, MacLISP was in use at over 50 sites.

InterLISP introduced many ideas into LISP programming environments and methodology. One of the InterLISP ideas that influenced Common LISP was an iteration construct that inspired the loop macro used both on the LISP Machines and in MacLISP, and now in Common LISP.

During the late 1970's, LISP Machine LISP began to expand towards a much fuller language. Sophisticated lambda lists, setf, multiple values, and structures like those in Common LISP are the results of early experimentation with programming styles by the LISP Machine group. These features were migrated to MacLISP. Around 1980, work was begun on a LISP to run on the Scientific Personal Integrated Computing Environment (SPICE) workstation. One of the goals of this project was to design a simpler dialect than LISP Machine LISP.

The Macsyma group at MIT began a project during the late 1970's called the New Implementation of LISP (NIL) for the VAX, which was headed by White. One of the stated goals of the NIL project was to fix many of the historic, but annoying, problems with LISP while retaining significant compatibility with MacLISP. At about the same time, a research group at Stanford University and Lawrence Livermore National Laboratory began the design of a LISP to run on the S-1 Mark IIA supercomputer. S-1 LISP, never completely functional, was the test bed for adapting advanced compiler techniques to LISP implementation. Eventually the S-1 and NIL groups collaborated.

LISP Language Standards

PSL and Franz LISP (a MacLISP-like dialect for Unix machines) were the first examples of widely available LISP dialects on multiple hardware platforms.

One of the most important developments in LISP occurred during the second half of the 1970's: Scheme. Scheme, designed by Gerald J. Sussman and Guy L. Steele Jr., is a simple dialect of LISP whose design brought to LISP some of the ideas from programming language semantics developed in the 1960's. Sussman was one of the prime innovators behind many other advances in LISP technology from the late 1960's through the 1970's. The major contributions of Scheme were lexical scoping, lexical closures, first-class continuations, and simplified syntax (no separation of value cells and function cells). Some of these contributions made a large impact on the design of Common LISP.

In the late 1970's object-oriented programming concepts started to make a strong impact on LISP. At MIT, certain ideas from Smalltalk made their way into several widely used programming systems. Flavors, an object-oriented programming system with multiple inheritance, was developed at MIT for the LISP machine community by Howard Cannon and others. At Xerox, the experience with Smalltalk and Knowledge Representation Language (KRL) led to the development of LISP Object Oriented Programming System (LOOPS) and later Common LOOPS. These systems influenced the design of the Common LISP Object System (CLOS). CLOS was developed specifically for this standardization effort.

In 1980 Symbolics and LMI were developing LISP Machine LISP; stock-hardware implementation groups were developing NIL, Franz LISP, and PSL; Xerox was developing Interlisp; and the SPICE project at CMU was developing a MacLISP-like dialect of LISP called SpiceLISP.

In April 1981, after a DARPA-sponsored meeting concerning the splintered LISP community, Symbolics, the SPICE project, the NIL project, and the S-1 LISP project joined together to define Common LISP. Initially spearheaded by White and Gabriel, the driving force behind this grassroots effort was provided by Fahlman, Daniel Weinreb, David Moon, Steele, and Gabriel. Common LISP was designed as a description of a family of languages. The primary influences on Common LISP were LISP Machine LISP, MacLISP, NIL, S-1 LISP, Spice LISP, and Scheme. Common LISP: The Language is a description of that design. Its semantics were intentionally underspecified in places where it was felt that a tight specification would overly constrain Common LISP research and use.

In 1986 X3J13 was formed as a technical working group to produce a draft for an ANSI Common LISP standard. Because of the acceptance of Common LISP, the goals of this group differed from those of the original designers. These new goals included stricter standardization for portability, an object-oriented programming system, a condition system, iteration facilities, and a way to handle large character sets. To accommodate those goals, a new LISP language specification was developed.

Why Study LISP?

The ease of procedural abstraction combined with the strength of its macro-writing facilities makes LISP an ideal language for both, a) writing extensive libraries of general-purpose routines using user-tailored syntax, and b) writing complete new languages on top of LISP. LISP's simple syntax and weak typing, combined with friendly development environments, make it one of the most general and effective rapid prototyping languages.

LISP Basics

 et105:~/lisp$ gcl
 GCL (GNU Common Lisp)  Version(2.2.2) Wed Sep  3 19:35:17 CDT 1997
 Licensed under GNU Public Library License
 Contains Enhancements by W. Schelter

 >

To exit the GCL interpreter and return to the UNIX prompt, issue the bye command at the gcl prompt.

 >(bye)
 et105:~/lisp$

 >bye

 Error: The variable BYE is unbound.
 Fast links are on: do (si::use-fast-links nil) for debugging
 Error signalled by EVAL.
 Broken at EVAL.  Type :H for Help.
 >>:q

 Top level.
 >

Simple Arithmetic. The example below illustrates the evaluation of some simple arithmetic forms (expressions).

 >(+ 2 77)
 79

 >(+ 3 (* 4 5))
 23

 >(* 1 2 3 4)
 24

 >(+ (* 3 (+ 1 (- 4 2 (+ 3 4)))))
 -12

 >

 +, -, *, /, exp, expt, log, sqrt, 
 sin, cos, tan, max, min 

 Top level.
 >(sqrt 6)
 2.4494897427831779

 >(max 1 4 7 2 9 3 5 )
 9

 >

 >(/ 25 7)
 25/7

 >(float (/ 25 7))
 3.5714285714285716

 >(round (float (/ 25 7)))
 4                       ; the nearest integer
 -0.42857142857142838    ; the remainder

 >

 >(setq items 3)
 3

 >items
 3

 >

 Top level.
 >(setq p 1)
 1

 >(if p (+ 3 4) 6)
 7

 >(setq p 0)
 0

 >(if p (+ 3 4) 6)
 7

 >(setq p (eq 'a 'b))
 NIL

 >(if p (+ 3 4) 6)
 6

 >

 (print "Hello, world!")

 (princ "Hello, world!")

 (DEFUN HELLO-WORLD ()
    (PRINT (LIST 'HELLO 'WORLD)))

(HELLO-WORLD)

 (LOOP (FORMAT T "~%Hello World"))

Stored Programs. LISP programs can be stored in a file and run from within the interpreter. The example below illustrates the traditional Hello World program, written in LISP:

 ;;; HelloWorld.lsp

 ;;; ================================== ;;;
 ;;; === SIMPLE HELLO WORLD PROGRAM === ;;;
 ;;; ================================== ;;;

 ;;; This function returns the string 
 ;;; Hello World that is in quotes.

 (DEFUN HELLO ()
   "HELLO WORLD" )

 >(load "HelloWorld.lsp")
 Loading HelloWorld.lsp
 Finished loading HelloWorld.lsp
 T

 >(hello)
 "HELLO WORLD"

 >

 (defun what-is-your-name (name)
   (format NIL "Hello ~A!" name))

Program Organization

 GOOD:
  (defun foo (x y)
    (let ((z (+ x y 10)))
      (* z z)))

 BAD:
  (defun foo(x y)(let((z(+ x y 10)))(* z z)))

 ALSO BAD:
  (defun foo ( x  y )
    (let ( ( z (+ x y 10) ) )
       ( * z z )
       )
    )

Comment your code. Use three semicolons in the left margin before the definition for major explanations. Use two semicolons that float with the code to explain the routine that follows. Two semicolons may also be used to explain the following line when the comment is too long for the single semicolon treatment. Use a single semicolon to the right of the code to explain a particular line with a short comment. The number of semicolons used roughly corresponds with the length of the comment. Put at least one blank line before and after top-level expressions.

A function to convert from degrees Fahrenheit to degrees Celsuis.

 >(defun f-to-c (f)
   (float (- (/ (* (+ f 40) 5) 9) 40)))
 F-TO-C

 >(f-to-c 75)
 23.888888888888889

 >

 >(defun c-to-f (c)
   (float (- (/ (* (+ c 40) 9) 5) 40)))
 C-TO-F

 >(c-to-f 23.9)
 75.02000000000001

 >

Variables and Identifiers

Use descriptive variable and function names. If it is not clear from the name of a function or variable what its purpose is, document it with a documentation string and a comment. In fact, even if the purpose is evident from the name, it is still worth documenting your code.

Make the names of special (global) variables begin and end with an asterisk (*):

 (DEFVAR *GLOBAL-VARIABLE*)

Use local variables in preference to global variables whenever possible. Do not use global variables in lieu of parameter passing. Global variables can be used in the following circumstances:

• When one function needs to affect the operation of another, but the second function is not called by the first. For example,

   *load-pathname*
   *break-on-warnings*
  

• When a called function needs to affect the current or future operation of the caller, but it does not make sense to accomplish this by returning multiple values.
• To provide hooks into the mechanisms of the program. For example,

   *evalhook*, *, /, +
  

• Parameters which, when their value is changed, represent a major change to the program. For example,

   *print-level*
   *print-readably*
  

• For state that persists between invocations of the program. Also, for state which is used by more than one major program. For example,

   *package*
   *readtable*
   *gensym-counter*
  

• To provide convenient information to the user. For example,

   *version*
   *features*
  

• To provide customizable defaults. For example,

   *default-pathname-defaults*
  

• When a value affects major portions of a program, and passing this value around would be extremely awkward. (The example here is output and input streams for a program. Even when the program passes the stream around as an argument, if you want to redirect all output from the program to a different stream, it is much easier to just rebind the global variable.)

 (defun power-of-two (n)
    "Compute two raised to the exponent n,
    where n must be a positive integer."
    (declare (type integer n))
    (do ((result 1 (* result 2))
         (expon n (- expon 1)))
        ((>= 0 expon) result)))

Reserved Words

Declarations

1. It allows the compiler to check the programmer's code at compile time for code which is inconsistent with the declarations. If the compiler can be certain at compile-time that the types are correct, it need not insert any run-time type tests in the compiled code. Some implementations allow the programmer to specify that such run-time tests should be avoided in any case. When this is provided for, it can be done on a global basis or in only selected regions of code.
2. It allows the compiler to generate more efficient code. When the compiler is able to be certain of the type of data held in certain variables, it can use more efficient machine instructions to manipulate that data. This results in fewer function calls and less garbage.

 >(defun discriminant (a b c)
   (declare (number a b c))
   "Compute the discriminant for a quadratic
    equation. Given a, b, and c, the value
    b^2-4*a*c is calculated. The quadratic
    equation a*x^2+b*x+c=0 has real, multiple,
    or complex roots depending on whether
    this calculated value is positive, zero,
    or negative, respectively."
   (- (* b b) (* 4 a c)))
 DISCRIMINANT

 >(discriminant 1 2/3 -2)
 76/9

 >

 second, third, fourth,..., last, 
 nthcar, nthcdr, butlast, 
 nbutlast, reverse, caar, cddr, 
 cadr, cdar, constantp, integerp

Basic Data Types

• Atoms are represented as sequences of characters of reasonable length.
• Lists are recursively constructed from atoms.

 ATOMS 		 LISTS
 a 		 ()
 john		 (a)
 34		 (a john 34 c3po)
 c3po		 ((john 34) a ((c3po)))

Recursion

 >(defun fact (x)         ;a recursive function
    (if (> x 0)
      (* x (fact (- x 1)))
      1))
 FACT

 >(fact 6)
 720

 >

 >(defun rpower-of-two (n)
      (cond ((= n 0) 1)
            (t (* 2 (rpower-of-two (- n 1))))))
 RPOWER-OF-TWO

 >(rpower-of-two 9)
 512

 (defun bottles (n)
  "Prints the lyrics to '99 Bottles of Beer'"
 (if (< n 1)
    (format t "~%Time to go to the store.~%")
    (progn (format t "~% ~a bottle~:p of beer on the wall." n)
           (format t "~% ~a bottle~:p of beer." n)
           (format t "~% Take one down, pass it around.")
           (format t "~% ~a bottle~:p of beer on the wall.~%" (- n 1))
           (bottles (- n 1)))))

Assignment Statements

 >(setq a (list "hello" "world"))
 ("hello" "world")

 >(cadr a)
 "world"

 >(substring (cadr a) 2 4)
 "rl"

 >(setf (substring (cadr a) 2 4) "o")
 "o"

 >(cadr a)
 "wood"

 >a
 ("hello" "wood")

 >

Numbers and Constants

    5
    17
   -34
   +6
    3.1415
    1.722e-15
 #c(1.722e-15 0.75)

 defconstant name initial-value [documentation]

 >(defconstant +half-pi+ (/ pi 2.0))
 +HALF-PI+

 >

 >(defconstant +half-pi+ (/ pi 2.0)
    "pi/2, to avoid doing this division repeatedly")
 +HALF-PI+

 >

Again, the convention is to make the names of constants begin and end with a + plus sign:

 >(defconstant +E+ 2.7182818) 
 +E+

 >(+ 3 +E+)
 5.7182817999999997

 >

Some people prefer to use macros to define constants, since this avoids the problem of coidentally trying to bind a symbol declared with defconstant.

Boolean/Logical Comparisons

LISP provides a standard set of logical functions, for example and, or, and not. The and and or functions are short-circuiting: and will not evaluate any arguments to the right of the first one which evaluates to nil, while or will not evaluate any arguments to the right of the first one which evaluates to t.

 >(setf thing 'circle r 4)
 4

 >(cond ((eq thing 'circle) (* pi r r))
       ((eq thing 'sphere) (* 4 pi r r)))
 50.26548245743669

 >

We could also make this a function:

 >(defun area (thing r)
 (cond ((eq thing 'circle) (* pi r r))
        ((eq thing 'sphere) (* 4 pi r r))))
 AREA

 >(area 'circle 2)
 12.566370614359172

 >

Printing

• prin1 produces output suitable for input to read. It binds *print-escape* to true.
• princ is just like prin1 except that the output has no escape characters. It binds *print-escape* to false and *print-readably* to false. The general rule is that output from princ is intended to look good to people, while output from prin1 is intended to be acceptable to read.
• print is just like prin1 except that the printed representation of object is preceded by a newline and followed by a space.
• pprint is just like print except that the trailing space is omitted and object is printed with the *print-pretty* flag non-nil to produce pretty output.

The examples below illustrate the different versions of print.

 Top level.
 >(setf *global-variable* 33)
 33

 >*global-variable*
 33

 >(print *global-variable*)

 33
 33

 >(princ *global-variable*)
 33
 33

 >(prin1 *global-variable*)
 33
 33

 >(pprint *global-variable*)

 33

 >

• prin1 writes a single symbolic-expression (composed of atoms or composite s-expressions ie. lists) to standard output in a form that would be acceptable to a later attempt to read it back (which means the value of the argument passed to prin1 is returned). No whitespace is outputted on either side of the argument to prin1.
  Example:
  (prin1 "This is a test")
  (prin1 1)
  (prin1 '(2 3))
  Would result:
  "This is a test"1(2 3)

  princ behaves like prin1, except it makes no attempt to make its output acceptable to read (which tends to make its output more acceptable to humans!) Specifically:

  1. It prints strings without the quotation marks on either side.
  2. It prints special characters without the escape symbol.

  
  Example:

  (prin1 "This is a test")

  (prin1 1)

  (prin1 '(2 3))
  Would result:

  This is a test1(2 3)

  print behaves like prin1, except it outputs a newline BEFORE the object (argument) and a space AFTER it.
  Example:

  (prin1 "This is a test")

  (prin1 1)

  (prin1 '(2 3))
  Would result:

  "This is a test" 1

  (2 3)

  pprint is just like print except that the trailing space is omitted and object is printed to produce pretty output.
  Example:

  (pprint "This is a test")

  (pprint 1)

  (pprint '(2 3))
  Would result:

  "This is a test"

  1

  (2 3)

Directives

  Directive   Interpretation
  ---------   --------------
     ~%       new line
     ~&       fresh line
     ~|       page break
     ~T       tab stop
     ~<       justification
     ~>       terminate ~<
     ~C       character
     ~(       case conversion
     ~)       terminate ~(
     ~D       decimal integer
     ~B       binary integer
     ~O       octal integer
     ~X       hexadecimal integer
     ~bR      base-b integer
     ~R       spell an integer
     ~P       plural
     ~F       floating point
     ~E       scientific notation
     ~G       ~F or ~E, depending upon magnitude
     ~$       monetary
     ~A       legibly, without escapes
     ~S       READably, with escapes
     ~~       ~

~%	Insert a CR.	This is like \n in a C printf call.
~&	Insert a CR unless already at beginning of line.
~S	S-expression.	Insert an arbitrary Lisp expression, and print it just as that expression would normally be printed if it were returned as a value.
~A	ASCII.	Similar to ~S, but if one of the args is a string, its double quotes will be dropped.
~D	Integer	(like %d in C)
~widthD	extra spaces.	(format NIL "~5D" 6) returns " 6"
~:D	commas.	(format NIL "~:D" 1234567) returns "1,234,567"
~F	Floating point	(like %f in C)
~width,decimalsF
~	for long lines.	This lets you hit CR in the string (to keep it within 80 columns), but not really put a CR in the output.

Sorting

LISP provides two primitives for sorting: sort and stable-sort.

 >(sort '(2 1 5 4 6) #'<)
 (1 2 4 5 6)

 >(setf a '(2 3 44 6 1 8 22 5))
 (2 3 44 6 1 8 22 5)

 >(sort a #'<)
 (1 2 3 5 6 8 22 44)

 >(sort a #'>)
 (44 22 8 6 5 3 2)

 >

The first argument to sort is a list; the second is a comparison function. The stable-sort function is exactly like sort, except that it guarantees that two equivalent elements appear in the sorted list in the same order that they appeared in the original list.

Be careful: sort is allowed to destroy its argument, so if the original sequence is important to you, make a copy with the copy-list or copy-seq/ function.

 

Footnotes

1

The term CLtL1 refers to the first edition of the book "Common LISP The Language." The second edition of this book is similarly referenced as CLtL2 and is available on the web.

2

The Haskell language is a functional programming language. In particular, it is a polymorphicly typed, lazy, purely functional language, quite different from most other programming languages. The language is named for Haskell Brooks Curry, whose work in mathematical logic serves as a foundation for functional languages. Haskell is based on lambda calculus, hence the Greek symbol lambda is used as a logo for the language.

3

The letters SML stand for Standard ML, another functional programming language. ML stands for meta-language, and is a family of advanced programming languages with (usually) functional control structures, strict semantics, a strict polymorphic type system, and parameterized modules. It includes Standard ML, Lazy ML, CAML, CAML Light, and various research languages.

4

The IEEE P1178 is IEEE Standard 1178-1990, "IEEE Standard for the Scheme Programming Language," published by IEEE in 1991. ISBN 1-55937-125-0. It is now also an ANSI standard. It may be ordered from IEEE by calling 1-800-678-IEEE or 908-981-1393 or writing IEEE Service Center, 445 Hoes Lane, P.O. Box 1331, Piscataway, NJ 08855-1331, and using order number SH14209 ($28 for IEEE members, $40 others).

    Click on the button at left to return to the calling page.

 

There have been visitors since 11/26/2003