What are the strictly minimun set of Lisp commands and/or keywords that
are needed to recreate a complete CL system?
I'd like to debate this here, and got some conclusions from you experts.
Javier wrote:
> What are the strictly minimun set of Lisp commands and/or keywords that
> are needed to recreate a complete CL system?
> I'd like to debate this here, and got some conclusions from you experts.
For example (wrong and/or incomplete):
NIL
T
QUOTE
SPECIAL
LET
SET
PROG
BACKQUOTE
VALUES
APPLY
CAR
CDR
<
/
*
+
-
PRINT
*STANDAR-INPUT*
*STANDAR-OUTPUT*
LOAD
IF
CONS
EQ
EQUAL
*PACKAGES*
LABELS
EVAL
ATOM
LISTP
It would be nice if we debate here what keywords would be necesary to
include, what not and can be obtained in other ways, etc.
Anyone would like to present his own list. Sorry if I'm not an expert
and cannot do better!!
Javier wrote:
> Javier wrote:
> > What are the strictly minimun set of Lisp commands and/or keywords that
> > are needed to recreate a complete CL system?
> > I'd like to debate this here, and got some conclusions from you experts.
>
> For example (wrong and/or incomplete):
>
> NIL
> T
> QUOTE
> SPECIAL
> LET
> SET
> PROG
> BACKQUOTE
> VALUES
> APPLY
> CAR
> CDR
> <
> /
> *
> +
> -
> PRINT
> *STANDAR-INPUT*
> *STANDAR-OUTPUT*
> LOAD
> IF
> CONS
> EQ
> EQUAL
> *PACKAGES*
> LABELS
> EVAL
> ATOM
> LISTP
READ
READ-CHAR
READ-BYTE
DESTRUCTURING-BIND ?
TAGBODY ?
DEFUN
PRINC
>
> It would be nice if we debate here what keywords would be necesary to
> include, what not and can be obtained in other ways, etc.
> Anyone would like to present his own list. Sorry if I'm not an expert
> and cannot do better!!
Your going to need "read" to read in the rest of the implementation.
"Read-char" is also necessary as far as I can tell. Print can't print
out any arbitrary string as far as I know, so you need something more.
Destructuring-bind and the exception handling mechanism would also seem
necessary to me, but I'm not sure.
I think maybe you could do without lambda, but it would make things
rather evil if you did. I think it would be very hard to do everything
else without either defun or lambda.
I've seen the following from http://www.modeemi.fi/~chery/lisp500/
NIL
T
&REST
&BODY
&OPTIONAL
&KEY
&WHOLE
&ENVIRONMENT
&AUX
&ALLOW-OTHER-KEYS
DECLARE
SPECIAL
QUOTE
LET
LET*
FLET
LABELS
MACROLET
SYMBOL-MACROLET
SETQ
FUNCTION
TAGBODY
GO
BLOCK
RETURN-FROM
CATCH
THROW
UNWIND-PROTECT
IF
MULTIPLE-VALUE-CALL
MULTIPLE-VALUE-PROG1
PROGN
PROGV
DPB
LDB
LIST
VALUES
FUNCALL
APPLY
EQ
CONS
CAR
CDR
=
<
+
-
*
/
HASH
GENSYM
STRING
PRINT
GC
FLOOR
LOAD
LAMBDA
CODE-CHAR
CHAR-CODE
*STANDARD-INPUT*
*STANDARD-OUTPUT*
*ERROR-OUTPUT*
*PACKAGES*
STRING=
EVAL
RUN-PROGRAM
UNAME
But it got also a series of keywords wich are not part of common lisp,
which are:
FINISH-FILE-STREAM
MAKEI
BACKQUOTE
UNQUOTE
UNQUOTE-SPLICING
IBOUNDP
LISTEN-FILE-STREAM
MAKE-FILE-STREAM
IERROR
FASL
MAKEJ
MAKEF
FREF
CLOSE-FILE-STREAM
IVAL
READ-FILE-STREAM
WRITE-FILE-STREAM
IMAKUNBOUND
JREF
IREF
It would be interesting if we comment out this list, add or remove
words which are needed/not needed.
"Javier" <·······@gmail.com> writes:
> I've seen the following from http://www.modeemi.fi/~chery/lisp500/
Well, this is a good start. It's indeed better to start from an
implementation, and see what subset of Common Lisp is needed to write
it.
> [...]
> But it got also a series of keywords wich are not part of common lisp,
> which are:
>
> FINISH-FILE-STREAM
> MAKEI
> BACKQUOTE
> UNQUOTE
> UNQUOTE-SPLICING
This have already been expressed, but perhaps not too explicitely.
You don't need only to list symbol names, but actually "features" of
the language you want to use to implement CL.
For example, listing LAMBDA or LET would be meaningless without
mentionning the wanted semantic properties (eg. lexical scoping,
closure creation, etc).
In the case of BACKQUOTE, UNQUOTE and UNQUOTE-SPLICING, this is an
"unnamed", but specified feature of the lisp reader default readtable,
which implement ` , and ,@ as reader macros (that may translate to
normal macros named BACKQUOTE, UNQUOTE and UNQUOTE-SPLICING).
> It would be interesting if we comment out this list, add or remove
> words which are needed/not needed.
Depends on your implementation. If you can easily implement Common
Lisp with the given set, then it's OK. If it would greatly simplify
your work as an implementor to add another feature to your preCL
language, they you could choose to do so.
--
__Pascal Bourguignon__ http://www.informatimago.com/
COMPONENT EQUIVALENCY NOTICE: The subatomic particles (electrons,
protons, etc.) comprising this product are exactly the same in every
measurable respect as those used in the products of other
manufacturers, and no claim to the contrary may legitimately be
expressed or implied.
Pascal Bourguignon wrote:
> "Javier" <·······@gmail.com> writes:
>
> > I've seen the following from http://www.modeemi.fi/~chery/lisp500/
>
> Well, this is a good start. It's indeed better to start from an
> implementation, and see what subset of Common Lisp is needed to write
> it.
>
>
> > [...]
> > But it got also a series of keywords wich are not part of common lisp,
> > which are:
> >
> > FINISH-FILE-STREAM
> > MAKEI
> > BACKQUOTE
> > UNQUOTE
> > UNQUOTE-SPLICING
>
> This have already been expressed, but perhaps not too explicitely.
>
> You don't need only to list symbol names, but actually "features" of
> the language you want to use to implement CL.
>
> For example, listing LAMBDA or LET would be meaningless without
> mentionning the wanted semantic properties (eg. lexical scoping,
> closure creation, etc).
>
> In the case of BACKQUOTE, UNQUOTE and UNQUOTE-SPLICING, this is an
> "unnamed", but specified feature of the lisp reader default readtable,
> which implement ` , and ,@ as reader macros (that may translate to
> normal macros named BACKQUOTE, UNQUOTE and UNQUOTE-SPLICING).
Can't these be implemented in Lisp then hooked into the readtable at
startup?
Backticks in Emacs Lisp - which is not the same as CL by any means - is
an elisp function.
From: Kent M Pitman
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <uu05xccbm.fsf@nhplace.com>
"Javier" <·······@gmail.com> writes:
> TAGBODY
> GO
> BLOCK
> RETURN-FROM
> CATCH
> THROW
You only need one of these three pairs as long as you have various other
operators that you'll find you need for other reasons.
From: Ari Johnson
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <m23bdhs2m5.fsf@hermes.theari.com>
"Javier" <·······@gmail.com> writes:
> Javier wrote:
>> What are the strictly minimun set of Lisp commands and/or keywords that
>> are needed to recreate a complete CL system?
>> I'd like to debate this here, and got some conclusions from you experts.
>
> For example (wrong and/or incomplete):
>
> NIL
> T
> QUOTE
> SPECIAL
> LET
> SET
> PROG
> BACKQUOTE
> VALUES
> APPLY
> CAR
> CDR
> <
> /
> *
> +
> -
> PRINT
> *STANDAR-INPUT*
> *STANDAR-OUTPUT*
> LOAD
> IF
> CONS
> EQ
> EQUAL
> *PACKAGES*
> LABELS
> EVAL
> ATOM
> LISTP
>
> It would be nice if we debate here what keywords would be necesary to
> include, what not and can be obtained in other ways, etc.
> Anyone would like to present his own list. Sorry if I'm not an expert
> and cannot do better!!
You won't go far without some way to get DEFMACRO. You also probably
just forgot to include LAMBDA. EVAL can be implemented in lisp quite
easily. TAGBODY and GO probably cannot be implemented in terms of the
list you have here. INTERN would be nice to have. And PROG (in any
of its forms) is unnecessary if you have LET. For instance:
(defmacro prog1 (form1 &body forms)
(let ((s (gensym)))
`(let ((,s ,form1)) ,@forms ,s)))
"Javier" <·······@gmail.com> writes:
> Javier wrote:
>> What are the strictly minimun set of Lisp commands and/or keywords that
>> are needed to recreate a complete CL system?
>> I'd like to debate this here, and got some conclusions from you experts.
>
> For example (wrong and/or incomplete):
>
> NIL
> T
> QUOTE
> SPECIAL
> LET
> SET
> PROG
> BACKQUOTE
> VALUES
> APPLY
> CAR
> CDR
> <
> /
> *
> +
> -
> PRINT
> *STANDARD-INPUT*
> *STANDARD-OUTPUT*
> LOAD
> IF
> CONS
> EQ
> EQUAL
> *PACKAGES*
> LABELS
> EVAL
> ATOM
> LISTP
>
> It would be nice if we debate here what keywords would be necesary to
> include, what not and can be obtained in other ways, etc.
> Anyone would like to present his own list. Sorry if I'm not an expert
> and cannot do better!!
Ok. Now, how do you read a lisp form?
How do you intern a symbol (notably, the symbols you've specified)?
Now, if you don't like LAMBDA, (read again Kent's followup; but we
don't really need to implement a physical universe, we can just
simulate I/O), another solution is to consider that existing Lisp
implementation work on Von Neuman computers, so you only need what is
needed to implement a Von Neuman computer.
MAKE-ARRAY, AREF, (SETF AREF), DEFPARAMETER, to make the memory,
(a simple version of MAKE-ARRAY, to build a simple vector of bytes).
If you prefer, you could exchange DEFPARAMETER with LET, but LET is
more complex (equivalent to LAMBDA).
LOOP, CASE, LOGAND, LOGNOT, to implement the ALU (of course, you could
replace LOGAND and LOGNOT by LOGXOR).
(the simple LOOP!)
I'd add: 1+ to get an efficient PC, otherwise you'd have to implement
it with LOGAND and LOGNOT...
+ one symbol to refer the memory vector.
Note that some of these symbols from COMMON-LISP refer to functions or
macros that are more complex than what is really needed. For example,
we don't need a full SETF, only something like:
(ASET vector index value), but this primitive is hidden behind the high
level facility (SETF AREF) in Common Lisp.
--
__Pascal Bourguignon__ http://www.informatimago.com/
ATTENTION: Despite any other listing of product contents found
herein, the consumer is advised that, in actuality, this product
consists of 99.9999999999% empty space.
From: Zach Beane
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <m3wtatig46.fsf@unnamed.xach.com>
"Javier" <·······@gmail.com> writes:
> What are the strictly minimun set of Lisp commands and/or keywords that
> are needed to recreate a complete CL system?
> I'd like to debate this here, and got some conclusions from you experts.
Whatever other people say, I assert no CL system is complete if it
lacks:
SYMBOLICATE, KEYWORDICATE, LOGICAL-CHUNKIFY, BACKQUOTIFY,
SYMBOL-LISTIFY, HEAPIFY, PRIMIFY, CONSIFY
I would be willing to negotiate on KEYWORDIFY.
Zach
From: Ari Johnson
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <m21wt1to0i.fsf@hermes.theari.com>
"Javier" <·······@gmail.com> writes:
> What are the strictly minimun set of Lisp commands and/or keywords that
> are needed to recreate a complete CL system?
> I'd like to debate this here, and got some conclusions from you experts.
Common Lisp is an ANSI-standardized language. The minimum set of
"commands and/or keywords" required to recreate a complete CL system
is specified in the standard.
If you are talking about a lisp other than Common Lisp, though, that's
different; and the minimum set of operators needed to be complete
depends on what you want to do with it.
Ari Johnson wrote:
> "Javier" <·······@gmail.com> writes:
>
> > What are the strictly minimun set of Lisp commands and/or keywords that
> > are needed to recreate a complete CL system?
> > I'd like to debate this here, and got some conclusions from you experts.
>
> Common Lisp is an ANSI-standardized language. The minimum set of
> "commands and/or keywords" required to recreate a complete CL system
> is specified in the standard.
>
> If you are talking about a lisp other than Common Lisp, though, that's
> different; and the minimum set of operators needed to be complete
> depends on what you want to do with it.
I think what the OP means is "what set of keywords are necessary so
that the rest of the language can be constructed only in lisp". I.e.
what does a minimal interpreter need to support.
Rob Thorpe wrote:
> I think what the OP means is "what set of keywords are necessary so
> that the rest of the language can be constructed only in lisp". I.e.
> what does a minimal interpreter need to support.
Yes, sorry, that's exactly what I mean, with one appreciation: not only
a Lisp dialect, but a complete CL system, and I don't worry about
performance here.
From: Kent M Pitman
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <usllhqre1.fsf@nhplace.com>
"Rob Thorpe" <·············@antenova.com> writes:
> Ari Johnson wrote:
> > "Javier" <·······@gmail.com> writes:
> >
> > > What are the strictly minimun set of Lisp commands and/or keywords that
> > > are needed to recreate a complete CL system?
> > > I'd like to debate this here, and got some conclusions from you experts.
> >
> > Common Lisp is an ANSI-standardized language. The minimum set of
> > "commands and/or keywords" required to recreate a complete CL system
> > is specified in the standard.
> >
> > If you are talking about a lisp other than Common Lisp, though, that's
> > different; and the minimum set of operators needed to be complete
> > depends on what you want to do with it.
>
> I think what the OP means is "what set of keywords are necessary so
> that the rest of the language can be constructed only in lisp". I.e.
> what does a minimal interpreter need to support.
That sounded like what was wanted to me, too, and Javier should clarify.
But I'm going to go out on a limb and speculate not to put words in his
mouth but because I have time to reply now and might not have time later.
Perhaps I will turn out to be commenting on the wrong issues; c'est la
vie.
The question seems to presuppose an agenda.
Almost all Lisp systems are bootstrapped in this way--by having a
kernel of non-Lisp and then writing the rest in Lisp. But I doubt
those implementations agree.
So the question then becomes "whose minimal set is better"?
"Better" is not a predicate with a canonical solution. It must be assumed
that there is a goal, and betterness must be evaluated with respect of the
goal to be achieved.
It's possible Javier thinks Lisps are written in C++ or Java or VB all the
way down and that they just execute Lisp as an end-goal. In that case,
it's just a misconception.
It's possible he thinks the reason there isn't more Lisp availability
is that our community lack s central implementation, as some languages
these days seem to have, where people can write once and run
everywhere as long as there's a minimal amount of support. But if
many implementations already constructed using that architecture
didn't yield that result, it's unlikely that reducing the number would.
The worry I'm left with is that he thinks the world would be better with
fewer choices. For example, that it would be better to have only one
Lisp that ran everywhere and then there would be no standards issue.
Instead, you'd define the language to be what the implementation did.
This would be a disaster for specification, because it would mean that the
users would be at the mercy of the implementors, with no objective test of
goodness.
This would also pessimize Lisp's perception in the world because for
those things the canonical implementation got wrong, there would be no
way to fix it. Any given implementation can optimize only certain
things, at the expense of others. The nature of optimization is that.
An implementation cannot "optimize all things". Optimizations are
trade-offs. Some users can use Lisp only because the given
implementation the use makes speed/space/safety trade-offs that are
appropriate to them but not to others. The language is designed to
permit this kind of trade-off, yet to still be relatively portable.
There is already a tendancy of users to take advantage of more things in
their implementation than the spec allows. Users try things and assume
that what works for them at that moment is constrained to work. That's
a bad assumption already but is compounded if they think they are using
the "canonical implementation" because they think they can trust it to
port both to other implementations and to future releases of the current
implementation. And, worse, the implementor never gets feedback about
what the user relied upon. Specifications are not a panacea, they are a
choice, and one of the positives of that choice is that it's made explicit
what people can and can't rely upon, so implementors know what part is
left to them "to play with".
So I don't understand the virtue of discussing a "minimal set". I would
think the "minimal interesting replacement question" (heh) would be
"What is an example of the set of primitives that some implementation
chose and was usefully able to bootstrap the rest of CL from."
Even there, though, Zach Beane's implicit observation in his reply about
SYMBOLICATE, BACKQUOTIFY, HEAPIFY, and the like is important not for the
specific operators it provides but becuase it reminds us of several things:
- some implementations may put all objects on the heap, some may
do stack allocation. that's a choice point. it's easier to be
more minimal with no stack allocation, but it pessimizes
implementations.
- a kernel lisp involves more than a linguistic kernel. 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 OPEN.
some "library" support has invoke magic, and the question then becomes
whether your "magic" will do only what CL wants and nothing more
(pretty limiting) or whether you'll provide a ANSI CL-compatible superset.
if you start down the path of minimalism, you'll end up precluding the
many ANSI CL-compatible supersets. indeed, you might even not be able
to implement the MOP, because you'll get mired in a question of whether
the MOP's presence adds or removes minimalness. It will depend on your
simplicity metric how you resolve that.
- CL was designed to permit implementations on strange systems you
may never use. like a CDC 7600 or a Honeywell Multics or a
Symbolics 3600. Does a "minimal set" support all implementations or
only the one on which the experiment is run? Does it ignore operating
and file systems that are unfamiliar, preferring to pretend that the
language was not designed to support them in order to improve the "look"
of minimalness.
- And when you're done, what does all of this buy you other ... other than
articial conflict?
The entire Eulisp effort, years ago, seemed to me (from the outside
looking in) to get seriously derailed on the issue of "core language"
because half the implementors I talked with insisted that the core
language was a subset of the language which would be visible in the
superset, and the other half of them thought it was an implementation
substrate that would be covered over in the outcome. They probably
worked that out in the end, but the fact that this confusion seemed to
me to persist over a long period of time among thoughtful people seemed
to me to imply it was a potential rat's nest that might do well to be
avoided.
Kent M Pitman wrote:
> "Rob Thorpe" <·············@antenova.com> writes:
> > Ari Johnson wrote:
> > > "Javier" <·······@gmail.com> writes:
> > >
> > > > What are the strictly minimun set of Lisp commands and/or keywords that
> > > > are needed to recreate a complete CL system?
> > > > I'd like to debate this here, and got some conclusions from you experts.
> > >
> > > Common Lisp is an ANSI-standardized language. The minimum set of
> > > "commands and/or keywords" required to recreate a complete CL system
> > > is specified in the standard.
> > >
> > > If you are talking about a lisp other than Common Lisp, though, that's
> > > different; and the minimum set of operators needed to be complete
> > > depends on what you want to do with it.
> >
> > I think what the OP means is "what set of keywords are necessary so
> > that the rest of the language can be constructed only in lisp". I.e.
> > what does a minimal interpreter need to support.
>
> That sounded like what was wanted to me, too, and Javier should clarify.
>
> But I'm going to go out on a limb and speculate not to put words in his
> mouth but because I have time to reply now and might not have time later.
> Perhaps I will turn out to be commenting on the wrong issues; c'est la
> vie.
>
> The question seems to presuppose an agenda.
>
> Almost all Lisp systems are bootstrapped in this way--by having a
> kernel of non-Lisp and then writing the rest in Lisp. But I doubt
> those implementations agree.
>
> So the question then becomes "whose minimal set is better"?
>
> "Better" is not a predicate with a canonical solution. It must be assumed
> that there is a goal, and betterness must be evaluated with respect of the
> goal to be achieved.
I think that I would be interested to know a few of the minimal sets.
The point is that if you can implement the minimal set then the rest is
just lisp, which is likely to be much less complex than a compiler or
interpreter.
It would be a useful thing for an implementor to know writing a
compiler. The compiler need initially implement only the minimum set,
with the rest in lisp. It could then compile itself and optimization
could be done to remove the inefficient constructs by expanding the set
of basic operations.
> It's possible Javier thinks Lisps are written in C++ or Java or VB all the
> way down and that they just execute Lisp as an end-goal. In that case,
> it's just a misconception.
>
> It's possible he thinks the reason there isn't more Lisp availability
> is that our community lack s central implementation, as some languages
> these days seem to have, where people can write once and run
> everywhere as long as there's a minimal amount of support. But if
> many implementations already constructed using that architecture
> didn't yield that result, it's unlikely that reducing the number would.
>
> The worry I'm left with is that he thinks the world would be better with
> fewer choices. For example, that it would be better to have only one
> Lisp that ran everywhere and then there would be no standards issue.
> Instead, you'd define the language to be what the implementation did.
>
> This would be a disaster for specification, because it would mean that the
> users would be at the mercy of the implementors, with no objective test of
> goodness.
I agree with that mostly. But I find Common Lisp irritating as it is
because of the lack of standardisation of many things. The problem is
not the number of implementations, or the existance of standardisation,
the problem is that further standardisation has stopped.
Languages that have a central implementation have a large advantage
right now because their implementors can add to the language at will
and solve many problems that would be very difficult to solve by
specification. I imagine this will continue for years to come. But it
won't last for ever, eventually implementors will have differing
opinions and multiple implementations will arise. When this happens
they will need standardisation. I expect that until then their
adoption rates will continue to increase.
Anyway, I'm drifting of-topic.
> This would also pessimize Lisp's perception in the world because for
> those things the canonical implementation got wrong, there would be no
> way to fix it. Any given implementation can optimize only certain
> things, at the expense of others. The nature of optimization is that.
> An implementation cannot "optimize all things". Optimizations are
> trade-offs. Some users can use Lisp only because the given
> implementation the use makes speed/space/safety trade-offs that are
> appropriate to them but not to others. The language is designed to
> permit this kind of trade-off, yet to still be relatively portable.
>
> There is already a tendancy of users to take advantage of more things in
> their implementation than the spec allows. Users try things and assume
> that what works for them at that moment is constrained to work. That's
> a bad assumption already but is compounded if they think they are using
> the "canonical implementation" because they think they can trust it to
> port both to other implementations and to future releases of the current
> implementation. And, worse, the implementor never gets feedback about
> what the user relied upon. Specifications are not a panacea, they are a
> choice, and one of the positives of that choice is that it's made explicit
> what people can and can't rely upon, so implementors know what part is
> left to them "to play with".
>
> So I don't understand the virtue of discussing a "minimal set". I would
> think the "minimal interesting replacement question" (heh) would be
> "What is an example of the set of primitives that some implementation
> chose and was usefully able to bootstrap the rest of CL from."
That would be interesting. I think the minimal set may be interesting
from another perspective... At present CL is specified in the CLHS, but
many implementations don't really follow the specification. It may be
useful to write an minimally simple CL interpreter, then work to ensure
that it follows the spec exactly. Without optimization something like
this could be very simple. Then the interpreter could be used for
testing how close some practical implementation is to meeting the spec
by comparing the output of programs fed to each.
There would be bugs in the minimal interpreter of-course, the challenge
in this strategy would be to see if they could be made sufficient few
than those in real implementations to make it useful.
> The entire Eulisp effort, years ago, seemed to me (from the outside
> looking in) to get seriously derailed on the issue of "core language"
> because half the implementors I talked with insisted that the core
> language was a subset of the language which would be visible in the
> superset, and the other half of them thought it was an implementation
> substrate that would be covered over in the outcome. They probably
> worked that out in the end, but the fact that this confusion seemed to
> me to persist over a long period of time among thoughtful people seemed
> to me to imply it was a potential rat's nest that might do well to be
> avoided.
Yes, these are two very different minimal sets. The "substrate that is
covered" set could be more or less a bytecode interpreter for example.
As such it might be possible to make it work with absurdly few
instructions, maybe 1.
From: Don Geddis
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <8764iccad4.fsf@geddis.org>
"Rob Thorpe" <·············@antenova.com> wrote on 4 Jul 2006 09:49:
> At present CL is specified in the CLHS, but many implementations don't
> really follow the specification.
Really? Which ones did you have in mind?
All the "Common Lisp" implementations that I know, make the claim that they
"purport to comform" to the spec. Which means that they might have differences
in operation from the spec, but they acknowledge that any differences are
bugs in their implementation which they intend to eventually fix.
The way you describe it, the spec is an obsolete document, and every
implementation is just doing their own thing. That's far from reality.
Code written in portable Common Lisp really does seem to Just Work across
implementations.
I'm thinking here of SBCL, CMUCL, Allegro CL, Lispworks, OpenMCL, etc.
Can you be more specific with your criticism?
> It may be useful to write an minimally simple CL interpreter, then work to
> ensure that it follows the spec exactly. Without optimization something
> like this could be very simple. Then the interpreter could be used for
> testing how close some practical implementation is to meeting the spec by
> comparing the output of programs fed to each.
This would be a useless effort, for three reasons:
1. The existing implementations already are very very close to following
the spec "exactly" (modulo remaining bugs).
2. Even if you had the implementation you suggest, you'd still need the
sample programs to run, in order to compare output. I.e., a test suite.
3. But once you have a test suite, with the known correct output ... then you
don't even need the standard implementation! Just run the test suite itself.
And, as it turns out, the Gnu CL folks are well on their way to developing
just such a cross-implementation test suite.
So your problem is solved, apparently.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
The poor wish to be rich, the rich wish to be happy, the single wish to be
married, and the married wish to be dead. -- Ann Landers (1918-2002)
Don Geddis wrote:
> "Rob Thorpe" <·············@antenova.com> wrote on 4 Jul 2006 09:49:
> > At present CL is specified in the CLHS, but many implementations don't
> > really follow the specification.
>
> Really? Which ones did you have in mind?
>
> All the "Common Lisp" implementations that I know, make the claim that they
> "purport to comform" to the spec. Which means that they might have differences
> in operation from the spec, but they acknowledge that any differences are
> bugs in their implementation which they intend to eventually fix.
>
> The way you describe it, the spec is an obsolete document, and every
> implementation is just doing their own thing. That's far from reality.
> Code written in portable Common Lisp really does seem to Just Work across
> implementations.
>
> I'm thinking here of SBCL, CMUCL, Allegro CL, Lispworks, OpenMCL, etc.
>
> Can you be more specific with your criticism?
I didn't intend to imply that every implementation is doing there own
thing. What I intended to imply is what I think we both agree on, that
their are bugs and incompleteness in lisp implementations.
> > It may be useful to write an minimally simple CL interpreter, then work to
> > ensure that it follows the spec exactly. Without optimization something
> > like this could be very simple. Then the interpreter could be used for
> > testing how close some practical implementation is to meeting the spec by
> > comparing the output of programs fed to each.
>
> This would be a useless effort, for three reasons:
>
> 1. The existing implementations already are very very close to following
> the spec "exactly" (modulo remaining bugs).
I don't know about the commercial ones, I've only used the free ones.
Most of the free ones I've used have comments in their documentation
remarking on quite a few deviations from the spec.
> 2. Even if you had the implementation you suggest, you'd still need the
> sample programs to run, in order to compare output. I.e., a test suite.
Yes.
> 3. But once you have a test suite, with the known correct output ... then you
> don't even need the standard implementation! Just run the test suite itself.
> And, as it turns out, the Gnu CL folks are well on their way to developing
> just such a cross-implementation test suite.
The problem is knowing the correct output from the spec. It isn't
always clear.
Once a test is written if all implementations pass it it doesn't mean
they're correct if they do not obey the spec. Equally if they all
behave differently it may not be incorrect if the spec does not define
the behaviour.
> So your problem is solved, apparently.
Maybe yes. I'll admit I haven't looked into this in great detail.
I work in communications though, where huge paper specs have been
constructed for telecoms systems. Despite massive validation efforts
the first time systems from different vendors are plugged together they
practically never work. This happened with Bluetooth, WCDMA and is
still happening especially with WLAN. Everyone ends up basing real
implementations on a mixture of the spec and other peoples
interpretations of it given by the behaviour or their devices
This is why Alan Kay proposed specifying languages with a reference
implementation, and why others have done it using formal semantic (for
example R5RS Scheme).
I think Paul Dietz who is writing the portable test library is the only
person who would know one way or the other whether this would be
useful.
From: Don Geddis
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <87ac7m7khd.fsf@geddis.org>
"Rob Thorpe" <·············@antenova.com> wrote on 5 Jul 2006 09:55:
> I didn't intend to imply that every implementation is doing there own
> thing. What I intended to imply is what I think we both agree on, that
> their are bugs and incompleteness in lisp implementations.
Yet they all attempt to conform to the spec. So it's clearly a hard problem
to eliminate every bug from implementing such a large spec.
How would this become easier by starting a brand new project to produce yet
another ("reference") implementation? Why do you think all the bugs would be
eliminated in that new implementation? Surely it's easier to start with one
of the existing ones that is 99.99% complete, and just fix the last remaining
bugs.
> I don't know about the commercial ones, I've only used the free ones.
> Most of the free ones I've used have comments in their documentation
> remarking on quite a few deviations from the spec.
"Quite a few" is overstating the case. The spec is huge, and the amount of
detail can be overwhelming. The implementations are trying to be complete, and
record every known difference. Most of the remaining ones don't matter to any
typical real program, so they're lower on the priority list.
But I bet, without cheating and looking at the lists themselves, you'd be hard
pressed to generate a portable CL program yourself that demonstrates a spec
violation in one of the implementations.
> The problem is knowing the correct output from the spec. It isn't
> always clear.
That's a matter of reading comprehension, not a matter of having a reference
implementation. (I'm not saying it's easy: the process of writing a spec,
reading it carefully, and implementing it is enormously complex, and not a
task for everyone.)
In fact, an English spec is far better than a reference implementation, because
an implementation often has to make arbitrary choices. If you run some code,
and it has some output, how do you know whether that MUST be the output of
every implementation, or whether that is merely one of a set of permissible
outputs?
There's no way around needing to read and understand the spec.
> Once a test is written if all implementations pass it it doesn't mean
> they're correct if they do not obey the spec. Equally if they all
> behave differently it may not be incorrect if the spec does not define
> the behaviour.
Well, the test suite can have errors itself, but that's the point of the
test suite, isn't it? It's supposed to test what the spec says that an
implementation MUST do. Including if it allows different behavior.
> This is why Alan Kay proposed specifying languages with a reference
> implementation, and why others have done it using formal semantic (for
> example R5RS Scheme).
None of this solves the problem that you think it solves.
Eventually it comes down to: you're a programmer, and you're writing
(portable) code, and you read the spec to see what you think you can rely on.
If the code fails in some implementation, then you have a complaint to the
vendor. The spec (or reference impl., or formal semantics) is the judge of
last resort about who needs to change code in the case of breakage: the
application programmer, or the implementation vendor.
But there is no way to guarantee ahead of time that breakage will never occur.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
The primary purpose of the Data statement is to give names to constants;
instead of referring to pi as 3.141592653589793 at every appearance, the
variable Pi can be given that value with a Data statement and used instead of
the longer form of the constant. This also simplifies modifying the program,
should the value of pi change.
-- Fortran manual for Xerox Computers
For Kent M Pitman:
I'm actually not asking for "whose minimal set is better", but instead
"whose minimal set is NECESARY".
The goal here is not for real world, in wich performance and
optimization is a must. I'm just talking in a theorical situation.
And I don't think that the world would be better with fewer choices...
just, that wasn't my question and not the direction in wich I made the
question we are debating here. ;)
From: Frode Vatvedt Fjeld
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <2h8xn9s29h.fsf@vserver.cs.uit.no>
"Javier" <·······@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. However I think it could be a neat (community) project to define
one (or perhaps a couple of) such package(s). And then to have
implementation(s) of the common-lisp package on top of that. (And then
some conformance testers on top of that..)
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
+---------------
| "Javier" <·······@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.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Don Geddis
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <871wt0ca1l.fsf@geddis.org>
"Javier" <·······@gmail.com> wrote on 4 Jul 2006 09:53:
> I'm actually not asking for "whose minimal set is better", but instead
> "whose minimal set is NECESARY".
So, why isn't just LAMBDA, as has been suggested to you, the answer to your
question?
> The goal here is not for real world, in wich performance and
> optimization is a must. I'm just talking in a theorical situation.
So, you don't care about performance.
Then you only need LAMBDA. Are you now satisfied with the answer?
If not, why not? Perhaps you have concerns that go beyond just the
THEORETICAL NECESSARY MINIMAL SET that you're claiming.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
I hope life isn't a big joke, because I don't get it.
-- Deep Thoughts, by Jack Handey [1999]
Don Geddis wrote:
> "Javier" <·······@gmail.com> wrote on 4 Jul 2006 09:53:
> > I'm actually not asking for "whose minimal set is better", but instead
> > "whose minimal set is NECESARY".
>
> So, why isn't just LAMBDA, as has been suggested to you, the answer to your
> question?
It is not really the minimum set since it does no I/O, as I mentioned
earlier.
So unless your prepared to speculate about implementing the whole
universe using lambda then you need a least one input and one output
operation.
Also I don't think you can really "build up" from Lambda. You could
implement a lisp compiler entirely with it and one input and output
operation. But you couldn't build an implementation that was built on
only lambda, you need some form of quoting and expansion of
expressions, as far as I can see.
> > The goal here is not for real world, in wich performance and
> > optimization is a must. I'm just talking in a theorical situation.
>
> So, you don't care about performance.
>
> Then you only need LAMBDA. Are you now satisfied with the answer?
>
> If not, why not? Perhaps you have concerns that go beyond just the
> THEORETICAL NECESSARY MINIMAL SET that you're claiming.
I don't think the OP really want that (even though that's what he
said). I think what the OP is looking for is the smallest set that
meets some very limited criteria of practicality. That was the sense I
answered the question in anyway.
Javier, is that correct?
It is interesting when learning lisp to understand what can be done in
the lisp layer. I remember when I learnt Emacs being impressed by the
number of things that seemed quite fundamental that were done in Lisp,
such as backticks. I found later that, Emacs isn't actually a great
example. I remember thinking later just how few operations would
actually be necessary in order to build up the rest. Whether there is
any real use in finding this "minimum set" is another matter. I can
certainly see uses for implementors in finding a practical
just-less-than minimum set they can use to build from.
From: Don Geddis
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <87ejwy7kym.fsf@geddis.org>
"Rob Thorpe" <·············@antenova.com> wrote on 5 Jul 2006 10:23:
> It is not really the minimum set since it does no I/O, as I mentioned
> earlier. So unless your prepared to speculate about implementing the whole
> universe using lambda
Why not implement the "whole universe" using lambda?
Of course it would be silly in practice, but so is the original question.
If you don't want "just LAMBDA" to be the answer, then you have to ask a
more precise question.
> I think what the OP is looking for is the smallest set that meets some very
> limited criteria of practicality. That was the sense I answered the
> question in anyway.
Yes, of course, but what we're doing here is a kind of Socratic method of
uncovering the answer. We're demonstrating that the original question isn't
a very good one, and suggesting that maybe even the OP's original motivations
are misplaced.
The truth, as many people have already said, is that there is no single unique
canonical "minimal" set of lisp "primitives".
There is the whole spec. It would be possible to implement each function
there directly in some other language (assembly, Fortran, etc.). It's also
possible to implement some small subset of them in another language (perhaps
C), and then the rest in Lisp itself. Pretty much all CL implementations do
this latter thing.
But it is somewhat arbitrary which operations you choose to put in the subset,
and which you choose to implement in Lisp. It is arbitrary for two reasons:
1. There are different possible "minimal" sets, rather than a single
canonical one. Much like you can implement any logical operation either
just using NAND gates, or else just using AND/OR/NOT gates. Either choice
is a fine basis for building up all logical operations.
2. Unlike this theoretical exercise, in practice you need to worry about
efficiency. So an implementation might "primitively" implement many different
functions, even if it is theoretically possible for some of them to be
defined in terms of others.
Conclusion? The theoretical question "what is the minimal subset of Lisp" is
either silly or malformed or useless. "Just LAMBDA" is one possible answer,
likely of only minor interest. It's actually hard to ask a precise question
that gives the kind of answer the OP thought he was looking for.
But what he thinks he's looking for isn't as interesting as he believes it is.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
Instead of trying to build newer and bigger weapons of destruction, mankind
should be thinking about getting more use out of the weapons we already have.
-- Deep Thoughts, by Jack Handey
Don Geddis <···@geddis.org> writes:
> "Rob Thorpe" <·············@antenova.com> wrote on 5 Jul 2006 10:23:
>> It is not really the minimum set since it does no I/O, as I mentioned
>> earlier. So unless your prepared to speculate about implementing the whole
>> universe using lambda
>
> Why not implement the "whole universe" using lambda?
>
> Of course it would be silly in practice, but so is the original question.
> If you don't want "just LAMBDA" to be the answer, then you have to ask a
> more precise question.
I believe that's how the universe's implemented, but we don't even
need to do it ourselves.
Just ask the electronicians to provide hardware implementing only this
one operator: LAMBDA.
Instead of storing bits in memory, you'll have only closures.
So now the question is how you do I/O in a Von Neuman computer? I/O
is not done by any microinstruction! It's done by the hardware, that
eventually presents the data as bit in memory (even if it's thru a I/O
"port", it's still basically a normal memory read/write).
On a lambda computer, the I/O hardware could present the data as
lambda closures, and this would be implemented by the electronicians,
not our problem.
Since you have to bootstrap the machine, you'll have one main function
called by the hardware at boot time. This function could be passed the
"I/O registers":
For example, this boot function in ROM:
(lambda (keyboard-in disk-in disk-out tty-out)
(tty-out (lambda (f) (lambda (x) x)) (lambda (f) (lambda (x) x)) (keyboard-in)))
would just read one character from the keyboard, and display it on the
tty at position 0,0, then shutdown the machine (assuming the tty-out
function expects numbers encoded as Church numerals, it could be more
practical to encode them in "binary").
> Conclusion? The theoretical question "what is the minimal subset of Lisp" is
> either silly or malformed or useless. "Just LAMBDA" is one possible answer,
> likely of only minor interest. It's actually hard to ask a precise question
> that gives the kind of answer the OP thought he was looking for.
>
> But what he thinks he's looking for isn't as interesting as he believes it is.
>
> -- Don
--
__Pascal Bourguignon__ http://www.informatimago.com/
"You can tell the Lisp programmers. They have pockets full of punch
cards with close parentheses on them." --> http://tinyurl.com/8ubpf
Don Geddis wrote:
> "Rob Thorpe" <·············@antenova.com> wrote on 5 Jul 2006 10:23:
> > It is not really the minimum set since it does no I/O, as I mentioned
> > earlier. So unless your prepared to speculate about implementing the whole
> > universe using lambda
>
> Why not implement the "whole universe" using lambda?
I don't think it's really in the spirit of computer science. When
discussing abstractions like minimal sets etc its useful to try to pick
meaningful ways of talking about them, rather than trying to pick ways
that deliberately reveal weaknesses in the question.
> Of course it would be silly in practice, but so is the original question.
> If you don't want "just LAMBDA" to be the answer, then you have to ask a
> more precise question.
Well if you mention something like Common Lisp which has I/O then
really you don't want that answer.
> > I think what the OP is looking for is the smallest set that meets some very
> > limited criteria of practicality. That was the sense I answered the
> > question in anyway.
>
> Yes, of course, but what we're doing here is a kind of Socratic method of
> uncovering the answer. We're demonstrating that the original question isn't
> a very good one
And not much of this has helped. The problem with Socratic examination
is that it irritates as much as it informs.
Almost every question asked is not a good one. People assume that
those they are asking can fill in the gaps. If we didn't ask questions
like this then it would be very difficult to communicate, we would have
to define everything precisely in discussion. It would be like
programming.
> and suggesting that maybe even the OP's original motivations
> are misplaced.
People did this on the basis of not really any evidence. The problem
was that the OP seemed to be talking about minimalism which is a
subject people are rather hostile to on c.l.l.
> The truth, as many people have already said, is that there is no single unique
> canonical "minimal" set of lisp "primitives".
>
> There is the whole spec. It would be possible to implement each function
> there directly in some other language (assembly, Fortran, etc.). It's also
> possible to implement some small subset of them in another language (perhaps
> C), and then the rest in Lisp itself. Pretty much all CL implementations do
> this latter thing.
>
> But it is somewhat arbitrary which operations you choose to put in the subset,
> and which you choose to implement in Lisp. It is arbitrary for two reasons:
>
> 1. There are different possible "minimal" sets, rather than a single
> canonical one. Much like you can implement any logical operation either
> just using NAND gates, or else just using AND/OR/NOT gates. Either choice
> is a fine basis for building up all logical operations.
Yes. I think that's clear.
> 2. Unlike this theoretical exercise, in practice you need to worry about
> efficiency. So an implementation might "primitively" implement many different
> functions, even if it is theoretically possible for some of them to be
> defined in terms of others.
Certainly. Or even define things that look "primitive" functions in
terms of more complex things that actually are.
> Conclusion? The theoretical question "what is the minimal subset of Lisp" is
> either silly or malformed or useless. "Just LAMBDA" is one possible answer,
> likely of only minor interest. It's actually hard to ask a precise question
> that gives the kind of answer the OP thought he was looking for.
Functions clearly fall into two categories though, setf could be useful
in a minimal set, stable-sort could not be that useful.
> But what he thinks he's looking for isn't as interesting as he believes it is.
I think it's of some interest. I mentioned some reasons it might be
interesting previously.
I thought of another one since. Lets say you want to implement CL on a
very small platform. So to do this you use slightly different
workflow, more like a C compiler. That is rather than dumping an image
you compile an executable, in that executable you need:
* All the user code put in
* All the code the user code calls
* All the code that code calls.
Solving this problem -or some nearby problem- could be much simpler if
you knew one of the possible small sets.
Rob Thorpe <·············@antenova.com> wrote:
+---------------
| Don Geddis wrote:
| > But what he thinks he's looking for isn't as interesting as he
| > believes it is.
|
| I think it's of some interest. I mentioned some reasons it might be
| interesting previously. I thought of another one since.... rather than
| dumping an image you compile an executable, in that executable you need:
| * All the user code put in
| * All the code the user code calls
| * All the code that code calls.
+---------------
There is already considerable literature on this; it's usually
called "tree shaking" -- as in, grab the root(s) of the specific
application's heap and shake it so that all of the branches
and leaves that are *not* called/referenced by that application
"fall out", leaving you with an image which is "minimal" FOR THAT
SPECIFIC APPLICATION. Some implementations provide a tree shaker
as a built-in; most don't.
+---------------
| Solving this problem -or some nearby problem- could be much
| simpler if you knew one of the possible small sets.
+---------------
I want to go back to the problem as originally stated, because I
think the discussion has seriously missed viewing the problem from
one very significant angle: In the case of Common Lisp at least, it
seems to me what's really important is not so much the minimal set
of special forms & functions per se [which, as I & others have noted,
isn't well-determined or unique in any event], but instead, the
question should be: What is the minimal set of *semantics* that a
"Common Lisp" run-time environment must provide before most users
would agree that the implementation was a useful subset [in the
sense of CLHS 1.7 "Language Subsets"].
In a previous comment in this thread, I mentioned that I've been
tinkering with my own "minimal CL subset", and that even though I
had a bunch of stuff working -- (NIL T QUOTE LAMBDA PROGN IF SETQ
DEFUN LET LET* PRINT PRINC TERPRI VECTOR FUNCALL APPLY EVAL CAR CDR
CONS LIST LENGTH ASSOC) plus fixnum arithmetic -- I've realized
that the implementation is a dead end, because it lacks one of
the *defining* characteristics of a "Common Lisp": exceptions!!
Or to be precise, the CL Condition System [CLHS 9.0].
[It also currently lacks a GC, but given today's memory sizes,
that's less important for an implementation that will mainly be
used for short, throwaway "scripts". Though adding GC later will
certainly require recoding almost all the "primitives"....]
Also, looking at what I use (say) CMUCL for on a daily basis,
fixnum-only arithmetic is, well, simply lame: ;-} ;-}
qdl> (defun fact (n) (if (< n 2) 1 (* n (fact (1- n)))))
FACT
qdl> (fact 12)
479001600
qdl> (fact 13)
*: ERROR: Result will not fit in a fixnum: 6227020800 [0x5cca33000]
qdl>
To be a "CL", you need a full numeric stack [even if non-fixnum
arithmetic is "slow", i.e., naively-coded].
So I'd like to suggest that a starting set of semantics for a
"minimal CL" include at least the following:
- At least one of the set of non-local control transfer primitives
sufficient to implement the rest, i.e. GO, RETURN-FROM, THROW, and
their establishing forms TAGBODY, BLOCK, & CATCH. [I currently think
that TAGBODY/GO is "the hardest" for a C-based implementation[1],
so it feels "more primitive" to me, but the previously-mentioned
Baker paper suggests they're all equal.]
- The CL exception system, minimally [Kent might suggest a better set]
MAKE-CONDITION, SIGNAL, HANDLER-BIND, RESTART-BIND, FIND-RESTART, and
INVOKE-RESTART. [I think ERROR, xxx-CASE, etc., can be defined in terms
of these plus the non-local transfers.]
- A debugger, or at the very least *DEBUGGER-HOOK* and the ability
for it to call user code.
- The full numeric tower: Reals [float, rational, integer (fixnum
and bignum)] and Complex [pairs of those] and the usual related
functions. [Personally, for the stuff I use CL for, I'd want the
LOGxxx and BYTE functions as well, but that's just me.]
- Lists (of course!), symbols/packages, characters, vectors (including
strings), structures, and enough hooks to add fully-general arrays
later. [I *think* that's all you absolutely need in terms of datatypes
to later add CLOS, say, using PCL.]
- CLHS 3.2.2.2 "Minimal Compilation", so you can at least have macros
that only expand once. [If you're going to build up everything from
some minimal core, you need this to avoid horrible inefficiencies.]
- CLHS 3.3.1 "Minimal Declaration Processing Requirements", which
[to me] also implies "doing the right thing" with dynamic and
lexical scoping, including special variables in LAMBDA lists.
[Some of this can be "faked" with lexical-only LAMBDA lists with
some parameter name re-writing and wrapping the LAMBDA body in an
UNWIND-PROTECT and some added SETQs.]
- Places & DEFINE-SETF-EXPANDER & a basic set of SETF/INCF/etc.
- The rest of the expected "minimal" set of special forms/macros
[what the thread was all about up until now]. ;-} ;-}
Anything less is just "a" Lisp...
I await serious comments/corrections with great interest.
-Rob
[1] Consider this tiny example:
> (defun foo (x) (funcall x))
FOO
> (tagbody
(foo (lambda () (go works)))
(print 'failed)
(go out)
works
(print 'works)
out)
WORKS
NIL
>
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Marcus Breiing
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <e8qo18$r8c$1@chessie.cirr.com>
····@rpw3.org (Rob Warnock) writes:
> I await serious comments/corrections with great interest.
In another post, you quoted from the spec:
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.
Now you write:
> [I think ERROR, xxx-CASE, etc., can be defined in terms
> of these plus the non-local transfers.]
I'm sure they can. But because of the subset restriction, I think
programs would have to be prohibited from adding their ERROR as
COMMON-LISP:ERROR, because that wouldn't fly in the full language. On
the other hand, I don't think you'd want everybody to have to provide
their own PRIVATE:ERROR, nor introduce a pointless
"looks-like-common-lisp-but-isn't" package. So you'd end up providing
ERROR in the subset, anyway. Likewise, probably, with many other
non-primitive but commonly used derivable operators.
I think this would strongly push an attempt to provide a "minimal"
subset of ultimately all-powerful operators to end up rather
non-minimal after all.
So I guess what I want to say is that a special purpose subset (for
scripting, say), probably should be a proper subset not just
syntactically, but semantically, too. "If you really need
HANDLER-BIND, just use the FULL language."
--
Marcus Breiing
Marcus Breiing <······@2006w27.mail.breiing.com> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > I await serious comments/corrections with great interest.
|
| In another post, you quoted from the spec:
|
| 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.
|
| Now you write:
|
| > [I think ERROR, xxx-CASE, etc., can be defined in terms
| > of these plus the non-local transfers.]
|
| I'm sure they can. But because of the subset restriction, I think
| programs would have to be prohibited from adding their ERROR as
| COMMON-LISP:ERROR, because that wouldn't fly in the full language.
+---------------
I think you have misunderstood my intent in describing a "minimal
subset of semantics". What I am looking at [which, granted, may be
somewhat different from what the original question was in this thread]
is the issue of what is a "minimal set of primitive semantics",
as it were, on top of which an *implementor* can build the full set
of Common Lisp semantics [or at least a consistent subset, but see
below on "subsets"]. So when I said "ERROR, xxx-CASE, etc., can be
defined in terms of these plus the non-local transfers", I was talking
about an *implementor* doing that defining, *not* the end user.
Sorry if that caused any confusion.
+---------------
| On the other hand, I don't think you'd want everybody to have
| to provide their own PRIVATE:ERROR, nor introduce a pointless
| "looks-like-common-lisp-but-isn't" package. So you'd end up providing
| ERROR in the subset, anyway. Likewise, probably, with many other
| non-primitive but commonly used derivable operators.
+---------------
See above. My goal is a small internal/implementor set of
semantics/special-forms/functions written in some other langauge
(probably C), with the *remainder* of the "Common Lisp subset"
written in terms of the "internal/implementor" set. So to a
*user* of the resulting CL subset, there would indeed be only
one ERROR provided as an external, namely, COMMON-LISP:ERROR.
[And, yes, COMMON-LISP:ERROR *might* use/call special-forms/functions
that are not in the COMMON-LISP package, but so what?!? All CL
implementations do that kind of thing. That doesn't imply they're
exported to the user.]
+---------------
| I think this would strongly push an attempt to provide a "minimal"
| subset of ultimately all-powerful operators to end up rather
| non-minimal after all.
+---------------
Well, just the needs of non-local transfers, basic conditions,
special variables, and arithmetic *already* take one into quite
"non-minimal" territory. But that's what you get with CL, which
is, after all, not Scheme.
+---------------
| So I guess what I want to say is that a special purpose subset
| (for scripting, say), probably should be a proper subset not
| just syntactically, but semantically, too. "If you really need
| HANDLER-BIND, just use the FULL language."
+---------------
What I've been discovering is that one can't *HAVE* a "proper
subset" without most of the semantics I called "minimal" in
my previous reply, since the very CLHS 1.7 "Language Subsets"
section we both have quoted from says:
...any valid program in that [the subset] language has
equivalent semantics... in any conforming implementation
of the full language.
That "equivalent semantics" constraint has been looming larger
and larger the more I look at the problem. E.g., it's why a
fixnum-only subset *cannot* be a "subset of ANSI Common Lisp".
(* 17 MOST-POSITIVE-FIXNUM) *will* overflow in a fixnum-only
subset and *won't* overflow in full ANSI Common Lisp, which is
*not* "equivalent semantics"! And so on & so on...
To say it another way: I'm now trying to find out whether or
not there can *exist* a "subset of ANSI Common Lisp" under the
criterion of CLHS 1.7 that is not (nearly) the whole language! ;-} ;-}
[And in a related but not identical question, find out what
a reasonable minimal set of primitives/semantics might be for
bootstrapping an ANSI CL (or a smaller subset, if a reasonable
one exists) from scratch.]
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Kent M Pitman
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <u64i59xrz.fsf@nhplace.com>
····@rpw3.org (Rob Warnock) writes:
> - The CL exception system, minimally [Kent might suggest a better set]
> MAKE-CONDITION, SIGNAL, HANDLER-BIND, RESTART-BIND, FIND-RESTART, and
> INVOKE-RESTART. [I think ERROR, xxx-CASE, etc., can be defined in terms
> of these plus the non-local transfers.]
I'm not going to venture a minimal set for lack of time.
As raw data, though, I will point to
http://www.nhplace.com/kent/CL/Revision-18.lisp.txt
while at the same time pointing out that historically, this was written
before all the details of the error system were nailed down and there
are things in the spec not reflected (pardon obscure pun) in this
description.
But I'll also note that the real problem in an error system, as you'll
see when you read this description, is that really none of the
functionality needs to be primitive. This was already possible to
write in portable CL. What was not portable to write was the "fact"
that it gets called. That is, what makes an error system interesting
is not its "capability" but that it is the chosen entry point for
doing what it does. All of what it does is non-primitive, and yet it
is not "the error system" it is just "a toy" unless it's the function
the system calls when it detects an error. How that factors into your
discussion of minimality I'll leave to the group to talk about, since
I'm busy this week.
From: Lars Brinkhoff
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <85psg76mma.fsf@junk.nocrew.org>
····@rpw3.org (Rob Warnock) writes:
> So I'd like to suggest that a starting set of semantics for a
> "minimal CL" include at least the following:
I've implemented much of CL in Emacs Lisp, which has a much smaller
set of primives than CL. You could even subset Emacs Lisp and use
that as an implementation substrate, which would get us a lot closer
to a "minimal" subset.
> - At least one of the set of non-local control transfer primitives
> sufficient to implement the rest, i.e. GO, RETURN-FROM, THROW, and
> their establishing forms TAGBODY, BLOCK, & CATCH.
Right. Emacs Lisp only has catch and throw.
> - The CL exception system, minimally [Kent might suggest a better set]
> MAKE-CONDITION, SIGNAL, HANDLER-BIND, RESTART-BIND, FIND-RESTART, and
> INVOKE-RESTART.
None of these are primitive. The binding forms can just add some
information to a dynamic variable. SIGNAL and FIND/INVOKE-RESTART
search that information and calls a closure. MAKE-CONDITION can be a
thin layer on top of MAKE-INSTANCE. (And all of CLOS can be
implemented from more primitive constructs.)
> - The full numeric tower: Reals [float, rational, integer (fixnum
> and bignum)] and Complex [pairs of those] and the usual related
> functions.
Emacs Lisp only has fixnums and floats. In my implementation, all
other types of numbers are built from those. Of course, floats could
be implemented with fixnums.
> - Lists (of course!), symbols/packages, characters, vectors (including
> strings), structures, and enough hooks to add fully-general arrays
> later.
It's enough to build up from conses, symbols, and vectors. Emacs Lisp
has more data types, which is useful, but not necessary. I guess
vectors could go if you don't need their O(1) properties.
You don't need hash tables, but weak hash tables are very very handy,
and I don't see how those could be implemented outside the core.
> I *think* that's all you absolutely need in terms of datatypes to
> later add CLOS, say, using PCL.
Yes, or almost. In my implementation, instances of many built-in
types, classes, and structures are vectors where the first element
indicates the type. You may want funcallable instances, but they are
not absolutely necessary.
> - CLHS 3.2.2.2 "Minimal Compilation", so you can at least have macros
> that only expand once. [If you're going to build up everything from
> some minimal core, you need this to avoid horrible inefficiencies.]
You do need minimal compilation, but the (minimal) compiler can be
written in the core language. If you consider bootstrapping a solved
problem, I don't think the compiler is a necessary primitive.
> - CLHS 3.3.1 "Minimal Declaration Processing Requirements", which
> [to me] also implies "doing the right thing" with dynamic and
> lexical scoping, including special variables in LAMBDA lists.
Declaration processing is just part of the compiler. You need one
kind binding: lexical or dynamic. Or maybe none at all, just
assignment to memory locations.
> - Places & DEFINE-SETF-EXPANDER & a basic set of SETF/INCF/etc.
These are quite easy to write in the subset language.
Lars Brinkhoff <·········@nocrew.org> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > So I'd like to suggest that a starting set of semantics for a
| > "minimal CL" include at least the following:
|
| I've implemented much of CL in Emacs Lisp, which has a much smaller
| set of primives than CL.
+---------------
Very interesting indeed! Do you think your "much of CL" meets the
definition of a "subset of CL" given in CLHS 1.7 "Language Subsets"?
I'm particularly concerned about the "equivalent semantics" clause
and the "no extralingual pre-processing, and no special compatibility
packages" clauses. If you hid/disabled/undocumented the pieces of
your "much of CL" which don't meet the strict "subset" definition,
would you still have a generally-useful language?
[Note: One may still use non-compatible/non-equivalent features
inside the *implementation* of a "subset CL", as long as they are
not documented/exported to the "user", so that any "valid program"
that is written in the "subset CL" does not explicitly depend on
those features and thus will run "with equivalent semantics" on
any comformant full ANSI CL.]
+---------------
| You could even subset Emacs Lisp and use that as an implementation
| substrate, which would get us a lot closer to a "minimal" subset.
+---------------
Right, but consider the above comments on the relationship between
the implementation substrate and the "subset CL" which it hosts.
I may differ from others in this regard, but personally I am not so
much interested in "just another small Lisp" [there are a plethora
of those!] as I am in a "reasonably-shaped" [no "sharp corners",
though huge "missing areas" are o.k. as long as the edges are "clean"]
language which meets all of the following criteria:
1. Is substantially "smaller" than full ANSI CL by at least *some*
"obvious"/noncontroversial metric(s). [Else what's the point?!?
Just use full CL. There are plenty of those already.]
2. Is "large enough" to be generally useful for at least *some*
area(s) of interest -- say, "scripting", one-off programs,
introductory tutorials/teaching, etc., or as an "extension
language" [yet another ill-defined term, sorry] for embedding
in other programs.
3. Meets the strict "letter of the law", CLHS 1.7 "Language
Subsets", even if to do so one must bend the spirit a bit,
e.g., hide/undocument/unexport portions of the implementation
substrate so that they are *not* a part of the "valid programs"
which are being considered to be written in the "subset".
The CLHS "Issue SUBSETTING-POSITION Writeup" [linked from CLHS 1.7]
makes very interesting reading, especially the discussion of the
then-current practice in other languages, particularly these bits:
Cobol had multiple levels of subsets. However, the only two
levels that were important were the minimum subset and the
full language. The middle levels were seldom used other than
transient points to the full language.
...
At one point, there was an ANSI standard for "Minimal Basic".
It was too minimal.
That's probably my real interest in this topic. Phrased another way,
*is* there any (at least one) subset of CL [by the CLHS 1.7 definition]
that is neither "too minimal" nor too close to the full language?
It is not yet clear to me that there is... or isn't.
+---------------
| > - At least one of the set of non-local control transfer primitives
| > sufficient to implement the rest, i.e. GO, RETURN-FROM, THROW, and
| > their establishing forms TAGBODY, BLOCK, & CATCH.
|
| Right. Emacs Lisp only has catch and throw.
+---------------
Right, but as Baker's paper shows, any of the three pairs is "primitive"
with respect to the other two. In my "QDL" (attempt at a subset), I'm
probably going to use TAGBODY/GO as the "primitive" one, if only because
I want those forms with implicit TAGBODYs [DO, DO*, DO{LIST,TIMES}, etc.]
to be efficient.
+---------------
| > - The CL exception system, minimally [Kent might suggest a better set]
| > MAKE-CONDITION, SIGNAL, HANDLER-BIND, RESTART-BIND, FIND-RESTART, and
| > INVOKE-RESTART.
|
| None of these are primitive. The binding forms can just add some
| information to a dynamic variable. SIGNAL and FIND/INVOKE-RESTART
| search that information and calls a closure. MAKE-CONDITION can be a
| thin layer on top of MAKE-INSTANCE. (And all of CLOS can be
| implemented from more primitive constructs.)
+---------------
O.k., fine. And as Kent has pointed out elsewhere in this thread:
...in an error system...really none of the functionality needs
to be primitive. This was already possible to write in portable CL.
What was not portable to write was the "fact" that it gets called.
That is, what makes an error system interesting is not its
"capability" but that it is the chosen entry point for doing what
it does. All of what it does is non-primitive, and yet it is not
"the error system" it is just "a toy" unless it's the function the
system calls when it detects an error.
So at least enough hooks have to be provided in the implementation
substrate that the implementation of the subset *will* find it
convenient -- nay, necessary -- to call the defined condition
system rather than either do nothing or do something idiosyncratic.
In particular, it needs to be possible to cleanly "call back into"
the CL subset during exception handling.
+---------------
| > - The full numeric tower: Reals [float, rational, integer (fixnum
| > and bignum)] and Complex [pairs of those] and the usual related
| > functions.
|
| Emacs Lisp only has fixnums and floats. In my implementation, all
| other types of numbers are built from those. Of course, floats could
| be implemented with fixnums.
+---------------
It's that sticky little "equivalent semantics" clause that worries me.
Right now, I could make the case [though it would be a stretch! ;-} ]
that fixnum-only QDL *does* meet the clause, since it catches fixnum
overflow or non-integer division result and throws an error. One could
claim that a program that does that is not a "valid program", and thus
is not in the subset. The SUBSETTING-POSITION:NONE writeup allows that:
Some subsets are "dynamically" determinable, e.g, a subset might
signal an error if [an invalid argument].
...
Some "subsets" might be merely restrictive interpretations, e.g.,
a "run-time" implementation that [disallows some calls or exits on
BREAK].
But once you extend a fixnum-only subset to include floats, with
automatic coercion to floats for non-fixnum results, then I think
you can no longer claim to meet the "equivalent semantics" clause!!
And if Emacs Lisp is your implementation substrate, then the expression
(/ 3 5) ==> 0.6 would fail to have equivalent semantics in full CL.
+---------------
| > - Lists (of course!), symbols/packages, characters, vectors (including
| > strings), structures, and enough hooks to add fully-general arrays
| > later.
|
| It's enough to build up from conses, symbols, and vectors. Emacs Lisp
| has more data types, which is useful, but not necessary. I guess
| vectors could go if you don't need their O(1) properties.
+---------------
For a "useful" [IMHO] scripting language, you do need O(1) access
to strings, so vectors might as well stay. And as you point out,
from vectors come structs, and from structs, CLOS.
+---------------
| You don't need hash tables, but weak hash tables are very very handy,
| and I don't see how those could be implemented outside the core.
+---------------
Just curious... How are weak hash tables more useful than generic
weak pointers? [You need weak pointers for finalization, which I'll
grant can be useful.]
+---------------
| > - CLHS 3.2.2.2 "Minimal Compilation", so you can at least have macros
| > that only expand once. [If you're going to build up everything from
| > some minimal core, you need this to avoid horrible inefficiencies.]
|
| You do need minimal compilation, but the (minimal) compiler can be
| written in the core language. If you consider bootstrapping a solved
| problem, I don't think the compiler is a necessary primitive.
+---------------
Well, if you allow the use of an external full CL for your bootstrapping
[the way SBCL does, for example], then, yes, bootstrapping is a "solved
problem". ;-} ;-} But I was kinda hoping to avoid requiring that.
Though standalone bootstrapping is a *lot* more work, and I'm no longer
sure I have enough enthusiasm to do it that way. I'm particularly
tempted by a suggestion from Carl Shapiro to "simply" build a run-time
interpreter for CMUCL's byte-compiled code, which is a fairly simple
stack machine. Then as long as the byte-compiled code only called
other byte-code or "primitives" that were hand-coded, I could get
a fairly high-quality compiler "for free" during the bootstrapping.
[Tempting, indeed...]
[Side note: It actually looks harder to read/parse CMUCL's FASL
format than to interpret the byte-compiled codes contained *within*
a FASL!! The FASL reader is its own separate stack machine, sort of.]
+---------------
| > - CLHS 3.3.1 "Minimal Declaration Processing Requirements", which
| > [to me] also implies "doing the right thing" with dynamic and
| > lexical scoping, including special variables in LAMBDA lists.
|
| Declaration processing is just part of the compiler. You need one
| kind binding: lexical or dynamic. Or maybe none at all, just
| assignment to memory locations.
+---------------
Well, mere "assignment to memory locations" doesn't provide the
right semantics for LAMBDA, and if you have LAMBDA, then almost all
the other binding constructs are just a hop, skip, & jump away.
+---------------
| > - Places & DEFINE-SETF-EXPANDER & a basic set of SETF/INCF/etc.
|
| These are quite easy to write in the subset language.
+---------------
Yup.
So anyway, I'm still curious as to whether any CL implementors or
serious users have an opinion/belief/hunch about whether a "useful"
subset of CL exists that meets CLHS 1.7...
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Sun, 16 Jul 2006 21:27:10 -0500, ····@rpw3.org (Rob Warnock) wrote:
>
> 1. Is substantially "smaller" than full ANSI CL by at least *some*
> "obvious"/noncontroversial metric(s). [Else what's the point?!?
> Just use full CL. There are plenty of those already.]
>
> 2. Is "large enough" to be generally useful for at least *some*
> area(s) of interest -- say, "scripting", one-off programs,
> introductory tutorials/teaching, etc., or as an "extension
> language" [yet another ill-defined term, sorry] for embedding
> in other programs.
I think these two pose a question that has to be answered first:
are there in fact obvious/noncontroversial metrics, and if so,
what are they?
--
Jack Unrue
Jack Unrue <·······@example.tld> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) wrote:
| > 1. Is substantially "smaller" than full ANSI CL by at least *some*
| > "obvious"/noncontroversial metric(s). [Else what's the point?!? ...]
| > 2. Is "large enough" to be generally useful for at least *some*
| > area(s) of interest -- say, "scripting", one-off programs, ...
|
| I think these two pose a question that has to be answered first:
| are there in fact obvious/noncontroversial metrics, and if so,
| what are they?
+---------------
Fair enough, but one doesn't have to get bogged down in excess
precision here. Fairly "soft" metrics would do fine, for me
at least. Esthetics *is* an important part of what I'm aiming for.
That is, one would rather that others look at the result and say,
"Ooh! That's cute" instead of "Yucckk! That's a total crock!".
So the overall "shape" of the subset has to be at least somewhat
"pleasing" to the eye of most experienced CL-ers. [Sorry for all
the scare quotes, but as you note, these are precisely the terms
which are ill-defined.]
We *do* have one extant example of a "small" Lisp which has
been found useful by many: Scheme. My question is whether
there is any Common Lisp subset meeting CLHS 1.7 which would
be similarly useful and not *too* ugly! ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Some days investigating this, and at the end I encounter the response
in a Graham article:
http://www.paulgraham.com/rootsoflisp.html
He just defines quote, atom, eq, cons, car, cdr, cond and of course
defun. But I think it is just not enough for constructing a CL system,
because we need some IO, return multiple values, etc.
In special, look at this code:
http://lib.store.yahoo.net/lib/paulgraham/jmc.lisp
It is quite impresive that he has written an eval function in 25 lines
of code, using only 8 keywords.
Javier <·······@gmail.com> wrote:
+---------------
| Some days investigating this, and at the end I encounter
| the response in a Graham article:
| http://www.paulgraham.com/rootsoflisp.html
| http://lib.store.yahoo.net/lib/paulgraham/jmc.lisp
+---------------
Those are indeed the academic "roots of Lisp", but really
have nothing to do with "constructing a full CL system", sorry.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) wrote:
>
>Jack Unrue <·······@example.tld> wrote:
>+---------------
>| ····@rpw3.org (Rob Warnock) wrote:
>| > 1. Is substantially "smaller" than full ANSI CL by at least *some*
>| > "obvious"/noncontroversial metric(s). [Else what's the point?!? ...]
>| > 2. Is "large enough" to be generally useful for at least *some*
>| > area(s) of interest -- say, "scripting", one-off programs, ...
>|
>| I think these two pose a question that has to be answered first:
>| are there in fact obvious/noncontroversial metrics, and if so,
>| what are they?
>+---------------
>
>Fair enough, but one doesn't have to get bogged down in excess
>precision here. Fairly "soft" metrics would do fine, for me
>at least. Esthetics *is* an important part of what I'm aiming for.
>That is, one would rather that others look at the result and say,
>"Ooh! That's cute" instead of "Yucckk! That's a total crock!".
>So the overall "shape" of the subset has to be at least somewhat
>"pleasing" to the eye of most experienced CL-ers. [Sorry for all
>the scare quotes, but as you note, these are precisely the terms
>which are ill-defined.]
Yeah, I understand the aesthetics aspect. Must the experienced
CL-ers be the target audience, though? I'm just speculating because
I haven't actually done a survey, but I would guess many of the
gurus wouldn't care about any subset because they know quite a bit
about the subtle details and prefer more options over less.
So, what do you think about weighting the tradeoffs in favor
of attracting new Lispers? Keeping in mind the feedback from
established gurus, of course. Or was that your goal already
and I just missed it?
I was also thinking that, aesthetics and performance aside,
it's pretty easy to settle on one's own private subset of CL.
This is inertia that your proposed subset would have to
overcome from a mindshare standpoint.
>We *do* have one extant example of a "small" Lisp which has
>been found useful by many: Scheme. My question is whether
>there is any Common Lisp subset meeting CLHS 1.7 which would
>be similarly useful and not *too* ugly! ;-}
Right, but as everyone knows, Scheme has some important
distinguishing characteristics -- whereas the CL subset
has to be compatible with its ancestor. And after one
implements all the SRFIs, it's not clear (to me anyway)
how small Scheme is at that point. IMHO Scheme isn't
comparable to this. :-)
--
Jack Unrue
Jack Unrue <·······@example.tld> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) wrote:
| >at least. Esthetics *is* an important part of what I'm aiming for.
| >That is, one would rather that others look at the result and say,
| >"Ooh! That's cute" instead of "Yucckk! That's a total crock!".
| >So the overall "shape" of the subset has to be at least somewhat
| >"pleasing" to the eye of most experienced CL-ers.
|
| Yeah, I understand the aesthetics aspect. Must the experienced
| CL-ers be the target audience, though? I'm just speculating because
| I haven't actually done a survey, but I would guess many of the
| gurus wouldn't care about any subset because they know quite a bit
| about the subtle details and prefer more options over less.
+---------------
I said "experienced CL-ers" for two reasons: (1) Because it's CL-ers
who will have the context to understand/judge whether any given subset
of CL is "reasonable"; and (2) because I don't see many non-CL-ers
being particularly interested in the issue -- there are many other
"small Lisps" which are a lot simpler to define/implement.
+---------------
| So, what do you think about weighting the tradeoffs in favor
| of attracting new Lispers? Keeping in mind the feedback from
| established gurus, of course. Or was that your goal already
| and I just missed it?
+---------------
Personally [I can't speak for the OP of the "minimal keywords"
question], I wasn't thinking about new Lispers at all, actually.
I like using the full language wherever I can, especially CMUCL,
but there are sometimes some places where I can't [e.g., embedded
systems, places where CMUCL doesn't run yet, etc.], where a very
portable, small, subset of CL would be useful -- not just a toy
interpreter, but one with adequate performance for "scripting"
and other string-bashing, say.
+---------------
| I was also thinking that, aesthetics and performance aside,
| it's pretty easy to settle on one's own private subset of CL.
| This is inertia that your proposed subset would have to
| overcome from a mindshare standpoint.
+---------------
Well, yes, but then [for whatever reason] I got really intrigued
with the idea of having the subset meet the criteria of CLHS 1.7,
so I could call it "a real Common Lisp subset". ;-} ;-}
+---------------
| >We *do* have one extant example of a "small" Lisp which has
| >been found useful by many: Scheme. My question is whether
| >there is any Common Lisp subset meeting CLHS 1.7 which would
| >be similarly useful and not *too* ugly! ;-}
|
| Right, but as everyone knows, Scheme has some important
| distinguishing characteristics -- whereas the CL subset
| has to be compatible with its ancestor. And after one
| implements all the SRFIs, it's not clear (to me anyway)
| how small Scheme is at that point. IMHO Scheme isn't
| comparable to this. :-)
+---------------
I came to CL from Scheme[1], specifically, MzScheme versions
97-102 or thereabouts, which I had found *quite* adequate for
the things I'd want a CL subset to do: misc. "shell scripting",
web CGI scripts, misc. systems administration utilities, etc.
Aside: The performance of my current fixnum-only "QDL" for
(ACKERMANN 3 7) is about twice as slow as interpreted CLISP or
byte-compiled CMUCL, and slightly *faster* than interpreted CMUCL.
That's "good enough" for what I have in mind, but should be
able to be significantly improved with a little preprocessing
["minimal compilation"].
-Rob
[1] Still owe the community a RoadToLisp article... (*sigh*)
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Kent M Pitman
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <ufygzsksa.fsf@nhplace.com>
····@rpw3.org (Rob Warnock) writes:
> Jack Unrue <·······@example.tld> wrote:
> +---------------
> | ····@rpw3.org (Rob Warnock) wrote:
> | > 1. Is substantially "smaller" than full ANSI CL by at least *some*
> | > "obvious"/noncontroversial metric(s). [Else what's the point?!? ...]
> | > 2. Is "large enough" to be generally useful for at least *some*
> | > area(s) of interest -- say, "scripting", one-off programs, ...
> |
> | I think these two pose a question that has to be answered first:
> | are there in fact obvious/noncontroversial metrics, and if so,
> | what are they?
> +---------------
>
> Fair enough, but one doesn't have to get bogged down in excess
> precision here. Fairly "soft" metrics would do fine, for me
> at least. Esthetics *is* an important part of what I'm aiming for.
> That is, one would rather that others look at the result and say,
> "Ooh! That's cute" instead of "Yucckk! That's a total crock!".
> So the overall "shape" of the subset has to be at least somewhat
> "pleasing" to the eye of most experienced CL-ers. [Sorry for all
> the scare quotes, but as you note, these are precisely the terms
> which are ill-defined.]
>
> We *do* have one extant example of a "small" Lisp which has
> been found useful by many: Scheme. My question is whether
> there is any Common Lisp subset meeting CLHS 1.7 which would
> be similarly useful and not *too* ugly! ;-}
No. Not a per-se subset, but what I have sometimes called a
conceptual subset... check out ISLISP.
http://www.islisp.info/
(Yeah, I apologize for the bad coloring and the frames.)
····@rpw3.org (Rob Warnock) writes:
> And if Emacs Lisp is your implementation substrate, then the expression
> (/ 3 5) ==> 0.6 would fail to have equivalent semantics in full CL.
Actually, (/ 3 5) ==> 0
--
Johan Bockgård
Johan Bockgård wrote:
> Actually, (/ 3 5) ==> 0
CLtL 12.4 Arithmetic Operations
http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node125.html
"/ will produce a ratio if the mathematical quotient of two integers is
not an exact integer. For example:
(/ 12 4) => 3
(/ 13 4) => 13/4
(/ -8) => -1/8
(/ 3 4 5) => 3/20
To divide one integer by another producing an integer result, use one of
the functions floor, ceiling, truncate, or round."
--
Sidney Markowitz
http://www.sidney.com
Sidney Markowitz <······@sidney.com> wrote:
+---------------
| XXJohan Bockgård wrote:
| > Actually, [in Emacs Lisp?] (/ 3 5) ==> 0
|
| CLtL 12.4 Arithmetic Operations
| / will produce a ratio if the mathematical
| quotient of two integers is not an exact integer.
+---------------
Exactly. Which breaks the "equivalent semantics" rule of CLHS 1.7.
[So it's going to be hard to use Emac Lisp as the implementation
substrate of a conforming "CL subset".]
Whereas, if a purported "CL subset" gave a "don't do that!" error:
qdl> (/ 3 5)
/: Error: Division by 5 produced non-integer result!
qdl>
Then as long as you exclude programs that do that from the set of
"valid programs" for the purported subset, then that *wouldn't*
break the rule. [Bend real hard, maybe, but not break.] ;-}
The question is whether such a subset would be considered "useful"...
-Rob
p.s. If a fixnum-only subset included MOD and/or REM,
it would be a lot more useful than if it didn't. ;-}
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Lars Brinkhoff
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <851wsk5adw.fsf@junk.nocrew.org>
····@rpw3.org (Rob Warnock) writes:
> Sidney Markowitz <······@sidney.com> wrote:
> > Johan Bockgård wrote:
> > > Actually, [in Emacs Lisp?] (/ 3 5) ==> 0
> > CLtL 12.4 Arithmetic Operations / will produce a ratio if the
> > mathematical quotient of two integers is not an exact integer.
> Exactly. Which breaks the "equivalent semantics" rule of CLHS 1.7.
> [So it's going to be hard to use Emac Lisp as the implementation
> substrate of a conforming "CL subset".]
I don't understand that. I have used Emacs Lisp as the implementation
substrate of a (purportedly) conforming CL subset, and I didn't find
the differences between / in Emacs Lisp and Common Lisp to be a hard
problem. It's probably on par with using, say, C as a substrate,
which is common enough.
You wouldn't be say that C is an inappropriate *implementation*
language just because its operators doesn't have a subset of CL
semantics, would you? Of course, C isn't a CL subset. :-)
Lars Brinkhoff <·········@nocrew.org> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > Sidney Markowitz <······@sidney.com> wrote:
| > > Johan Bockgård wrote:
| > > > Actually, [in Emacs Lisp?] (/ 3 5) ==> 0
| > > CLtL 12.4 Arithmetic Operations / will produce a ratio if the
| > > mathematical quotient of two integers is not an exact integer.
| > Exactly. Which breaks the "equivalent semantics" rule of CLHS 1.7.
| > [So it's going to be hard to use Emac Lisp as the implementation
| > substrate of a conforming "CL subset".]
|
| I don't understand that. I have used Emacs Lisp as the implementation
| substrate of a (purportedly) conforming CL subset, and I didn't find
| the differences between / in Emacs Lisp and Common Lisp to be a hard
| problem. It's probably on par with using, say, C as a substrate,
| which is common enough.
+---------------
So you're saying you implemented rationals in your CL subset?
O.k., then no problem, any more than doing it in C [with all
that that implies!] is a "problem". But in that case you didn't
use Emac's own arithmetic *as* the arithmetic for the subset,
which is what I addressing.
And my apologies if I misunderstood the context of your previous
remarks...
+---------------
| You wouldn't be say that C is an inappropriate *implementation*
| language just because its operators doesn't have a subset of CL
| semantics, would you? Of course, C isn't a CL subset. :-)
+---------------
So is it your opinion that Emacs Lisp is a reasonable -- or at least,
substantially easier/better than C -- implementation substrate for
a conforming CL subset? If so, that's a interesting & potentially
very useful datapoint, since AFAIK Emacs can iteself be compiled
directly from C.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Lars Brinkhoff
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <85d5c24s85.fsf@junk.nocrew.org>
····@rpw3.org (Rob Warnock) writes:
> So you're saying you implemented rationals in your CL subset?
Yes (and bignums, complex numbers, packages, readtables, streams,
multiple values, adjustable arrays, the condition system, etc).
> But in that case you didn't use Emac's own arithmetic *as* the
> arithmetic for the subset, which is what I addressing.
Right.
> And my apologies if I misunderstood the context of your previous
> remarks...
No need, I probably misunderstood you first. :-)
> So is it your opinion that Emacs Lisp is a reasonable -- or at least,
> substantially easier/better than C -- implementation substrate for
> a conforming CL subset?
Better by what metric? But probably no. Easier, yes. Reasonable,
I guess.
From: Thomas A. Russ
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <ymiveptz9y5.fsf@sevak.isi.edu>
Sidney Markowitz <······@sidney.com> writes:
> Johan Bockgård wrote:
> > Actually, (/ 3 5) ==> 0
>
> CLtL 12.4 Arithmetic Operations
>
> http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node125.html
>
> "/ will produce a ratio if the mathematical quotient of two integers is
> not an exact integer. For example:
But the original context was Emacs Lisp, not Common Lisp.
--
Thomas A. Russ, USC/Information Sciences Institute
····@rpw3.org (Rob Warnock) writes:
> +---------------
> | You don't need hash tables, but weak hash tables are very very handy,
> | and I don't see how those could be implemented outside the core.
> +---------------
>
> Just curious... How are weak hash tables more useful than generic
> weak pointers? [You need weak pointers for finalization, which I'll
> grant can be useful.]
Some weak structures can be implemented above mere weak pointers, but
some other cannot. For example, weak-or-relation is primitive, you
cannot implement it with only weak-pointer.
Also, depending on the invariants you expect after a garbage
collection, you may need to implement the other weak structures as
primitives too.
For one thing, the unsuspecting garbage collector will collect only
the first layer of the weak pointer. The weak pointers that become
dead because of this first garbage collecting are not further
collected. So if you implement non primitive weak structures, you
need to run the garbage collector several times in a row to get the
same effect as with primitive weak structures. The situation is worse
with circular structures of weak pointer. As soon as it goes thru a
non weak structure such as a hash table (or merely a structure that
won't be normally garbage collected, because it's used), the weak
pointers won't die, and won't be collected. This is particularly true
with hash table, when the value contains a back reference to the weak
key: the weak key won't die, even if the only reference there is to it
comes from the value.
http://www.informatimago.com/develop/lisp/index.html#clext
Ad: The best weak structure support is in clisp!
--
__Pascal Bourguignon__ http://www.informatimago.com/
Kitty like plastic.
Confuses for litter box.
Don't leave tarp around.
From: Lars Brinkhoff
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <8564hw5at7.fsf@junk.nocrew.org>
····@rpw3.org (Rob Warnock) writes:
> Lars Brinkhoff <·········@nocrew.org> wrote:
> > I've implemented much of CL in Emacs Lisp, which has a much
> > smaller set of primives than CL.
> Very interesting indeed! Do you think your "much of CL" meets the
> definition of a "subset of CL" given in CLHS 1.7 "Language Subsets"?
Absolutely. It's actually quite close to full ANSI CL, but some major
chunks are missing, like pretty printing and CLOS. Other than that,
it's just another implementation of CL.
> > You could even subset Emacs Lisp and use that as an implementation
> > substrate, which would get us a lot closer to a "minimal" subset.
> Right, but consider the above comments on the relationship between
> the implementation substrate and the "subset CL" which it hosts.
Ok, in that case, my implementaion uses Emacs Lisp almost exclusively
as a substrate, and the CL layer is a separate language on top of
that.
However, I believe you could take the Emacs Lisp language (not the
implementation) as a starting point, modify it somewhat, and get a
language that would be both a strict subset of CL, and a useful CL
implementation language. Or at least use Emacs Lisp as some kind of
guide to which features to include. Emacs Lisp is actually already
quite close to being a CL subset, at least culturally.
> > Emacs Lisp only has catch and throw.
> In my "QDL", I'm probably going to use TAGBODY/GO as the "primitive"
> one
Yes, that would have been my choise too.
> > > - The CL exception system [...]
> > None of these are primitive.
> O.k., fine. And as Kent has pointed out elsewhere in this thread:
> ...in an error system...really none of the functionality needs
> to be primitive. This was already possible to write in portable CL.
> What was not portable to write was the "fact" that it gets called.
> So at least enough hooks have to be provided in the implementation
> substrate
Right, but to pick nits, a substrate doesn't need those hooks (like,
provably, Emacs Lisp), but a subset does.
> > > - The full numeric tower: Reals [float, rational, integer (fixnum
> > > and bignum)] and Complex [pairs of those] and the usual related
> > > functions.
> > Emacs Lisp only has fixnums and floats. In my implementation, all
> > other types of numbers are built from those. Of course, floats could
> > be implemented with fixnums.
>
> It's that sticky little "equivalent semantics" clause that worries me.
By now, you should have realised (as have I) that I was writing about
something slighly different from what you was asking for. Of course,
most Emacs Lisp operators have wildly different semantics from the
corresponding CL operators. So Emacs Lisp hardly qualifies as the
subset language you want. However, it's quite straightforward to use
it to implement the CL semantics in a distinct set of operators.
> But once you extend a fixnum-only subset to include floats, with
> automatic coercion to floats for non-fixnum results, then I think
> you can no longer claim to meet the "equivalent semantics" clause!!
No, but a fixnum-only subset wouldn't have to handle things that way.
By your suggestion, signals could be raised at appropriate points, and
handled to implement CL semantics.
> And if Emacs Lisp is your implementation substrate, then the expression
> (/ 3 5) ==> 0.6 would fail to have equivalent semantics in full CL.
But because Emacs Lisp is a *substrate*, not a subset, this doesn't
matter. In my CL implementation, (/ 3 5) evaluates to 3/5, as it
should. Obviously, the emacs-lisp:/ operator isn't the same as
common-lisp:/.
> as you point out, from vectors come structs, and from structs, CLOS.
(Or structs come from CLOS, or they may be separate. Each way has its
merits.)
But if you do this, there may be problems with the subset semantics.
You wouldn't want the subset to say that TYPE-OF a struct is VECTOR.
Of course you can make the subset have its own operator, say
CL-SUBSET:TYPE-OF, and implement CL:TYPE-OF in terms of that, but then
a small part of your subset has been expatriated to substrate layer,
and then you have a situation that is similar to my implementation.
> > You don't need hash tables, but weak hash tables are very very handy
> Just curious... How are weak hash tables more useful than generic
> weak pointers?
I didn't say they are. I don't know enough on generic weak pointers
to comment on that.
> > Declaration processing is just part of the compiler. You need one
> > kind of binding: lexical or dynamic. Or maybe none at all, just
> > assignment to memory locations.
> Well, mere "assignment to memory locations" doesn't provide the
> right semantics for LAMBDA, and if you have LAMBDA, then almost all
> the other binding constructs are just a hop, skip, & jump away.
Right. It's just the substrate vs subset thing again.
> I'm still curious as to whether any CL implementors or serious users
> have an opinion/belief/hunch about whether a "useful" subset of CL
> exists that meets CLHS 1.7...
I believe Lisp500 may be quite close to such a subset. When I last
looked at it, it really seemed to go out of its way to only implement
the most necessary primitives in C, and add more CL operators in a
Lisp initiation file.
From: Don Geddis
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <87slla4lf9.fsf@geddis.org>
>> "Rob Thorpe" <·············@antenova.com> wrote on 5 Jul 2006 10:23:
>> > It is not really the minimum set since it does no I/O, as I mentioned
>> > earlier. So unless your prepared to speculate about implementing the
>> > whole universe using lambda
> I don't think it's really in the spirit of computer science. When
> discussing abstractions like minimal sets etc its useful to try to pick
> meaningful ways of talking about them, rather than trying to pick ways
> that deliberately reveal weaknesses in the question.
Well, let me try a different approach then. Many computer use special memory
locations for interfacing to external hardware. Rather than having addition
processor instructions, they just re-use existing instructions (like STORE),
but with magic arguments, to have a different semantics (namely, I/O).
Similarly, unix uses part of the filesystem (like /dev/null) to access
external hardware too.
So why can't you use "just" LAMBDA, but happen to define on the side that
certain specially named functions have the side effect of doing I/O?
It would seem to me to be analogous to not implementing special CPU
instructions for I/O.
So again, you only need LAMBDA.
> Well if you mention something like Common Lisp which has I/O then
> really you don't want that answer.
Well, I don't think you ever really want that answer, but I also don't think
that I/O is the big stumbling block.
> And not much of this has helped. The problem with Socratic examination
> is that it irritates as much as it informs.
Well, I provided a real answer in addition, which is that the question doesn't
have a unique answer.
> Functions clearly fall into two categories though, setf could be useful
> in a minimal set, stable-sort could not be that useful.
I don't agree with this at all. Not all functions (and/or special forms)
"clearly" fall into two categories (I assume you mean "primitive" vs. "complex"
or something like that).
Of course some functions do "feel" more primitive than others. But there are
a whole lot in the middle grey area as well.
How about SIN & COS, vs. TAN? Are some primitive and others not? Do you
even need any trig functions, if you "could" define them in terms of series
expansions using ordinary arithmetic?
> Lets say you want to implement CL on a very small platform. So to do this
> you use slightly different workflow, more like a C compiler. That is
> rather than dumping an image you compile an executable, in that executable
> you need:
> * All the user code put in
> * All the code the user code calls
> * All the code that code calls.
As another poster has said, this is a (well-known) tree-shaker. Which results
in a "minimal" collection of code _for_a_specific_application_. Not some
globally optimal sense of minimal.
> Solving this problem -or some nearby problem- could be much simpler if
> you knew one of the possible small sets.
I disagree. That probably helps a tree shaker very little. But maybe people
who have actually implemented such things could weigh in here.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
Reading computer manuals without the hardware is a frustrating as reading sex
manuals without the software. -- Arthur C. Clarke
Don Geddis wrote:
> >> "Rob Thorpe" <·············@antenova.com> wrote on 5 Jul 2006 10:23:
> >> > It is not really the minimum set since it does no I/O, as I mentioned
> >> > earlier. So unless your prepared to speculate about implementing the
> >> > whole universe using lambda
> > I don't think it's really in the spirit of computer science. When
> > discussing abstractions like minimal sets etc its useful to try to pick
> > meaningful ways of talking about them, rather than trying to pick ways
> > that deliberately reveal weaknesses in the question.
>
> Well, let me try a different approach then. Many computer use special memory
> locations for interfacing to external hardware. Rather than having addition
> processor instructions, they just re-use existing instructions (like STORE),
> but with magic arguments, to have a different semantics (namely, I/O).
> Similarly, unix uses part of the filesystem (like /dev/null) to access
> external hardware too.
>
> So why can't you use "just" LAMBDA, but happen to define on the side that
> certain specially named functions have the side effect of doing I/O?
Remember we're not talking about creating a new language here, we're
talking about building Common Lisp from smaller parts. So, we can't
change what Lambda means, the CLHS defines it. If we're talking about
making a new language then of course we can use a "one instruction set
language"
http://en.wikipedia.org/wiki/OISC
Thinking about it more carefully though if there is enough leeway in
the spec for undefined behaviour it may be possible.
> > Well if you mention something like Common Lisp which has I/O then
> > really you don't want that answer.
>
> Well, I don't think you ever really want that answer, but I also don't think
> that I/O is the big stumbling block.
>
> > And not much of this has helped. The problem with Socratic examination
> > is that it irritates as much as it informs.
>
> Well, I provided a real answer in addition,
Yes, you did. I was a bit overcritical.
> which is that the question doesn't
> have a unique answer.
>
> > Functions clearly fall into two categories though, setf could be useful
> > in a minimal set, stable-sort could not be that useful.
>
> I don't agree with this at all. Not all functions (and/or special forms)
> "clearly" fall into two categories (I assume you mean "primitive" vs. "complex"
> or something like that).
I meant fairly much what I said. There is a difference between "could
be useful in a minimal set" and "could not be useful in a minimal set".
Notice I say _could_. Setf could be useful in a one particular small
set of functions to create a lisp, but another could be used instead.
The "primitive" side of the equation is fuzzy, all kinds of things are
usable.
> Of course some functions do "feel" more primitive than others. But there are
> a whole lot in the middle grey area as well.
Yes.
> How about SIN & COS, vs. TAN? Are some primitive and others not? Do you
> even need any trig functions, if you "could" define them in terms of series
> expansions using ordinary arithmetic?
Probably the most minimal way would be to use power series. That is to
build them from normal arithmetic.
> > Lets say you want to implement CL on a very small platform. So to do this
> > you use slightly different workflow, more like a C compiler. That is
> > rather than dumping an image you compile an executable, in that executable
> > you need:
> > * All the user code put in
> > * All the code the user code calls
> > * All the code that code calls.
>
> As another poster has said, this is a (well-known) tree-shaker. Which results
> in a "minimal" collection of code _for_a_specific_application_. Not some
> globally optimal sense of minimal.
I think I've used one a while ago, I didn't know they were called tree
shakers though.
> > Solving this problem -or some nearby problem- could be much simpler if
> > you knew one of the possible small sets.
>
> I disagree. That probably helps a tree shaker very little.
Lets say you solve a nearby problem instead of the above. Instead of
finding the absolute minimum tree lets put one of the minimal subsets
into each compile. Lets also say that in the "superset" language all
the operations are written in terms of the subset. In this case the
problem boils down to looking for every superset function and including
code if it's found.
> But maybe people who have actually implemented such things could weigh in here.
That would be interesting.
From: Don Geddis
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <877j2iyg0w.fsf@geddis.org>
"Rob Thorpe" <·············@antenova.com> wrote on 11 Jul 2006 15:4:
> Instead of finding the absolute minimum tree lets put one of the minimal
> subsets into each compile. Lets also say that in the "superset" language
> all the operations are written in terms of the subset. In this case the
> problem boils down to looking for every superset function and including
> code if it's found.
But of course no reasonable implementation is actually structured this way.
For efficiency reasons, if nothing else, the set of operations that are
implemented "primitively" in a given implementation is unlikely to be the
"minimal subset" you describe. So a real implementation won't have lisp code
"for every superset function".
In addition, even your minimal subset is necessarily a minimal one for the
WHOLE LANGUAGE. Whereas, a given application may never use huge portions of
the language (e.g.: bignums, macros, trig). So a tree-shaker for a given
application might be able to eliminate even MORE of the language than your
design suggests.
Finally: Lisp implementations have only grown in size relatively slowly over
the decades, whereas available RAM has increased with Moore's law. Most real
customers would put only a little value on this whole exercise of tree shaking.
In almost every case, it's a fine solution to just include the entire CL
implementation along with the application.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
What I look forward to is continued immaturity followed by death.
-- Dave Barry
Kent M Pitman wrote:
>
> Almost all Lisp systems are bootstrapped in this way--by having a
> kernel of non-Lisp and then writing the rest in Lisp. But I doubt
> those implementations agree.
What other languages are famous for this bootstrapping method of
implementation, besides lisp?
············@gmail.com writes:
> Kent M Pitman wrote:
>
>>
>> Almost all Lisp systems are bootstrapped in this way--by having a
>> kernel of non-Lisp and then writing the rest in Lisp. But I doubt
>> those implementations agree.
>
> What other languages are famous for this bootstrapping method of
> implementation, besides lisp?
>
Forth, I think.
--
Fred Gilham ······@csl.sri.com
linus doesnt have what they call a GUI which means that you cant use a
mouse and click on things you have to type in words in a different
language probably finnish I dont know but it wont work unless you
speak at least 10 different languages and one of those languages has
to be a slavic language and you have a phd in 10 different languages
and also can do math real real good - From geraldholmes.freeyellow.com
From: Lars Brinkhoff
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <85vepw3rfr.fsf@junk.nocrew.org>
Fred Gilham <······@snapdragon.csl.sri.com> writes:
> ············@gmail.com writes:
>> Kent M Pitman wrote:
>>> Almost all Lisp systems are bootstrapped in this way--by having a
>>> kernel of non-Lisp and then writing the rest in Lisp. But I doubt
>>> those implementations agree.
>> What other languages are famous for this bootstrapping method of
>> implementation, besides lisp?
> Forth, I think.
From what little I know about implementing Forth, I believe it's
common to bootstrap Forth with a special metacompiler. This compiler
takes a small kernel written in Forth and produces a bootable runtime
image. Some primitive words may be written in assembly language, but
the assembler is usually a seamless part of Forth.
Bootstrapping from other languages (usually C) may also be common, but
that's regarded as impure and unsatisfactory. By some. I believe.
(My Forth metacompiler is written in Lisp, but of course usually Forth
is used. The kernel has about 80 words in Forth and 30 primitives,
everything else is loaded and compiled at boot time. Unfortunately,
there's a 30-line C file for the inner interpreter. Shame on me.)
"Javier" <·······@gmail.com> writes:
> What are the strictly minimun set of Lisp commands and/or keywords that
> are needed to recreate a complete CL system?
> I'd like to debate this here, and got some conclusions from you experts.
LAMBDA
All the rest can be build as layers over layers over LAMBDA.
Search for "lambda calculus", on google or wikipedia.
--
__Pascal Bourguignon__ http://www.informatimago.com/
This is a signature virus. Add me to your signature and help me to live.
Pascal Bourguignon wrote:
> "Javier" <·······@gmail.com> writes:
> > What are the strictly minimun set of Lisp commands and/or keywords that
> > are needed to recreate a complete CL system?
> > I'd like to debate this here, and got some conclusions from you experts.
>
> LAMBDA
>
> All the rest can be build as layers over layers over LAMBDA.
>
> Search for "lambda calculus", on google or wikipedia.
Hmm, I would be impressed if you could implement "read" and "print"
with only lambda.
From: Kent M Pitman
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <uk66tqq8h.fsf@nhplace.com>
"Rob Thorpe" <·············@antenova.com> writes:
> Pascal Bourguignon wrote:
> > "Javier" <·······@gmail.com> writes:
> > > What are the strictly minimun set of Lisp commands and/or keywords that
> > > are needed to recreate a complete CL system?
> > > I'd like to debate this here, and got some conclusions from you experts.
> >
> > LAMBDA
> >
> > All the rest can be build as layers over layers over LAMBDA.
> >
> > Search for "lambda calculus", on google or wikipedia.
>
> Hmm, I would be impressed if you could implement "read" and "print"
> with only lambda.
It's not that hard. You start with appropriate abstractions for atoms
and patterns of energy (or maybe just energy is appropriately minimal)
and then you build up computer consoles, printers, and networks from
those. [Probably the reference Structure and Interpetation of
Classical Mechanics will be a help. I don't know if he has library
support for macro objects like computer equipment or if you have to
start all the way back at the subatomic level. You could talk to him
about creating a repository...] Anyway, once you're at that macro
level, you implement data transport among computer components as
streams, and finally you create operations that mediate that transport
using read and print.
This may seem silly, but I recall a lecture in Physics at MIT where
the professor was explaining maxwell's equations and he drew back and
said, "really we'd like to be able to say that there's just one big
quantity U that's conserved" and he wrote "U=0" on the board. Modern
math isn't up to that, but maybe that's how it really works. Maybe
the Universe is just a single wave form and everything we perceive as
matter is just a fine-grained wiggle of some corner of that wave. If
that's so, then Lambda is arguably as powerful as anything we've got for
talking about its characteristics, and everything beyond that is just
abstraction. Using Lambda and a few basic physics equations, we implement
matter and call it distinct from the universe's proto-energy, and then we
build all other things out of that, just as the OP wanted to build Lisp
out of a minimal set.
So Pascal's suggestion seems fair to me.
Kent M Pitman wrote:
> "Rob Thorpe" <·············@antenova.com> writes:
> > Pascal Bourguignon wrote:
> > > "Javier" <·······@gmail.com> writes:
> > > > What are the strictly minimun set of Lisp commands and/or keywords that
> > > > are needed to recreate a complete CL system?
> > > > I'd like to debate this here, and got some conclusions from you experts.
> > >
> > > LAMBDA
> > >
> > > All the rest can be build as layers over layers over LAMBDA.
> > >
> > > Search for "lambda calculus", on google or wikipedia.
> >
> > Hmm, I would be impressed if you could implement "read" and "print"
> > with only lambda.
>
> It's not that hard. You start with appropriate abstractions for atoms
> and patterns of energy (or maybe just energy is appropriately minimal)
> and then you build up computer consoles, printers, and networks from
> those. [Probably the reference Structure and Interpetation of
> Classical Mechanics will be a help. I don't know if he has library
> support for macro objects like computer equipment or if you have to
> start all the way back at the subatomic level. You could talk to him
> about creating a repository...] Anyway, once you're at that macro
> level, you implement data transport among computer components as
> streams, and finally you create operations that mediate that transport
> using read and print.
>
> This may seem silly, but I recall a lecture in Physics at MIT where
> the professor was explaining maxwell's equations and he drew back and
> said, "really we'd like to be able to say that there's just one big
> quantity U that's conserved" and he wrote "U=0" on the board.
Those equations are Maxwells equations in terms of differential forms,
they are:-
dF = 0
dG = J
Unfortunately there are two of them, which wrecks the purity a bit and
lots of associated hard maths. I'm an antenna designer and I've never
used them.
Something similar in this problem would be to define it in terms of one
primitive operation called say "common-lisp", which takes a program as
an input and supplies the correct output.
> Modern
> math isn't up to that, but maybe that's how it really works. Maybe
> the Universe is just a single wave form and everything we perceive as
> matter is just a fine-grained wiggle of some corner of that wave. If
> that's so, then Lambda is arguably as powerful as anything we've got for
> talking about its characteristics, and everything beyond that is just
> abstraction. Using Lambda and a few basic physics equations, we implement
> matter and call it distinct from the universe's proto-energy, and then we
> build all other things out of that, just as the OP wanted to build Lisp
> out of a minimal set.
>
> So Pascal's suggestion seems fair to me.
>From the point of view of physics your allowed to start with the whole
universe. But I don't think it's really in the spirit of the question.
From: Kent M Pitman
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <uodw5qqos.fsf@nhplace.com>
Pascal Bourguignon <···@informatimago.com> writes:
> "Javier" <·······@gmail.com> writes:
> > What are the strictly minimun set of Lisp commands and/or keywords that
> > are needed to recreate a complete CL system?
> > I'd like to debate this here, and got some conclusions from you experts.
>
> LAMBDA
>
> All the rest can be build as layers over layers over LAMBDA.
>
> Search for "lambda calculus", on google or wikipedia.
Heh. Not practical for CL, but I assume Pascal didn't mean it to be.
Certainly an excellent idea for an educational "field trip" if one
has not gone down that path.
But you know, when we did the T design (Yale Scheme) we adopted this
kind of approach, trying to reanalyze as many things as possible in
terms of lambda and trying to optimize lambda to death.
The one puzzle that baffled me relentlessly at the time, and that I
only sorted out years later, was array reference. I repeatedly
modeled it with LAMBDA in various ways but I was led over and over to
the inevitable and annoying conclusion that the time it should take is
O(log(n)) and I could never figure out how to squeeze O(1) out of it.
It seemed weird and unsatisfying to say that LAMBDA and AREF were
needed to be minimal. It took me until years later to discover the
source of my confusion.
I won't spoil it by offering the answer here. I'll leave it for now as
an exercise to the reader, partly for the fun of it and partly to see if
others have a differing take.
But it leads me to again say that there's questionable value in
addressing minimalism for its own sake. It can cause you to focus on
the wrong things. Minimalism is a tool or a state. At best a
theoretical goal. Not a very practical one in many cases. And it
always bears intense scrutiny when applied in a practical situation.
In the design of ISO ISLISP, it was seriously proposed that the
language have only some of the set of six comparison operators. Then,
like a cancer, people turned to the trig functions and started wanting
to remove TAN because SIN and COS should be enough. But serious
applied mathemeticians don't implement TAN by combining SIN and
COS because it introduces unwanted errors needlessly. And real people
prefer the flexibility of choosing <= rather than (not (> ...)), if
for no other reason than that it maps better. It just isn't enough
savings to be worth the pain when you leave this out. And what about
unary minus? There are languages where you write 0-1 rather than -1
because it saves them unary minus. But it makes it hard to get -0.0,
which is not gotten by 0-0.0.
I could go on, but hopefully I've made my point.
From: Marcus Breiing
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <e8icsg$3dq$2@chessie.cirr.com>
Kent M Pitman <······@nhplace.com> writes:
> [simulate AREF with LAMBDA and get O(1)]
> I won't spoil it by offering the answer here. I'll leave it for now as
> an exercise to the reader, partly for the fun of it and partly to see if
> others have a differing take.
How to get confused over this problem, and how to solve it, depends on
what assumptions we make in order to believe (or know) that our
primitive AREF is O(1). Searching for how it is done in Common Lisp,
we find ARRAY-DIMENSION-LIMIT. We can do *that* with LAMBDA, too.
--
Marcus Breiing
Kent M Pitman wrote:
>
> The one puzzle that baffled me relentlessly at the time, and that I
> only sorted out years later, was array reference. I repeatedly
> modeled it with LAMBDA in various ways but I was led over and over to
> the inevitable and annoying conclusion that the time it should take is
> O(log(n)) and I could never figure out how to squeeze O(1) out of it.
> It seemed weird and unsatisfying to say that LAMBDA and AREF were
> needed to be minimal. It took me until years later to discover the
> source of my confusion.
>
> I won't spoil it by offering the answer here. I'll leave it for now as
> an exercise to the reader, partly for the fun of it and partly to see if
> others have a differing take.
No takers? I was puzzled by this, too, but I came to a conclusion that
turned out to be the same one that Kent came to. An interesting
implication is that hash tables must be O(log(n)) rather than the
commonly believed O(1).
On 6 Jul 2006 09:51:00 -0700, "Joe Marshall" <··········@gmail.com> wrote:
>
>Kent M Pitman wrote:
>>
>> The one puzzle that baffled me relentlessly at the time, and that I
>> only sorted out years later, was array reference. I repeatedly
>> modeled it with LAMBDA in various ways but I was led over and over to
>> the inevitable and annoying conclusion that the time it should take is
>> O(log(n)) and I could never figure out how to squeeze O(1) out of it.
>> It seemed weird and unsatisfying to say that LAMBDA and AREF were
>> needed to be minimal. It took me until years later to discover the
>> source of my confusion.
>>
>> I won't spoil it by offering the answer here. I'll leave it for now as
>> an exercise to the reader, partly for the fun of it and partly to see if
>> others have a differing take.
>
>No takers? I was puzzled by this, too, but I came to a conclusion that
>turned out to be the same one that Kent came to. An interesting
>implication is that hash tables must be O(log(n)) rather than the
>commonly believed O(1).
I'm not disputing that assertion, but here's an example of a paper
(an exercept from the SUGI 28 conference proceedings):
http://www2.sas.com/proceedings/sugi28/004-28.pdf
wherein the authors assert that a key-indexed search is O(1).
Are you guys assuming overhead due to cache misses or some
real-world hardware issue like that? My knowledge of the
theory on this stuff is too weak, so I'm genuinely curious
to know.
--
Jack Unrue
Jack Unrue wrote:
>
> I'm not disputing that assertion, but here's an example of a paper
> (an exercept from the SUGI 28 conference proceedings):
>
> http://www2.sas.com/proceedings/sugi28/004-28.pdf
>
> wherein the authors assert that a key-indexed search is O(1).
>
> Are you guys assuming overhead due to cache misses or some
> real-world hardware issue like that? My knowledge of the
> theory on this stuff is too weak, so I'm genuinely curious
> to know.
The conclusion that Kent and I reached is that we neglected the fact
that arithmetic is O(log(n)). Most hardware does arithmetic so fast
that it has to delay latching the result until the next clock tick. In
effect, it pads out the operation to be constant worst-case time.
There are similar effects in memory addressing.
From: Alexander Schmolck
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <yfsac7miixi.fsf@oc.ex.ac.uk>
"Joe Marshall" <··········@gmail.com> writes:
> Kent M Pitman wrote:
> >
> > The one puzzle that baffled me relentlessly at the time, and that I
> > only sorted out years later, was array reference. I repeatedly
> > modeled it with LAMBDA in various ways but I was led over and over to
> > the inevitable and annoying conclusion that the time it should take is
> > O(log(n)) and I could never figure out how to squeeze O(1) out of it.
> > It seemed weird and unsatisfying to say that LAMBDA and AREF were
> > needed to be minimal. It took me until years later to discover the
> > source of my confusion.
> >
> > I won't spoil it by offering the answer here. I'll leave it for now as
> > an exercise to the reader, partly for the fun of it and partly to see if
> > others have a differing take.
>
> No takers? I was puzzled by this, too, but I came to a conclusion that
> turned out to be the same one that Kent came to. An interesting
> implication is that hash tables must be O(log(n)) rather than the
> commonly believed O(1).
Well, my immediate reaction on reading this was that memory access can't be
constant time unless the amount of memory is bounded (it would violate the
laws of physics and you'd also need constant time bignum operations). And if
you've got a finite amount of memory and hence a finite array-total-size-limit
you can just e.g. use a search that is say linear in array-total-size-limit
(as opposed to N, the number of items of the array that is being indexed, e.g.
simply by doing a linear search and pessimizing the lookup of all items to be
uniformly bad, e.g. do a linear search for item N-i, discard the result and
then search for item i and return it). That gives you O(1) array indexing,
since array-total-size-limit is a constant.
I thought there must be something more to it, so I'm curious to hear it now
that everyone has had some time to mull over it.
'as
Alexander Schmolck <··········@gmail.com> writes:
> "Joe Marshall" <··········@gmail.com> writes:
>
>> Kent M Pitman wrote:
>> >
>> > The one puzzle that baffled me relentlessly at the time, and that I
>> > only sorted out years later, was array reference. I repeatedly
>> > modeled it with LAMBDA in various ways but I was led over and over to
>> > the inevitable and annoying conclusion that the time it should take is
>> > O(log(n)) and I could never figure out how to squeeze O(1) out of it.
>> > It seemed weird and unsatisfying to say that LAMBDA and AREF were
>> > needed to be minimal. It took me until years later to discover the
>> > source of my confusion.
>> >
>> > I won't spoil it by offering the answer here. I'll leave it for now as
>> > an exercise to the reader, partly for the fun of it and partly to see if
>> > others have a differing take.
>>
>> No takers? I was puzzled by this, too, but I came to a conclusion that
>> turned out to be the same one that Kent came to. An interesting
>> implication is that hash tables must be O(log(n)) rather than the
>> commonly believed O(1).
>
> Well, my immediate reaction on reading this was that memory access can't be
> constant time unless the amount of memory is bounded (it would violate the
> laws of physics and you'd also need constant time bignum operations). And if
> you've got a finite amount of memory and hence a finite array-total-size-limit
> you can just e.g. use a search that is say linear in array-total-size-limit
> (as opposed to N, the number of items of the array that is being indexed, e.g.
> simply by doing a linear search and pessimizing the lookup of all items to be
> uniformly bad, e.g. do a linear search for item N-i, discard the result and
> then search for item i and return it). That gives you O(1) array indexing,
> since array-total-size-limit is a constant.
>
> I thought there must be something more to it, so I'm curious to hear it now
> that everyone has had some time to mull over it.
It's a question of representation. All we have are functions.
#(a vector of five elements)
may be represented as:
(lambda (f) (f 'a 'vector 'of 'five 'elements))
Then you can index it in O(1) with the following numbers:
(lambda (a b c d e) a)
(lambda (a b c d e) b)
(lambda (a b c d e) c)
(lambda (a b c d e) d)
(lambda (a b c d e) e)
For example, for the second element:
((lambda (f) (f 'a 'vector 'of 'five 'elements))
(lambda (a b c d e) b))
--> vector
Now, of course, if you want to use Church numbers it may be more complicated.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"By filing this bug report you have challenged the honor of my
family. Prepare to die!"
Pascal Bourguignon wrote:
>
> It's a question of representation. All we have are functions.
>
> #(a vector of five elements)
> may be represented as:
>
> (lambda (f) (f 'a 'vector 'of 'five 'elements))
>
> Then you can index it in O(1) with the following numbers:
>
> (lambda (a b c d e) a)
> (lambda (a b c d e) b)
> (lambda (a b c d e) c)
> (lambda (a b c d e) d)
> (lambda (a b c d e) e)
You are assuming that procedure application and variable lookup are
constant time.
"Joe Marshall" <··········@gmail.com> writes:
> Pascal Bourguignon wrote:
>>
>> It's a question of representation. All we have are functions.
>>
>> #(a vector of five elements)
>> may be represented as:
>>
>> (lambda (f) (f 'a 'vector 'of 'five 'elements))
>>
>> Then you can index it in O(1) with the following numbers:
>>
>> (lambda (a b c d e) a)
>> (lambda (a b c d e) b)
>> (lambda (a b c d e) c)
>> (lambda (a b c d e) d)
>> (lambda (a b c d e) e)
>
> You are assuming that procedure application and variable lookup are
> constant time.
These are primitives in lambda calculus, so I think I'm justified to assume so.
--
__Pascal Bourguignon__ http://www.informatimago.com/
The world will now reboot. don't bother saving your artefacts.
Alexander Schmolck wrote:
>
> Well, my immediate reaction on reading this was that memory access can't be
> constant time unless the amount of memory is bounded (it would violate the
> laws of physics and you'd also need constant time bignum operations). And if
> you've got a finite amount of memory and hence a finite array-total-size-limit
> you can just e.g. use a search that is say linear in array-total-size-limit
> (as opposed to N, the number of items of the array that is being indexed, e.g.
> simply by doing a linear search and pessimizing the lookup of all items to be
> uniformly bad, e.g. do a linear search for item N-i, discard the result and
> then search for item i and return it). That gives you O(1) array indexing,
> since array-total-size-limit is a constant.
>
> I thought there must be something more to it, so I'm curious to hear it now
> that everyone has had some time to mull over it.
That's part of it. If there is a known worst-case in an algorithm, you
can claim that it is O(1) provided that you choose a large enough
constant and pad out the fast cases to take longer. (Since big O is an
upper bound anyway, you don't even have to pad out the fast cases.)
Joe Marshall wrote:
> implication is that hash tables must be O(log(n)) rather than the
> commonly believed O(1).
It depends what you're measuring, really. If you're measuring arithmetic
on a (theoretical) processor with unbounded-width registers, it's O(1).
If you're measuring memory lookups on a Turing machine (with no
random-access read-write storage), "array access" isn't close to O(1).
Most people talking about hashtables disregard the cost of generating
the hashes to start with, as regardless of the number of inputs, each is
hashed only once. Unless the size of each input rivals the number of
inputs it's a negligable cost.
--
Darren New / San Diego, CA, USA (PST)
This octopus isn't tasty. Too many
tentacles, not enough chops.
From: Pierpaolo BERNARDI
Subject: Re: Minimal keywords needed for constructing a full CL system
Date:
Message-ID: <op.tb8a5h0rxbm8ci@eraora>
On Tue, 04 Jul 2006 15:50:59 +0200, Javier <·······@gmail.com> wrote:
> What are the strictly minimun set of Lisp commands and/or keywords that
> are needed to recreate a complete CL system?
> I'd like to debate this here, and got some conclusions from you experts.
http://home.pipeline.com/~hbaker1/MetaCircular.html
--
Anything below this line is being added by the newsserver
Pierpaolo BERNARDI <·········@secondbox.net> wrote:
+---------------
| Javier <·······@gmail.com> wrote:
| > What are the strictly minimun set of Lisp commands and/or keywords that
| > are needed to recreate a complete CL system?
| > I'd like to debate this here, and got some conclusions from you experts.
|
| http://home.pipeline.com/~hbaker1/MetaCircular.html
+---------------
That paper isn't really about a "strictly minimum set of Lisp
[special forms]", rather, it's an examination of the non-uniqueness
of any such "minimum set", and how some "basic" special forms
can be expressed in terms of others no more or less "basic".
And as I said in a parallel reply, even it doesn't do nearly a
complete job -- it just points the reader at the enormity of the
available design space within which one has to make tradeoffs and
eventually "just pick something" as the basis set for a specific
implementation.
Still very much worth reading, of course... ;-} ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607