Defining Functions

Fixed arity functions

Functions are defined in Lisp using the defun defining form. Defining a function with defun looks like this:

(defun fn-name ( arg-1 ... arg-m) exp-1 ... exp-n)

where fn-name is an identifier as are arg-1 to arg-m. The body of the function is the sequence of expressions exp-1 to exp-n. A function is called as was described earlier in function application, by using the identifier which names the function in the operator position of the application, for example:

(fn-name exp-1 ... exp-m)

calls the function defined with the name fn-name, passing as arguments the values of the expressions exp-1 to exp-m. Note that there are the same number of expressions in the call to the function as there are defined arguments in the definition.

Variable arity functions

Most Lisps offer a facility to define a function which accepts an arbitrary number of argument expressions. Beware! The syntax for this varies widely, but in EuLisp, it looks like this:

(defun fn-name ( arg-1 ... arg-m rest: arg-m+1) exp-1 ... exp-n)

This defines a function which accepts at least m arguments. There are three cases to consider:

fewer than m arguments:
This is an error, and the system should tell you so, just as when the wrong number of arguments is supplied to a fixed arity function.
exactly m arguments:
arg-1 to arg-m receive the corresponding values of the argument expressions and arg-m+1 receives the value ().
more than m arguments:
arg-1 to arg-m receive the corresponding values of the argument expressions. arg-m+1 receives a list whose elements are the values of the remaining argument expressions.
user> (defun foo1 x x) foo1 user> (foo1 1 2 3) (1 2 3) user> (defun foo2 (x . y) (cons x y)) foo2 user> (foo2 1 2 3) (1 2 3) user> (defun foo3 (x . y) y) foo3 user> (foo3 1 2 3) (2 3) The function foo1 takes 0 or more arguments and returns the list of those arguments. foo2 takes 1 or more arguments and returns the list constructed by joining the first argument on to the front of the list of the second and subsequent arguments. foo3 takes 1 or more arguments and returns the list of the second and subsequent arguments.

Examples of function definition

Computing the length of a list

Since lists are a fundamental datatype in Lisp, it seems reasonable to start by defining a function which operates on lists, specifically, one to count the number of elements in a list. Of course, such a function is very likely already defined: in EuLisp this function is called size. We will define a function called list-length.

First, we must work out the algorithm. This also illustrates a common way of solving problems in Lisp and in the many functional languages descended from it and lambda-calculus (its theoretical underpinning), where we identify one case for which the result is trivial and the general case which is successively reduced to the trivial case. If you have done mathematical induction, you will find this obvious: this is just induction over a structure.

trivial case:
is of an empty list, that is (). The length of ()is 0.
general case:
is of a non-empty list. Given a list, we can obtain a list that is one element shorter by taking its cdr. Thus, the length of the non-empty list is 1 plus the length of its tail.
Consequently, we can make the following definition: (defun list-length (l) (if (null l) 0 (+ 1 (list-length (cdr l))))) Note the use of the predicate (returns true or false) function null. Its result is () if its argument is (), otherwise, it returns t. Also note that the input again extends over more than one line.

To confirm our understanding of how list-length works, let us consider its application to the list '(a b c):

(length '(a b c)) => (+ 1 (length '(b c))) => (+ 1 (+ 1 (length '(c)))) => (+ 1 (+ 1 (+ 1 (length ())))) => (+ 1 (+ 1 (+ 1 0))) => (+ 1 (+ 1 1)) => (+ 1 2) => 3 where each of the (important) steps of the computation have been written out like substitutions into a formula.

Reversing a list

Another favorite beginning exercise in Lisp. To solve this problem we can use the append function. As before, we tackle the development of the algorithm by identifying a trivial case and a general case:
trivial case:
the empty list, the reverse of which is the empty list.
general case:
if we can reverse the tail of the list and then tack the head on to the end, we have reversed a non-empty list. The second bit uses append.
The code looks like this: (defun reverse-list (l) (if (null l) () (append (reverse-list (cdr l)) (list (car l))))) Note that append joins two lists, so we have to make the head of l into a list, using the constructor function list.

We can use the same analysis technique as before to see how reverse-list works:

(reverse-list '(a b c)) => (append (reverse-list (b c)) (list 'a)) => (append (append (reverse-list (c)) (list 'b)) (list 'a)) => (append (append (append (reverse-list ()) (list 'c))) (list 'b))) (list 'a)) => (append (append (append () (list 'c))) (list 'b))) (list 'a)) => (append (append (c) (list 'b))) (list 'a)) => (append (append (c b)) (list 'a)) => (c b a)
Julian Padget,, this version December 9, 1994