Common LISP

A Gentle Introduction to Symbolic Computation

David S. Touretzky

• Publisher: Dover Publications
• Year: 2014
• Print ISBN: 9780486498201
• eBook ISBN: 9780486791708
• Topic: Technology & Engineering
• Subtopic: Electrical Engineering & Telecommunications
• Index: Technology & Engineering

This highly accessible introduction to Lisp is suitable both for novices approaching their first programming language and experienced programmers interested in exploring a key tool for artificial intelligence research. The text offers clear, reader-friendly explanations of such essential concepts as cons cell structures, evaluation rules, programs as data, and recursive and applicative programming styles.
The treatment incorporates several innovative instructional devices, such as the use of function boxes in the first two chapters to visually distinguish functions from data, use of evaltrace notation in later chapters to illustrate the operation of evaluation rules, and "Dragon stories" to explain recursion. The book contains nearly 400 diagrams and illustrations, and 77 pages of answers to exercises. Advanced topics and "toolkit" sections, and a variety of complete programs, extend readers' programming power.

1

Functions and Data

1.1 INTRODUCTION

This chapter begins with an overview of the notions of function and data, followed by examples of several built-in Lisp functions. If you already have some experience programming in other languages, you can flip through this chapter in just a few minutes. You’ll see arithmetic functions, followed by an introduction to symbols, one of the key datatypes of Lisp, and predicates, which answer yes-or-no questions. When you think you’ve grasped this material, read the summary section on page 26 to test your understanding.

If you’re new to programming, this chapter is designed specifically for you. We’ll start by explaining what functions and data are.* The term data means information, such as numbers, words, or lists of things. You can think of a function as a box through which data flows. The function operates on the data in some way, and the result is what flows out.

After covering some of the built-in functions provided by Lisp, we will learn how to put existing functions together to make new ones—the essence of computer programming. Several useful techniques for creating new functions will then be presented.

1.2 FUNCTIONS ON NUMBERS

Probably the most familiar functions are the simple arithmetic functions of addition, subtraction, multiplication, and division. Here is how we represent the addition of two numbers:

The name of the function is “ + .” We can describe what’s going on in the figure in several ways. From the point of view of the data: The numbers 2 and 3 flow into the function, and the number 5 flows out. From the point of view of the function: The function “ + “ received the numbers 2 and 3 as inputs, and it produced 5 as its result. From the programmer’s point of view: We called (or invoked) the function “ + “ on the inputs 2 and 3, and the function returned 5. These different ways of talking about functions and data are equivalent; you will encounter all of them in various places in this book.

Here is a table of Lisp functions that do useful things with numbers:

+	Adds two numbers
-	Subtracts the second number from the first
*	Multiplies two numbers
/	Divides the first number by the second
ABS	Absolute value of a number
SQRT	Square root of a number

Let’s look at another example of how data flows through a function. The output of the absolute value function, ABS, is the same as its input, except that negative numbers are converted to positive ones.

The number -4 enters the ABS function, which computes the absolute value and outputs a result of 4.

1.3 THREE KINDS OF NUMBERS

In this book we will work mostly with integers, which are whole numbers. Common Lisp provides many other kinds of numbers. One kind you should know about is floating point numbers. A floating point number is always written with a decimal point; for example, the number five would be written 5.0. The SQRT function generally returns a floating point number as its result, even when its input is an integer.

Ratios are yet another kind of number. On a pocket calculator, one-half must be written in floating point notation, as 0.5, but in Common Lisp we can also write one-half as the ratio 1/2. Common Lisp automatically simplifies ratios to use the smallest possible denominator; for example, the ratios 4/6, 6/9, and 10/15 would all be simplified to 2/3.

When we call an arithmetic function with integer inputs, Common Lisp will usually produce an integer or ratio result. If we use a mixture of integers and floating point numbers, the result will be a floating point number:

1.4 ORDER OF INPUTS IS IMPORTANT

By convention, when we refer to the “first” input to a function, we mean the topmost arrow entering the function box. The “second” input is the next highest arrow, and so on. The order in which inputs are supplied to a function is important. For example, dividing 8 by 2 is not the same as dividing 2 by 8:

When we divide 8 by 2 we get 4. When we divide 2 by 8 we get the ratio 1/4. By the way, ratios need not always be less than 1. For example:

EXERCISE

1.1. Here are some function boxes with inputs and outputs. In each case one item of information is missing. Use your knowledge of arithmetic to fill in the missing item:

Here are a few more challenging problems. I’ll throw in some negative numbers and ratios just to make things interesting.

1.5 SYMBOLS

Symbols are another type of data in Lisp. Most people find them more interesting ...

Table of contents

• Cover
• Title Page
• Copyright Page
• Dedication
• Preface
• Note to Instructors
• Acknowledgements
• Contents
• 1. Functions and Data
• 2. Lists
• 3. EVAL Notation
• 4. Conditionals
• 5. Variables and Side Effects
• 6. List Data Structures
• 7. Applicative Programming
• 8. Recursion
• 9. Input/Output
• 10. Assignment
• 11. Iteration and Block Structure
• 12. Structures and The Type System
• 13. Arrays, Hash Tables, And Property Lists
• 14. Macros and Compilation
• Appendix A. The SDRAW Tool
• Appendix B. The DTRACE Tool
• Appendix C. Answers to Exercises
• Glossary
• Further Reading
• Index