I have been working on a unique hobby Lisp engine for the past few
years (on and off), and I am thinking of publishing it on the
internet, but want to make it more CL compatable first.
Is there a COMPLETE listing of the true Common Lisp "Primitaves"
(functions that cannot be created from other Lisp functions) somewhere
on the internet? (or in a book)
I know I could not posibly have the time to completly implement every
CL function in the standard myself, but if I implement ALL of the
'Primitaves' used by CL, leaves the posibility of any CL function
implementation. (and importing function libraries from other sources?)
Any help would be appreciated.
sh0rty :P
··············@yahoo.ca (sh0rty) writes:
> I have been working on a unique hobby Lisp engine for the past few
> years (on and off), and I am thinking of publishing it on the
> internet, but want to make it more CL compatable first.
>
> Is there a COMPLETE listing of the true Common Lisp "Primitaves"
> (functions that cannot be created from other Lisp functions) somewhere
> on the internet? (or in a book)
I don't know of anything online, but in Paul Graham's "ANSI Common
Lisp", I think he has an appendix where he provides example
implementations of a lot of the language in terms of a small,
primitive subset. Probably worth a look.
Don't be fooled into thinking that the small size of the subset makes
it easy to get from there to the type system and exception system, for
example.
> I know I could not posibly have the time to completly implement every
> CL function in the standard myself, but if I implement ALL of the
> 'Primitaves' used by CL, leaves the posibility of any CL function
> implementation. (and importing function libraries from other sources?)
I suppose you could look at it that way :). It's possible, if too
easy, to port lots of CMUCL to another compiler. That, and the fact
that I'm intentionally keeping a CMUCL-like approach to things, unless
I have a reason to differ, is why I consider the Lisp system I'm
working on to be CMUCL-derived. No Python, but there's more to it
than just Python.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
There is an entry on that subject in the Lisp FAQ:
http://www.landfield.com/faqs/lisp-faq/part1/section-6.html
But it doesn't give the list of all the primitives, so it may not be of
much help to you...
--Matthieu
sh0rty wrote:
>
> I have been working on a unique hobby Lisp engine for the past few
> years (on and off), and I am thinking of publishing it on the
> internet, but want to make it more CL compatable first.
>
> Is there a COMPLETE listing of the true Common Lisp "Primitaves"
> (functions that cannot be created from other Lisp functions) somewhere
> on the internet? (or in a book)
>
> I know I could not posibly have the time to completly implement every
> CL function in the standard myself, but if I implement ALL of the
> 'Primitaves' used by CL, leaves the posibility of any CL function
> implementation. (and importing function libraries from other sources?)
>
> Any help would be appreciated.
>
> sh0rty :P
+ ··············@yahoo.ca (sh0rty):
| Is there a COMPLETE listing of the true Common Lisp "Primitaves"
| (functions that cannot be created from other Lisp functions)
| somewhere on the internet? (or in a book)
I doubt it very much: What is a "primitive" is very much up to the
implementor. In fact, I doubt that that you could in fact make an
implementation of CL out of "primitives" in your sense. You could
perhaps find three functions A, B and C so that any two of them is
sufficient to implement the third, but no single one of them is
sufficient. By your definition none of them would be a primitive, yet
if we leave them out, what is left is insufficient. Thus I claim,
with almost total certainty, that there exist more than one minimal
sufficient set of functions in CL (where "sufficient" means you could
build all of CL from the given set, and "minimal" means that no proper
subset would be sufficient).
Another reason I doubt you'll find such a list is that the CL folks
are very practical people, and I doubt that questions about minimal
sets of functions appeal to them any more that questions about the
number of angels that can dance on the head of a pin. Heck, it
doesn't even appeal to me, and as a mathematician, I am supposed to be
attracted to abstract existence questions. But this one has such a
mix of real-world messiness and useless abstraction that I personally
really couldn't care less.
Yet another reason is that even such "obvious" primitives as cons, car
and cdr aren't all that obviously primitive:
(defun kons (a b)
#'(lambda (f) (funcall f a b)))
(defun kar (kons-or-nil)
(and kons-or-nil
(funcall kons-or-nil
#'(lambda (a b) (declare (ignore b)) a))))
(defun kdr (kons-or-nil)
(and kons-or-nil
(funcall kons-or-nil
#'(lambda (a b) (declare (ignore b)) b))))
(defvar foo (kons 1 (kons 2 3)))
(kar foo) ==> 1
(kdr foo) ==> #<A function>
(kar (kdr foo)) ==> 2
(kdr (kdr foo)) ==> 3
(Okay, you'll have a hard time to implement konsp, I'll grant you
that. You'd have to play some games with the type system to make a
definition like this work in every aspect. But I digress.)
| I know I could not posibly have the time to completly implement every
| CL function in the standard myself, but if I implement ALL of the
| 'Primitaves' used by CL, leaves the posibility of any CL function
| implementation.
The bottom line is, you'd just have to find a sufficient set and
implement it; it's a lot easier. You could look at the source of,
say, CMU CL for some hints.
But seriously, while I am sure building a Lisp system may be an
interesting learning experience, I think you'd quickly reach a point
where it ceases to be such and just becomes a chore - or even worse, a
sort of obsession that keeps you from doing something useful with your
life. If I were you, I'd rather get to know a good, existing Lisp
system and try to build something really neat with it - something that
nobody made before, and which solves a real problem. Amateur Lisp
systems are a dime a dozen. If you could only think of the right
project, you could both have fun and do the world a service - and
maybe even make a living while you're at it.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Yes it works in practice - but does it work in theory?
In article <····························@posting.google.com>,
sh0rty <··············@yahoo.ca> wrote:
>Is there a COMPLETE listing of the true Common Lisp "Primitaves"
>(functions that cannot be created from other Lisp functions) somewhere
>on the internet? (or in a book)
There's no official list of which CL functions are primitives and which are
derived. Different implementations probably divide it up differently.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
sh0rty wrote:
>
> I have been working on a unique hobby Lisp engine for the past few
> years (on and off), and I am thinking of publishing it on the
> internet, but want to make it more CL compatable first.
>
> Is there a COMPLETE listing of the true Common Lisp "Primitaves"
> (functions that cannot be created from other Lisp functions) somewhere
> on the internet? (or in a book)
>
> I know I could not posibly have the time to completly implement every
> CL function in the standard myself, but if I implement ALL of the
> 'Primitaves' used by CL, leaves the posibility of any CL function
> implementation. (and importing function libraries from other sources?)
Many of the earlier posters have correctly opined that there is no
prescribed set of primitives and have included some clever examples.
It is, of course, still instructive to examine particular sets of
primitives to learn how they make up a complete set.
But you and everyone else I have read so far on this thread seems to
have missed the disctinction between "functions" and "operators".
here is nothing special about any of the functions in Common Lisp.
The whole point of being a function is that the way a function is
called and the way it argument subforms is completely regular and
determined. What the function does inside is opaque to the caller.
The poster who mentioned that either if or cond could be implemented
as a macro in terms of the other was correct, but he didn't mention
the subtle point that neither of these may be implemented as a function.
Consider:
(defun bogus-if (pred true false)
(cond (pred true)
(t false)))
This is not the same as if, as in:
(if (oddp x) (incf *odd*) (incf *even*))
So, if you're implementing a Common Lisp one of the first things you
need to consider is the set of "special operators" (previously known
as "special forms"). This set is precisely defined by the CL ANS,
and these are the operators that a CL compiler, evaluator, or any
other code walker must implement.
* "Steven M. Haflich" <·······@pacbell.net>
| So, if you're implementing a Common Lisp one of the first things you
| need to consider is the set of "special operators" (previously known
| as "special forms").
Strictly speaking, (if ...) is a special form, while if is (or names) a
special operator.
///
--
In a fight against something, the fight has value, victory has none.
In a fight for something, the fight is a loss, victory merely relief.
In article <·················@pacbell.net>, ···@alum.mit.edu wrote:
> But you and everyone else I have read so far on this thread seems to
> have missed the disctinction between "functions" and "operators".
> here is nothing special about any of the functions in Common Lisp.
> The whole point of being a function is that the way a function is
> called and the way it argument subforms is completely regular and
> determined. What the function does inside is opaque to the caller.
>
> The poster who mentioned that either if or cond could be implemented
> as a macro in terms of the other was correct, but he didn't mention
> the subtle point that neither of these may be implemented as a function.
I didn't mention it, but I had it in mind, which is why I included
another example using functions (cons, car, cdr).
> there is nothing special about any of the functions in Common Lisp.
Well, that's not true. Unless you want to get into implementing Church
Numerals yourself, the arithmetic functions such as "+" are certainly
pretty special.
In theory, you don't need *anything* but "lambda", but compiler
technology isn't quite up to making that as efficient as having a few
things built in -- it's just that there's no unique set of those "few
things". Even in arithmetic, you don't need both "+" and "-" as long as
you have one of them and unary negation.
-- Bruce
So we have all determined that there is no "set in stone" list of
promitives. What are a common set "built in" of functions to included
in the creation of an interpreter.
It will be an interpreter only (for now), and I have already found
that implementing certan functions (often not "Primitaves") being
"built in" to the interpreter (written in Delphi) is MUCH more
efficient. (ie. NTH being hardcoded into the interpreter showed to be
much more efficient than recursive LISP function using CAR and CDR
"primitives" when used in REALY long lists)
So any suggestions on what functions you think should be "built in" to
the interpreter would be appreciated.
sh0rty :P
sh0rty wrote:
> So any suggestions on what functions you think should be "built in" to
> the interpreter would be appreciated.
sh0rty, there are at least four implementations out there that I am aware
of that have source code available (CMUCL/SBCL, GCL, CLisp, Corman Lisp).
All of these have C-language RT's used to bootstrap the system. There are
probably more of them. And this does not count the Scheme systems out
there (no they're not Lisp, but they often have many of the same issues WRT
choosing primitive sets). There is also available 40 odd years of
interpreter knowledge in various papers, journals, symposia, and what not.
I suggest that, rather than trying to get us to do your research for you,
post a proposed set of primitives and we'll critique it and let you know if
you're on the right track.
Feeling in a magnanimous mood, I will start you off in saying that you'll
probably at least need object allocation and GC with both byte-level and
pointer-level indexing. In addition, you'll probably need some way of
dealing with direct OS pointers (to deal with external I/O libraries,
unless you like file descriptors a lot), some sort of trampolining
mechanism to call OS functions, and some sort of stack-like mechanism for
call contexts. Finally, you'll need some sort of control primitives to
build IF and GO, and probably some support for building and throwing
exceptions (include that code for searching back up the stack to find the
handlers, too). And don't forget the killer set of floating-point and
complex arithmetic functions you'll need if you want any sort of speed.
Speaking of speed (and usability, because hand coding functions can get to
be SUCH a pain after a while), you'll need a reasonably decent compiler.
Now toss in read (plus simple readtable support) and a symbol table. Add
in enough support to do somewhat fast GF dispatch for CLOS and you're
almost halfway to a decent Lisp implementation.
Anyway, that's where I'd start unless I wanted to make the compiler REALLY
smart. If that's the case, I'd just start with objects and slot access, a
GC, a trampoline mechanism and a minimal set of control, logic, and
arithmetic primitives and then let the compiler do the work.
faa
··············@yahoo.ca (sh0rty) writes:
> So we have all determined that there is no "set in stone" list of
> promitives. What are a common set "built in" of functions to included
> in the creation of an interpreter.
>
> It will be an interpreter only (for now), and I have already found
> that implementing certan functions (often not "Primitaves") being
> "built in" to the interpreter (written in Delphi) is MUCH more
> efficient. (ie. NTH being hardcoded into the interpreter showed to be
> much more efficient than recursive LISP function using CAR and CDR
> "primitives" when used in REALY long lists)
>
> So any suggestions on what functions you think should be "built in" to
> the interpreter would be appreciated.
I don't know that very many serious Lisp implementation are
interpreters. For some purposes, I prefer the term virtual machine,
which is neutral as to the question of whether a compiler or an
interpreter will be accessing its services.
There is no end to the set of functions that need to be "built in", I think.
For example, every time you need a new primitive behavior (such as "opening
a file", "manipulating a robot arm", "calling an elevator", "blinking the
lights in the room", "scanning a page of paper", etc. you will need a new
primitive function). You will never enumerate that set, so you will never
finish.
The question of what should be "built in" for efficiency is also not
just an issue of language simplicity. It's as much a statement of
which kinds of programs you plan to encourage people to write. Some
people, for example, encourage people never to use car/cdr, while
others strongly emphasize it. Whether you want to include special
support for NTH in your virtual machine depends a lot on what you want
to encourage. IMO, NTH is almost always the wrong thing to use, so I
would never bother to optimize it in any virtual machine I wrote--not
that I spend my time writing virtual machines.
The only sense in which you are going to get any finite list is to
enumerate the language glue (the special operators out of which macros
can usefully compose all other "language glue"). These things are the
things compilers and interpreters need to understand in order to
compile programs down into code for a virtual machine. Functions can
be black-boxed from the point of view of a virtual machine and added
from the outside.
In article <····························@posting.google.com>,
··············@yahoo.ca (sh0rty) wrote:
> Is there a COMPLETE listing of the true Common Lisp "Primitaves"
> (functions that cannot be created from other Lisp functions) somewhere
> on the internet? (or in a book)
There is no such thing. It's impossible to define.
For example, under your definition, neither "if" nor "cond" can be
primitive, since either can be defined using the other.
For that matter, none of "cons", "car" and "cdr" are prmitive, since
they can be defined using a closure:
(defun cons (car cdr) (lambda (sel) (if sel car cdr)))
(defun car (p) (funcall p t))
(defun cdr (p) (funcall p nil))
If you're asking which functions are *normally* primitive then that's a
different matter :-)
-- Bruce
From: Tim Bradshaw
Subject: Re: Complete list of CL Primitaves?
Date:
Message-ID: <ey3d6z1zvaf.fsf@cley.com>
* Bruce Hoult wrote:
> For example, under your definition, neither "if" nor "cond" can be
> primitive, since either can be defined using the other.
However CL has chosen to make IF primitive and COND a macro.
... But of course a system is free to actually treat COND as a
primitive so long as the macro expansion is available...
--tim