> (setf letters '(a b c))
(A B C)
> (append letters (reverse letters))
(A B C C B A)

A new function can be defined to perform this task for an arbitrary list:

(defun make-palindrome (list1)
   (append list1 (reverse list1)))

The general form for a function definition is:

(defun function-name (parameter-1 parameter-2 ... parameter-n)
   form-1
   form-2
   ...
   form-m)


The word defun is followed by the name of the new function and a parenthesized list of names of the input parameters for the function. In the make-palindrome function, there is a single input parameter named list1. The parameter list is followed by any number of LISP expressions (forms) that comprise the body of the function definition. When the function is executed, the successive forms in the body are evaluated one by one and the value of the last form is returned and printed. The make-palindrome function has only a single LISP expression in the body of the definition, so this one expression is evaluated and its value is returned.

A function can have no inputs, and in this case, an empty parameter list must be placed after the function name, as in the following example:

(defun no-inputs ()
   (list 'have 'a 'nice 'day))

The parameter list1 in the make-palindrome function is a local variable that only exists while the function is being executed. Consider the following LISP interaction:

> (setf newlist '(three blind mice))
(THREE BLIND MICE)
> (make-palindrome newlist)
(THREE BLIND MICE MICE BLIND THREE)
> newlist
(THREE BLIND MICE)
> list1
...
EVAL: variable LIST1 has no value

The function first-name defined below has two inputs, a list and an integer. The function assumes that the input list contains nested lists that each specify a person's full name. The function returns the first name of the person who appears at the position in the input list corresponding to the input integer.

(defun first-name (namelist position)
   (first (nth position namelist)))

The following examples illustrate the execution of the first-name function:

> (setf names '((Diana Chapman Walsh) (Wendy Wellesley)(Mark Twain)))
((DIANA CHAPMAN WALSH) (WENDY WELLESLEY) (MARK TWAIN))
> (first-name names 0)
DIANA
> (first-name names 2)
MARK

Exercise 6:
Write a function named rotate that has a single input parameter that is assumed to be a list. This function should return a new list in which the first element of the input list is moved to the end of the list, as illustrated below:

> (rotate '(sunny rainy cloudy windy))
(RAINY CLOUDY WINDY SUNNY)

6. Creating local variables with let, let*

The following function chop-ends includes a call to the setf function that creates a new variable named templist. When executed, this function has a side-effect. The templist variable is created as a global variable (called a special variable in LISP) that still exists after execution is complete, as illustrated in the LISP interaction below the function definition.

(defun chop-ends (list1)
   (setf templist (reverse (rest list1)))
   (reverse (rest templist)))

> (chop-ends '(sunny rainy cloudy windy snowy))
(RAINY CLOUDY WINDY)
> templist
(SNOWY WINDY CLOUDY RAINY)

To avoid such side-effects, local variables can be created inside a function definition using the let function. The following is an example of the general form of a function definition that uses let to create local variables:

(defun function-name (parameter-1 ... parameter-n)
   (let ((variable-name-1 value-1)
         (variable-name-2 value-2)
         ...
         (variable-name-m value-m))
     form-1
     form-2
     ...
     form-k))


The chop-ends function can be rewritten using let to create a local variable named templist:

(defun chop-ends (list1)
   (let ((templist (reverse (rest list1))))
     (reverse (rest templist))))

In this case, templist only exists during the execution of the function.

The following function distance calculates the distance between two points whose coordinates are given by (x1,y1) and (x2,y2). Here, let is used to create two local variables, dx and dy.

(defun distance (x1 y1 x2 y2)
   (let ((dx (- x2 x1))
         (dy (- y2 y1)))
     (sqrt (+ (* dx dx) (* dy dy)))))

When multiple local variables are created using let, they are conceptually created and assigned values in parallel. The function let* is similar to let, except that the creation of multiple local variables takes place sequentially rather than in parallel. This allows a new local variable to depend on the value of a variable defined earlier, as shown in the following example:

(defun geometry (radius)
   (let* ((area (* PI radius radius))
          (volume (* area radius)))
     (list area volume)))

The print function can be used inside a function definition to print out intermediate results or to print literal strings. The print function only has a single input, but other functions such as list can be used to combine multiple values in one print expression:

(defun distance (x1 y1 x2 y2)
   (let ((dx (- x2 x1))
         (dy (- y2 y1)))
     (print "Local variables:")
     (print (list 'dx dx 'dy dy))
     (sqrt (+ (* dx dx) (* dy dy)))))

> (distance 1 2 6 5)
"Local variables:"
(DX 5 DY 3)
5.830951894845301

Note that when LISP prints a double-quoted string, capitalization is preserved.

Exercise 7:
Write a function named triplet that has three input parameters. This function should first construct a list of the three inputs and then return a final list in which this 3-element list is repeated three times, as illustrated below. Use let to create a local variable that is assigned to the list of three inputs.

> (triplet 'one 'two 'three)
((ONE TWO THREE) (ONE TWO THREE) (ONE TWO THREE))

7. Predicates: equal, =, eq, eql, endp, member, and, or, not

A predicate is a function that returns true (T) or false (NIL). The first group of predicates that we consider are those that test whether two things are the same. There are multiple functions to do this in LISP. The most general is the equal function, which tests whether two expressions have the same printed value:

> (equal '(a b c) '(a b c))
T
> (equal '((a) b c) '(a b c))
NIL
> (setf nlist '(1 2 3))
(1 2 3)
> (equal (cons '(a b) nlist) (append (list (list 'a 'b)) (list 1 2 3)))
T


The equal function can have an arbitrary number of input arguments and will return T if all of the arguments yield the same printed value.

The function = is used with arguments that have numerical values, and tests whether the arguments all have the same numerical value:

> (= 7 6)
NIL
> (setf a 10)
10
> (= (+ a 6) (* 4 4) (- 24 8))
T
> (= 3 3.0)
T

The function eq returns T if two inputs refer to the same object stored in memory, and is the most strict form of equality. This function is typically used to test whether two variable names refer to the same object (e.g. the same list). Sometimes it is difficult to determine what to expect from the eq function, because it depends on LISP implementation details that may not be apparent. The last few examples below illustrate this.

> (eq '(3 4) '(3 4))
NIL
> (setf alist '(3 4))
(3 4)
> (setf blist alist)
(3 4)
> (eq alist blist)
T
> (eq 'C3PO 'C3PO)
T
> (eq 3.0 3.0)
NIL
> (eq 3 3)
T
> (setf a 3 b 3)
3
> (eq a b)
T

Finally, the function eql returns T if either the two inputs satisfy the criterion for being equal using the eq function, or they are numbers of the same type and value. eql would behave the same as eq on the non-numerical examples shown above, but the two functions can behave differently on numerical examples:

> (eql 3.0 3.0)
T
> (eql 2.0 (/ 8 4))
NIL
> (eql 2.0 (/ 8.0 4))
T

Throughout the course we will see contexts that require the use of these different equality functions.

The function endp has a single input that is assumed to be a list. It returns T if the list is empty:

> (endp ())
T
> (endp (rest '(cat)))
T
> (endp '(cat))
NIL
> (endp 'cat)
...
ENDP: A true list must not end with CAT

The function member tests whether an input expression is contained as a top-level element in an input list. If it is not, then the value NIL is returned. If the input expression is contained in the input list, the member function returns the rest of the input list, starting with the first occurrence of the input expression. This is illustrated in the following examples:

> (member 'cat '(bird cat dog))
(CAT DOG)
> (member 'pig '(bird cat dog))
NIL
> (member 'cat '(bird dog cat pig cat))
(CAT PIG CAT)
> (member 'cat '((bird cat) (dog mouse)))
NIL
> (member '(bird cat) '((bird cat) (dog mouse)))
NIL


The last example may seem puzzling. By default, when the member function compares the input expression to each element of the input list, it uses the eql function to test for equality. The comparison function can be changed by using a keyword argument named test. In the example below, the :test specifies that a value is being supplied for the keyword argument named test, and #'equal is the value being supplied for this argument. The special pair of characters #' placed before the function name specify that the definition of the function equal is to be used for comparison when the member function is executed. Consider the examples below, in which the comparison function has been specified using the :test keyword:

> (member '(bird cat) '((bird cat) (dog mouse)) :test #'equal)
((BIRD CAT) (DOG MOUSE))
> (member '(bird cat) (list (list 'bird 'cat) 'pig) :test #'equal)
((BIRD CAT) PIG)
> (member 3 '(1.0 2.0 3.0))
NIL
> (member 3 '(1.0 2.0 3.0) :test #'=)
(3.0)

More elaborate logical expressions can be created using the functions and, or and not. Conceptually, you would expect the and function to return true (T) if all of its arguments are true and return NIL otherwise. But in detail, the arguments to the and function are evaluated from left to right. If an argument with a NIL value is encountered, the value NIL is immediately returned. If all of the arguments have a non-NIL value, then the value of the last argument is returned. This behavior allows the and function in LISP to be used in broader contexts than those that require a simple logical combination of expressions. Consider the following examples:

> (and (= 4 4.0) (member 'b '(a b c)))
(B C)
> (and (member 3 '(1 2 3)) (equal 'a (list 'a)))
NIL

Conceptually, you would expect the or function to return T if at least one of its arguments has the value T. But in detail, the arguments to the or function are evaluated from left to right. If an argument with a non-NIL value is encountered, this first non-NIL value is immediately returned. If all of the arguments evaluate to NIL, then the value NIL is returned. The behavior of the or function is illustrated in the following examples:

> (or (= 3 4) (print 'hello))
HELLO
HELLO
> (or (member 'b '(a b c)) (eq 2.0 (/ 4.0 2.0)))
(B C)
> (or (eq 'a 'a) (equal 'a 'a))
T

Finally, the not function returns T if its argument has the value NIL, and returns NIL if its argument has a non-NIL value:

> (not (= 3 3.0))
NIL
> (not (member '(a) '((a) (b))))
T
> (not t)
NIL
> (not ())
T

Exercise 8:
Determine the values returned by each of the following expressions:

(a) (and (member '(a) '(a b c)) (= 6 (* 2.0 3.0)))
(b) (member '(a b) (list (cons '(a) '(b)) (append '(a) '(b))
             (list '(a) '(b))))
(c) (not (or (member 3 '(7 3 8)) (eql (* 2.0 4.0) 8)))

8. Conditional statements: if, cond

The simplest conditional expressions use the function if, which has the following general form:

(if test then-form else-form)

If the test expression has a non-NIL value, then the then-form is evaluated and returned. If test has a NIL value, then the else-form is evaluated and returned. The else-form is optional.

> (setf a 10.0)
10.0
> (if (= a 10) (print 'yes) (print 'no))
YES
YES
> (if (member a '(1 2 3) :test #'equal) a 0)
0
> (setf num (if (= a 5) (* a a) (+ a a)))
20.0

The then-form and else-form must each be a single LISP expression. The function progn allows multiple LISP expressions to be grouped together into a single expression, similar to the use of curly braces {} in Java or C. The general form of a progn expression is:

(progn
   form-1
   form-2
   ...
   form-n)

This function allows multiple actions to be grouped together in the then-form or else-form in an if statement:

> (if (= a 0)
      (progn (setf b 10) (print 'multiple-actions) (list a b))
      (progn (print 'non-zero) (setf a 10)))
NON-ZERO
10


The function cond allows the construction of more general conditional statements and has the following general form:

(cond (test-1 form-1 ... form-n1)
      (test-2 form-1 ... form-n2)
      ...
      (test-m form-1 ... form-n3) )

The test expressions are evaluated in order, until one with a non-NIL value is found. When a non-NIL test is found, all of the remaining forms inside the list containing this test are evaluated. The value of the last form in this list is returned. Consider the following example:

> (setf animal 'hawk)
HAWK
> (cond ((member animal '(dog cat goat)) (setf group 'mammal))
        ((member animal '(ant flea bee)) (setf group 'insect))
        ((member animal '(hawk gull)) (setf group 'bird)))
BIRD

Sometimes a final test of t is used to force some actions to be performed if all other tests fail:

> (cond ((= a 0) (setf b 10))
        ((= a 10) (setf b 0))
        (t (setf b 5)))
0

Exercise 4:
Earlier, we defined the following function first-name:

(defun first-name (namelist position)
    (first (nth position namelist)))

Suppose that the input namelist can consist of names that may have a title at the beginning of the name, for example:

(setf names '((President Diana Chapman Walsh) (Doctor Wendy Wellesley) (Mark Twain)))

Assume that a global variable named titles has been created whose value is a list of possible titles:

(setf titles '(President Doctor Professor Sir Madame))

Modify the first-name function so that if a title is present in the name list, this title is disregarded and the person's real first name is returned. Consider using let to create a useful local variable.

9. Formatting printed output

The format function allows nicer printing of output. A string is a built-in datatype in LISP that consists of a sequence of characters surrounded by double-quotes. The format function prints strings. The first input to this function is a specification of where the output should be printed, and the second input is the string to be printed. We will only print output in the terminal window, which can be specified by writing t as the first input:

> (format t "Hello!")
Hello!
NIL

The evaluation of a format statement returns the value NIL. The following function prints three strings, which are all printed on the same line when the function is executed:

(defun print-things ()
   (format t "This is one line")
   (format t "This is a second line")
   (format t "This is a third line"))

> (print-things)
This is one lineThis is a second lineThis is a third line
NIL

Special characters can be placed within the string to modify the printout. Special characters must be preceded with the ~ character. For example, the combination ~% specifies that a carriage return should be printed at this location in the string, as in the following example:

(defun new-print-things ()
   (format t "This is one line")
   (format t "~%This is a second line")
   (format t "~%This is a third line")
   (format t "~%one ~%two ~%three"))


> (new-print-things)
This is one line
This is a second line
This is a third line
one
two
three
NIL

The combination ~a indicates a place in the string for a value to be inserted. The value is supplied as an additional input to the format function, after the close of the string input. In the following example, the value 'Jane is inserted into the output string where the ~a appears:

> (format t "Hi there ~a-- how are you today?" 'Jane)
Hi there JANE-- how are you today?
NIL

For text contained within the double-quoted string, the capitalization of letters is preserved, but the value 'Jane is printed in capital letters. Multiple values can be inserted into a string that contains multiple ~a characters. The values to be inserted must be given in the desired order, as inputs following the string. These values can be specified through LISP expressions to be evaluated, as shown below:

> (setf name '(President Diana Chapman Walsh))
(PRESIDENT DIANA CHAPMAN WALSH)
> (format t "May I address you as ~a? Or ~a? Or Ms. ~a?"
       (first name) (second name) (first (last name)))
May I address you as PRESIDENT? Or DIANA? Or Ms. WALSH?
NIL

Extra spaces can be added to the output string by placing an integer between the "~" and "a" in the ~a characters. The inserted value is printed at the far left end of the requested space:

> (format t "Hi there ~10a-- how are you today?" 'Jane)
Hi there JANE      -- how are you today?
NIL

10. Mapping functions over lists: mapcar, remove-if

Consider the following two functions:

(defun find-numbers (numlist)
   (cond ((endp numlist) ())
         ((numberp (first numlist))
             (cons t (find-numbers (rest numlist))))
         (t (cons nil (find-numbers (rest numlist))))))

(defun get-lengths (list1)
   (if (endp list1) ()
       (cons (length (first list1)) (get-lengths (rest list1)))))

In both cases, a new list is created that is the result of applying the same function to each element of an input list. In the case of find-numbers, the numberp function is applied to each element of the input list, and in the case of get-lengths, the length function is applied to each element. The concept of applying the same function to every element of a list is such a common programming pattern in LISP that a special function exists to perform this generic computation: mapcar. The above functions are rewritten below using mapcar:

(defun find-numbers (numlist)
   (mapcar #'numberp numlist))

(defun get-lengths (list1)
   (mapcar #'length list1))

The first input to mapcar is the function to be applied - the #' characters must precede the function name, in order to specify that the definition of this function should be used. The second input to mapcar is a list of input values. When the mapcar statement is evaluated, the input function is applied to each element in the input list, and a list of the resulting values is returned.

mapcar can also be used with functions of multiple inputs. In this case, multiple lists of inputs must be provided in the call to the mapcar function. In the first example below, mapcar first applies the + operator to the two elements that appear in the first location of each input list, 1 and 10, to obtain the value of 11 that appears in the first location of the list of values that is returned. Then + is applied to the two values that appear in the second location of each input list, 2 and 20, to yield the 22 that appears in the returned list, and so on. In the second example, the + operator is applied to three numbers (for example, 1+10+100) to obtain the values in the list that is returned. In the last example, the > operator is applied to successive pairs of numbers taken from the two input lists.

> (mapcar #'+ '(1 2 3 4) '(10 20 30 40))
(11 22 33 44)
> (mapcar #'+ '(1 2 3 4) '(10 20 30 40) '(100 200 300 400))
(111 222 333 444)
> (mapcar #'> '(10 20 30 40) '(5 25 10 50))
(T NIL T NIL)

The function that is supplied as input to the mapcar function can be a user-defined function, as shown in the following example:

(defun double (val)
   (* 2 val))

> (mapcar #'double '(1 2 3 4))
(2 4 6 8)

Finally, the following examples illustrate the use of mapcar with input functions whose inputs are lists:

> (mapcar #'second '((a b c) (d e f g h) (8 (9 10) 11)))
(B E (9 10))
> (mapcar #'append '((a b) (w x)) '((c d) (y z)))
((A B C D) (W X Y Z))
> (setf names '((John Q Public) (Wendy Wellesley) (Admiral Grace Murray Hopper) (Sir Laurence Olivier) (Miss Scarlet)))
((JOHN Q PUBLIC) (WENDY WELLESLEY) (ADMIRAL GRACE MURRAY HOPPER)
(SIR LAURENCE OLIVIER) (MISS SCARLET))
> (defun last-name (name)
     (first (last name)))
LAST-NAME
> (mapcar #'last-name names)
(PUBLIC WELLESLEY HOPPER OLIVIER SCARLET)

Exercise 10:
Define a function make-pairs that has two input lists that each contain the same number of top-level atoms. Using mapcar, make-pairs should return a list of pairs formed from atoms in corresponding locations of the input lists, as demonstrated below:

> (make-pairs '(alice jane sally judy) '(george james harris john))
((ALICE GEORGE) (JANE JAMES) (SALLY HARRIS) (JUDY JOHN))

The function remove-if also applies an input function to each element of an input list. In this case, the input function must be a predicate, and all elements that satisfy the predicate (i.e. return a non-nil value) are removed.

> (remove-if #'numberp '(3 4 a j (2 3) hello))
(A J (2 3) HELLO)
> (remove-if #'endp '(() nil (a b) (3)))
((A B) (3))
> (defun length3p (list)
     (= (length list) 3))
LENGTH3P
> (remove-if #'length3p '((1 2) (3 4 5) (6 7 8 9) (10 11 12) (13 14) (15)))
((1 2) (6 7 8 9) (13 14) (15))

Exercise 11:
Write a function remove-presidents that has a single input that is a list of names. remove-presidents should remove any name that starts with the word President. Define a separate predicate named presidentp that has a single input list, and which returns T if the first element of the input list is the word President, and NIL otherwise. Use remove-if and presidentp in your definition of remove-presidents. The following call to the remove-presidents function should return the list ((JOHN Q PUBLIC) (WENDY WELLESLEY) (SIR LAURENCE OLIVIER))

(setf new-names '((John Q Public) (Wendy Wellesley)
                  (President Diana Chapman Walsh)
                  (Sir Laurence Olivier)
                  (President George Bush)))

(remove-presidents new-names)

11. Invoking functions with funcall

A user-defined function can also have an input parameter that is a function, similar to built-in functions like mapcar and remove-if. The input function can be applied to a set of inputs using the funcall function. In the test-list function below, the first input is assumed to be a function that can be applied to two lists. In the body of the test-list function, funcall is used to apply the input function to the two inputs list1 and (reverse list1).

(defun test-list (op list1)
   (funcall op list1 (reverse list1)))

> (test-list #'append '(1 2 3))
(1 2 3 3 2 1)
> (test-list #'list '(1 2 3))
((1 2 3) (3 2 1))
> (test-list #'cons '(1 2 3))
((1 2 3) 3 2 1)
> (test-list #'equal '(1 2 1))
T

The following example uses funcall to invoke arithmetic operators:

(defun compute (op num base)
   (if (= num 0) base
       (funcall op num (compute op (- num 1) base))))

> (compute #'* 5 1)      (the factorial function)
120
> (compute #'+ 5 0)
15

12. Defining Local Functions with lambda

In the following example, the new function greater100 is defined separately and used in a mapcar statement:

(defun greater100 (num)
   (> num 100))

> (mapcar #'greater100 '(341 27 622 58 99 101))
(T NIL T NIL NIL T)

As a shortcut, we can avoid creating the separate greater100 function definition by placing a description of what this function does inside the mapcar statement itself, using a lambda expression:

(mapcar #'(lambda (num) (> num 100)) '(341 27 622 58 99 101))

Note the similarity between the following two expressions:

(defun greater100 (num) (> num 100))

(lambda           (num) (> num 100))

You can think of the generic name lambda as replacing defun greater100. The lambda expression effectively creates a temporary, nameless function definition that only exists during the execution of the function containing this expression. Examine the following additional examples using lambda expressions:

> (mapcar #'(lambda (val) (* 2 val)) '(1 2 3 4))
(2 4 6 8)
> (mapcar #'(lambda (name) (first (last name))) names)
(PUBLIC WELLESLEY HOPPER OLIVIER SCARLET)
> (mapcar #'(lambda (element list) (member element list))
          '(a b c d)
          '((c a t) (d o g) (b i r d) (t o a d)))
((A T) NIL NIL (D))

Exercise 12:
Rewrite the following mapcar statement so that it uses a lambda expression instead of the presidentp function

(mapcar #'presidentp new-names)

lambda expressions can also be used with remove-if:

(remove-if #'(lambda (list) (= (length list) 3))
     '((1 2) (3 4 5) (6 7 8 9) (10 11 12) (13 14) (15)))

13. The sort function

The function sort sorts the elements of a list using an arbitrary predicate to compare the relative values of each pair of elements in the list. The first input to the sort function is the list to be sorted, and the second input is the predicate to use for comparison. The two examples below sort a list of numbers in increasing and decreasing order, respectively. Note that duplicate values in the input list are duplicated in the result.

> (sort '(3 8 6 2 5 4 9) #'<)
(2 3 4 5 6 8 9)
> (sort '(3 8 6 2 5 4 9 3 8) #'>)
(9 8 8 6 5 4 3 3 2)

An important thing to keep in mind is that the sort function permanently alters the input list in the process of sorting its elements, as illustrated in the following example:

> (setf nlist '(7 8 5 6 7 4))
(7 8 5 6 7 4)
> (setf newlist (sort nlist #'<))
(4 5 6 7 7 8)
> nlist
(7 7 8)

To avoid destroying the input list, a copy of this list can be used as input to the sort function. The copy-list function creates a copy of a list:

(setf newlist (sort (copy-list nlist) #'<))

The sort function can use a predicate defined by the user or an embedded lambda expression. In the first example below, numbers are sorted by their absolute value. The second example sorts a list of lists by the lengths of the lists:

> (defun abs-value (n1 n2)
     (< (abs n1) (abs n2)))
ABS-VALUE
> (sort '(2 -9 13 -4 -12 6) #'abs-value)
(2 -4 6 -9 -12 13)
> (sort names #'(lambda (list1 list2) (< (length list1) (length list2))))
((WENDY WELLESLEY) (MISS SCARLET) (JOHN Q PUBLIC) (SIR LAURENCE OLIVIER) (ADMIRAL GRACE MURRAY HOPPER))

14. Iteration with dotimes, dolist and do

dotimes is the simplest iteration function, and is used to repeat a set of actions a specific number of times. The general form is:

(dotimes (count-variable upper-bound-form **result-form**)
     body)

Throughout this section, parts of the general forms that are optional will be surrounded with ** characters. When a dotimes statement is entered, the upper-bound-form is evaluated to yield an integer n. Then the count-variable is assigned to the numbers 0 to n-1 and expressions in the body are executed for each value of this variable. After this process is done, the result-form is evaluated and its value is returned. If a result-form is not present, NIL is returned. Consider the following function addnums that adds the integers from 0 to 9:

(defun addnums ()
   (let ((sum 0))
      (dotimes (num 10 sum)
         (setf sum (+ sum num))
         (format t "~%num is ~a and sum is ~a" num sum))))

> (addnums)
num is 0 and sum is 0
num is 1 and sum is 1
num is 2 and sum is 3
num is 3 and sum is 6
num is 4 and sum is 10
num is 5 and sum is 15
num is 6 and sum is 21
num is 7 and sum is 28
num is 8 and sum is 36
num is 9 and sum is 45
45

When the dotimes statement in addnums is executed, the variable num is assigned to the integers from 0 to 9, and the two expressions in the body of the dotimes statement are executed for each value of num. The following isolated dotimes statement illustrates that the upper-bound-form can be an arbitrary expression, and the result form is optional:

> (setf sum 0)
0
> (dotimes (num (* 2 4))
     (setf sum (+ sum num)))
NIL
> sum
28

Exercise 13:
Define a function factorial that has a single input integer n, and which returns the factorial of n. Use a dotimes statement to compute the factorial function.

The function dolist performs iteration on a list. The general form of a dolist statement is:

(dolist (element-variable list-form **result-form**)
     body)

When a dolist statement is executed, the element-variable is assigned to each element in list-form, one by one, and the statements inside the body are evaluated for each value of the element-variable. After this process is done, the result-form is evaluated and its value is returned. If result-form is not present, the value NIL is returned. In the example below, the variable elt is first assigned to the atom a, and the two statements in the body of the loop are executed. Then elt is assigned to the atom b and the two statements are executed again, and so on. When this process is done, the value of newlist is returned.

> (setf newlist ())
NEWLIST
> (dolist (elt '(a b c d) newlist)
     (setf newlist (cons (list elt elt) newlist))
     (format t "~%The element is ~a and newlist is ~a" elt newlist))
The element is A and newlist is ((A A))
The element is B and newlist is ((B B) (A A))
The element is C and newlist is ((C C) (B B) (A A))
The element is D and newlist is ((D D) (C C) (B B) (A A))
((D D) (C C) (B B) (A A))

A return statement can be placed inside a dotimes or dolist statement. If a statement of the form (return expression) is encountered, the loop is immediately terminated and the value of expression is returned. In the following example, the iteration stops as soon as a three-element list is encountered, and this list is returned.

(defun find-first-list3 (list)
   (dolist (elt list)
     (if (= (length elt) 3) (return elt))))


> (find-first-list3 '((d g h j) (g t) (h y u) (a b c)))
(H Y U)

Exercise 14:
Define a new version of the get-lengths function that uses a dolist statement. Recall that get-lengths has one input that is a list of nested lists, and returns a list of the lengths of the nested lists.

Finally, do is a more flexible iteration function with the following general form:

(do ((variable-1 initial-value-1 **update-form-1**)
     (variable-2 initial-value-2 **update-form-2**)
     ....
     (variable-n initial-value-n **update-form-n**))
    (termination-test **intermediate-forms** **result-form**)
   body)

When entered, the variables are created and assigned to their initial values. After each execution of the expressions in body, each variable is updated according to their respective update-form. The repetition stops when termination-test becomes true (i.e. non-NIL). After termination, the intermediate-forms are evaluated. Finally, the result-form is evaluated and its value returned. If there are no forms following the termination-test, NIL is returned. In the following example, the variables x, y and sum are first created and assigned to the initial value 0 and the two statements in the body are executed. Then x is incremented by 1 and y is incremented by 2, and the two statements in the body are executed again. This process repeats until y reaches 10. At this point, the value of sum is returned.

> (do ((x 0 (+ x 1))
       (y 0 (+ y 2))
        (sum 0))
      ((= y 10) sum)
    (setf sum (+ sum (- y x)))
    (format t "~%x is ~a, y is ~a, sum is ~a" x y sum))
x is 0, y is 0, sum is 0
x is 1, y is 2, sum is 1
x is 2, y is 4, sum is 3
x is 3, y is 6, sum is 6
x is 4, y is 8, sum is 10
10

Note that variables created inside a dotimes, dolist or do statement are local to these forms and disappear when the iteration is completed, as illustrated in the following example:

> (setf x 100)
100
> (do ((x 10 (1- x)))
      ((= x 0))
     (format t "~%x is ~a" x))
x is 10
x is 9
x is 8
x is 7
x is 6
x is 5
x is 4
x is 3
x is 2
x is 1
NIL
> x
100

15. Using arrays in LISP

The function make-array creates an n-dimensional array. To create a one-dimensional array, a single integer input can be provided to specify the size of the array. In the example below, numarray is a one-dimensional array of 10 elements. By default, the array is filled with 0's. The LISP evaluator returns a representation of the array and its contents.

> (setf numarray (make-array 10))
#(0 0 0 0 0 0 0 0 0 0)

A two-dimensional array can be created by providing an input to the make-array function that is a list of integers that represent the two dimensions of the array. When the array is created, the LISP evaluator returns a representation of the array that again includes the contents of the array, printed as a list of lists, where each list shows the contents of one row of the array:

> (setf board (make-array '(8 8)))
#2a((0 0 0 0 0 0 0 0) (0 0 0 0 0 0 0 0) (0 0 0 0 0 0 0 0) (0 0 0 0 0 0 0 0) (0 0 0 0 0 0 0 0) (0 0 0 0 0 0 0 0) (0 0 0 0 0 0 0 0) (0 0 0 0 0 0 0 0))

The initial-element keyword argument to the make-array function can be used to initialize all elements in the array to a desired value:

> (setf numarray (make-array 10 :initial-element 10))
#(10 10 10 10 10 10 10 10 10 10)

The initial-contents keyword argument can be used to place a set of differing initial values in the array:

> (setf data (make-array 10 :initial-contents '(1 2 3 4 5 6 7 8 9 10)))
#(1 2 3 4 5 6 7 8 9 10)

In the case of a two-dimensional array, the contents of successive rows are placed in separate lists. Within each inner list, the first index of the array remains constant while the second index increments from 0. Across the inner lists, the first index changes. In the following example, initial contents are placed in a two-dimensional array:

> (setf board
       (make-array '(4 4) :initial-contents
           '((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16))))
#2a((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16))

Note that the list of initial contents could be derived from an arbitrary expression:

(defun make-numlist (n)
   (let ((list ()))
     (dotimes (num n (reverse list))
       (setf list (cons num list)))))


> (setf newdata
       (make-array 10 :initial-contents (make-numlist 10)))
#(0 1 2 3 4 5 6 7 8 9)

The functions setf and aref are used to access individual elements of the array:

> (aref newdata 8)
8
> (setf (aref newdata 6) 100)
100
> (aref newdata 6)
100
> (setf board
       (make-array '(4 4) :initial-contents
           '((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16))))
BOARD
> (aref board 0 0)
1
> (aref board 0 1)
2
> (aref board 0 2)
3
> (aref board 1 0)
5
> (aref board 2 0)
9

Arrays can store arbitrary things, as illustrated in the following examples:

> (setf names (make-array 7 :initial-contents
                 '(claire venessa judy jane debbie liz linda)))
#(CLAIRE VENESSA JUDY JANE DEBBIE LIZ LINDA)
> (aref names 3)
JANE
> (setf list-array (make-array 3))
LIST-ARRAY
> (setf (aref list-array 0) '(this is a list)
        (aref list-array 1) '(so is this)
        (aref list-array 2) '(and this))
(AND THIS)

The following loop counts the number of occurrences of the word this in the lists contained in list-array:

> (do ((index 0 (1+ index))
       (count 0))
      ((= index 3) count)
    (if (member 'this (aref list-array index))
        (setf count (1+ count))))
3

The following function prints the contents of the two-dimensional array board in a nicer format:

(defun print-board ()
   (dotimes (y 4)
     (format t "~%---------------------~%|")
     (dotimes (x 4)
       (format t " ~2a |" (aref board x y)))
     (format t "~%---------------------")))


> (print-board)
---------------------
| 1  | 5  | 9  | 13 |
---------------------
---------------------
| 2  | 6  | 10 | 14 |
---------------------
---------------------
| 3  | 7  | 11 | 15 |
---------------------
---------------------
| 4  | 8  | 12 | 16 |
---------------------
NIL

Finally, the function array-dimension can be used to access the dimensions of an array. Its first input is the name of an array, and the second input is an integer specifying the desired dimension:

> (array-dimension lists 0)
3
> (array-dimension names 0)
7
> (array-dimension board 0)
4
> (array-dimension board 1)
4

Exercise 15:
Define a function sum-array-1D whose input is a one-dimensional array of numbers, and which returns the sum of the contents of the array. Then define a function sum-array-2D whose input is a two-dimensional array of numbers, and which returns the sum of the contents of the array. In both cases, assume that the input array is an arbitrary size.

16. Grouping data with structures

A structure provides a way to group together related data about a particular type of object, similar to a class definition in Java. The function defstruct defines a new type of structure and allows instances of this structure type to be created. The general format of a defstruct statement is:

(defstruct structure-name optional-documentation-string
     (slot-name-1 default-slot-value-1)
     (slot-name-2 default-slot-value-2)
     ...
     (slot-name-n default-slot-value-n))

The default values for the slots are optional. The format of a defstruct statement that contains only the required components is:

(defstruct structure-name
     slot-name-1 slot-name-2 ... slot-name-n)


Consider the definition of the following structure to store names:

(defstruct name "structure to store peoples' names"
     (title nil)
     (first nil)
     (middle nil)
     (last nil)
     (suffix nil))

When a defstruct statement is evaluated, LISP automatically creates a new function to create an instance of a structure, whose name is the word make- followed by the name of the structure. For the above structure, this function has the name make-name. Keywords are used to specify the values to be placed in the slots of the structure. Each keyword is the name of one of the slots in the structure definition, preceded by a colon. The keyword is immediately followed by a value to be placed in the corresponding slot in the structure. The following statement creates a new instance of a name using the make-name function, and assigns this structure to the variable test-name:

(setf test-name
     (make-name :title '(Sir) :first '(Harry) :middle '(Joseph George)
                :last '(Hollingsworth) :suffix '(Jr)))

Functions are also automatically created to determine whether a particular object is an instance of this kind of structure, and to access the values in the slots of the structure, for example:

> (name-p test-name)
T
> (name-title test-name)
(SIR)
> (name-first test-name)
(HARRY)
> (name-middle test-name)
(JOSEPH GEORGE)
> (name-last test-name)
(HOLLINGSWORTH)
> (name-suffix test-name)
(JR)

These functions can be used inside a new function definition, for example:

(defun print-full-name (name)
   (append (name-title name)
           (name-first name)
           (name-middle name)
           (name-last name)
           (name-suffix name)))

> (print-full-name test-name)
(SIR HARRY JOSEPH GEORGE HOLLINGSWORTH JR)

The following function same-title-p returns T if two input names have the same title, and NIL otherwise.

(defun same-title-p (name1 name2)
   (equal (name-title name1) (name-title name2)))

Answers to exercises:

(1)   -128.0

(2)   num has the value 24, and val has the value 12

(3) (a)   (first (rest (first (rest (rest classes)))))
     (b)   (nth 1 (nth 2 classes))

(4) (a)   ((JOE) JIM JACK JAN JILL)
     (b)   (ANN ALICE (AMY ART) ABE)

(5) (a)   4
     (b)   (D C (A B))
     (c)   (HAVE A NICE DAY)

(6)   (defun rotate (list1)
       (append (rest list1) (list (first list1))))

(7)   (defun triplet (val1 val2 val3)
       (let ((list1 (list val1 val2 val3)))
             (list list1 list1 list1)))

(8)   All three expressions return the value NIL

(9)   (defun first-name (namelist position)
       (let ((name (nth position namelist)))
         (if (member (first name) titles :test #'equal)
             (first (rest name))
             (first name))))

     (defun remove-presidents (names)
       (remove-if #'presidentp names))

(12)   (mapcar #'(lambda (name) (equal (first name) 'President)) new-names)

(13)   (defun factorial (n)
       (let ((fact 1))
         (dotimes (num n fact)
           (setf fact (* fact (+ num 1))))))

(14)   (defun get-lengths (list1)
       (let ((lengthlist ()))
         (dolist (lst list1 (reverse lengthlist))
           (setf lengthlist (cons (length lst) lengthlist)))))

(15)   (defun sum-array-1D (arr)
       (let ((dim (array-dimension arr 0))
             (sum 0))
         (dotimes (x dim sum)
             (setf sum (+ sum (aref arr x))))))

  (defun sum-array-2D (arr)
     (let ((xdim (array-dimension arr 0))
           (ydim (array-dimension arr 1))
           (sum 0))
       (dotimes (x xdim sum)
         (dotimes (y ydim)
           (setf sum (+ sum (aref arr x y)))))))