Frode Vatvedt Fjeld  <frodef@cs.uit.no> wrote:
+---------------
| "Javier" <javuchi@gmail.com> writes:
| > I'm actually not asking for "whose minimal set is better", but
| > instead "whose minimal set is NECESARY".
| 
| I would be surprised if it's possible to deduce a canonical such set.
+---------------

Especially given the fact that which special forms are "necessary"
is pretty much an open choice a.k.a. implementation tradeoff, as
Henry Baker's 1992 "ACM Lisp Pointers" paper shows:

    http://home.pipeline.com/~hbaker1/MetaCircular.html
    Metacircular Semantics for Common Lisp Special Forms
    ...
    In the following sections, we will develop a series of definitions
    of various Common Lisp special forms in terms of one another. While
    these definitions, by themselves, will not pin down the semantics
    of Common Lisp completely, they can be used in conjunction with a
    rough understanding of Common Lisp semantics to understand the less
    usual cases of interactions of the various features.
    ...
    In short, the choice of which "macros" are "special forms" is just
    as arbitrary as the choice of a axes in a coordinate system for
    the Cartesian X-Y plane--e.g., some sets of macros are "linearly
    independent", and some sets of macros "span" the space of special
    forms.
    ...

IMHO this paper is *required* reading for anyone brave/foolish enough
to attempt a "subset" Common Lisp [such as yours truly -- see below].
And even it doesn't do nearly a complete job -- it just points the
reader at the enormity of the available design space.

+---------------
| However I think it could be a neat (community) project to define
| one (or perhaps a couple of) such package(s).
+---------------

As it happens, I am part way through doing such a "quick & dirty
Lisp" (QDL) Common Lisp subset myself [because I need one in a
place where CMUCL can't (yet) run], and I can attest that Kent
Pitman's concerns about excessive minimalism leading to dead ends
which preclude further progress towards full ANSI CL are quite
justified. I've had to essentially start over a couple of times
already, and it looks like I'm going to have to start all over
from the beginning once again, even though I already have a CL
subset that can execute FACT, FACT-ITER, and ACKERMANN!!
FWIW, the current oblist is quite short:

    (NIL T QUOTE LAMBDA PROGN IF SETQ DEFUN LET LET* PRINT PRINC
     TERPRI VECTOR FUNCALL APPLY EVAL CAR CDR CONS LIST LENGTH ASSOC
     1+ 1- + - * / = /= < > <= >=)

One of my personal goals for my QDL is that it meet the letter --
even if it bends the spirit a bit! -- of CLHS 1.7 "Language Subsets":

    For a language to be considered a subset, it must have the property
    that any valid program in that language has equivalent semantics
    and will run directly (with no extralingual pre-processing, and
    no special compatibility packages) in any conforming implementation
    of the full language.

Due to the normal default definition of the COMMON-LISP-USER package
(particularly, that it USEs the COMMON-LISP package), it turns out
that you can meet this with a subset so small that it has no packages,
no keywords, and only conses, fixnums, symbols, and strings (and
hence vectors) -- and still be somewhat useful for "scripting".

Of course, you have to specify that a "valid program in the language"
never overflows a fixnum, never divides two fixnums that would produce
a remainder, etc.!  ;-} ;-}

Anyway, I was just about to add TAGBODY (needed for DO, DO*, DOLIST,
DOTIMES, etc.) when I ran into one of those dead ends Kent warned about:

    ...you can write all the special forms and data constructors in C
    and then set about writing your library, only to find that it's
    hard to implement [something]...

So. Back to the drawing board.

[Aside to potential implementers: Looks like I probably have to add
a whole SECD-like virtual machine runtime, so I can do unwinding
"the right way". Ugh.]


-Rob

p.s. An interesting suggestion from Carl Shapiro is to make the
QDL VM run exactly the CMUCL compiled byte codes, which *are*
fairly platform-independent: only ~20 stack ops plus a few inline
function calls. The main obstacle to that is that the only easy way
to get *at* the compiled byte codes is to parse the CMUCL FASL file
format, which is a whole separate, different, interpreted byte code
of its own!! (*sigh*)

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607