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)