=================[ Readings ]=================

Please read Chapter 2 of the free book "On Lisp",
http://www.paulgraham.com/onlisp.html ---pay special attention to
2.5 "Scope" and 2.6 "Closures". Try all examples at the command
line in GCL or SBCL. Try the scopes examples in Emacs, to see
how they behave under Emacs' default _dynamic scoping_.

Read Chapter 3 of "On Lisp". Section 3.1 explains the advantages of
the functional design by first showing a poor way to reverse a lisp
(Fig, 3.1) and then the native functional LISP way (Fig. 3.2). It goes
on to discuss _destructive_ implementations and their dangers, and
gives a list of destructive functions.

-----------------------[ REPL, CONSes, and symbols ]-----------------------

One very unusual feature of LISP is that the interfaces between the
READ, EVAL and PRINT parts of the interpreter are strictly defined,
and you are actually expected to think of READ as creating symbols and
CONS cells; EVAL gets them already created. So EVAL gets a ready LISP
list of cons cells and symbols, picks it apart, and remakes its; then
PRINT traverses the list that EVAL made and produces a printable
representation of it.

Thus typing  'x  into REPL actually creates a list (quote x), with
the symbols for "quote" and "x" and 2 cons cells. EVAL in this case
merely strips away the quote and the cons cells and passes the
pointer to symbol x to PRINT. There's more to a symbol than just
the name "x", of course; you can think of a symbol as a struct
with various slots, of which the name, obtainable via the symbol-name
function, is only one. GCL nicely tab-completes the functions for
getting these fields:

>(SYMBOL-<tab>
SYMBOL-FUNCTION  SYMBOL-NAME      SYMBOL-PACKAGE   SYMBOL-PLIST     SYMBOL-VALUE 

Symbol-package also affects how symbols are printed; we'll see that
when we look into packages.

You could say that for (quote x) EVAL does exactly the job of CADR,
taking first the CDR and then the CAR of (quote x). Similarly:

>(quote (quote x))

'X

That is, EVAL stripped one level of quote with its two cons cells,
and passed (quote x) to PRINT, which it printed. To wit:

>(car (quote (quote x)))

QUOTE

>(car ''x)

QUOTE

As everything else in LISP, quote is just a symbol, same as nil, same
as any other atom. It's easy to take it for some special syntactic
escaping element, but in fact it's not---it's just a symbol and
a list wrapper.

LISP syntax develops complications around _special forms_ such as IF
or SETQ, which don't evaluate some of its arguments---we wouldn't want
to evaluate both the "then" and "else" parts, and SETQ is just
shorthand---and it predictably gets more complicated with macros---but
fundamentally it's very simple and uniform.

-----------------------[ Filtering lists ]-----------------------

In LISP, making new lists from existing lists is the most natural operation.
LISP takes care of allocating and deallocating cons cells as needed; most
of the time, it's only cons cells that get created (or reused)---there's
usually no need to copy the objects themselves.

See filtering-lists.txt for more examples of using MEMBER, REMOVE-IF, REMOVE-IF-NOT,
and EQ, EQL, EQUAL for predicates.

"Anonymous functions" (a.k.a. "closures") made with LAMBDA are very
useful for filtering or transforming lists. They can be created
on the fly to formulate the desired condition, and will live just
long enough to do their job. We'll talk about closures on Tuesday.

>(lambda (x) (+ x 1))

(LAMBDA-CLOSURE () () () (X) (+ X 1))

This has created a function that, when called, will take its argument,
add 1 to it, and return the value. Notice that LAMBDA is a special
form, too: it does not evaluate its body (but it does capture
symbols it refers to at the moment of its creation---we'll see
exactly how it's done when we look at LISP bytecode).

>(mapcar (lambda (x) (+ x 1)) '(1 2 3 4 5 5 6 66))

(2 3 4 5 6 6 7 67)

>(mapcar (lambda (x) (* x 100)) '(1 2 3 4 5 5 6 66))

(100 200 300 400 500 500 600 6600)

-----------------------[ Recursion, not loops ]-----------------------

LISP introduces a new way of thinking about traversing collections
such as lists and trees. These are inherently recursive (a list
is an element and a list; a tree is an element and subtrees).
If a structure is naturally recursive, it can be traversed without
loops and indices, simply by following its natural structure.

For example, a LISP list is a CAR (an element) and a CDR (which is
either another list in its own right, or nil). When we get a list for
an argument for a function, we actually just get its first cons cell;
we have to take it apart ("deconstruct" it---although, of course, the
cons itself remains as it was, we just get pointers to its internals)
before we can do anything else. That gets us at two different cases:
whether the CDR (a.k.a., the rest of the list) is empty or not. If
it's not empty, then we can call the function again on this rest and
combine the result with whatever we do for the element (CAR).

If you think of cons cells as opaque structures that are built by a
special constructor (cons), and can only be taken apart with special
tools (car & cdr), then it stands to reason that traversing a list
must be done by reversing how it was constructed, cons cell by cons cell.

Here is a recursive function for list length:

(defun rlen (x)
  (cond ((null x) 0)  ; <-- we got a null list, return 0
        ((atom x) 0)  ; <-- it's an atom, so we can either signal error or say it has length 0
        ((consp x) (+ 1 (rlen (cdr x)))))) ; <-- if it's a cons, then add 1 to the length of the rest 

We could omit the atom case and let the function error out instead.

-----------------------[ Quicksort in LISP ]-----------------------

Quicksort sorts collections by divide-and-conquer, first picking a
"pivot", a collection element that divides all other elements into two
groups, one less than the pivot, the other greater, and by sorting
these groups (sub-collections) in turn, and so on, recursively. The
choice of the pivot can be arbitrary; in practice, picking the first
element at each round works well enough.

A C implementation typically sort an array by swapping pairs of
elements around until the "pivot" separates them, lesser ones to the
left, greater ones to the right, and then goes to sort these two
shorter arrays in place. There's a fair amount of looping over the
array with loops and indices, swapping by index, and plenty of
opportunity for off-by-one errors.

A LISP implementation, on the other hand, can do exactly what the
text description above says:

; This example is from http://blog.thezerobit.com/2012/09/01/beautiful-quicksort-in-common-lisp.html,
;   changed for GCL: 
(defun quicksort (list)
  (when list
      (let ((p (car list))   ; <-- deconstruct the cons we get for the argument list
            (xs (cdr list))) ; <---  take a 1st element and the rest 
        (let ((lesser (remove-if-not (lambda (x) (< x p)) xs))       ; <-- use the first element for the pivot
              (greater (remove-if-not (lambda (x) (>= x p)) xs)))
          (append (quicksort lesser) (list p) (quicksort greater))))))  ; <-- recursive call and merge

This function works :) It throws an error, though, if fed a number; so we can
tweak it to report that error via a special return value instead:

(defun quicksort (list)
  (cond ((consp list)
         (let ((p (car list))   ;; deconstructing list recursively                                                                          
               (xs (cdr list)))
           (let ((lesser (remove-if  (lambda (x) (>= x p))
                                     xs))
                 (greater (remove-if (lambda (x) (< x p))
                                     xs)))
             (append (quicksort lesser) (list p) (quicksort greater)))))
        ((null list) ())
        (t :qs-error)))

Note that the empty list case was handled by the first quicksort implicitly,
whereas our modification uses an explicit check for it.

:qs-error is a special symbol, a "keyword". Such symbols evaluate
to themselves, and their bindings cannot be changed. They are used as
special singleton values.

-----------------------[ Running LISP in Emacs ]-----------------------

When writing LISP, I find it absolutely necessary to have the editor's
help in matching the closing parentheses to the opening ones, and in
indenting the s-expressions with the tab key to confirm which part
of the function or special form I am writing. So Emacs is my environment
of choice---and there are several ways to use it to edit and run LISP. 

See:  running-lisp-in-emacs.txt