4.4BSD/usr/src/contrib/emacs-18.57/man/cl.texinfo

\input texinfo    @c -*-texinfo-*-
@setfilename ../info/cl
@settitle Common Lisp Extensions

@iftex
@finalout
@end iftex

Copyright (C) 1987 Cesar Quiroz

@node Top, Generalities,,(DIR)
@chapter Common Lisp Extensions

The routines described in this chapter provide some of the functionality of
Common Lisp inside Emacs Lisp.

@menu
* gen: Generalities.           Things you need to know.
* sym: Symbols.                Gensym, gentemp, keyword-p, @dots{}
* lis: Lists.                  List*, pairlis, acons, @dots{}
* seq: Sequences.              Every, any, notevery, notany, @dots{}
* con: Conditionals.           When, unless, case, ecase.
* ite: Iterations.             Do, do*, dolist, dotimes, @dots{}
* mul: Multiple Values.        Values, values-list, @dots{}
* ari: Integer Arithmetic.     Floor, ceiling, round, truncate, @dots{}
* stf: Generalized Variables.  Setf and friends.
* str: Structures.             Like Pascal records or C structs.
* mis: Miscellanea.            Odds and ends that didn't fit elsewhere.
* tod: To Do.                  Suggestions for future hackery.
@end menu

@node Generalities, Symbols, Top, Top
@section Generalities

This section tells you want you need to know about the routines in the file
@file{cl.el}, so that you can use them.  The distribution also includes
this documentation and perhaps a few example files.

@subsection License, Availability, Maintenance

These files are covered by the GNU Emacs General Public License (if you
don't know its terms, try @kbd{@key{C-h} @key{C-c}}) and the statement of
no warranty (again, you can type @kbd{@key{C-h} @key{C-w}} if you don't
know its terms) also applies to them. @refill

I, Cesar Quiroz, the original author of the software described here, will
appreciate hearing about bug reports (and fixes), suggestions and comments,
applying both to the code and to this documentation.  I don't promise to
act on those communications, but whenever they might conduce to
improvements of this software, I will make those improvements available to
the general community through the Free Software Foundation.  You can reach
me at the following net addresses:
@quotation
quiroz@@seneca.cs.rochester.edu
quiroz@@rochester.arpa
@{allegra | seismo | @dots{} @} ! rochester ! quiroz
CSNET: Cesar Quiroz at node Rochester
@end quotation

@subsection Purpose and Limitations

These routines were written with two purposes in mind:

@enumerate
@item
To make programming in Emacs Lisp even more compatible with Common Lisp.
Indeed, my original motivation was to have a @code{do} macro.
@item
To facilitate to novice Lisp programmers a chance to practice with
features commonly found only in expensive implementations of Lisp. 
@end enumerate

In order to satisfy these purposes, the routines were written in such a way
that it is practical to use them inside Emacs: no effort was given to
implement features that could slow down the host Emacs unnecessarily nor
require recoding of the Emacs Lisp interpreter.

For instance, no support is given to floating point arithmetic.

So, I have tried to implement a subset of the functionality of Common Lisp.
Whatever is implemented, has syntactic and semantic properties like the
equally named features of Common Lisp, but not all the relevant features
have been implemented (@pxref{To Do}, for some suggestions).  When
deciding what to include, I have tried to strike a balance between these
constraints:

@enumerate
@item
Keep it simple, I didn't want to spend much time in this idea.
@item
Keep it compatible with Common Lisp.
@item
Keep it flexible, so my code doesn't oppose a better implementation (when
this looked hard, I just didn't implement the feature).
@item
Keep an eye on the intended use of Emacs Lisp: to support an advanced
editor.  I don't expect that more arithmetic support will be as conducive
to this goal as having better iterations and conditionals will.
@end enumerate

For background, the reference is ``Common Lisp: The Language'' by Guy
Steele Jr. (Digital Press, 1984).  For all the features described here
you can assume that the intent has been to provide the syntax and
semantics of the features of like name in the book.  For the most part,
this documentation will concentrate on how my routines @i{fail} to
implement Common Lisp faithfully.

@subsubsection Specific Limitations

Emacs Lisp and Common Lisp differ enough to make some of the emulation
difficult, expensive or nearly impractical.  Some specific limitations are
stated here:

@enumerate
@item
Common Lisp is lexically scoped (mostly), while Emacs Lisp is dynamically
scoped.  Things like @code{block}, @code{return}, @code{tagbody} are then
practically impossible to imitate correctly (in principle, rewriting
@code{eval}, @code{apply} and a couple of other functions would suffice,
problem is that such rewriting amounts to  a new interpreter on top
of the old.)  Things like @samp{implicit-blocks},
@samp{implicit-tagbodies} and the like have not been implemented at all.
Where they are needed, the most you can assume is that I tried to put
@samp{implicit-progns} around places where it made sense. @refill

@item
Emacs Lisp's @code{lambda} does not support all the possible argument
markers.  Similarly, @code{defmacro} doesn't support automatic
destructuring of the calls.  An approximation to a keyword-based calling
style was implemented, mainly for the sake of @code{defstruct}, but is
not general enough.  @refill

@item
Emacs Lisp supports arithmetic only on integers.

@item
Emacs Lisp doesn't support many of the basic types of Common Lisp.  In
particular, there are no arrays beyond vectors and strings (although these
ones are compatible), characters are essentially small
integers, etc. @refill

@item
There are no declarations in Emacs Lisp (in the sense of Common Lisp's
@code{declare}, @code{proclaim}, @dots{}) nor there is a explicit lattice
of types.  These limitations could be effectively overcome from Lisp code
(to a extent), but I don't see them as a very pressing need, if a need at
all in Emacs Lisp.  @code{defstruct} can be used to generate new types
that can be recognized at runtime. @refill

@item
The Emacs Lisp reader is not programmable.  The syntax it accepts is
almost standard, but it preempts '?' as a dispatching macro of sorts.
The @code{format} function is incompatible with Common Lisp.  There
isn't a `quasi-constant' notation (the usual @code{backquote} of Common
Lisp).  None of these differences causes any problems when writing Emacs
Lisp (although the lack of backquoting is felt sorely), but they oppose
a Common Lisp emulation. @refill

@end enumerate

@subsection Loading and Compiling

The file @file{cl.el} provides the @samp{cl} feature, you can use this to
test whether these routines have been loaded, or to load them from your
code (by means of @code{(require 'cl)}).  The compiled file is a little
larger than 50K bytes.

If you need to recompile the sources, make sure you load them first on the
Emacs that will do the recompilation.  This is because many syntactic
characteristics (like the special forms) have been implemented as macros
and you need to make sure that macros are known to the compiler before they
are used.

These extensions work correctly when interpreted in a GNU Emacs of
version 17.64 or beyond.  Compiling them requires a more recent byte
compiler, preferably one strictly younger than version 18.XX.

@subsection On Line Help

The routines in this file have documentation strings, so you can (and
should) consult them for the exact syntax allowed.  That information is
not repeated in this manual.  Some of the routines are also documented
explicitly in the Common Lisp reference, their doc-strings begin with
@samp{[cl]} to represent this fact.

The rest (those without the @samp{[cl]} mark) are auxiliary functions or
macros used by the rest of the implementation.  They are not constrained
by any standard and are advertised only in as much as they can be useful
in other applications. @refill

Each of the following sections contains a subsection called `Features
Provided'.  It lists briefly the user-visible features of this
implementation.  In its entries, names by themselves refer to functions.
Macros and variables are identified by a `MACRO' or a `VARIABLE' ahead
of their names.

@node Symbols, Lists, Generalities, Top
@section Symbols

The most important omission is that of a @var{packages} mechanism.
(For a possible implementation, @pxref{To Do})  Whenever a Common Lisp
function expects a package, I have substituted an obarray.  There is a
hack to have pseudo-keywords, see below. @refill

There are two other notorious omissions over which I haven't lost any
sleep.  The first is the lack of a @code{remprop} function, which could be
easily provided if needed.  The second is the lack of ways to modify the
print name of a symbol.  This one would probably be good only to
introduce strange bugs, so I don't miss it. @refill

@subsection Features Provided

@table @code
@item VARIABLE *gensym-index*
@itemx VARIABLE *gensym-prefix*
@itemx VARIABLE *gentemp-index*
@itemx VARIABLE *gentemp-prefix*
These variables are used to keep the state of the generator of new names.
Better leave them alone.
@item gensym
@itemx gentemp
These do the same as the Common Lisp names of like names.
@item MACRO defkeyword 
@itemx keyword-of
@item keywordp
These provide the pseudo-keywords implementation.
@end table

@subsection Keywords

The lack of packages makes it difficult to implement keywords correctly.
I have provided a macro @code{defkeyword} that takes a symbol and makes
sure it evaluates to itself.  (So, it is like @code{defconst}.)  If your
programs ever need keywords, put a bunch of calls to @code{defkeyword} at
the beginning of your code, so when loaded they will be in effect. @refill

The (standard) predicate @code{keywordp} tests to see if the given
symbol's name begins with a colon and then ensures that it evaluates to
itself. @refill

The function @code{keyword-of} takes a symbol and returns a keyword of
like name. @refill

@example
 (keyword-of 'foo)
:foo
 (keyword-of ':bar)
:bar
@end example

This feature was added mainly to support @code{defstruct} and the tests of
the sequence functions.  It is fragile and easy to fool.

@subsection New Symbols

A common need (especially when writing macros) is to be able to invent new
names for things.  I provide the @code{gensym} and @code{gentemp}
functions.  The global state needed is kept in the variables
@code{*gentemp-index*}, @code{*gentemp-prefix*}, @code{*gensym-index*} and
@code{*gensym-prefix*}.  Changing them, especially the index ones, is a
very bad idea.  I am not providing the Common Lisp default prefixes ('G'
for @code{gensym} and 'T' for @code{gentemp}) because of debugging
paranoia.  My default prefixes are harder to come by when giving sane
names to things. @refill

@node Lists, Sequences, Symbols, Top
@section Lists

Lists (indeed, conses) are so deeply involved in Lisp that there seems
to be little need to justify improving the list handling of a Lisp.

Common Lisp, however, is a rather huge Lisp.  I haven't provided all the
functions in the chapter of lists, mainly because some of them could be
implemented correctly only if keyword arguments were supported.
That explains why I haven't rushed to provide
@code{subst}, @code{sublis}, etc.  Also, that explains the rather
temporary nature of the implementation of @code{member} and
@code{adjoin}.  I will welcome any efforts to extend
this work. @refill

@subsection Features Provided

@table @code
@item endp
@itemx list*
@itemx list-length
Very standard utilities.  List* has proven especially useful to
overcome the lack of a real @code{backquote}.  In addition, things that
usually required the relatively clumsy
@example
(cons 'a (cons 'b oldlist))
(append (list a b) oldlist)
@end example
can now be simply put:
@example
(list* 'a 'b oldlist)
@end example
See also @code{acons}.

@item member
Another well known function.  Supports test with @code{eql} only.

@item acons
@itemx pairlis
These two are part of the standards association lists implementation.  I
am leaving @code{sublis} as an exercise for the reader.

@item adjoin
Done mainly for the sake of @code{pushnew}.

@item butlast
@itemx last
@itemx ldiff
Occasionally useful ways to access the last cons or a specified tail of
a list.  I don't remember why there isn't a @code{tailp} here.

@item c[ad][ad][ad][ad]r, up to four a's or d's
These 28 functions (and their setf inverses) have been provided once and
for all.  Many packages contributed to Emacs Lisp contain macros that
implement some of these, I think this code will make most of them
unnecessary. 

@item first
@itemx rest
@itemx second
@itemx third
@itemx fourth
@itemx fifth
@itemx sixth
@itemx seventh
@itemx eighth
@itemx ninth
@itemx tenth
More standard accessors (and their setf inverses).  Not particularly
useful but easy to provide.

@item setnth
@itemx setnthcdr
These functions are non-standard.  They are here for @code{defsetf}
purposes only, but they might be useful on their own.

@end table

@node Sequences, Conditionals, Lists, Top
@section Sequences

Sequences are partly supported in Emacs Lisp (see, for instance, the
@code{elt} function).  This limited support is compatible with Common
Lisp, so it should be easy to extend.  However, the lack of
keyword arguments makes many of the functions impossible so far (but, as
mentioned below, a basic framework for that extension
is provided here). @refill

The functionality really provided here is given by the functions
(essentially, predicates) @code{every}, @code{some}, @code{notevery},
@code{notany}.  I have found them useful countless times, so I thought
to provide them before anything else. @refill

That still leaves many omissions, though.

@subsection Features Provided

@table @code
@item every
@itemx notany
@itemx notevery
@itemx some
Extremely useful functions.  If your favorite Lisp doesn't have them,
you are missing a lot.

@item setelt
A setf-inverse to @code{elt}.

@item add-to-klist
@itemx build-klist
@itemx extract-from-klist
A @dfn{klist} is just an alist whose keys are keywords.  I based the
pseudo-keyword argument support of @code{defstruct} on this idea, but
their best fit is here, as they could help to write the remaining
sequence-handling functions (@code{find}, @code{substitute}, @dots{})
that I didn't provide for the lack of a good keyword
arguments mechanism. @refill

@item elt-satisfies-if-not-p
@itemx elt-satisfies-if-p
@itemx elt-satisfies-test-p
@itemx elts-match-under-klist-p
The Common Lisp book defines some of the semantics of sequence functions
in terms of satisfaction of certain tests.  These predicates provide
that functionality, but I haven't integrated them with the rest of the
extensions.  However, I thought it was better to include them anyway, as
they can serve somebody else as a starting point.

@end table


@node Conditionals, Iterations, Sequences, Top
@section Conditionals

An elementary incompatibility prevents us from producing true Common
Lisp here.  The @code{if} forms are different.  In Emacs Lisp, @code{if}
can take any number of subforms, there being a @var{condition} form, a
@var{then} form, and after them any number of @var{else} subforms,
which are executed in an implicit @code{progn}.  Moreover, that style is
widely used in the Emacs sources, so I thought most impractical to break
with 
it to support Common Lisp's @code{if} (where only one @var{else} form is
tolerated).  For the most part, I use @code{cond} almost always, so it
doesn't bother me much.  If you use single-branch @code{if}s often,
consider @code{when} or @code{unless} as alternatives.  @refill

@code{case} and @code{ecase} are a convenient way to write things that
usually end up in a very baroque @code{cond}.  

@subsection Features Provided

@table @code
@item MACRO case
@itemx MACRO ecase
@itemx MACRO unless
@itemx MACRO when
The standard stuff, completely implemented.
@end table

@node Iterations, Multiple Values, Conditionals, Top
@section Iterations

Having a @code{do} macro was my original motivation.  The alternatives
in standard Emacs Lisp are either expensive (recursion) or correspond
directly to the expansion of my macros:
@example
 (macroexpand '
  (do ((i 0) (j 1 (+ 1 j)))
      ((> j (foo i)) (cons i bar))
    (setq i (baz i j))))

(let ((i 0) (j 1))
  (while (not (> j (foo i)))
    (setq i (baz i j))
    (psetq j (+ 1 j)))
  (cons i bar))
@end example
So I prefer to leave to the macros the problem of remembering the
details right.

The incompatibilities are due to the problems already discussed
(@pxref{Generalities}, for more details). @refill

If you write Emacs Lisp code often, you will find enough uses for these.
Examples are cooking up a translation table to move @key{C-s} out of the
way of multiplexers, switches, concentrators and similar fauna, or
building keymaps.  @refill

@subsection Features Provided

@table @code
@item MACRO do
@itemx MACRO do*
@itemx MACRO dolist
@itemx MACRO dotimes
The standard, but for the lack of implicit blocks.

@item MACRO loop
The basic standard one, not the fancy one.  As per the book, warns you
about atomic entries at the surface of the macro (to guarantee that the
fancy @code{loop} macros can be made standard later).

@item MACRO do-all-symbols
@itemx MACRO do-symbols
These operate on obarrays, the default is the current one.

@end table

@node Multiple Values, Integer Arithmetic, Iterations, Top
@section Multiple Values

The multiple values mechanism covers (simply and elegantly, in my
opinion) various common needs:

@enumerate
@item
The case where a function returns a composite value, that has to be
assembled in the callee and disassembled in the caller.  An example is
@code{pair-with-newsyms}.
@item
The case where a function might cheaply compute redundant information
that is useful to the caller only eventually.  For instance, routines
that compute quotients and remainders together, whose callers might be
more often interested in just receiving the quotient.
@item
The case of functions that usually return a useful value, but might need
to elaborate on occasion (say, returning a reason code too).
@end enumerate

The general idea is that one such function @i{always} returns the extra
values, but only callers that are aware of this ability receive them.
Unaware callers just receive the first value.

I think my implementation is pretty much complete.  I am imposing no
limits on the number of multiple values a function may return, so
I am not providing the constant @code{multiple-values-limit}.  You can
assume multiple values are bound by the memory 
size only. @refill

@subsection Features Provided

@table @code
@item values
@itemx values-list
These are the forms that produce multiple values.

@item MACRO multiple-value-bind
@itemx MACRO multiple-value-call
@itemx MACRO multiple-value-list
@itemx MACRO multiple-value-prog1
@itemx MACRO multiple-value-setq
These are the forms that receive multiple values.

@item VARIABLE *mvalues-count*
@itemx VARIABLE *mvalues-values*
Used by the implementation.  Don't touch them!

@end table

@node Integer Arithmetic, Generalized Variables, Multiple Values, Top
@section Integer Arithmetic

I have provided most of the functions that are supposed to act on
integers.  Of those that take arbitrary numbers, I have implemented
those that have a reasonable implementation if restricted to integers
only, although some more could be added (like a restricted form of
@code{expt}).

Being a little worried about the bad fame that affects some
implementations of the '%' C operator, I have taken perhaps unnecessary
precautions whenever integer division is concerned (see the function
@code{safe-idiv}).  This should be of interest only when dividing
numbers that might be negative, but I have preferred here to be safe
rather than fast.  @refill

@subsection Features Provided

@table @code
@item abs
@itemx signum
The usual.

@item gcd
@itemx lcm
The usual.

@item isqrt
A rather annoying function.  Only use I can think of: to cut short a
prime number sieve.

@item evenp
@itemx oddp
@itemx plusp
@itemx minusp
A few predicates that use to come handy.

@item ceiling
@itemx floor
@itemx round
@itemx truncate
@itemx mod
@itemx rem
The intention is to give everybody his preferred way to divide integers.
I have tried not to depend on the unreliable semantics of C's integer
division, I hope I got it right.  Read the code when in doubt.

@end table

@node Generalized Variables, Structures, Integer Arithmetic, Top
@section Generalized Variables

This implementation has many limitations.  Take a look to see if you
want to overcome them, the fixes might prove unnecessarily expensive for
Emacs purposes.  The ones I am clearly aware of:

@enumerate
@item
Common Lisp suggests an underlying mechanism (the setf-methods) to
implement generalized variables.  I have used ad-hoc ideas that gave me
a rather trivial implementation 
that suffers from some inflexibility.  As a result, @code{defsetf}
only admits the simplest form and there is no @code{define-modify-macro}
nor there are functions to handle the (nonexistent) setf-methods. @refill
@item
I haven't implemented (I was uninterested) @code{getf} and friends.
This shouldn't be hard.
@end enumerate

In addition to providing this mechanism, I have written @code{defsetf}s
for almost every accessor I thought of.  There is room for improvement
here, as Emacs Lisp provides many types of its own (buffers, windows,
keymaps, syntax tables, @dots{}) for which pairs of accessors and
mutators could be defined.

If you want to check whether a function has a setf-inversor, look at the
property `:setf-update-fn' of its name.  This is a characteristic of my
implementation, not mandated by Common Lisp, so you
shouldn't use it in code, but only to determine interactively what can
be setf'd.  @refill

@subsection Features Provided

@table @code
@item MACRO setf
@itemx MACRO psetf
Almost complete implementation.  @code{Setf} should handle @code{apply}
inside itself and not in a @code{defsetf}, but the difference is so
minute I feel lazy about fixing this. @code{Psetf} is the version where
the assignments occur in parallel. @refill

@item MACRO defsetf
Very sketchy implementation.  I will appreciate if somebody puts some
time in implementing the whole works of setf-methods and such.

@itemx MACRO incf
@itemx MACRO decf
The usual and standard.

@item MACRO pop
@itemx MACRO push
@itemx MACRO pushnew
Should be the usual, but I haven't had the time to test them properly. 

@item MACRO rotatef
@itemx MACRO shiftf
Very fancy.  Good for implementing history rings and such.
To swap two values, the following forms are equivalent:
@example
(rotatef a b)
(psetf a b b a)
(psetq a b b a)  ;not good for anything but variables
@end example

@end table

@node Structures, Miscellanea, Generalized Variables, Top
@section Structures

I haven't had the time to construct a complete implementation of
structures, but the part provided should stand on its own for many
purposes.  I am not supporting `BOA constructors', nor typed slots (the
@code{:type}, @code{:named} and @code{:initial-offset} options), nor
explicit representational types.  The rest should be
pretty much complete.  See the example file @file{fractions.el} for an
idea of how complete the implementation is, and for exercises. @refill

When writing these functions, I noticed I was incurring in lots of
auxiliaries.  I used dollar signs in their names, in the hope that this
could prevent clashes with user functions.  In retrospect, I should have
done it in the other sections, too.


@subsection Features Provided

@table @code
@item MACRO defstruct
Create records (a la C structs) and use them as types in your programs.
Almost completely standard.

@item make$structure$instance
This non-standard function implements most of the `guts' of the `make-'
constructors.  It can be used as an example of the pseudo
keyword-arguments.  
@end table

@node Miscellanea, To Do, Structures, Top
@section Miscellanea

@subsection Features Provided

@table @code
@item MACRO psetq
A parallel-assignments version of @code{setq}, makes the expansions of
@code{do} and @code{do*} be very similar, as they should.  Otherwise
used to swap two values, now superseded by @code{rotatef}. @refill

@item duplicate-symbols-p
@itemx pair-with-newsyms
@itemx reassemble-argslists
@itemx unzip-list
@itemx zip-lists
These are utilities I find useful when parsing a call or generating code
inside a macro.  Non standard.
@end table

@node To Do, , Miscellanea, Top
@section To Do

No doubt many people will like to extend the functionality of these
routines.  When considering doing so, please try and do it in such a way
that your implementation of a subset of the functionality of Common Lisp
is not inimical with a more extensive or more correct one.  For
definiteness, ask yourself the questions:

@itemize @bullet
@item
Will my code run under a correct implementation of Common Lisp?
@item
Will a correct implementation of Common Lisp run if my code is loaded?
@end itemize
@noindent

The first question tests the pertinence of your extensions.  The second
tries to discover ``extensions'' that prevent correct implementations of
other features.  Please tell me if you notice a case in which my code
fails to pass any of those tests.

The next subsections propose some more extensions.  I hope that they are
attempted by people learning Lisp, as a way to enhance their
understanding.  Of course, experts are also admitted. @refill

@subsection Keyword Arguments

Some effort has been done to handle keywords almost right.  For
instance, a structure constructor (@pxref{Structures}) can be invoked
with keyword arguments.

Look for the functions whose names have a @samp{klist} in them.  They
were written to facilitate parsing calls with keyword arguments, but I
haven't done a complete implementation yet.  (Note that @code{member},
@code{assoc} and perhaps some other function, have to be implemented
independently of the general framework.  More details by Email if you
want to try 
your hand at this.) @refill

@subsection Mapping Functions

There is enough support to write @code{maplist}, @code{mapl}, etc.  Emacs
Lisp already provides some of the mapping functions, the trick now is to
code the rest in a very efficient manner, so there will be an incentive
to use @code{maplist} over an explicit iteration.  I have a draft
implementation, but I don't have the time to test it now.

@subsection Complete the current implementation

Some of the features described above are only a partial implementation
of the Common Lisp features.  Things that cry for a more complete form:

@table @code
@item defsetf
Only the simplest format is supported.  The most general one is needed
too.  Also, try to get @code{define-setf-method} and
@code{get-setf-method} to work. @refill
@item define-modify-macro
Same as above.  The modify-macros provided are all ad hoc.
@item defstruct
I think my version recognizes all the options and then proceeds to
ignore most of them.  Making sure that at least good error messages are
produced would be nice.  Also, what about BOA constructors?
@end table

There are other places where your programming ingenuity would help us
all.  For instance, @code{subst}, @code{sublis} and the like could be
easily provided in the @var{lists} section.  (I haven't done it because
I wanted to have the keyword arguments stuff first.) @refill

@subsection Hash Tables

A very simple implementation of hash tables would admit only strings as
keys.  For each string and a given number of buckets (a prime is
desirable here), add the numeric values of all (or of a reasonable
subset) of the characters and assign the bucket whose index is the
remainder of the sum modulo the (prime) number of buckets.

A more convenient implementation can then be based on using
@code{prin1-to-string} on an arbitrary Lisp object and using the output
string as a key. This should make it easy to write @code{sxhash}.
Remember that one needs to ensure that @code{(equal x y)} should imply
that @w{@code{(= (sxhash x) (sxhash y))}}; and also that the keys are
state-less (so you can write them to a 
file and read them back later). @refill

Don't forget to provide a @code{defsetf} for @code{gethash}.

@subsection Packages

Packages should be easy to implement on top of a good hash table
implementation, either by using it directly or by reusing some shared
code.  Don't worry too much about efficiency: package qualification has
no run-time cost, only read- and print-time costs.

The difficult thing is to integrate it correctly.  You have to replace
the built-in functions @code{read} and @code{write}.  This is not as bad
as writing a programmable reader, but still a pain.  For starters, your
routines could remember the default definitions of the above mentioned
functions: @refill

@example
(setf def-reader  (symbol-function 'read))
(setf def-printer (symbol-function 'print))
@dots{}
@end example

And then your specialized functions could just use @code{apply} to
exercise the default ones, intercepting their activity in time to do the
package qualification.  You might have to do this to @code{prin1},
@code{prin1-to-string} and friends. @refill

@subsection Streams and Files

This is the first ``To Do'' that might require doing some C programming.
The purpose is to construct an efficient byte stream abstraction that
will allow Streams and Files to be handled.  Think of stdio, not Unix
I/O, because Emacs already runs under other operating systems.  Also,
think of doing it in a way that can be generalized easily (for instance,
streams kept in memory without a file behind, streams as an interface to
a windowing system, etc.)  Of course, the intended syntax is that of
Common Lisp.

@subsection Reader and Printer

The Emacs Lisp reader (the C function @code{Fread}) is not reentrant nor
programmable.  It could be fixed as Lisp Code, but that is probably
uglily expensive (as bad as redoing @code{eval} and @code{apply} to
support lexical scoping).  Doing this  extension is probably a bad
idea: a Common Lisp reader is incompatible with Emacs Lisp code (because
of the @samp{?\} constructions) and the most important rule to keep in
mind is that this code is running under Emacs, so the host shouldn't be
burdened too much with these emulations.  Same goes for a more complete
printer (a Common Lisp @code{format} would be incompatible with the
Emacs Lisp one). @refill

@subsection Backquote
Even if the reader is not made programmable nor reentrant, a backquoting
mechanism could come handy.  You need to study the way the current
reader does @code{quote} and hack from there.  This might be a more
worthwhile extension than the complete rewrite of the reader.

@subsection Wild Ideas
Perhaps there is a way to implement @code{block}, @code{tagbody},
@code{return} and friends in spite of the dynamic scoping of Emacs Lisp.
By this, I mean an adequate definition that preserves remotely the
original intent and still provides a sensible set of constructs.  Other
dynamically scoped Lisps have these features, so implementing them is
not necessarily impossible.

In the same spirit of these extensions would be to provide a port of
something like Flavors 
(was there a PD version from Maryland, for Franz perhaps?) and then
rephrase the language of major and minor modes in an Object Oriented
paradigm. @refill

Also, the rather gross @code{loop} macros that are out there in many
Lisp systems could be helpful to some
people (but then think of a @code{lisp-indent-hook} that handles them
properly). @refill

@bye