Lisp (derives from “LISt Processing”) is one of the oldest programming languages. It was invented in 1958, with the language being conceived by John McCarthy and is based on his paper “Recursive Functions of Symbolic Expressions and Their Computation by Machine”. Over the years, Lisp has evolved into a family of programming languages. The most commonly used general-purpose dialects are Common Lisp and Scheme. Other dialects include Franz Lisp, Interlisp, Portable Standard Lisp, XLISP and Zetalisp.
The majority of Lisp implementations offer a lot more than just a programming language. They include an entire environment such as debuggers, inspectors, tracing, and other tools to add the Lisp developer. Lisp is a practical, expression-oriented, interactive programming language which uses linked lists as one of its major data structures. A Lisp list is written with its elements separated by whitespace, and surrounded by parentheses. Lisp source code is itself comprised of lists.
The language has many unique features that make it excellent to study programming constructs and data structures. Many regard Lisp as an extremely natural language to code complex symbolic reasoning programs. Lisp is popular in the fields of artificial intelligence and symbolic algebra.
We publish a series covering the best open source programming books for other popular languages. Read them here.
By Stuart C. Shapiro (358 pages)
COMMON LISP: An Interactive Approach is a self-paced study guide to teach readers the COMMON LISP programming language. It aims to help programmers learn this dialect by experimenting with it via an interactive computer terminal.
This book has been used as the text of the Lisp portion of data structures, programming languages, and artificial intelligence courses and as a self-study guide for students, faculty members, and others learning Lisp independently.
This book examines the following areas:
- Numbers – interact with the Lisp listener and distinguishing between objects and their printed representations
- Lists – discusses the most important type of Lisp object, the list
- Arithmetic – start evaluating list objects. Evaluating list objects is the basic operation involved in writing, testing, and using Lisp
- Strings and Characters – along with lists, symbols are the most important kind of objects in Lisp because they are used for program variables, for function names (as was already briefly mentioned), and as data to allow Lisp programs to manipulate symbolic data as well as numeric data
- Symbols – another Common Lisp data type, like integers, floating-point numbers, ratios, characters, strings, and lists
- Packages – the symbols a programmer intends others to use can be exported from its original package (called its home package) and imported into another package
- Basic List Processing – discusses the use of lists as data objects—that is, list processing—what Lisp was named for
Programming in Pure Lisp
- Defining your Own Functions – examines the special form defun
- Defining Functions in Packages
- Saving for Another Day
- Predicate Functions – functions that return either True, represented by Lisp as T, or False, represented by Lisp as NIL
- Conditional Expressions – one of the two most powerful features of any programming language is the conditional
- Recursion – the use of recursive functions is called recursion
- Recursion on Lists, Part 1 – Analysis: start writing recursive functions that operate on lists
- Recursion on Lists, Part 2 – Synthesis
- Recursion on Trees
- The Evaluator – Lisp’s evaluator is the function eval, a function of one argument. It gets its single argument evaluated, and it evaluates it one more time and returns that value
- Functions with Arbitrary Numbers of Arguments – consider the entire structure of lists whose members are also lists and allow recursion down the first parts as well
- Mapping Functions
- The Applicator
- Macros – another kind of functionlike object that get their arguments unevaluated
Programming in Imperative Lisp:
- Assignment – the most basic imperative statement is the assignment statement, which assigns a value to a variable
- Scope and Extent – the scope of a variable is the spatiotemporal area of a program in which a given variable has a given name. The extent of a variable is the spatiotemporal area of a program in which a given variable has a given storage location
- Local Variables – introduce one or more new local, lexically scoped variables that will be used only within the body of a single function
- Iteration – the traditional imperative way of repeating computations, and iterative constructs have been included in Common Lisp for those programmers who prefer them
- Destructive List Manipulation
- Property Lists – the use of property lists to store information about symbols or about the entities the symbols represent
- Hash Tables – a type of Common Lisp object that are used for associating arbitrary pieces of information with each of a set of Common Lisp objects
The licensing conditions of the book are sufficiently open. Web links must point to the author’s page rather than to a separate copy of the dvi, ps, or pdf file.
By David S. Touretzky (587 pages)
Common Lisp: A Gentle Introduction to Symbolic Computation is about learning to program in Lisp. Although widely known as the principal language of artificial intelligence research—one of the most advanced areas of computer science—Lisp is an excellent language for beginners.
The book is aimed at:
- Students taking their first programming course
- Psychologists, linguists, computer scientists, and other persons interested in Artificial Intelligence
- Computer hobbyists
Chapters cover the following:
- Introduction – begins with an overview of the notions of function and data, followed by examples of several built-in Lisp functions
- Lists – these are the central data type for Lisp
- EVAL notation – a more flexible notation. EVAL notation allows us to write functions that accept other functions as inputs
- Conditionals – study some special decision-making functions, called conditionals, that choose their result from among a set of alternatives based on the value of one or more predicate expressions
- Variables and Side Effects – provides readers with a better understanding of the different kinds of variables that may appear in Lisp programs, how variables are created, and how their values may change over time
- List Data Structures – presents more list-manipulation functions, and shows how lists are used to implement such other data structures as sets, tables, and trees
- Applicative Programming – based on the idea that functions are data, just like symbols and lists are data, so one should be able to pass functions as inputs to other functions, and also return functions as values
- Recursion – Recursive control structure is the main topic of this chapter, but we will also take a look at recursive data structures in the Advanced Topics section
- Input/Output – Lisp’s read-eval-print loop provides a simple kind of i/o, since it reads expressions from the keyboard and prints the results on the display
- Assignment – frequently used in combination with iterative control structures, which are discussed in the following chapter
- Iteration and Block Structure – provides powerful iteration constructs called DO and DO*, as well as simple ones called DOTIMES and DOLIST. Learn about block structure, a concept borrowed from the Algol family of languages, which includes Pascal, Modula, and Ada
- Structures and The Type System – explains how new structure types are defined and how structures may be created and modified. Structures are an example of a programmer-defined datatype
- Arrays, Hash Tables And Property Lists – briefly covers three distinct datatypes: arrays, hash tables, and property lists
- Macros and Compilation – use evaltrace diagrams and a little tool called PPMX (defined in the Lisp Toolkit section) to see how macros work. The chapter also looks at compilation. The compiler translates Lisp programs into machine language programs, which can result in a 10 to 100 times speedup
At the end of each chapter there is optional advanced material to hold interest of junior and senior science majors. There are also exercises for the reader to work through.
This 1990 edition may be distributed in hardcopy form, for non-profit educational purposes, provided that no fee is charged to the recipient beyond photocopying costs.
By Richard P. Gabriel (294 pages)
Performance and Evaluation of Lisp Systems focuses on what determines the performance of a Lisp implementation and how to measure it. It is the source of the so-called “Gabriel Benchmarks”, which are still in use to benchmark Unix systems.
- The Implementation:
- MacLisp – one of the first Lisps written on the PDP-10
- MIT CADR – The CADR is the MIT Lisp machine; it is quite similar to the Symbolics LM-2. Both machines run a dialect of Lisp called ZetaLisp, which is a direct outgrowth of the MIT Lisp Machine Lisp
- Symbolics – an intellectual descendant of the CADR and the LM-2 but has more hardware support for Lisp
- LMI Lambda – the Lambda is a 32-bit microprogrammed processor with up to 64K 64-bit words of virtual control store and a 200 nanosecond microcycle time
- S-1 Lisp – runs on the S-1 Mark IIA computer, which is a supercomputer-class complex instruction set computer. S-1 Lisp is almost entirely written in Lisp
- Franz Lisp – written at the University of California at Berkeley by Richard Fateman and his students. It was originally intended to be a Lisp that was suitable for running a version of MACSYMA on a Vax
- NIL – New Implementation of Lisp, one of the main influences on the design of Common Lisp
- Spice Lisp – an implementation of Common Lisp written mostly in Common Lisp and partly in microcode
- Vax Common Lisp – the first Common Lisp implemented on stock hardware
- Portable Standard Lisp – a ‘LISP in LISP’ that has been in development at the University of Utah since 1980 and at Hewlitt-Packard since 1982
- Xerox D-Machine
- The Benchmarks:
- Tak – a variant of the Takeuchi function that Ikuo Takeuchi of Japan used as a simple benchmark
- Stak – a variant of TAK; it uses special binding to pass arguments rather than the normal argument-passing mechanism
- Ctak – a variant of TAK that uses CATCH and THROW to return values rather than the function-return mechanism
- Takl – very much like TAK, but it does not perform any explicit arithmetic
- Takr – a function that was defined to thwart the effectiveness of cache memories. TAKR comprises 100 copies of TAK, each with a different name
- Boyer – a rewrite-rulebased simplifier combined with a very dumb tautology-checker, which has a three-place IF as the basic logical connective
- Browse – it is essentially a theorem-proving benchmark
- Destructive – benchmarks the ‘destructive’ (hence the name) list utilities. It does this by constructing a tree that is a list of lists and then destructively modifying its elements. This manipulation proceeds by means of a fairly elaborate iterative control structure
- Traverse – tries to measure the performance that can be expected from the abstract data structure systems provided by the various Lisp dialects
- Derivative – performs a simple symbolic derivative in which the data representation is the usual S-expression representation for functions
- Data-Driven Derivative – exactly like DERIV except that functions taking derivatives of specific operators are located on the property list of the operator rather than buried in a piece of code
- Another Data-Driven Derivative – a variant of DDERIV. It optimizes FUNCALL by using a FUNCALL-like function that assumes it is being handed compiled code
- Division by 2 – this benchmark that divides by 2 using lists of n NIL’s
- FFT – a FFT benchmark tests a variety of floating point operations including array references
- Puzzle – solves a search problem that is a block-packing puzzle invented by John Conway
- Triangle – similar in many respects to the Puzzle benchmark, but it does not use any two-dimensional arrays. Therefore it provides a differentiator between one-dimensional and two-dimensional array references
- File Print – measures the performance of file output. The program checks to see whether there is a file with a certain name (there should not be). Then it creates and opens a new file with that name, prints a test pattern into that file, and then closes it
- File Read – tests file input. It reads the file produced by FPRINT
- Terminal Print – tests terminal output
- Polynomial Manipulation – computes powers of particular polynomials
The book is available under this Creative Commons License.
By Harold Abelson and Gerald Jay Sussman with Julie Sussman (688 pages)
This is a textbook which teaches the principles of computing programming. It is a classic text in computer science, a definite must read.
The book focuses on the main role played by different approaches to dealing with time in computational models.
The material in this book has been the basis of MIT’s entry-level computer science subject since 1980. The authors use the programming language Lisp to educate the reader.
By Mark Watson (170 pages)
The purpose of this book is to provide a quick introduction to Common Lisp and then provide the user with many fun and useful examples for using Common Lisp.
This book may be shared using the Creative Commons “share and share alike, no modifications, no commercial reuse” license.
By Pavel Penev (91 pages)
The book is a set of tutorials and examples. It uses the Common Lisp language and some of the libraries we’ll be using for the examples and tutorials include:
- The hunchentoot web server
- The Restas web framework
- The SEXML library for outputting XML and HTML
- Closure-template for HTML templating
- Postmodern for PostgreSQL access, and cl-reddis as a simple datastore
- Various utilities
This book is released under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported license (CC BY-NC-SA 3.0).
Useful free-to-read books which are not released under an open source license.