Introduction to Small Lisp

CMPT 384 Lecture Notes
Robert D. Cameron
September 10, 1999

Small Lisp is Small

Small Lisp is a small, functional programming language that emphasizes recursive programming on symbolic data domains. Small Lisp has:

One data type: the S-expression (atoms and lists).
Five types of expression: values (constants), variables, function calls, conditional expressions, let expressions.
No types of statement. It is a functional language!
Two types of definition: constant definitions and function definitions.
Nineteen primitive functions that provide basic operations on S-expressions, plus one primitive for signalling errors.

S-Expressions

The basic data type of Lisp is the S-expression (from Symbolic-expression). It is a very flexible data type for representing symbolic data. S-expressions are of two subtypes: atoms and lists.

Atoms

Atoms are further divided into two subtypes: numeric atoms and symbolic atoms. Numeric atoms are basically integers, while symbolic atoms are symbols.

Numeric atoms: 4, -17.
Symbolic atoms: x17, Paul, WWW, x-abs, ++.

Symbolic atoms come in two forms: alphanumeric identifiers (possibly hyphenated), and operator symbols made as combinations of special characters.

Truth Values

The S-expression is the only data type of Small Lisp, so how do we represent truth values? Using the symbolic atoms T and F for true and false, respectively! (Common Lisp users, note that NIL does not represent false in Small Lisp.)

Lists

It is the list data type, however, which gives Lisp both its flavour and its name (list processor). Lisp lists are ordered collections of zero or more S-expressions.

(A LIST OF SYMBOLIC ATOMS).
(1 2 3).
(), the empty list.
(A Mixed List of 6 Atoms)
((A sublist)(Another sublist)), a list with two sublists.
(None 0 ()), a 3-element list consisting of one symbolic atom, one numeric atom and one list (the empty list).
(This is (a (partially parsed) sentence)). A list which shows structure imposed on an English sentence.

These examples illustrate some of the applications of Lisp lists.

List Processing

Small Lisp provides four primitive functions for constructing and analyzing lists: first, rest, cons, and endp.

first[x]: returns the first element of list x.
rest[x]: returns the list of remaining elements after the first element of list x.
cons[e; x]: returns a new list consisting of the element e, followed by the elements of list x.
endp[x]: determines whether x is the empty list, returning the symbolic atom T if x=(), or the symbolic atom F if x is nonempty.

With these primitives, we can start programming list processing functions. For example, consider the function append[x; y] that appends the lists x and y returning a list consisting of all the elements in both input lists.

append[(1 2); (3 4)] = (1 2 3 4)

The following recursive function achieves this.

append[x; y] =
  [endp[x] --> y;
   otherwise --> cons[first[x]; append[rest[x]; y]]]

The following series of evaluations result:

append[(1 2); (3 4)]
cons[first[(1 2)]; append[rest[(1 2)]; (3 4)]]
cons[1; append[(2); (3 4)]]
cons[1; cons[first[(2)]; append[rest[(2)]; (3 4)]]]
cons[1; cons[2; append[(); (3 4)]]]
cons[1; cons[2; (3 4)]]
cons[1; (2 3 4)]
(1 2 3 4)

Primitive Recognizers

When we take elements from a list, they can be arbitrary S-expressions, i.e., symbolic atoms, numeric atoms or lists. How do we tell them apart? Small Lisp provides 3 S-expression recognizers for the purpose.

symbolp["X"] => T     symbolp[3] => F     symbolp[(X 2)] => F
numberp["X"] => F     numberp[3] => T     numberp[(X 2)] => F
listp["X"] => F       listp[3] => F       listp[(X 2)] => T

In general, we use the term recognizer for any function that distinguishes between different types of some domain. Actually, the "p" on the end of recognizer names is a common convention; it stands for predicate.

Processing Symbolic Atoms

The basic operation that we usually perform on symbolic atoms is just testing them for equality, we use the eq function for this.

eq["X"; "X"] => T        eq["X"; "x"] => F

But there are three other useful functions. The sym-lessp function does lexicographic comparison of atom names

sym-lessp["A"; "B"] => T  
sym-lessp["B"; "A"] => F
sym-lessp["A"; "A"] => F

The individual characters of a symbolic atom can be determined by the explode function.

explode["HTML"] => (H T M L)  
explode["X10"] => (X 1 0)

The implode function inverts this process.

Arithmetic: Functions on Numeric Atoms

To emphasize that numeric processing is no more important than symbolic processing in Small Lisp, all arithmetic uses functional notation.

plus[4; -3] => 1
minus[4; -3] => 7
times[4; -3] => -12
divide[4; -3] => -1
rem[4; -3] => 1
eqp[4; -3] => F
lessp[4; -3] => T
greaterp[4; -3] => F