Stylish Lisp programming techniques

As the size of software systems being created and -- more importantly -- maintained increases, it becomes more important than ever to write clean, robust, modular programs. Hoare's ``Emperor's New Clothes'' is a spectre that haunts anyone engaged in the task of creating complex software systems today. And in a future that promises automatic generation and verification of programs, programming constructs and techniques that have simple, rigorous semantics will be of primary importance to help these intelligent tools function.

In light of this, I've put together a short list of lisp programming techniques that increase the clarity, robustness, and elegance of your code. Some have been floating around for years, but I don't think they've ever been collected in one place. So have fun...

Technique n-2:

Even though dynamically scoped lisps lack the ability to close a function over some piece of local state, we can get the same effect with clever manipulation of quoted constants inside a function. Consider the following function, ELEMENT-GENERATOR. On every call, it side effects a quoted list which is part of its definition. Thus, each time we call it, it returns the next element in its state list.

> (defun element-generator ()
    (let ((state '(() . (list of elements to be generated)))) ;() sentinel.
      (let ((ans (cadr state)))       ;pick off the first element
        (rplacd state (cddr state))   ;smash the cons
        ans)))
ELEMENT-GENERATOR
> (element-generator)
LIST
> (element-generator)
OF
> (element-generator)
ELEMENTS
> (element-generator)
TO
> (element-generator)
BE
> (element-generator)
GENERATED

It is a simple matter to generalise this function to take an argument, which, if non-nil, is the new list to smash into STATE's cdr. Thus we can determine at runtime which list ELEMENT-GENERATOR will generate its elements from.

Technique n-1:

Some purists, concerned with style and readability, will object to the above function, claiming that it is difficult to perceive what is going on. They have a point, which leads us to the following technique. We can write a generator as a macro, where all the generator's state is represented explicitly as arguments to the macro. The macro simply expands into its next incarnation, displacing its old instantiation, and returns its true computation, quoted if need be. Consider, for instance, a generator for the positive integers. Every time we evaluate it, we want to get the next integer. When the evaluator tries to evaluate (GEN-COUNTER 5), it replaces itself with (GEN-COUNTER 6) in the body of the program, and returns 5. This is the sort of thing the functional programming advocates are referring to when they talk about making the state of a system explicit in the arguments. Note that this macro rewrites itself, which is what Steele is referring to in the Lambda papers when he describes macros as ''syntactic rewrite rules.''

> (defun gen-counter macro (x)    ;X is the entire form (GEN-COUNTER n)
    (let ((ans (cadr x)))         ;pick the ans out of (gen-counter ans)
      (rplaca (cdr x)             ;increment the (gen-counter ans) form
              (+ 1 ans))
      ans))                       ;return the answer

> ;this prints out the numbers from 0 to 9.
  (do ((n 0 (gen-counter 1)))
      ((= n 10) t)
    (princ n))
0.1.2.3.4.5.6.7.8.9.T
>

Technique n:

The dogma of structured programming frowns on the use of all-powerful constructs such as GOTO in favor of more restricted constructs such as WHILE and nested IF. We can take this even one step farther -- producing comparable gains in clarity -- if we take advantage of our ability to pass circular list structure to the evaluator. An unconditional loop implemented by a PROGN with a circular tail is surely more copacetic and pleasing to the eye than a Lisp DO, with all its complex syntax. We can further replace conditional loops with COND's whose clause bodies are actually circular pointers back to the top of the loop. Note, of course, that this is a much more powerful technique than simple WHILE-DO, enabling us to generate clean solutions to Knuth's examples of loops hard to implement with previous structured programming imperative constructs. Looping with circular progs:

> (defmacro circularize (&rest forms)         ;replace the forms with
    (cons 'progn (nconc forms forms)))        ;a circular list of the forms.
CIRCULARIZE

> (let ((a 0))                        ;Simple increment-and-print loop
    (circularize (princ a)            ;Indentation is important
		 (setq a (+ a 1))))   ;for clear code!
0.1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.
28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52
.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.73.74.75.76.7
7.78.79.80.81.82.83.84.85.86.87.88.89.90.91.92.93.94.95.96.97.98.99.100.10

If we implement all our branching and looping this way, we can remove the very notion of looping from

EVAL, who never has to worry about anything
but following ``sequential'' list structure.  This simplification of
EVAL naturally brings consequent efficiency and performance
benefits.


Some short-sighted individuals will point out that these programming
techniques, while certainly laudable for their increased clarity and
efficiency, would fail on compiled code.  Sadly, this is true.  At
least two of the above techniques will send most compilers into an
infinite loop.  But it is already known that most lisp compilers do
not implement full lisp semantics -- dynamic scoping, for instance.
This is but another case of the compiler failing to preserve semantic
correctness.  It remains the task of the *compiler implementor* to
adjust his system to correctly implement the source language, rather
than the user to resort to ugly, dangerous, non-portable, non-robust
``hacks'' in order to program around a buggy compiler.


I hope this provides some insight into the nature of clean, elegant
Lisp programming techniques.


			    -Olin Shivers