CS 3723
 Programming Languages 
   Lisp Introduction  

Overview: This is the Lisp Introduction Page. Refer to various Lisp materials online through the calendar page, or at the links below:

Lisp: Lisp is a full-featured programming language that has traditionally supported AI applications. In fact, AI courses are often taught using Lisp, although this is done less often now (too difficult to teach enough Lisp to be useful). Lisp is the oldest programming language still actively used. Some Lisp systems come with a complete development environment, and Lisp has been used for large software projects (such as Macsyma) and as the basis for software engineering. Lisp appears simple, but this is deceptive.

Lisp is an interpreted language, and as such it has flexibility and power not available to traditional compiled languages such as C, C++, or Java. In Lisp more decisions are made at run-time. In exchange for this flexibility and power, Lisp execution has always been much slower than the traditional languages. Modern Lisp systems have a compiler that improves performance considerably, though not to the level of traditional languages.

Lisp presents editing problems, particularly the large number of parentheses. Special lisp editors (or EMACS configured for Lisp) can help a lot, but we'll be doing small enough programs that we can ignore this. If you can, you should use an editor that matches parentheses for you.

The Lisp We Will Use: In this course, we will mostly study a subset that can be called "pure Lisp", just the basics. Lisp has the equivalent of ordinary loops, but you will not be allowed to use such loops in this course, because I want you to study recursion and a "functional programming style." This means in part the use of parameters, functions, and recursion, without using assignments or loops. We will only be using assignments (the function setq) at the top level.

A dialect of Lisp called Scheme is often used in courses, but you are not to use it in this course. Scheme is a "stripped down" and "cleaned up" small version of Lisp. However, Scheme has a number of significant differences from Common Lisp.

So-called Common Lisp was created to combine most of the features in use by the various Lisp dialects. Common Lisp has a very large number of features, including many alternative ways to do the same thing. Common Lisp even includes classes and object-oriented programming.

In this course we will use Common Lisp, but restricted to a small collection of permitted features. I expect you to use the notation and functions presented here, and not the various alternatives. (This is partly to force you to write the functions yourself, rather than finding them online.) Several faculty members know Lisp better than I do, but you are not to ask them to help you with assignments and other problems.

Lisp, Access and References:
  • Accessing Lisp:
    • Right now at UTSA Lisp is only available on the machine elk01. (Maybe other elks later.) To access this Lisp, you first must ssh to elk01. This is Common Lisp, available as gnu clisp, using
      % /usr/bin/clisp or just % clisp, where '%' is the Linux/Unix prompt.
    • On my Linux at home it took me 5 minutes to download this.
    • The first link that came up under google for PC Lisp was: Common Lisp Download. (I haven't tried this.)

  • Exiting Lisp:
    • Use (exit) or (quit) (parentheses required -- just exit or quit is an error)
    • Ctrl-D works also, but not in error mode.

  • Lisp is NOT case sensitive: Normally input is in lower-case, but it doesn't have to be. The output is always upper-case, except of course for quoted material.

  • Lisp references: Here are some online references to use along with class notes. But beware! The references contain far too much material.
    • Online tutorials (the two below seem good, but the one in red is probably your best choice):
      • Lisp Primer, by Colin Allen and Maneesh Dhagat: (.html)
      • Successful Lisp: How to Understand and Use Common Lisp, by David Lamkins: (.html).
    • "Elementary" lisp books:
      • Common Lisp,by David Touretzky: (.pdf) [1 MB]. (This is OK, but uses weird non-standard diagrams.)
      • Basic Lisp Techniques, by David Cooper: (.pdf) [404 KB]. (This book is harder.)
    • Lisp references (insanely complex and incomprehensible):
      • Pocket guide: (.pdf). (I include this to show how crazy these Lisp people are.)
      • 1100 page lisp reference manual: (.pdf) (3.9 meg). This is Common Lisp the Language by Guy L. Steele, Second Edition, 1990, 1072 + xxvii pages. (I include this to show how large and complex Common Lisp is.)
      • Official standard, the "Common Lisp HyperSpec": (.html) (Makes the other crazy references above seem sane.)
    • Clisp implementation notes: (Some very useful material.)

Using Lisp: Lisp behaves in ways similar to some of the "scripting" languages and others. When you type the command "clisp", the Lisp interpreter gives you a prompt and processes further commands, one after the other. As with some scripting languages, Lisp does not require a declaration for a variable, and a given variable can be used for different data types in the same program.

Here is a sample Lisp session, where material in red boldface (with comments in orange) is what you type in. The rest is what the system responds with. The system puts in bracketed input line numbers, but I'm usually going to leave them off in examples, because I want to cut and paste and edit these examples.

What Lisp Looks Like
elk01:~> clisp 
  [blah, blaah, blaaah, ...]
> 15     ; constant value = itself
15
> (+ 5 8)  ; prefix functions
13
> (+ 5 8 3 6)  ; any number of args
22
> (/ 355 113)  ; rational type
355/113
> (/ 355.0 113.0) ; float arguments
3.141593
> (/ 355L0 113L0) ; greater precision
3.1415929203539823009L0
> (- (/ 355L0 113L0) pi) ; comparison
2.667641890623587142L-7
> (= (+ (* 10 10 10) (* 9 9 9))
       (+ (* 12 12 12) (* 1 1 1)))
      ; 103 + 93 = 123 + 13
T
> (defun factorial (n) ; function def
        (cond ((= n 0) 1)
              (t  (* n (factorial (1- n)))) ))
FACTORIAL
> (factorial 5) ; calling function
120
> (quit) ; th-th-th-that's-all-folks
 
Loading and Compiling (Optional, % = Linux prompt)
% cat comb.l  (file can hold any # of functions)
(defun c (r k) ;; comp r things, k at a time
   (cond ((or (= k 0) (= k r)) 1)
         (t (+ (c (1- r) k) (c (1- r) (1- k)))) ))
% clisp
> (load "comb.l")  ; load in the file
;; Loaded file comb.l
T
> (c 26 13)  (50 seconds)
10400600
> (c 30 15)  (790 seconds, over 13 minutes!)
155117520

% clisp -C  ("-C" for "compile when loading")
> (load "comb.l")
0 errors, 0 warnings
;; Loaded file comb.l
> (c 26 13)  (6 seconds)
10400600
> (c 30 15)  (75 sec, 3 sec in Java and in C)
155117520
The function c above in C or Java
int c(int r, int k) {
   if (k == 0 || k == r) return 1;
   return c(r-1, k) + c(r-1, k-1);
}

 
The Power of Lisp: As mentioned above, Common Lisp, and this particular implementation (clisp), are extremely powerful. Lisp includes almost any feature you can imagine in a programming language: arrays. vectors, strings, macros, packages, hash tables, structures, and even classes that fully support O-O programming with multiple inheritance.

In addition to the normal data types, this Lisp has:

  • Arbitrarily large integers. These are often provided in the scripting languages, such as perl, ruby, and python.

  • Arbitrary precision floats, that is, floats with arbitrarily many digits of precision (well, bits of course). The floating point features include all the usual transcendental functions, also implemented at arbitrary precision. Besides clisp, there are only a few packages like this available: mainly Mathematica (very expensive), and Maxima (formerly macsyma, not readily available or in wide use).
We will show some of this in the computations below:

High-precision Computations
> (factorial 50)  ; arbitrarily large ints
30414093201713378043612608166064768844377641568960512000000000000
> (SETF (EXT:LONG-FLOAT-DIGITS) 200)  ; arbitrarily large floats
200
> (exp (* pi (sqrt 163L0)))   ; famous expression
2.6253741264076874399999999999925007259719818568887935385633733699091L17
; rewritten and truncated, this is:
; 262537412640768743.999999999999250072597198
> (SETF (EXT:LONG-FLOAT-DIGITS) 300)
300
>
(defun g (n)  ; Gregory's series for pi/4
   (setq sum 0)
   (dotimes (i n sum) (setq sum (+ sum
            (/ (+ (* (rem (+ i  1) 2) 2) -1) (+ (* i 2L0) 1L0))))
   ))
G
> (* (g 1000) 4L0)
3.1405926538397929259635965028693959704513893307797244893674577835432L0
> (* (g 1000000) 4L0)  ; ten seconds elapsed
3.1415916535897932387126433832791903841971703525001058155647883423586L0
> (* (g 10000000) 4L0)  ; 130 seconds elapsed
3.141592553589793238462893383279502881072169399375201133474944587123L0
> pi
3.14159265358979323846264338327950288419716939937510582097494459230787L0
> (quit)
Bye.

The first example above shows 50! calculated, all 65 digits.

The second example evaluates a famous expression that is extremely close to an integer:

The third example considers the following series, known as Gregory's series

This series is similar to the harmonic series that you studied in calculus, along with the alternating harmonic series:

Gregory's series also converges very slowly. In fact, for each additional digit of accuracy in the computation of π, you need to sum ten times as many terms. The computations above use a Lisp function g that computes the sum of n terms of the series for n = 103, 106, 107. These calculations were carried out with roughly 90-digit accuracy (with more for the last one). The digits that are equal to the digits of π are given in blue, while incorrect digits are given in red. (Single isolated digits might agree with probability 0.1, and most of these have been left red.) You can see that the value of the sum of 10 ^ i terms has an error in the ith decimal place (off by 1). But the table shows an astonishing number of other digits are equal to the corresponding digit of π, even though the numbers themselves are very poor approximations to π. Can you imagine what is happening here? I also performed all these calculations in Mathematica and got exactly the same answers. (There results are an artifact of using a power of 10 as the number of terms. The last line gives the sum of 9876543 terms of the series, and only a few early digits of it agree with π.)

Approximations to π
10^1: 3.0418396189 2940221113
10^2: 3.1315929035 5855276430 7414238276 
10^3: 3.1405926538 3979292596 3596502869 3959704513
10^4: 3.1414926535 9004323845 9518383374 8153787870 1364274418 0460513479
10^5: 3.1415826535 8979348846 2643352029 5028937284 1939396494 9575908635 9919594
10^6: 3.1415916535 8979323871 2643383279 1903841971 7035250010 5815564788 3423571533 2034804914 3891718868
10^7: 3.1415925535 8979323846 2893383279 5028810721 6939937520 1133474944 5868976601 5628670236 7768659759
10^8: 3.1415926435 8979323846 2643633279 5028841971 3814937510 5820984475 8423078164 0087605274 8628039759 0335233179 75

pi:   3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 82
ran:  3.1415927548 3979539002 4929611291 2755437003 6080736183 6126709814 8691643667 1905184480 0246716560

It is rare for a software package to provide transcendental functions of arbitrary precision floating point numbers. I also performed most of these calculations in Mathematica and got exactly the same answers.

For the Lisp function g above, I originally wrote a recursive version (as I expect students to do), but that version ran out of stack space when trying to add up 10^4 terms. The non-recursive version above had no problem with 10^7 terms at roughly 100 digits, which took 2 minutes on my (slow) PC workstation.

Revision date: 2013-10-26. (Please use ISO 8601, the International Standard Date and Time Notation.)