Most important:  Where can I find an online introduction to LISP for
perfectly intelligent people who have never used it before?  (No `LISP
for Dummies', please.)  I've used C for quite a while and BASIC before
that, and now I'm trying to expand my horizons.  I've looked through
the FAQ for pointers to resources, but all of the introductory
materials listed are books, and for various reasons I can't buy a
book.

Also, what relevant reasons (besides novelty) are there to learn LISP?
I guess what I want to know is, what can I do in LISP that is more
difficult or not possible in C?  Will a program to generate more
digits of Pi than any sane human would ever need be any easier in LISP
than other languages?  What about prime numbers?  A game such as
Tetris?

If anybody has any simple but nontrivial code samples they're willing
to share (with an explanation of what they do and how would also be
nice), I would probably also find those useful once I've figured out
the basic concepts of the language (beyond figuring out things like
the fact that
(caar (cons (cons 'a 'b) 'c))
returns
A
, that is.)

Thanks in advance.

You can do, (caar (acons 'a 'b 'c)) as well. You can use first instead
of car; some like this better, I'm surprised that c{ad}r haven't been
declared archaic.

Are you interested in fonts? I have some code that will extract the
string table of truetype fonts (like the name, copyright, etc), as
well as some stuff for working with type1, and pfm files.

You like graphics? I have a terminfo decompiler/parser and some other
stuff that you probably wouldn't like to re-write :) (those
conditionals are _real_ nasty - and then there's the blasted xterm
entry; it should not be that complicated to move a cursor to a given
address - it's very sick.)

I have a silly inference program that does the rule/assertion/forward
chaining, and a silly prolog thing.

Cheers

It's a little library of functions for working with infinite-precision
real numbers. And I really *do* mean "infinite", not just "variable
and possibly very large": a real number is represented as a function
that generates approximations to the number. (More precisely, it's
a function that takes a positive integer argument n and returns some
number within 1/2 of n*x, however big n is. This is not necessarily
the best way to do it[2].)

In a few hundred lines you can implement the usual arithmetic
operations, conversion between my representation and infinite
continued fractions (represented, roughly, as infinite lists,
which again use the first-class-ness of functions to good effect),
some interesting transcendental numbers, roots of arbitrary
polynomials, and so on.

So, if I want to know what pi - root(17)*e^1/2 is, I say something
like

    (real:print-via-pipe
      (real:minus
        real:pie       ;; yes, there is a reason for not calling this PI.
        (real:times
          (real:nth-root-of-rational 2 17)
          (real:e-to-the-rational 1/2))))

and it starts churning out digits, and won't stop until either I
interrupt it or it runs out of memory.

The whole thing is very primitive and rather slow, and there are
plenty of important things I haven't implemented yet and plenty
of others that are a real mess. But that's a few evenings' work
in Lisp; I couldn't have done anything like as much in a few
evenings of C. (And I'm relatively more expert in C than in Lisp.)

Things about Lisp that make it much easier:

  - we already have arbitrary-precision rational numbers
  - we have garbage collection, so it's safe to construct
    complicated things on the fly and use them without the
    need to keep a pointer around so we can free them
  - we have closures as first-class objects, allowing a simple
    representation of numbers and of "infinite lists"
  - it's interactive, so debugging is easier and the resulting
    system gets I/O and parsing for free

[1] real.py, by Jurjen Bos. Actually, I've just looked and it
    *doesn't* do the same as my code (though it does do some
    important things my code doesn't yet do).

[2] It would possibly be better to use a function that takes n
    and returns a rational number within 1/n of x. The main reason
    why I didn't do that is that I started off implementing this
    in Scheme, and the Scheme implementation I use doesn't have
    rationals.

    In fact, better still would be a "mixed" representation
    allowing you to record simple representations of simple numbers
    (notably, rationals and algebraic numbers). Operations on these
    could then work better.

  because CONS is not a list-building operator, it's a tree-building
  operator.  lists are just special cases of trees.  and vice versa. :)

  FIRST, SECOND,... and REST work on lists, C[AD]+R on trees.

[''Are you interested in...'']

The way I did digits of Pi in C was to store the numbers as large
(currently working on 500000 digits) arrays of integers, and perform
the math (using the arctangent formula to calculate Pi, addition and
subtraction of these big numbers and multiplying/dividing them by
32-bit integers is all that is needed) using them as fixed-point
numbers.  The major disadvantage to this (at least as I see it) is
that if I want more digits I have to start over at the beginning, and
that I can't get a partial value before it's done the n digits (though
with an evening of work I *might* be able to get it to store its
progress digit-by-digit as it works it out).

[...]

[...]

   In the context of dealing with lists  FIRST and REST seem much
   more appropriate.   If you are dealing with conses  then CAR and CDR.
   [ Yes, there is a difference if you want to respect the List Abstract
     Data Type. Most of the List ADT operations take proper lists.
     Whereas when you are dealing with conses you don't need to maintain
     a proper list.  If lift the "hood" then lists are cons and Lisp
     sometimes doesn't do a good job of cleanly seperated the two.  ]

--

In non-embedded applications (but I would not be so sure that embedded
applications would not benifit as well) Lisp programmer are right.

        TREE-T          tree top
        TREE-LT         tree left top
        TREE-RT         tree right top
        TREE-LRT        tree left rigth top
        TREE-RLLRT      tree right left left right top
        TREE-[RL]+T
?

Cheers

As a first example:

(defun make-adder (number)
  (lambda (x) (+ x number)))

Calling (make-adder 8) returns a function that remembers that NUMBER
is 8, even after the function MAKE-ADDER returns.

If you then call (make-adder 6), you will have two function objects,
each of which have their own opinion of what NUMBER is:

(setf add-8 (make-adder 8))

(setf add-6 (make-adder 6))

(funcall add-8 10)
18

(funcall add-6 10)
16

Second example:

(let (womble)
  (defun set-womble (x)
    (setf womble x))
  (defun get-womble ()
    womble))

After the let has finished, the variable WOMBLE is only accessible
through the two functions.

Note: The last example is a not considered 'The Right Thing' by some
as it is hard to change the accessor functions without losing the
state of the closure variable, because running the (let) again creates
a _new_ WOMBLE.

The Right Thing, these days, is using CLOS for stuff like this.

An obvious way of representing a promise is as a function of no
arguments.  Forcing the promise is just calling the function:

    (defmacro delay (thing)
      `(function (lambda ()
         ,thing)))

    (defun force (promise)
      (funcall promise))

DELAY must be a macro because it can not evaluate its arguments.

This has problems because you probably want to remember whether a
promise has been forced or not or you might get odd results.  A
slightly more sophisticated version is:

    (defstruct (promise
                 (:print-function
                  (lambda (p s k)
                    (declare (ignore k))
                    (print-unreadable-object (p s :type t :identity t)))))
      thing
      forced-p)

    (defmacro delay (thing)
      `(make-promise
        :thing #'(lambda ()
                   ,thing)
        :forced-p nil))

    (defun force (thing)
      (typecase thing
        (promise
         (if (promise-forced-p thing)
             (promise-thing thing)
             (prog1
                 (setf (promise-thing thing)
                       (funcall (promise-thing thing)))
               (setf (promise-forced-p thing) t))))
        (t thing)))

    (setq x (f (g y) (h z)))

and that's it. In C you have to do something like

    { Foo * gy = g(y), hz=h(z);
      x = f(gy,hz);
      free(gy); free(hz);
    }

which is a real nuisance. Of course, it becomes even more
unpleasant if you are doing more complicated operations than
this.      

  the word is "deprecated", but it is certainly not used about CAR/CDR/etc.

  BTW, never "think" a standard says something.  consult it and _know_.
  <URL:http://www.harlequin.com/books/HyperSpec/>

  how about (first (second (second (first foo))))?

  in case you're referring to a tree, how about (tree-node foo 0 1 1 0)?
  note that the order of the arguments is reversed from the above code.
  the location in a tree is specified with the number of CDRs before a CAR.
  other location specifications may be more useful in a given case.

| Of course, code that does something like that would have to be documented
| well enough for the average programmer to easily understand what it's
| doing and why, since at the moment I'm more interested in maintainability
| than job security.  >:]

  funny how that actually improves job security...  :)

My opinion is that either you're doing a quick-and-dirty or you aren't.
If you're doing a quick-and-dirty with six-layer trees, you're in
trouble already, particularly if you're accessing a sample node 50
times.  If you're not, then you should keep it maintainable and
changeable.

Of course, as you say, you could document it.  My preferred method
of documentation would be something like

(defun foo-value (x)
  (declaim inline)
  (caadr (cadar x)))

and using foo-value, rather than write caadaadr (note the typo -
are you going to notice this any time you make it?) fifty times.

It works in emacs lisp... my mistake.

< Everything. Could you post them?

Here's the binary type1 to ascii type1 converter. It takes a binary
font (pfb) and dumps an ascii font (pfa) suitable for sending to a
postscript printer. I'm still working on the other stuff though.

Would love to hear some comments of improvemnts and such.

#|
Some commentary...

Binary type1 fonts have three sections, an ascii section for the font
dictionary (fontname, encoding, etc.), a binary section for the
encoded charstrings (font program), and a final ascii section that is
usually just a bunch of zeros for faster decoding on printers.

A section header is six 8-bit bytes:
 1    #x80 magic header
 2    section type, 1 for ascii or 2 for binary
 3-6  used to find the section size in 8-bit bytes (read-section-size).

|#

;;;; November 30, 1998 Monday  5:30 PM
;;;; Convert a binary type1 to an ascii type1 font

(in-package :user)

(defmacro t1-read-byte (stream)
  `(ldb (byte 8 0)
     (the fixnum (read-byte ,stream))))

(defmacro with-open-file-stream (direction type file/options &body forms)
  `(with-open-file
       (,@file/options :direction ,direction :element-type ,type)
     ,@forms))

(defmacro with-binary-input-stream (file/options &body forms)
  `(with-open-file-stream :input '(unsigned-byte 8) ,file/options ,@forms))

(defmacro with-binary-output-stream (file/options &body forms)
  `(with-open-file-stream :output '(unsigned-byte 8) ,file/options ,@forms))

(define-condition t1-error (file-error)
  ((file :initarg :file
         :initform (error ":FILE required")
         :reader t1-error-file)
   (position :initarg :position
             :initform (error ":POSITION required")
             :reader t1-error-position)
   (section :initarg :section
            :initform (error ":SECTION required")
            :reader t1-error-section))
  (:report (lambda (condition stream)
             (format stream
                "~@<Invalid ~[header~;ascii~;binary~:;, unidentifiable~] ~
                   section reading file ~a at position ~d.~:@>"
                (t1-error-section condition)
                (t1-error-file condition)
                (t1-error-position condition)))))

(defconstant +marker+ 128)

(defconstant +hex-vector+
    ;; `binary' equivalent of "0123456789ABCDEF"
    #(48 49 50 51 52 53 54 55 56 57 65 66 67 68 69 70))

(defun read-section-size (stream)
  "Return following section size as a 32-bit byte
Destructively advance binary-input-stream STREAM four 8-bit bytes"
  (macrolet ((%ash (x y) `(ldb (byte 32 0) (ash ,x ,y))))
  (ldb (byte 32 0)
       (logior
        (t1-read-byte stream)
        (%ash (t1-read-byte stream) 8)
        (%ash (t1-read-byte stream) 16)
        (%ash (t1-read-byte stream) 24)))))

(defun section-length (stream)
  ;; values: section-size section-type
  (let ((section-type (t1-read-byte stream)))
    (values (read-section-size stream) section-type)))

(defun dump-ascii-section (size input output)
  (loop repeat size
      for byte of-type fixnum = (t1-read-byte input)
      if (= byte 13) do
        (write-byte 10 output)
      else do (write-byte byte output)))

(declaim (inline write-hex-char))

(defun write-hex-char (byte output)
  (declare (optimize speed (safety 0) (debug 0) (space 0)) (fixnum byte))
  (macrolet ((%hex-byte (byte)
               `(svref +hex-vector+ (the fixnum ,byte))))

    (write-byte (%hex-byte (ldb (byte 8 4) byte)) output)
    (write-byte (%hex-byte (ldb (byte 4 0) byte)) output)))

(defun dump-binary-section (size input output)
  (let ((lines (floor size 32))
        (extra-chars (mod size 32)))
    (declare (optimize speed (space 0) (debug 0) (safety 0)))
    (loop repeat lines
        do (loop repeat 32
               do (write-hex-char (t1-read-byte input) output))
        do (write-byte 10 output))
    (loop repeat extra-chars do
          (write-hex-char (t1-read-byte input) output)
        finally (write-byte 10 output))))

(defmacro section-assertion-bind ((size-var) section-type input-stream)
  "Bind the variable SIZE-VAR to the length of the following section.
Check that the following section has the proper marker and is the type
indicated by SECTION-TYPE. Destructively modify the binary-input
input-stream by five 8-bit bytes."

  (let ((local-size (gensym "SIZE"))
        (local-section (gensym "SECTION"))
        (section (gensym "SECTION"))
        (stream (gensym "STREAM"))
        let-bindings)
    (assert (symbolp size-var) (size-var)
      "SIZE-VAR must be a setf-able symbol, not ~s" size-var)

    ;; If the variables are constants then we can evaluate them more
    ;; than one time - so check for it. Is this bad idea?
    (cond ((integerp section-type)
           (setq section section-type))
          (t (push `(,section ,section-type) let-bindings)))

    (cond ((symbolp input-stream)
           (setq stream input-stream))
          (t (push `(,stream ,input-stream) let-bindings)))

    `(let ,let-bindings
       (if (/= (t1-read-byte ,stream) +marker+)
           (error 't1-error
                  :file (file-namestring ,stream)
                  :section ,section :position (file-position ,stream))
           (multiple-value-bind (,local-size ,local-section)
               (section-length ,stream)
             (if (/= ,local-section ,section)
                 (error 't1-error
                        :section ,section
                        :file (file-namestring ,stream)
                        :position (file-position ,stream))
                 (setq ,size-var ,local-size)))))))

(defun t1-ascii (font outfile)
  (with-binary-input-stream (input font)
    (with-binary-output-stream (output outfile :if-exists :supersede)
      (let (section-size)
        ;; section 1
        (section-assertion-bind (section-size) 1 input)
        (dump-ascii-section section-size input output)
        ;; section 2
        (section-assertion-bind (section-size) 2 input)
        (dump-binary-section section-size input output)
        ;; section 3
        (section-assertion-bind (section-size) 1 input)
        (dump-ascii-section section-size input output)))))