Some Guidance with Lisp

The first and most important requirement for quick and easy programming is
to adopt the Lisp style. Don't prolong the agony of conversion by clinging
to standard programming methods when you are not using a standard
programming language. Don't design programs in the old familiar way then
convert them to Lisp syntax, design them the Lisp way from the beginning.

Forget loops. Forget assignments (the only good use for SETQ is to give
variables their initial values before running a program). Even forget the
familiar direct "imperative" programming style: "do-first-thing;
do-second-thing; do-third-thing; ..." Lisp is more subtle and needs to be
used more subtly.

The main operations of normal programming are:
   Construction (making a new value from old ones) e.g.  a*2
   Assignment e.g. a=a*2
   Sequencing e.g. a=a*2; b=b-1; 
   Looping e.g. while (b>0) { a=a*2; b=b-1; }

The main operations of lisp programming are:
   Construction e.g. (* a 2)
   Composition (applying one function to result of another) e.g. (NULL (CDR X))
   Recursion e.g. (defun f (...) ......(f ..) .....)

Lets take a really simple example: evaluating polynomials. A polynomial
such as  -8 +2x -6x^2 +3x^3 +7x^4  (^ means to-the-power-of) may be
represented by the list (-8 2 -6 3 7) i.e. its coefficients alone. We will
design a gunction that takes this representation of a polynomial, together
with a value for X, and tell us what the overall value of the polynomial
would be. For example:
   (poly-val '(-8 2 -6 3 7) 0)  ->  -8
   (poly-val '(-8 2 -6 3 7) 1)  ->  -2
   (poly-val '(-8 2 -6 3 7) 2)  ->  108

Where to start? The only convenient things you can do with a list in Lisp
are: see if its empty (NULL L), look at its first element (CAR L), and
look at its other (non-first) elements (CDR L). To go with the Lisp style,
we'll let it guide us by trying to do something based on these. Just as in
all programming, no methodology is guaranteed to give the answer, but this
is the best bet. Go with the flow, the designer of Lisp knew what he was
doing.

Looking at it in those terms:
   Given L = (-8 2 -6 3 7) representing -8+2x-6x^2+3x^3+7x^4, (NULL L) is
false, telling us that there is some work to do, (CAR L) is -8 which
certainly is part of the desired end result, and (CDR L) is (2 -6 3 7).
What use could we make of (CDR L)? well, given that we are dealing with
representations of polynomials, look at what polynomial it represents:
(2 -6 3 7) represents 2-6x+3x^2+7x^3. That is all the rest of the desired
result (excluding the -8), if we multiply it by X.

So, (poly-val (-8 2 -6 3 7) X) is -8 plus ( X times (poly-val (2 -6 3 7)  X))

Generalising: (poly-val L X) is (CAR L) + ( X * (poly-val (CDR L) X))

Which gives us a naturally recursive solution. What is the special case
that makes the recursion stop? Of course L being empty springs to mind.
The empty polynomial () represents nothing at all, which may seem hard
to implement, except that what it really means is "no terms at all,
added together", which would come to zero. So we have:

   (defun poly-val (L X)
     (if (null  L)
         0
         (+ (car L) (* X (poly-val (cdr L) X)))))

This simple program is a clear example of both recursion and composition.

However, suppose that we had not said that
 (-8 2 -6 3 7) represents -8+2x-6x^2+3x^3+7x^4, but that
 (7 3 -6 2 -8) represents 7x^4+3x^3-6x^2+2x-8. The same thing, but
differently arranged. We are often not in conrol of how our inputs are
presented, so this could easily happen.

If we had already written the version of poly-val above, we could cleverly
make use of composition, and say
   (defun new-poly-val (L X) (poly-val (reverse L) X))
and everything would be fixed, but if we didn't have that idea, and nobody
can realy on having the right idea at the right time, we would have come
across a different, and slightly more tricky solution. Let's do it...

We are given the list (7 3 -6 2 -8) and a value for X, and are supposed to
find the value that 7x^4+3x^3-6x^2+2x-8 would have. The thing we have
immediate access to, (CAR L), which is 7, has to be multiplied by some as
yet unknown value before it can become part of the solution. We only find
that this unknown multiplier is x^4 after we've seen how long the list is:
one more element at the end and it would have been x^5 instead.
   The solution is to just keep the 7 somewhere. Every time we see a new
number at the head of the list (3 will be seen next) we know that the 7 we
are keeping need to be multiplied by X, and have 3 added to it to keep it
up to date. So as we work through the list (7 3 -6 2 -8) we would go
through this sequence of values in the special kept-aside somewhere:
                    7
                   (7)*x+3
                  ((7)*x+3)*x-6
                 (((7)*x+3)*x-6)*x+2
                ((((7)*x+3)*x-6)*x+2)*x-8 = 7x^4+3x^3-6x^2+2x-8.

This implementation COULD be acheived by simply having a variable that is
assigned the new value each time it is calculated, but that is not the
lisp way. Instead, we make it a third parameter, to represent the value of
the polynomial as seen so far:

  (defun new-poly-val (L X SoFar)
     (if (null L)
         SoFar       ; when run out of work, value so far is whole value
         (new-poly-val (cdr L) X (+ (* SoFar X) (car L)))))

It would be unfair to expect users to work out what this third parameter
should be, so we would then define something like:

  (defun real-new-poly-val (L X)  (new-poly-val L X 0))

just to start it properly, so let'd run it through:

            (real-new-poly-val (7 3 -6 2 -8) 2)
         -> (new-poly-val      (7 3 -6 2 -8) 2 0)
         -> (new-poly-val        (3 -6 2 -8) 2 7)
         -> (new-poly-val          (-6 2 -8) 2 17)
         -> (new-poly-val             (2 -8) 2 28)
         -> (new-poly-val               (-8) 2 58)
         -> (new-poly-val                 () 2 108)
         -> 108

Isn't that nice!


The multiplication table:

The table ((1 2 3 4)(2 4 6 8)(3 6 9 12)(4 8 12 16)) consists of a bunch of
lists, such as (2 4 6 8), which are very similar to one-another. in
general each is a list of N numbers starting from A and increasing in
steps of A.

(1) a list of N numbers starting from A and increasing by steps of B
  consists of
(2) the number A
  followed by
(3) a list of N-1 numbers starting from A+B and increasing by steps of A

The similarity of (1) and (3) show that this is another ideally recursive
function of 3 parameters: number of numbers desired, starting point, and
step size. The special simple case is simply that when the number of
desired numbers is zero, the list is of course empty.

   (defun table-line (num start step)
     (if (= num 0)
         nil
         (cons start (table-line (- num 1) (+ start step) step))))

How do we know to use CONS? Because that is the way lists are made.
Whenever you have a single element to be put at the front of a list, which
is exactly what we are doing, CONS is the man for the job.

Now for the table itslf:
  A times-table going up to 4 consists of (table-line 4 1 1) followed by
the degenerate times-table going up to 4, but starting from 2. i.e.
(table-line 4 1 1) produces (1 2 3 4), and the rest ((2 4 6 8) (3 6 9 12)
(4 8 12 16)) is just a shorter times table. The first line can be CONSed
onto the shorter table.
  To be able to produce these degenerate tables that don't start from 1,
we need to make the starting point for the times table be a parameter too.

  (defun times-table (begin end)
     (if (> begin end)
         nil
         (cons (table-line end begin begin)
               (times-table (+ begin 1) end)))))

Again we use CONS to produce the result because even though the thing
being CONSed (table-line end begin begin) is itself a list, we want that
list to appear as a single item in a list of lists. If we had used APPEND
instead of cons, the final result woyuld have been (1 2 3 4 2 4 6 8 3 6 9
12 4 8 12 16).

Naturally, we want to make this user-friendly, so
   (defun real-times-table (size)  (times-table 1 size))


An alternate definition

  We could make this much more useful by making it an anything-table
generator, so we could provide the multiply function to it as an extra
parameter to make it produce a times-table, or the addition operator for a
plus-table, or whatever. For example:

   (defun a-sq-plus-b (a b) (+ (* a a) b))

   (anything-table #'a-sq-plus-b 3) produces ((2 3 4)(5 6 7)(10 11 12))

[when you want to use a function-value, you have to put #' before the name
of the function. Its just one of those things]


The table-line function will now have to behave quite differently. No good
having it go up in simple steps, because that isn't how some functions
behave. What it needs to do is simply keep track of its "co-ordinates" in
the table at the moment, so when it is creating the seventh element of the
third line, it will be able to look at two of its parameters, lets call
then X and Y, and see the values 7 and 3.

the new table-line will need to know which line it is on (Y, given to it 
by times-table, which is responsible for arranging the lines), which
element of that line it is about to produce (X, which simply steps from 1,
2, 3, ... up to the size of the line), and how many elements are supposed
to be on the line (N). Of course, it must also be given the operation that
is to be applied (OP). For reasons to be seen later, we'll accept this OP
operation parameter, but not use it yet, jut carry on using multiplication
instead. Sounds strange, but you'll see.

   (defun newer-table-line (Y X N OP)
       (if (> X N)
           nil
           (cons (* X Y) (newer-table-line Y (+ X 1) N OP))))

The trouble with the OP parameter is that if we just say (OP X Y) it won't
work. When lisp sees (OP X Y) it looks for a function that was DEFUNed
with the name OP. There wasn't one, OP is a variable in which the
function is temporarily lurking. When a variable contains a function you
have to use the APPLY function to use it. Apply expects two parameters, a
function-value and a list of that function's parameters:
   e.g.   (apply #'a-sq-plus-b '(3 4))
So you can see why I didn't want to introduce that earlier.
newer-table-line now becomes:

   (defun newer-table-line (Y X N OP)
       (if (> X N)
           nil
           (cons (apply OP (list X Y))
                 (newer-table-line Y (+ X 1) N OP))))

Now the function anything-table will need to know what line it is on (Y),
how many lines are required (N), and the operation (OP):

   (defun anything-table (Y N OP)
      (if (> Y N)
          nil
          (cons (newer-table-line Y 1 N OP)
                (anything-table (+ Y 1) N OP))))

and to make it nice:

   (defun table (N OP)  (anything-table 1 N OP))

and call it thus (for example):

   (table 4 #'a-sq-plus-b)

or even:

   (defun very-new-times-table (N) (table N #'*))


Printing a table nicely in columns.

Lets allow 3 digits plus a space for each number (a times-table that goes
beyond 999 would be too big to read anyway). One key requirement then is
to be able to print numbers occupying exactly four character positions.
Lets experiment with PRINC to see exactly what it does:
  (progn (princ "X") (princ 12) (princ "X")) prints X12X
no extraneous spaces at all, so we can make use of that in a very
straight-forward, but perhaps inelegant way. (only impractical academics
go for elegance at the expense of all else, and usually fail anyway)

   (defun print-int-four (x)
      (cond ((< n 10) (progn (princ "   ") (princ n)))
            ((< n 100) (progn (princ "  ") (princ n)))
            ((< n 1000) (progn (princ " ") (princ n)))
            (t (princ " ???"))))

Now there are two ways to go about printing the table. One is to rewrite
the original table functions so that they just print values instead of
making lists out of them, the other is to write a separate function that
takes the table generated by the old function, and print it out nicely.

First way first.

Recall the original times-table-generator:

   (defun table-line (num start step)
     (if (= num 0)
         nil
         (cons start (table-line (- num 1) (+ start step) step))))

   (defun times-table (begin end)
      (if (> begin end)
          nil
          (cons (table-line end begin begin)
                (times-table (+ begin 1) end)))))

we will modify table-line so that it still generates the two parts of the
answer (on the last line);
    (1)  start
    (2)  (table-line (- num 1) (+ start step) step)
but instead of CONSing them to make a list, it prints them, one after the
other. When we reach the special case of (= num 0), we'll print a new line
before stopping:

   (defun print-table-line (num start step)
     (if (= num 0)
         (terpri)
         (progn (print-in-four start)
                (print-table-line (- num 1) (+ start step) step))))

Now the function to print the whole table simply does the same
calculations as before, but this time calling print-table-line instead of
table-line, so the line gets printed, and not CONSing the two results
together again:

   (defun print-times-table (begin end)
      (if (> begin end)
          nil
          (progn (print-table-line end begin begin)
                 (print-times-table (+ begin 1) end)))))

And Bob's your uncle.

The second way, taking a function that prints an existant table, provided
to it as a list of lists. It will of course run through the table one
sub-list at a time, somehow printing each of them prettily, then stopping.
The rule to follow is:

   To print a big table:
      print the first line, then
      print the rest of the big table.

   (defun print-table (tab)
      (if (null tab)
          nil
          (progn (print-line (car tab))
                 (print-table (cdr tab))))

How do we print the individual lines prettily? Easy:

   To print a whole line prettily:
      print the first number prettily, then
      print the rest of the line prettily.

   (defun print-line (lin)
      (if (null lin)
          (terpri)
          (progn (print-in-four (car lin))
                 (print-line (cdr lin)))))

That wasn't too bad, was it?

What about the problem of prime detection? That's actually quite easy.
A prime number is a number with no divisors between 2 and itself-1. A key
concept is obviously telling whether one number is a divisor of another or
not.

   (mod n m) returns the remainder after dividing n by m.
   (mod 10 4) -> 2     (mod 17 6) -> 5    (mod 8 2) -> 0
   if (mod n m) is zero, then m is a divisor of n

Let's encapsulate that in a function:

   (defun is-divisor (n m)
          (= (mod n m) 0))

Now the question of divisors in a range: Has N got any divisors between A
and B?
    if B>A then No, because there is nothing between A and B
    if A is a divisor of N then Yes, we've found one.
    otherwise, we don't know yet; A is not a divisor, so we continue to
               search for divisors of N between A+1 and B.


   (defun any-divisors-in-range (N A B)
      (cond ((> A B) NIL)
            ((is-divisor N A) T)
            (T (any-divisors-in-range N (+ A 1) B))))


Now the test for primality is easy-peasy:

   (defun is-prime (N)   (any-divisors-in-range N 2 (- N 1)))

You could be more efficient and use the square root of N as the upper
limit of the search, instead of N-1, but that's a trivial thing.

I hope these worked examples help, if you want more, just yell.