Last night I had a difficult time falling asleep (getting myself back
on schedule from the late nights surrounding the holidays) and was
thinking. In most Forth systems, very little of the actual language is
written in assembly. Most of it is written in Forth. This, of course,
is true for Lisp as well.
My curiosity is in how much of a (typical, ie commercial) Lisp system
is actually written in Lisp. Now, let me be more specific. I do not
mean the compiler or IDE - these are of course written in Lisp. I mean
to say just the ANSI spec. How much of the spec (%) is just macros
around what might be the "core" of CL? Also, for optimization, how much
*could* be written in CL and isn't? In Forth, for example, there is
actually very little that needs optimized, because the optimizations
build on each other. Taking a specific look at a function, DOTIMES is
nothing more than a declared fixnum LET with a TAGBODY, IF and GO.
I guess, in the end, I'm hoping to define what is the minimum set of
functions that need to be available for the rest of the ANSI CL spec to
be built on top of it? Just with DECLARE, TAGBODY, GO, PROGN, IF,
LAMBDA, LET, and DEFMACRO, quite a bit is already possible... Outside
of scoped functions, how about just type specific ones (CONS, CAR, CDR,
ELT, FIND, etc)?
Jeff M.
"Jeff M." <·······@gmail.com> wrote on 4 Jan 2005 08:32:
> I guess, in the end, I'm hoping to define what is the minimum set of
> functions that need to be available for the rest of the ANSI CL spec to
> be built on top of it? Just with DECLARE, TAGBODY, GO, PROGN, IF,
> LAMBDA, LET, and DEFMACRO, quite a bit is already possible...
But there is no unique minimal set. Many functions can be defined in
terms of others. It's an arbitrary choice about which is primitive and which
is built on top of the others.
Moreover, you have efficiency tradeoffs. Are you just asking whether a
lisp theoretically _could_ be implemented using a few primitive functions?
It is _possible_ to implement arithmetic using only lists to represent numbers,
but any lisp implementation which didn't access the hardware's binary math
would probably be too slow to be useful.
If you're just asking a theoretical question, LAMBDA by itself gets you most
of the way there (perhaps with DEFMACRO for syntax).
If you're asking a practical question, then efficiency concerns suggest more
and more of the language be implemented natively, instead of built on top of
"more primitive" lisp. Not to mention that there are plenty of arbitrary
choices about which parts of lisp you decide are "more" vs. "less" primitive.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
It's easy to go get some lumber and nails and a saw and try to build something.
Anybody can do that. But what's hard is to try to take a nap while someone is
hammering and sawing.
-- Deep Thoughts, by Jack Handey [1999]
Don Geddis <···@geddis.org> writes:
> If you're just asking a theoretical question, LAMBDA by itself gets you most
> of the way there (perhaps with DEFMACRO for syntax).
With some syntax around it, lambda itself should get you the complete
thing. Btw, is there some implementation of lists in lambda calculus
around to look at?
Regards,
--
____________________________
Julian Stecklina / _________________________/
________________/ /
\_________________/ LISP - truly beautiful
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <87is6davs2.fsf@qrnik.zagroda>
Julian Stecklina <··········@web.de> writes:
>> If you're just asking a theoretical question, LAMBDA by itself gets you most
>> of the way there (perhaps with DEFMACRO for syntax).
>
> With some syntax around it, lambda itself should get you the complete
> thing.
No, it doesn't provide I/O.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> Julian Stecklina <··········@web.de> writes:
>
> >> If you're just asking a theoretical question, LAMBDA by itself gets you most
> >> of the way there (perhaps with DEFMACRO for syntax).
> >
> > With some syntax around it, lambda itself should get you the complete
> > thing.
>
> No, it doesn't provide I/O.
Yes and no.
Lambda does not provide I/O on the underlying hardware, but with only
lambda you can write a virtual world where I/O exist and are possible.
So the question is reduced to the actual _target_ "virtual" machine.
You can try to reduce Common-Lisp to some subset of Common-Lisp.
Or you can just write a compiler in Common-Lisp that generates the
"native" code for the target machine, and bootstrap from it, adding
only a couple of FFI functions/features (just what is needed to start
running the generated bytes as a function). Actually, if you accept
to bootstrap thru the system launcher, you would just need to write an
executable file and let the user start the new lisp image.
So you can use anything, from LAMBDA to the whole Common-Lisp as a
base to bootstrap/implement Common-Lisp. The exact "core" subset used
will depend on the target machine you choose and your degree of masochisms.
--
__Pascal_Bourguignon__ _ Software patents are endangering
() ASCII ribbon against html email (o_ the computer industry all around
/\ 1962:DO20I=1.100 //\ the world http://lpf.ai.mit.edu/
2001:my($f)=`fortune`; V_/ http://petition.eurolinux.org/
Pascal Bourguignon wrote:
> Lambda does not provide I/O on the underlying hardware, but with only
> lambda you can write a virtual world where I/O exist and are possible.
What follows is admittedly a digression to a side issue.
Some time before the first LBJ administration I learned the following
computer problem. Statistically, most readers of this list weren't
born then, so it may be useful to circulate it again.
Imagine a virtual machine that has been optimized to reduce the number
of bits wasted on op codes. In particular, this single-accumulator
machine implements only _one_ opcode, a 3-address operation:
subtract a1 and store in a2 and if negative branch to a3
so the number of bits wasted on the opcode is zero.
Clearly a winning design, provided that I/O can be done by referencing
specific hardware addresses (thank the company formerly known as Compaq
which was the company formally known as DEC for this innovation). Your
task is to write a FORTRAN compiler for this hardware, and as part of
that design you must figure out what code to generate for the statement
A = B + C
Please show in generic assembly language the 8 instructions that
implement this statemet.
For extra credit, explain succinctly why the machine could not be
implemented with this single instruction:
ADD a1 and store in a2 and if negative branch to a3
[Hint: Familiarity with XML is not necessary to answer this question.]
Steven Haflich wrote:
> Imagine a virtual machine that has been optimized to reduce the number
> of bits wasted on op codes. In particular, this single-accumulator
> machine implements only _one_ opcode, a 3-address operation:
>
> subtract a1 and store in a2 and if negative branch to a3
>
> so the number of bits wasted on the opcode is zero.
Let me just check that I've understood this: call the
accumulator X; then the operation <a1,a2,a3>, if stored
at a0, does the following:
X := X - [a1]
[a2] := X
if X<0, go to a3; else go to a0+1
where [] indicates memory lookup. And the accumulator
has no address. Is that right?
And I take it there's some conventional way to indicate
that computation is finished, though it's not clear to me
what that is.
> Clearly a winning design, provided that I/O can be done by referencing
> specific hardware addresses (thank the company formerly known as Compaq
> which was the company formally known as DEC for this innovation). Your
> task is to write a FORTRAN compiler for this hardware, and as part of
> that design you must figure out what code to generate for the statement
>
> A = B + C
>
> Please show in generic assembly language the 8 instructions that
> implement this statemet.
Nice problem. Solution follows after spoiler space.
...
...
...
...
Let alpha, beta, gamma be the addresses assigned
to the variables A, B and C. Also, let p,q be
the addresses of two scratch locations. In the
comments, X denotes the accumulator; x0 and p0
are the initial values of X and [p].
0 <p,p,1> ; [p] = X = x0-p0, say
1 <p,p,2> ; [p] = X = 0
2 <beta,p,3> ; [p] = X = -B
3 <gamma,p,4> ; [p] = X = -(B+C)
4 <p,q,5> ; [q] = X = 0
5 <alpha,p,6> ; A = X = B+C
That's only 6 instructions, so maybe I misunderstood
the capabilities of your machine. There are no conditional
branches, though of course they would be needed for other
purposes.
> For extra credit, explain succinctly why the machine could not be
> implemented with this single instruction:
>
> ADD a1 and store in a2 and if negative branch to a3
If initially all locations contain non-negative values,
then (by induction) the same is always true. Therefore
this machine cannot compute (e.g.) the function x -> -x.
That assumes (1) that we aren't allowed to pre-populate
the machine's memory, and (2) that it doesn't have any
wraparound feature that would enable negative numbers
to be produced by adding positive ones. Oh, and (3) that
program memory isn't usably writeable and data memory
isn't usably executable.
What happens if #3 is relaxed depends strongly on the
instruction encoding. Let's not go there.
Suppose #2 is relaxed in the traditional way: the values
the machine operates on are integers modulo 2^N, for some
value of N, and "negative" means "top bit set". Then we
can implement your original operation in terms of the new
one, thus:
;; Do this once, at program start:
0 add zero, store zero ; [zero] = X = x0+zero0
1 add zero, store zero ; [zero] = X = 2(x0+zero0)
2 add zero, store zero ; [zero] = X = 4(x0+zero0)
...
N add zero, store zero ; [zero] = X = 0
;; now here's how to do the subtract-store-branch op:
n add zero, store oldx ; [oldx] = X = x0
n+1 add a1, store p ; [p] = X = 1(x0+[a1]) <-- 2^1-1
n+2 add p, store q ; [q] = X = 2(x0+[a1])
n+3 add p, store q ; [q] = X = 3(x0+[a1]) <-- 2^2-1
n+4 add q, store q ; [q] = X = 6(a0+[a1])
n+5 add p, store q ; [q] = X = 7(a0+[a1]) <-- 2^3-1
...
n+2N-1 add q, store q ; [q] = X = -(a0+[a1]) <-- 2^N-1
n+2N add oldx, store q ; [q] = X = -[a1]
n+2N+1 add oldx, store a2, branch a3
(I've assumed, pseudo-realistically, that it's reasonable
to take O(N) times more instructions but not O(2^N) times more.)
Suppose #1 is relaxed instead. I claim that if the (variable)
data are all large enough then no "if negative" branch whose
outcome depends on the data is ever taken. Proof: suppose the
earliest this can happen is at time t, and at instruction i.
Then for large enough data nothing up to time t involves a
conditional branch depending on the data, and therefore the
machine state up to time t is a monotone nondecreasing function
of the data. Therefore either the branch at time t is always
taken, or it is always untaken for large enough data values.
So, by induction, for any *fixed* time t we can arrange that
no possibly-not-taken branch is ever actually-taken by making
the data large enough. In other words, the path taken through
the program is the same for all large-enough data. This
implies that unless the program unconditionally loops for
ever, there's an upper bound on how long it can compute
for, which in turn implies that no possibly-not-taken branch
is ever actually-taken at all. Which means that the output is
a monotone nondecreasing function of the input for large enough
data. Which means that we can't compute x -> -x.
> [Hint: Familiarity with XML is not necessary to answer this question.]
:-)
--
Gareth McCaughan
.sig under construc
I wrote:
> Steven Haflich wrote:
>
> > Imagine a virtual machine that has been optimized to reduce the number
[etc]
...
> Let me just check that I've understood this: call the
> accumulator X; then the operation <a1,a2,a3>, if stored
> at a0, does the following:
[etc]
Steven, if you're reading this: did I understand your
intention correctly? The fact that I took 6 instructions
for what you said should take 8 worries me. (And I suspect
that you may have had something cleverer in mind for the
"extra credit" bit.)
--
Gareth McCaughan
.sig under construc
From: Edi Weitz
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <u8y79ymx1.fsf@agharta.de>
On Tue, 04 Jan 2005 09:54:16 -0800, Don Geddis <···@geddis.org> wrote:
> But there is no unique minimal set. Many functions can be defined
> in terms of others. It's an arbitrary choice about which is
> primitive and which is built on top of the others.
Just for fun:
<http://home.pipeline.com/~hbaker1/MetaCircular.html>
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
From: Will Hartung
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <340rfqF44omacU1@individual.net>
"Jeff M." <·······@gmail.com> wrote in message
·····························@z14g2000cwz.googlegroups.com...
> In Forth, for example, there is actually very little that needs optimized,
> because the optimizations build on each other. Taking a specific look at a
> function, DOTIMES is nothing more than a declared fixnum LET with a
> TAGBODY, IF and GO.
There's a difference.
In Forth, and pretty much most other languages, abstraction will cost you
because each abstraction layers upon another abstraction until you get to
the actual primitives. Forth (notably the classic interpreters) is the
classic example of this since, as you said, most of the primitives are
written in assembly, and then the rest of the system is written on top of
the primitives.
However, if you then "decompiled" the high level Forth words, you'd see
references to the respective words that make up the higer level words. The
interpreter then de-references those until it finally hits a primitive that
it can run. Each of those de-references has a cost.
Now, in Lisp, and in this case DOTIMES, you have MACROs as your medium for
abstraction. The key difference is that the MACRO actually rewrites the code
before it gets to the lower level runtime (typically a compiler). Therefore
you take your peformance hit at compile time rather than at run time (modulo
the most crude of Lisp interpreters that macroexpand while interpreting...).
Of course, you'll get a space hit, as macros are large than subroutine
calls.
> I guess, in the end, I'm hoping to define what is the minimum set of
> functions that need to be available for the rest of the ANSI CL spec to
> be built on top of it? Just with DECLARE, TAGBODY, GO, PROGN, IF,
> LAMBDA, LET, and DEFMACRO, quite a bit is already possible... Outside
> of scoped functions, how about just type specific ones (CONS, CAR, CDR,
> ELT, FIND, etc)?
The other issue is that, particularly with the COMMON-LISP package, compiler
writers can make some assumptions about the behavior of specific symbols,
and optimize around that. obvious examples are primitives like CAR and +
etc.
The real question is simply "how little Lisp do I need to create a
self-hosting Lisp compiler". Once you have a CL compliant Lisp subset, then
at that point you can you can wean the compiler off of its Full CL parent
and continue development on its own.
Of course, you can look at the Scheme camp, which is very minimalistic, but
it doesn't have the same semantics as CL.
You can also consider trying to hunt down all of the Special Forms within
the standard, that would also give you an idea, though it's not clear how
realistic this is as there are some things are not special forms but may
well be difficult to implement solely as functions on top of the other
special forms (for example, the I/O routines are simply functions but
couldn't be implemented without some external interfacing with the run
time).
The biggest problem is simply that CL evolved and was not designed. If it
was designed, you would be able to see a distinct layer between the original
core and what was added on later. But whe you write Lisp systems on top of
Lisp systems, you get self-referential balls of code orbiting and circling
around each other rather than a nice, layered system.
Regards,
Will Hartung
(·····@msoft.com)
"Will Hartung" <·····@msoft.com> writes:
> In Forth, and pretty much most other languages, abstraction will
> cost you because each abstraction layers upon another abstraction
> until you get to the actual primitives. Forth (notably the classic
> interpreters) is the classic example of this since, as you said,
> most of the primitives are written in assembly, and then the rest of
> the system is written on top of the primitives.
Forth compilers today are much smarter than this. They can generate
high performance native code without the traditional token threading.
Inlining can and does happen. Plus the function call overhead in
Forth is very little compared with C or even more so Lisp. Check out
the web sites of Forth, Inc. and MPE for more information.
-russ
From: Rahul Jain
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <878y767yya.fsf@nyct.net>
"Will Hartung" <·····@msoft.com> writes:
> (modulo the most crude of Lisp interpreters that macroexpand while
> interpreting...).
To be pedantic, such systems would not have an ANSI compliant
implementation of COMPILE, in that case. IIRC, the only thing COMPILE is
really required to do is expand all macros.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: Wade Humeniuk
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <enGCd.55170$KO5.23392@clgrps13>
Jeff M. wrote:
>
> My curiosity is in how much of a (typical, ie commercial) Lisp system
> is actually written in Lisp.
All of a CL implementation can be written in CL. All one
needs is another fairly compliant CL compiler. Compile
the implementation with another CL implementation and then recompile
itself with itself. Once you have boot-strapped your first version,
use it to produce new versions of your system.
Wade
In article <·····················@clgrps13>,
Wade Humeniuk <····················@telus.net> wrote:
> Jeff M. wrote:
>
> >
> > My curiosity is in how much of a (typical, ie commercial) Lisp system
> > is actually written in Lisp.
>
> All of a CL implementation can be written in CL. All one
> needs is another fairly compliant CL compiler. Compile
> the implementation with another CL implementation and then recompile
> itself with itself. Once you have boot-strapped your first version,
> use it to produce new versions of your system.
Yeah, I remember looking at the Symbolics source, and I noticed lots of
definitions of the form:
(defun not (x)
(not x))
Exercise for the reader: why doesn't this cause infinite recursion?
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Barry Margolin wrote:
> In article <·····················@clgrps13>,
> Wade Humeniuk <····················@telus.net> wrote:
>
>
>>Jeff M. wrote:
>>
>>
>>>My curiosity is in how much of a (typical, ie commercial) Lisp system
>>>is actually written in Lisp.
>>
>>All of a CL implementation can be written in CL. All one
>>needs is another fairly compliant CL compiler. Compile
>>the implementation with another CL implementation and then recompile
>>itself with itself. Once you have boot-strapped your first version,
>>use it to produce new versions of your system.
>
>
> Yeah, I remember looking at the Symbolics source, and I noticed lots of
> definitions of the form:
>
> (defun not (x)
> (not x))
>
> Exercise for the reader: why doesn't this cause infinite recursion?
Because DEFUN is not NOT.
kt
--
Cells? Cello? Celtik?: http://www.common-lisp.net/project/cells/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Kenny Tilton wrote:
>> (defun not (x)
>> (not x))
>>
>> Exercise for the reader: why doesn't this cause infinite recursion?
> Because DEFUN is not NOT.
I don't agreee with this explanantion.
It is more relevant to underatand why the following definition would
not have resulted in a working CL implementation:
(defun not (x)
(declare (notinline not))
(not x))
From: Rahul Jain
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <87d5wi7z8u.fsf@nyct.net>
"Steven M. Haflich" <·················@alum.mit.edu> writes:
> It is more relevant to underatand why the following definition would
> not have resulted in a working CL implementation:
>
> (defun not (x)
> (declare (notinline not))
> (not x))
Are you sure? "Special-forming" of CL operators is not covered under
inlining, is it? I think the undefined behavior of redefining CL
operators leaves the door open to the compiler implementing NOT as a
direct assembly operation instead of a full function call. The NOTINLINE
declaration would not hurt such an implementation.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: Duane Rettig
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <4acrm3pra.fsf@franz.com>
Rahul Jain <·····@nyct.net> writes:
> "Steven M. Haflich" <·················@alum.mit.edu> writes:
>
> > It is more relevant to underatand why the following definition would
> > not have resulted in a working CL implementation:
> >
> > (defun not (x)
> > (declare (notinline not))
> > (not x))
Heh; I wasn't sure why Steve made this statement - it seemed
obvious. Now I understand why...
> Are you sure? "Special-forming" of CL operators is not covered under
> inlining, is it?
Special-forms has nothing to do with this example. Not is not a
special operator.
> I think the undefined behavior of redefining CL
> operators leaves the door open to the compiler implementing NOT as a
> direct assembly operation instead of a full function call. The NOTINLINE
> declaration would not hurt such an implementation.
The redefinition of CL operators is undefined, but the requirement
to obey the notinline declaration is not. It is not even clear
that the form given was placed in a package that uses the CL package.
What is clear, is that the example _must_ result in an infinite
loop/recursion in a conforming lisp.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
From: Rahul Jain
Subject: Inline and Notinline (Was: Re: Core foundation of Common Lisp (not pure Lisp))
Date:
Message-ID: <87r7kx7sm8.fsf_-_@nyct.net>
Duane Rettig <·····@franz.com> writes:
> Rahul Jain <·····@nyct.net> writes:
>
>> "Steven M. Haflich" <·················@alum.mit.edu> writes:
>>
>> > It is more relevant to underatand why the following definition would
>> > not have resulted in a working CL implementation:
>> >
>> > (defun not (x)
>> > (declare (notinline not))
>> > (not x))
>
> Heh; I wasn't sure why Steve made this statement - it seemed
> obvious. Now I understand why...
>
>> Are you sure? "Special-forming" of CL operators is not covered under
>> inlining, is it?
>
> Special-forms has nothing to do with this example. Not is not a
> special operator.
That's why I quoted it. It's treated as a special form in that it is
compiled in a primitive way, the same way that macros are allowed to be
implemented as special-forms but must provide a macro-function.
>> I think the undefined behavior of redefining CL
>> operators leaves the door open to the compiler implementing NOT as a
>> direct assembly operation instead of a full function call. The NOTINLINE
>> declaration would not hurt such an implementation.
>
> The redefinition of CL operators is undefined, but the requirement
> to obey the notinline declaration is not. It is not even clear
> that the form given was placed in a package that uses the CL package.
> What is clear, is that the example _must_ result in an infinite
> loop/recursion in a conforming lisp.
Yikes, looking at the spec I see that quite explicitly. What is
interesting is the requirement that the declaration be obeyed for
_local_ function calls, too. I'm not sure what exactly this is trying to
achieve, because it could be argued that the local function is bound
lexically to the name, and so a redefinition of the surrounding function
would simply create a new function bound lexically to that name. The
binding in the previous function would be unaffected.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Duane Rettig wrote:
>>"Steven M. Haflich" <·················@alum.mit.edu> writes:
>>
>>>It is more relevant to underatand why the following definition would
>>>not have resulted in a working CL implementation:
>>>
>>>(defun not (x)
>>> (declare (notinline not))
>>> (not x))
>
> The redefinition of CL operators is undefined, but the requirement
> to obey the notinline declaration is not. It is not even clear
> that the form given was placed in a package that uses the CL package.
> What is clear, is that the example _must_ result in an infinite
> loop/recursion in a conforming lisp.
I agree with Duane, who agrees with me, who agrees with Duane, who
agrees with me, who agrees with Duane, who agrees with me, who agrees ..
A sufficiently smart and optimized compiler might convert my above
statement to "Duane and I agree."
From: lin8080
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <41E058C9.54952426@freenet.de>
Duane Rettig schrieb:
> Rahul Jain <·····@nyct.net> writes:
> > "Steven M. Haflich" <·················@alum.mit.edu> writes:
> > > It is more relevant to underatand why the following definition would
> > > not have resulted in a working CL implementation:
> > > (defun not (x)
> > > (declare (notinline not))
> > > (not x))
> Heh; I wasn't sure why Steve made this statement - it seemed
> obvious. Now I understand why...
I don't get it :(
(not 15)
Lisp stack overflow. RESET
How can I redo this?
stefan
In article <··············@nyct.net>, Rahul Jain <·····@nyct.net>
wrote:
> "Steven M. Haflich" <·················@alum.mit.edu> writes:
>
> > It is more relevant to underatand why the following definition would
> > not have resulted in a working CL implementation:
> >
> > (defun not (x)
> > (declare (notinline not))
> > (not x))
>
> Are you sure? "Special-forming" of CL operators is not covered under
> inlining, is it? I think the undefined behavior of redefining CL
> operators leaves the door open to the compiler implementing NOT as a
> direct assembly operation instead of a full function call. The NOTINLINE
> declaration would not hurt such an implementation.
Since we're talking about code that exists *in* the implementation, it's
not really redefining a CL operator -- it's defining it in the first
place.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
From: Rahul Jain
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <877jmlubme.fsf@nyct.net>
Barry Margolin <······@alum.mit.edu> writes:
> In article <··············@nyct.net>, Rahul Jain <·····@nyct.net>
> wrote:
>> Are you sure? "Special-forming" of CL operators is not covered under
>> inlining, is it? I think the undefined behavior of redefining CL
>> operators leaves the door open to the compiler implementing NOT as a
>> direct assembly operation instead of a full function call. The NOTINLINE
>> declaration would not hurt such an implementation.
>
> Since we're talking about code that exists *in* the implementation, it's
> not really redefining a CL operator -- it's defining it in the first
> place.
I was referring, mistakenly, to the ability of the compiler to insert
appropriate assembly code, as it would with a special form in place of
any call to NOT. However, in the spec, the description of the NOTINLINE
declaration requires ALL calls to the function to be implemented as full
function calls.
I was just comparing it to the way that FLETting a CL-defined function
has undefined consequences because the function may be implemented
deeper in the compiler and the compiler may be keyed off the symbol
itself without referring to the lexical environment. However, the
lexical environment would contain the NOTINLINE declaration, so I'm not
sure how that prohibition is really conceptually consistent.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: John Thingstad
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <opsj6efw0bpqzri1@mjolner.upc.no>
On Wed, 05 Jan 2005 00:20:46 -0500, Barry Margolin <······@alum.mit.edu>
wrote:
> In article <·····················@clgrps13>,
> Wade Humeniuk <····················@telus.net> wrote:
>
>> Jeff M. wrote:
>>
>> >
>> > My curiosity is in how much of a (typical, ie commercial) Lisp system
>> > is actually written in Lisp.
>>
>> All of a CL implementation can be written in CL. All one
>> needs is another fairly compliant CL compiler. Compile
>> the implementation with another CL implementation and then recompile
>> itself with itself. Once you have boot-strapped your first version,
>> use it to produce new versions of your system.
>
> Yeah, I remember looking at the Symbolics source, and I noticed lots of
> definitions of the form:
>
> (defun not (x)
> (not x))
>
> Exercise for the reader: why doesn't this cause infinite recursion?
>
In LispWorks:
CL-USER 1 > (defun not (x) (not x))
Error: Redefining function NOT visible from package COMMON-LISP.
1 (continue) Redefine it anyway.
2 (abort) Return to level 0.
3 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other
options
CL-USER 2 : 1 > :c 1
Error: Redefining function NOT visible from package COMMON-LISP.
1 (continue) Redefine it anyway.
2 (abort) Return to level 0.
3 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other
options
CL-USER 3 : 1 > :c 1
NOT
CL-USER 4 > (not t)
Stack overflow (stack size 16000).
1 (abort) Return to level 0.
2 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other
options
I take it it is the fact they can be defined in different packages
that could cause it to work. Like your NOT is in common-lisp-user
and the compiler NOT in common-lisp.
But this must be implementation dependent.
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
From: John Thingstad
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <opsj6ekpx5pqzri1@mjolner.upc.no>
On Thu, 06 Jan 2005 11:08:10 +0100, John Thingstad
<··············@chello.no> wrote:
> On Wed, 05 Jan 2005 00:20:46 -0500, Barry Margolin <······@alum.mit.edu>
> wrote:
>
>> In article <·····················@clgrps13>,
>> Wade Humeniuk <····················@telus.net> wrote:
>>
>>> Jeff M. wrote:
>>>
>>> >
>>> > My curiosity is in how much of a (typical, ie commercial) Lisp system
>>> > is actually written in Lisp.
>>>
>>> All of a CL implementation can be written in CL. All one
>>> needs is another fairly compliant CL compiler. Compile
>>> the implementation with another CL implementation and then recompile
>>> itself with itself. Once you have boot-strapped your first version,
>>> use it to produce new versions of your system.
>>
>> Yeah, I remember looking at the Symbolics source, and I noticed lots of
>> definitions of the form:
>>
>> (defun not (x)
>> (not x))
>>
>> Exercise for the reader: why doesn't this cause infinite recursion?
>>
>
> In LispWorks:
>
> CL-USER 1 > (defun not (x) (not x))
>
> Error: Redefining function NOT visible from package COMMON-LISP.
> 1 (continue) Redefine it anyway.
> 2 (abort) Return to level 0.
> 3 Return to top loop level 0.
>
> Type :b for backtrace, :c <option number> to proceed, or :? for other
> options
>
> CL-USER 2 : 1 > :c 1
>
> Error: Redefining function NOT visible from package COMMON-LISP.
> 1 (continue) Redefine it anyway.
> 2 (abort) Return to level 0.
> 3 Return to top loop level 0.
>
> Type :b for backtrace, :c <option number> to proceed, or :? for other
> options
>
> CL-USER 3 : 1 > :c 1
> NOT
>
> CL-USER 4 > (not t)
>
> Stack overflow (stack size 16000).
> 1 (abort) Return to level 0.
> 2 Return to top loop level 0.
>
> Type :b for backtrace, :c <option number> to proceed, or :? for other
> options
>
> I take it it is the fact they can be defined in different packages
> that could cause it to work. Like your NOT is in common-lisp-user
> and the compiler NOT in common-lisp.
> But this must be implementation dependent.
>
Ahh. Yes it works when I compile the function.
Then it must inline not...
messy..
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
From: Duane Rettig
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <4r7ky4i9f.fsf@franz.com>
"John Thingstad" <··············@chello.no> writes:
> On Thu, 06 Jan 2005 11:08:10 +0100, John Thingstad
> <··············@chello.no> wrote:
>
>
> > On Wed, 05 Jan 2005 00:20:46 -0500, Barry Margolin
> > <······@alum.mit.edu> wrote:
> >> Yeah, I remember looking at the Symbolics source, and I noticed lots of
> >> definitions of the form:
> >>
> >> (defun not (x)
> >> (not x))
> >>
> >> Exercise for the reader: why doesn't this cause infinite recursion?
> >>
> >
> > In LispWorks:
> >
> > CL-USER 1 > (defun not (x) (not x))
> Ahh. Yes it works when I compile the function.
> Then it must inline not...
> messy..
Actually, not :-)
Barry alluded to the why in terms of why the technique is not a
Bad Thing, but not why the technique is in fact a Good Thing and
thus why an implementor would want to proliferate the technique ...
This is actually the cleanest way to implement a definition; there
needs to be functionality for the definition of not, and also for
its compilation. If this functionality is spread between both
functional code and compiler inlining, the knowledge of NOT is
harder to maintain, because it is in two different places. However,
if the functional definition is done as above, with the intelligence
about the real definition in the compiler, then the functionality
resides in one place and becomes very easy to maintain. Not that
NOT needs maintaining, but there are other more complex functions
that have this attribute...
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
From: John Thingstad
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <opsj60cslzpqzri1@mjolner.upc.no>
On 06 Jan 2005 08:47:08 -0800, Duane Rettig <·····@franz.com> wrote:
> Actually, not :-)
>
> Barry alluded to the why in terms of why the technique is not a
> Bad Thing, but not why the technique is in fact a Good Thing and
> thus why an implementor would want to proliferate the technique ...
>
> This is actually the cleanest way to implement a definition; there
> needs to be functionality for the definition of not, and also for
> its compilation. If this functionality is spread between both
> functional code and compiler inlining, the knowledge of NOT is
> harder to maintain, because it is in two different places. However,
> if the functional definition is done as above, with the intelligence
> about the real definition in the compiler, then the functionality
> resides in one place and becomes very easy to maintain. Not that
> NOT needs maintaining, but there are other more complex functions
> that have this attribute...
>
I can see how this makes sense from a implementor perspective.
It's the thought of having a function tested and debugged
and considered finished only to discover that it no longer
works when I compile it that bothers me.
Still if I had followed the suggestions given both by
the compiler and evaluator not to redefine the function
in the first place I suspect there would be no problem.
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
From: Duane Rettig
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <4mzvm46nb.fsf@franz.com>
"John Thingstad" <··············@chello.no> writes:
> On 06 Jan 2005 08:47:08 -0800, Duane Rettig <·····@franz.com> wrote:
>
> > Actually, not :-)
> >
> > Barry alluded to the why in terms of why the technique is not a
> > Bad Thing, but not why the technique is in fact a Good Thing and
> > thus why an implementor would want to proliferate the technique ...
> >
> > This is actually the cleanest way to implement a definition; there
> > needs to be functionality for the definition of not, and also for
> > its compilation. If this functionality is spread between both
> > functional code and compiler inlining, the knowledge of NOT is
> > harder to maintain, because it is in two different places. However,
> > if the functional definition is done as above, with the intelligence
> > about the real definition in the compiler, then the functionality
> > resides in one place and becomes very easy to maintain. Not that
> > NOT needs maintaining, but there are other more complex functions
> > that have this attribute...
> >
>
> I can see how this makes sense from a implementor perspective.
> It's the thought of having a function tested and debugged
> and considered finished only to discover that it no longer
> works when I compile it that bothers me.
I don't understand this. Such a self-descriptive function
will _only_ work when you compile it...
> Still if I had followed the suggestions given both by
> the compiler and evaluator not to redefine the function
> in the first place I suspect there would be no problem.
If you're talking about package locking deterring one from
redefining CL functions, then yes; implementors have ways
to get around these things. But as for never redefining a
function in the first place, consider the maxims that state
that large percentages (I usually hear 80%) of programming
effort is spent in maintenance, and not in writing new code,
so if that effort were not required, most programmers would
then be out of a job...
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Barry Margolin wrote:
> Yeah, I remember looking at the Symbolics source, and I noticed lots of
> definitions of the form:
>
> (defun not (x)
> (not x))
In connection with this (albeit tangentially), I commend
to any reader's attention Ken Thompson's famous article
entitled "On trusting trust". (I think it was originally
his lecture delivered on the occasion of his receiving
the Turing Award.)
--
Gareth McCaughan
.sig under construc
Gareth McCaughan <················@pobox.com> writes:
> Barry Margolin wrote:
>
> > Yeah, I remember looking at the Symbolics source, and I noticed lots of
> > definitions of the form:
> >
> > (defun not (x)
> > (not x))
>
> In connection with this (albeit tangentially), I commend
> to any reader's attention Ken Thompson's famous article
> entitled "On trusting trust". (I think it was originally
> his lecture delivered on the occasion of his receiving
> the Turing Award.)
Do you mean this one? http://www.acm.org/classics/sep95/
He who controls the compiler controls the world.
Meanwhile, I have just completed DWIM:
(defun dwim (x)
(dwim x))
At last any arbitrary program can be expressed in just two lines of
code! (one if you care to dump a newline)
--
An ideal world is left as an excercise to the reader.
--- Paul Graham, On Lisp 8.1
David Steuber wrote:
[I said:]
>> In connection with this (albeit tangentially), I commend
>> to any reader's attention Ken Thompson's famous article
>> entitled "On trusting trust". (I think it was originally
>> his lecture delivered on the occasion of his receiving
>> the Turing Award.)
>
> Do you mean this one? http://www.acm.org/classics/sep95/
>
> He who controls the compiler controls the world.
That's the one :-).
> Meanwhile, I have just completed DWIM:
>
> (defun dwim (x)
> (dwim x))
>
> At last any arbitrary program can be expressed in just two lines of
> code! (one if you care to dump a newline)
:-)
--
Gareth McCaughan
.sig under construc
From: Karl A. Krueger
Subject: Re: Core foundation of Common Lisp (not pure Lisp)
Date:
Message-ID: <crh92h$dnc$1@baldur.whoi.edu>
Wade Humeniuk <····················@telus.net> wrote:
> Jeff M. wrote:
>> My curiosity is in how much of a (typical, ie commercial) Lisp system
>> is actually written in Lisp.
>
> All of a CL implementation can be written in CL. All one needs is
> another fairly compliant CL compiler. Compile the implementation with
> another CL implementation and then recompile itself with itself. Once
> you have boot-strapped your first version, use it to produce new
> versions of your system.
You shouldn't even need another CL compiler ... just a CL interpreter.
If you have written a CL compiler in CL, you should be able to run it on
itself, using the interpreter.
Assuming EVAL is an interpreter and COMPILE is an interpreted function
for a compiler, you should be able to do (EVAL '(COMPILE COMPILE)) and
get a "bootstrapped" compiled compiler.
(Not that I've done it myself ... this is apparently how the first self-
hosting compiler, which was for Lisp, was compiled.)
--
Karl A. Krueger <········@example.edu> { s/example/whoi/ }
Every program has at least one bug and can be shortened by at least one line.
By induction, every program can be reduced to one line which does not work.
In article <············@baldur.whoi.edu>,
"Karl A. Krueger" <········@example.edu> wrote:
> Wade Humeniuk <····················@telus.net> wrote:
> > Jeff M. wrote:
> >> My curiosity is in how much of a (typical, ie commercial) Lisp system
> >> is actually written in Lisp.
> >
> > All of a CL implementation can be written in CL. All one needs is
> > another fairly compliant CL compiler. Compile the implementation with
> > another CL implementation and then recompile itself with itself. Once
> > you have boot-strapped your first version, use it to produce new
> > versions of your system.
>
> You shouldn't even need another CL compiler ... just a CL interpreter.
> If you have written a CL compiler in CL, you should be able to run it on
> itself, using the interpreter.
As long as the interpreter isn't written in CL -- what would you use to
run it? Since you don't have a compiler, you can't compile it, so you'd
have to interpret it, resulting in infinite regress.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***