[PG104, PG105] > Common LISP > Functional Programming Guidelines
created by pyg on 20 March 2007, last edition 28 February 2011

Modular approach

A LISP application consists in a number of function definitions, plus some structure definitions, and eventually some global variable definitions. Global variables are actually useless in functional programming. This collection of definitions should be spread into modules according to a logical decomposition. Modules are represented by .lisp files which may be compiled for added efficiency.

It is a good idea to provide examples with an application. However, examples should be clearly separated, so that a user is not forced to load them into memory, but  may do so if she wishes to.

Module dependancies

Because a function may invoke other functions, modules may depend on each other. Dependancies should form a DAG (Directed Acyclic Graph). Dependancies are easily expressed within modules, using require and provide Common LISP functions. Note that the *modules* global variable maintains a list of loaded modules, so that require does not do anything if the module already has been loaded. When you are developping your application, you are often changing your source files: you should use load instead of require, to get the most recent version of a given module.

Example: Assume GRAPH-SESSION requires DISCRETE-GRAPH, COMPLETE-GRAPH, and TREE-GRAPH, and the latter three modules all require GRAPHS, these are the corresponding .lisp files:

graph-session.lisp discrete-graph.lisp complete-graph.lisp tree-graph.lisp graphs.lisp
...
(require
 "DISCRETE-GRAPH"
 "discrete-graph")
(require
 "COMPLETE-GRAPH"
 "complete-graph")
(require
 "TREE-GRAPH"
 "tree-graph")
...
(provide
  "GRAPH-SESSION")
...
(require "GRAPHS"
         "graphs")
...
(provide
  "DISCRETE-GRAPH")
...
(require "GRAPHS"
         "graphs")
...
(provide
  "COMPLETE-GRAPH")
...
(require "GRAPHS"
         "graphs")
...
(provide "TREE-GRAPH")
...
(provide "GRAPHS")

Remark: If your files are to be compiled, it is safer (although not always mandatory) to enclose each require directive into an eval-when directive, so that required modules get loaded at compile time too, and not just at eval or load time only. For instance, write
(eval-when (:execute :load-top-level :compile-top-level)
    (require "GRAPHS" "graphs"))
instead of
(require "GRAPHS" "graphs")    .
Since there is no inconvenience in using eval-when, but only possible benefits, please always use eval-when!

The modular decomposition of your application should be such that any module M may be loaded and used independantly from the other modules, by means of a simple and unique LISP form:
(load "m")
or, equivalently
(require "M" "m")    .
Once one of these forms has been evaluated (we assume all modules belong to the directory from which LISP has been launched), the user should be able to use any function defined within module M. In other words, the user should not have to worry about module dependancies.

Defsystem: Another way to express module dependancies is the defsystem macro, not part of Common LISP environment, that was initially provided with LISP machine LISP (from LMI, Symbolics, or later on, Texas Instruments and Apple): you define your module dependancies, using defsystem, in a separate file, not within each file, as it is the case with require and provide forms. The defsystem macro is now available from <ask Robert Strandh>. Using this tool, you can easily maintain an application: files that need re-compiling, after some changes, will automatically be re-compiled, and just them.

Both methods have their advantages and drawbacks:

Structure of a module

Each module should have a clear and meaningful name. Each module should have the following structure:
It is important to provide a documentation with each definition, and respect LISP programming style. Note that all definitions def... should occur at the top level of your file: do not nest defun or defparameter forms within defun forms, for example.

Example of a module: see fermat.lisp.

Remark: You should only provide definitions in a module; you may provide test forms, but these should be commented out, so that they do not get evaluated upon loading the module. You may however easily evaluate such test forms, using Ctrl-x Ctrl-e, just as if they were not commented out.

Compiling an application

Compiling your files for greater efficiency (a speed factor of 10) may be achieved by means of the Common LISP compile-file function. On brahmane machine, this produces a .sparcf file. Beware of incompatibility of compiled files between different versions of Common LISP (we have two versions of Common LISP at ENSEIRB). The load or require functions always try to load the compiled version, if you do not specify the file extension; if the compiled version does not exist, they load the LISP source version.

It is good practice to provide a compile-all.lisp file as a means of compiling all your application, unless you are using a defsystem.

Example: compile-all.lisp.

Remark: We have two versions of CMU-CL (CMU18 and CMU19), depending on the machine. Compiled files are only compatible with the version under which they were compiled. I have designed tools that automatically place (or load) compiled files into (from) the appropriate subdirectory (CMU18 or CMU19), see cmu.lisp and cmu-compile-all.lisp example in 2007-2008 TP directory.

Back to Top

Documentation

Common LISP offers a means of extending documentation (already provided with library functions or global variables or the like) to your own application. All the defxxx special forms (defun, defstruct, defparameter, ...) feature a documentation string argument (usually the third argument). Documentation strings (when provided) are available using the Common LISP documentation function. This kind of active documentation is much more interesting than mere comments, since it is available even without the source files of an application.

Besides the technical aspects of Common LISP documentation, it is a very basic, reasonable, and good practice, to document a function before implementing it: you do not start building a house until you have a precise plan; you do not come up with a plan until you have a specification of your needs. Hence:

  • It does not make sense to start implementing a function before you have precisely typed its documentation string!
  • A function definition with no documentation string is not worth a penny!

The purpose of a LISP function is to solve a given problem. The LISP function documentation should be equivalent to the specification of the underlying problem. The expression of this specification, in functional programming, is essentially that of a relation between the function parameters and the result, carried by the function name itself (and not by so-called output variables as in imperative programming).

ADL [If you are providing descriptions of your algorithms in a separate document, using some Algorithm Description Language (ADL), you should stick to functional constructions of this ADL: ban loops, ":=" assignment statements, ";" statement sequences (also called statement composition); use recursion and high level functions. Note that these are also available in C language, so that your efforts toward a functional description (using ADL) of your algorithms will not be wasted, when you tackle C coding!]

The documentation string for a function foo with parameters p1, ..., pn, should be a sentence specifying the assumptions made on the parameters p1, ..., pn, and the result returned by foo, in terms of the parameters p1, ..., pn. Thus, each parameter should be quoted in the assumption part (unless there is no assumption on the parameter, which is a very unusual situation) and at least once in the result part of the sentence. A typical definition thus looks like

(defun foo (p1 ... pn)
  "Assuming P1 ..., ..., PN ...,
    FOO returns ... P1 ... PN ... ."
  ...)

For the sake of readability, parameters should be CAPITALIZED in the documentation string. The sentence fragment FOO returns may be replaced with returns, on the grounds that the result is implicitely that of the function.

Example:
(defun fact-mult (n p)
  "Assuming N and P are natural numbers,
    FACT-MULT returns N!*P."
  (if (zerop n)
    p
    (fact-mult (1- n) n*p)))

If some parameter is not quoted in the documentation string, and the documentation string makes sense in a precise way, then this parameter is useless, and should be removed from the list of parameters of the function, except in some very specific circumstances, where the (declare (ignore ...)) declaration should be used instead, e.g.:

(defun emptyset (x)
  "Yields NIL."
  (declare (ignore x))
   nil)


Remark: Auxillary functions locally defined within the scope of a defun (using flet or labels) cannot be documented; this is not too critical since such functions are considered unimportant, and cannot be invoked by a user. Hence, they do not belong to the user interface of the application. It is good practice, however, to introduce the specification of auxillary functions by means of comments. Here is an example:

(defun fact (n)
  "Assuming N is a natural number,
    returns N!."
  (labels ((fact-mult (n p)
            ;; Assuming N and P are natural numbers,
            ;;  FACT-MULT returns N!*P.
            
(if (zerop n)
                p
                (fact-mult (1- n) n*p))))
     (fact-mult n 1)))

Type discipline

Although Common LISP features types, it does not enforce a strict type discipline, unlike other programming languages such as ML. It is nevetherless good practice to introduce types in documentation strings. We suggest the following conventions regarding types:
Example:
(defun append (l1 l2)
  "Assuming L1, L2: list[A], for some type A,
    returns the concatenation of lists L1 and L2, which is of type list[A]."
  (if (null l1)
      l2
     (cons (car l1) (append (cdr l1) l2))))

Assertions

Assertions are a convenient means of checking function input, using the assert special form. They do not penalize compiled code efficiency, provided compiling options are turned to speed 3 safety 0, as they simply disappear from the compiled code. They are a useful and active support to input assumptions specified in assertions. They are particularly useful for debugging purposes during the implementation of a LISP application: one can thus discover input type assertion violations as early as possible.

Example:
(defun even-succ-p (n)
  "Assuming N is an non negative integer,
    yields T iff 1+N is an even number."
  (assert (and (integerp n) (>= n 0)))
  (evenp (1+ n)))
(even-succ-p 'potatoe)
Error in function COMMON-LISP::ASSERT-ERROR:
   The assertion (AND (INTEGERP N) (>= N 0)) failed.

Restarts:
  0: [CONTINUE] Retry assertion.
  1: [ABORT   ] Return to Top-Level.

Debug  (type H for help)

(COMMON-LISP::ASSERT-ERROR (AND (INTEGERP N) (>= N 0)) NIL NIL)
0] backtrace

0: (COMMON-LISP::ASSERT-ERROR (AND (INTEGERP N) (>= N 0)) NIL NIL)
1: (EVEN-SUCC-P POTATOE)
2: (INTERACTIVE-EVAL (EVEN-SUCC-P 'POTATOE))
3: (COMMON-LISP::%TOP-LEVEL)
4: (COMMON-LISP::RESTART-LISP)

0]
It is advised to use "simple" assertions that are unlikely to produce errors by themselves!

Back to Top

Functional programming

Common LISP is a rich blend of many (if not all) programming flavors: weakly typed (or untyped) functional programming, imperative programming (with side effects), object oriented programming (Common LISP Object System, CLOS, is probably the most complex object oriented programming language ever designed!).

Common LISP offers a rich library of functions for dealing with LISP objects (such as lists, arrays, sequences, ...). These functions are documented on line, and also (in a much more precise way), in the Common LISP HyperSpec. Many of these functions are not really functions, because they may destroy (or modify) the values of their arguments, as a side effect: such functions are not compatible with functional programming. We shall qualify them of unsafe. Side effects are clearly mentioned in the HyperSpec, so that it is quite possible to decide whether a function is safe or unsafe.

What is functional and what is not in Common LISP

Common LISP functional programming relies upon a small number of concepts and constructs:
Side effects are achieved by means of setf special form or unsafe functions (that really do not deserve the appellation of function): side effects are prohibited in functional programming. Since iterative constructions (such as do or loop) are useless without side effects, they are also prohibited. Note that sequential evaluation is meaningless in functional programming: hence, the body of a function should consist of just one LISP form; otherwise, forms preceding the last one are totally useless!

Safe versus unsafe functions

Here are some safe, versus unsafe, functions for dealing with lists:

Purpose Safe function Unsafe "function"
concatenation append nconc
element removal remove delete
elimination of duplicates remove-duplicates delete-duplicates
set union union nunion

Some additional safe functions

Here are some additional safe functions that you may find quite useful:
Note that remove and remove-duplicates functions also feature test and key keyword arguments.

High level functions

Functions such as mapcarsomeevery are considered "high level" because they take a functional parameter. These functions could easily be defined if they did not belong to standard Common LISP library.

High level functional programming is very powerful, and highly recommended. A high level function often replaces a number of low level functions.

An example of very useful high level function not provided with the Common LISP library is a fixpoint function. One can imagine several variants of this function. By definition, x: D is a fixpoint of function f: [D -> D] if and only if f(x) = x. In general, a fixpoint is not reachable in a finite number of steps; in many practical situations, however, a fixpoint may be reached in a finite number of steps, by iterating the application of f, starting from x: such a fixpoint will have the form fn(x). Here is a simple definition:

(defun fixpoint (f x)
  "Assuming F: [D -> D] for some type D, and X: D,
    and F has a fixpoint of the form F^N(X), for some
    natural number N,
   returns the first fixpoint of this form."
  (let ((fx (funcall f x)))
     (if (equalp fx x)
         x
        (fixpoint f fx))))

This definition is remarkably simple (a few lines of LISP), yet very general. It applies to many different contexts, depending on type D: for example, one can apply to the domain D of graphs, in order to compute the transitive closure of a graph, or its decomposition into strongly connected components.

Note the use of equalp in the above definition, for testing equality. This is the most general form of equality in Common LISP: it corresponds to mathematical equality. It applies to all kind of objects, numbers, symbols, strings, lists, arrays, defstruct instances, and is extendible to CLOS (Common LISP Object System) class instances.

Multiple values

Lists are a means of packing several values together. They are particularly well suited in situations where the elements are of a common type, and the number of elements is unspecified. This is not the case in the situation illustrated by the following function

(defun sum-difference-list (x y)
  "Assuming X and Y are numbers,
     returns the list of the two elements X+Y and X-Y."
  (list (+ x y) (- x y)))

For such a situation, Common LISP provides the notion of multiple value:

(defun sum-difference-values (x y)
  "Assuming X and Y are numbers,
     returns the multiple value of the two elements X+Y and X-Y."
  (values (+ x y) (- x y)))

The values special form does not exactly work like list. The LISP listener will print each value of a multiple value on a separate line, whereas it will eventually print a (short) list on a single line:

* (values 1 2)
1
2
* (list 1 2)
(1 2)

A multiple value is treated like its first value, when passed in argument of any function:

* (+ (values 10 20) (values 1 2))
11
* (+ (list 10 20) (list 1 2))
Argument X is not a NUMBER: (10 20).
Restarts:
  0: [ABORT] Return to Top-Level.

The only way of actually using all the values in a multiple value, is through the multiple-value-bind special form, which decomposes a multiple value into its components:

(defun sum-difference-product (x y)
  "Assuming X and Y are numbers,
    returns X**2 - Y**2."
  (multiple-value-bind (sum difference)
      (sum-difference-values x y)
      (* sum difference)))

This is better than

(defun sum-difference-product (x y)
  "Assuming X and Y are numbers,
    returns X**2 - Y**2."
  (let ((sum-difference (sum-difference-list x y)))
     (* (first sum-difference) (second sum-difference))))


because Common LISP handles multiple values in a very efficient way, w.r.t. speed and memory consumption: multiple values allocate memory for the time of the function call, whereas list cells continue to pollute memory until they are recycled by the garbage collector. Conceptually, multiple values correspond to a cartesian product of types.
Back to Top

LISP programming style

Appropriate comments, indentation according to LISP syntax, careful choice of symbols (function or parameter names) are very important, if you want your LISP module to be readable. Here is some basic advice:
See Robert Strandh's book (un bon style, règles de lisibilité) for more advice.

Back to Top