Defining 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.
However, 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 . 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.
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.
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)
Raising an integer to an integer power
This example is instructive for two reasons: it can be used to illustrate the
conversion of recursion to iteration (so called tail-recursion) and to illstrate a
nice algorithmic improvement at the cost of a less transparent program.
We begin by noting the equation a^n = a^(n-1) * a and that a^0
= 1. From this, it is fairly straightforward to derive a program:
(defun pow (a n)
(if (= n 0)
a
(* a (pow a (- n 1)))))
If we use the method developed earlier to explain its execution, then we see
the following:
(pow 3 4)
=> (* 3 (pow 3 3))
=> (* 3 (* 3 (pow 3 2)))
=> (* 3 (* 3 (* 3 (pow 3 1))))
=> (* 3 (* 3 (* 3 (* 3 (pow 3 0)))))
=> (* 3 (* 3 (* 3 (* 3 1))))
=> (* 3 (* 3 (* 3 3)))
=> (* 3 (* 3 9))
=> (* 3 27)
81
This program has a sigificant inefficiency, in that the number of recursive calls
is proportional to the argument n and hence, the depth of the stack is
proportional to n. In algorithmic analysis terms, it is a linear or O(n)
algorithm. In a procedural language such as FORTRAN, or Pascal, or C,
although the program could be expressed in the same way, it would be more
idiomatic to use a looping construct. Of course, it is well known that loops are
a degenerate case of recursion, and one particular case of recursion can be
optimized into a loop by the compiler: indeed, it is a feature programmers rely
upon. This case is when the last function called in a function's body is itself.
In fact, what happens is that the recursive call is replaced by a jump to the
beginning of the function. We can rewrite pow to permit this
optimization by adding a third parameter in which we accumulate the result:
(defun pow (a n x)
(if (= n 0)
r
(pow a (- n 1) (* a x))))
For this to work, the value of x in the initial call must be 1.
Now the evaluation proceeds like this:
(pow 3 4 1)
=> (pow 3 3 3)
=> (pow 3 2 9)
=> (pow 3 1 27)
=> (pow 3 0 81)
81
Now the number of recursive "jumps" is proportional to the argument n, as is
the number of multiplications we carry out - as before - but the depth of the
stack is fixed. We can reduce the number of recursive calls and the number of
multiplications by noting the following equation: a^n = (a^(n/2))^2, n in
2Z. Hence, we can derive another program:
(defun pow (a n)
(if (= n 0)
1
(let ((r (pow a (/ n 2))))
(if (= 0 (% n 2))
(* r r)
(* a r r)))))
Abusing our now familiar visualisation technique:
(pow 3 4)
=> ...(pow 3 2)
=> ... ... (pow 3 1)
=> ... ... ... (pow 3 0)
=> ... ... ... 1
=> ... ... (* 3 1 1)
=> ... (* 3 3)
=> (* 9 9)
81
Although this is not markedly different from the earlier examples, the
important point to note is that sometimes the intermediate result is squared.
In this particular example, we have the same number of multiplications as in
the previous version of pow, but consider the case of
(pow 3 8). That can be achieved with one more
multiplication here, while the previous version needs another four. In fact, the
number of multiplications is proportional to the number of times the exponent
can be divided by two, that is, its logarithm in base 2. Thus, this is called a
logarithmic or O(log n) algorithm.
Reversing a list revisited
Now that we have been sensitized to the analysis of recursive algorithms and,
in particular, the utility of conversion of proper recursion into tail recursion,
we look again at the definition of reverse we gave earlier:
(defun reverse-list (l)
(if (null l)
()
(append (revers-list (cdr l)) (list (car l)))))
The pattern of this function is identical to that of the power function
immediately above. There is a recursive call with a reduced argument and the
results of the recursive call are processed to build up the result. Thus, it
should be obvious that reverse-list does O(n)
append operations. However, let us consider a definition of
append:
(defun append (l1 l2)
(if (null l1)
l2
(cons (car l1) (append (cdr l1) l2))))
This. in turn, is linear in the cons operation, which is the
most basic list allocation operator. Thus, reverse-list does
O(n^2) cons operations to reverse a list of length n. A much
more efficient solution is possible if we rewrite reverse-list to
be tail recursive: the key idea is that as we take items from the front of the
source list, they can be put on to the front of a result list. When the source
list is exhausted, the result list will be the answer:
(defun reverse-list (l x)
(if (null l)
x
(reverse-list (cdr l) (cons (car l) x))))
This version is both tail recursive (the last function called is itself ) and uses a
number of list cells proportional to the length of the original list, ie. it is O(n).
Defining local functions
While the use of an additional parameter has helped to improve the efficiency
of the functions we considered above, there has been a price. The user of the
function has to supply the initial value of that parameter, yet that value is
private to the implementation of the function and is always the same. One
solution is to define two functions, eg.
(defun reverse-list (l) (reverse-list-aux l ()))
(defun reverse-list-aux (l x)
(if (null l)
x
(reverse-list-aux (cdr l) (cons (car l) x))))
However, a neater solution is to use a local function definition, by means of the
labels form, which looks like this:
(labels ((fn-name-1 arg-list-1 body-1)
...
(fn-name-i arg-list-i body-i))
exp-1 ... exp-n)
and in the case in question, allows us to make the following definition:
(defun reverse-list (l)
(labels
((loop (l x) (if (null l) x (loop (cdr l) (cons (car l) x)))))
(loop l ())))
Anonymous functions
This may sound like a pointless idea: after all, if you can't name a function,
you can't call it, nor can it be recursive. However, there are many situations
when anonymous functions can be useful, although if you have not used a
functional language before, you may not have felt their lack.
The notation for an anonymous function uses the special operator called
lambda and looks like this:
(lambda (arg-1 ... arg-m) exp-1 ... exp-n)
(lambda (arg-1 ... arg-m . arg-m+1) exp-1 ... exp-n)
(Note: in Common Lisp, this is prefixed by #'.) This can be used in the
function position in a function application:
((lambda (arg-1 ... arg-m) exp-1 ... exp-n) arg-exp-1 ... arg-exp-m)
or as a functional argument in a function application:
(f-name ... (lambda ...) ...)
or, arguably more important, and certainly a new concept if coming from
Pascal or C, as a functional result, returned from a function, for example:
(defun add-n (n) (lambda (x) (+ x n)))
(setq z (add-n 3))
=> (lambda (x) (+ x 3))
(z 4)
=> (+ 4 3)
12
Here, we have defined a function called add-n, the result of
which is an anonymous function which refers to the value of the argument
passed in the call to add-n which caused the anonymous
function to be created. Thus, the first application calls
add-n with 3, returning an anonymous
function. The second application calls the anonymous function, which is the
value of z, resulting in the addition of 4
and 3.
You can also try a self-assessment test.