From: ·······@ipfe.bau-verm.uni-karlsruhe.de (Wolfgang von Hansen)
I am interested in the set of basic primitives that a lisp interpreter
needs. `Basic primitives' are (this is my definition) all those functions
that can not be derived from other functions that are already known.
Example:
If CAR is a basic primitive then CAAR := (CAR (CAR list)) is not.
I am asking because I am planning to implement an experimental lisp
interpreter. It will have all basic primitives implemented via assembler.
All other lisp functions will then defined in lisp itself. Please don't
tell me that this approach will be awful slow, because it is intended to
use this special ability of lisp to extend itself to a large system with
only a small non-lisp kernel.
I think the minimum set is something like this:
READ-TURING-TAPE-AND-BRANCH-IF-0
WRITE-0-ON-TAPE
WRITE-1-ON-TAPE
STEP-LEFT
STEP-RIGHT
You can write the rest of Lisp in that, except maybe for FORMAT. :-)
-- Scott
P.S. The serious point is that you probably don't really want the most
primitive set of operations, but something a bit higher up, even though you
asked people not to tell you this.
===========================================================================
Scott E. Fahlman Internet: ····@cs.cmu.edu
Senior Research Scientist Phone: 412 268-2575
School of Computer Science Fax: 412 681-5739
Carnegie Mellon University Latitude: 40:26:33 N
5000 Forbes Avenue Longitude: 79:56:48 W
Pittsburgh, PA 15213
===========================================================================
In article <············@cs.cmu.edu> ···@sef-pmax.slisp.cs.cmu.edu writes:
>
> Example:
> If CAR is a basic primitive then CAAR := (CAR (CAR list)) is not.
>
> [most of my original posting deleted]
>I think the minimum set is something like this:
>
>READ-TURING-TAPE-AND-BRANCH-IF-0
>WRITE-0-ON-TAPE
>WRITE-1-ON-TAPE
>STEP-LEFT
>STEP-RIGHT
Oops. I seem to have crossposted this to alt.machines.turing accidently.
>P.S. The serious point is that you probably don't really want the most
>primitive set of operations, but something a bit higher up, even though you
>asked people not to tell you this.
Want I really want is the basic set of LISP instructions that are
necessary (sp?) to build a complete set of all functions. The best thing
would be a tree to see on which other functions a given function depends.
Wolfgang
--
·······@ipf.bau-verm.uni-karlsruhe.de | Gurus use `cat >a.out' instead of gcc
float o=0.075,h=1.5,T,r,O,l,I;int _,L=80,s=3200;main(){for(;s%L||
(h-=o,T= -2),s;4 -(r=O*O)<(l=I*I)|++ _==L&&putchar(*((--s%L?_<L?--_
%6:6:7)+"World! \n"))&&(O=I=l=_=r=0,T+=o /2))O=I*2*O+h,I=l+T-r;}
Wolfgang> Want I really want is the basic set of LISP instructions
Wolfgang> that are necessary (sp?) to build a complete set of all
Wolfgang> functions.
I think Scott Fahlman understood your question quite well. It is just
very academic.
What kind of Lisp are you interested in? For Common Lisp, there are
lots of `elementary' functions that you cannot write in terms of the
others (GET-UNIVERSAL-TIME, READ-CHAR, OPEN, CLOSE and dozens or
hundreds of others similar ones).
Wolfgang> The best thing would be a tree to see on which other
Wolfgang> functions a given function depends.
There are many different ways to structure this. For example, a
`minimal implementation' might represent all Lisp data internally as
conses out of NILs and Ts(*).
An `external' positive integer N could for example be represented
internally by a list of as a CONS of NIL and a list of N Ts:
0 -> ( nil . nil )
1 -> ( nil . ( t ))
2 -> ( nil . ( t t ))
Negative integers, rationals, floats, complexes, lists, arrays,
strings, symbols and characters could be represented similarly - just
use a different type marker than NIL.
Then you could certainly write a lot of stuff in terms of CONS, CAR,
CDR, QUOTE, ATOM, EQL and COND (or IF). Everything (even arithmetic)
would simply have to be implemented in terms of list operations. You
could certainly build an EVAL function that way, if you have enough
time and willpower. You could make this interpreter arbitratily
powerful, so that it handles closures, continuations, everything.
Would you call such a system a Lisp?
If you later want I/O and other such theoretically uninteresting but
useful in practice stuff, you can write (in assembler if you want) the
low-level functions like READ-CHAR, WRITE-CHAR, OPEN-FILE, CLOSE
etc. that accept the internal representation you chose. It should be
obvious that you can already write READ-LINE, READ, PRINT, FORMAT,
LOAD etc. in terms of these.
Real Lisp implementations are built upon many low-level primitives
that are not part of any Lisp standards (SYS:%POINTER-REF and such).
--
Simon.
*) You can also use just NILs if you want to be even more perverse.
Simon> Then you could certainly write a lot of stuff in terms of CONS,
Simon> CAR, CDR, QUOTE, ATOM, EQL and COND (or IF).
Hm, I should have been more careful. You want a way to define
recursive functions, for example LAMBDA and LETREC.
On the other hand, ATOM is not primitive in this restricted
representation:
ATOM <=> (LAMBDA (X) (IF (EQL X NIL) T (IF (EQL X T) T NIL)))
And EQL could be replaced by EQ. QUOTE isn't necessary either if T
and NIL are self-evaluating (or evaluate to each other :-).
--
Simon.
In article <··················@liasg3.epfl.ch>,
·····@lia.di.epfl.ch (Simon Leinen) writes:
> I think Scott Fahlman understood your question quite well. It is just
> very academic.
That's how I read his msg, too. You can look at Forth in the
same way, and some portable implementations can do just that,
tho they'd be much slower than necessary. You can also go to
the other extreme, and write as much as possible in a low
level language like C or assembly. Real Forth systems are
somewhere in between, and I imagine that mosts Lisps are
similarly in between the extremes.
No two Forth programmers I know will agree on which words
should be the ones written in assembly. :-)
If you're interest is mainly in the compiler theory and
state machine aspects, then Scott Fahlman's reply was
perfectly correct. A turing machine is just one extreme,
tho more of a theoretical one, as I'm not sure anyone
might build a Turing machine large enough (and fast enough)
for software as complex as a Lisp system.
Please correct me if I'm at all wrong about this, but I
remember something about the costs of running software
on a Turing machine rising steeply as the software
complexity rises. One of the first Lisps I read about
was running on a 16K TRS-80. It wasn't a very sophisticated
Lisp, even for the early 80s, but it may well have been,
for all I know, more complex than would be practical
to implement on a Turing machine such as the one Scott
Fahlman described.
You decide. :-)
> An `external' positive integer N could for example be represented
> internally by a list of as a CONS of NIL and a list of N Ts:
>
> 0 -> ( nil . nil )
> 1 -> ( nil . ( t ))
> 2 -> ( nil . ( t t ))
Alternately, you could use a binary representation:
0 -> ( nil . nil )
1 -> ( nil . ( t ))
2 -> ( nil . ( t nil ))
3 -> ( nil . ( t t ))
4 -> ( nil . ( t nil nil ))
That would work just as well, only faster and use less memory.
You could probably use 10 symbols and write some functions to
use BCD. Once you have a control structure like CASE, that might
be easy to write, tho if you're really making a test for each
digit, then binary would still be best.
Just my ( nil . ( t nil )) worth. :-)
Martin Rodgers
--- Cyber Surfing on CIX ---
In article <··········@nz12.rz.uni-karlsruhe.de> ·······@ipfr.bau-verm.uni-karlsruhe.de (Wolfgang von Hansen) writes:
>In article <············@cs.cmu.edu> ···@sef-pmax.slisp.cs.cmu.edu writes:
>>P.S. The serious point is that you probably don't really want the most
>>primitive set of operations, but something a bit higher up, even though you
>>asked people not to tell you this.
>
>Want I really want is the basic set of LISP instructions that are
>necessary (sp?) to build a complete set of all functions. The best thing
>would be a tree to see on which other functions a given function depends.
I think what Scott was facetiously pointing out is that it's possible to
get extremely primitive. For instance, numbers don't have to be a
primitive data type: you can implement them using lists (perhaps the length
of the list indicates the magnitude of the number, or maybe the list could
contain the binary representation of the number using the symbols OFF and
ON). Remember, you don't need CAR and CDR in order to implement a Lisp,
since Lisps have been implemented in C and assembler, which don't have
them.
I think a more practical response would be to suggest that you look at
Scheme. While it has some functions that can be derived from others, it's
much closer to the basic set than a rich dialect like Common Lisp. The
language specification is short, so it should be pretty easy to go through
it and determine which functions are basic and which are higher level. The
basic functions are probably just the ones that construct and access each
of the data types.
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar
|>
|>If my memory serves me there are seven lisp basic primitives :
|>eval, apply, cons, car, cdr, eq, cond.
|>
|
I think these are the basic primitives, but for a small implementation
I immediately think about two other aspects:
1. What about 'defun' ?
2. (defun apply (function &rest args) (eval (cons function args))) ?
|>I suggest you to read the excellent book "Anatomy of Lisp" (don't
|>remember the author but I think it's name is Allen). This is a "must read"
|>book for everyone who want to understand how lisp works (even if it is a
|>little bit outdated now).
|>
|>If you are interested in a complete implementation, see the xlisp source
|>code available at every major ftp site.
|>
|>David
|>
If you are interested in the devellopment of LISP see also the article
'Evolution of LISP' by Steele and Gabriel. It's ftp-able.
Jens
--------------------------------------------------------------------------------
Dipl.-Ing. Jens Franzen Tel. +49-511-762-5039
Laboratorium fuer Informationstechnologie Fax. +49-511-762-5051
University of Hannover Telex. 923868 unihn d
Schneiderberg 32 Email
D-3000 Hannover ·······@scoop.ims.uni-hannover.de
Fed. Rep. of Germany ·······@mars.lfi-main.uni-hannover.de
--------------------------------------------------------------------------------
>|>
>|>If my memory serves me there are seven lisp basic primitives :
>|>eval, apply, cons, car, cdr, eq, cond.
>|>
>|
>I think these are the basic primitives, but for a small implementation
>I immediately think about two other aspects:
>1. What about 'defun' ?
>2. (defun apply (function &rest args) (eval (cons function args))) ?
[..deleted..]
Ooopss ! Forget apply. Add lambda ...
Hey, I don't use Lisp any more (since at least four years, what a pitty).
Hope my beloved Lisp teacher (D. Ribbens from the University of
Liege in Belgium) will not read this one :-)
>If you are interested in the devellopment of LISP see also the article
>'Evolution of LISP' by Steele and Gabriel. It's ftp-able.
>Jens
David
+---------------------------+----------------------------------+
| David Brabant, | E-MAIL : ·····@tintin.csl.sni.be |
| Siemens Nixdorf, | Phone : +32 41 201 609 |
| Centre Software de Liege, | FAX : +32 41 201 642 |
| 2, rue des Fories, +----------------------------------+
| 4020 Liege, Belgium. | #include "disclaim.hpp" |
+---------------------------+----------------------------------+
> From: ·······@ipfe.bau-verm.uni-karlsruhe.de (Wolfgang von Hansen)
>
> I am interested in the set of basic primitives that a lisp interpreter
> needs. `Basic primitives' are (this is my definition) all those functions
> that can not be derived from other functions that are already known.
>
> Example:
> If CAR is a basic primitive then CAAR := (CAR (CAR list)) is not.
>
> I am asking because I am planning to implement an experimental lisp
> interpreter. It will have all basic primitives implemented via assembler.
> All other lisp functions will then defined in lisp itself. Please don't
> tell me that this approach will be awful slow, because it is intended to
> use this special ability of lisp to extend itself to a large system with
> only a small non-lisp kernel.
>
I don't know if there is a single best minimal set of primitives -
I think a great deal depends on what sort of implementation you
have in mind. Most of Lisp is definable in terms of other Lisp
functions, but there are several choices of a "basis set"
For example, see Dybvig's "Three Implementaion Models for Scheme"
for a justification of *one* particular set of scheme primitives.
( which aren't a minimal set, but perhaps a minimal PRACTICAL set.)
But probably the minimal set would include:
CAR,CDR,CONS ( things to manipulate S expr's )
READ,PRINT ( things to get S expr's in and out )
APPLY, EVAL ( the guts of your interpreter )
And then, you start to get into a more variable set where exactly
what type of Lisp, and your implementation strategy make a difference,
but basically, you need something to manipulate symbols and add
them to the symbol table, etc.
( arithmetic is pretty UN-primitive : If we have IMPLODE and EXPLODE
of symbols, then we can take numbers apart and do decimal addition
and subtraction by table lookup. ;-)
[ I can imagine a more "object-oriented" implementation, where
sequences were a more basic object than lists ( which would be
a particular type of sequence ) and "elt" and "concatenate"
would be more primitive than CAR/CDR/CONS, but even though
this language might be completely Lisp source compatible, there
is a valid argument that it, in fact, isn't "Lisp" ]
- Steve Majewski (804-982-0831) <·····@Virginia.EDU>
- UVA Department of Molecular Physiology and Biological Physics