Home > Archive > Lisp > August 2004 > Lisp in hardware
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
|
|
| Pascal Bourguignon 2004-08-07, 8:56 am |
| Frank Buss <fb@frank-buss.de> writes:
> I want to implement a processor core in a Xilinx FPGA
> (http://www.jroller.com/page/fb), which can execute Lisp. I think it should
> be possible to do something like Pico Lisp, which is not a normal compiler,
> but more an interpreter:
>
> http://www.cs.uni-bonn.de/~costanza...ions/Burger.pdf
> http://software-lab.de/ref.html
>
> If the processor knows the concept of a list and perhaps has low-level
> commands for CAR and CDR in hardware, it should be really fast.
I don't feel that CAR and CDR be so critical to lisp performance.
Hardware memory management, ie. garbage collection is probably much
more influencing the performance.
> But first I want to know how it was solved in other systems, like the
> Symbolics Lisp Machine. Where can I find a hardware description of the
> processor? Any other resources I should read?
Perhaps have a look at the clisp virtual machine. It would be nice if
it was implemented in hardware. ;-)
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
| |
| Stefan Ram 2004-08-07, 8:56 am |
| Frank Buss <fb@frank-buss.de> writes:
>If the processor knows the concept of a list and perhaps has
>low-level commands for CAR and CDR in hardware, it should be
>really fast.
The IBM 704 had a partial-word instruction to reference the
"address" (15 Bits) and "decrement" (15 Bits) part of a
machine location (36 Bits). The names "CAR" and "CDR" have
been derived from this. So the first LISP implementation
already had such commands in hardware.
| |
| Frank Buss 2004-08-07, 8:56 am |
| Pascal Bourguignon <spam@mouse-potato.com> wrote:
> I don't feel that CAR and CDR be so critical to lisp performance.
> hardware memory management, ie. garbage collection is probably much
> more influencing the performance.
Yes, GC should be hardware accelerated, too.
>
> Perhaps have a look at the clisp virtual machine. It would be nice if
> it was implemented in hardware. ;-)
Perhaps it is better to execute some byte code, like the CLISP bytecode:
http://clisp.cons.org/impnotes/intr-set.html
but is it really faster than an instruction set which executes Lisp
without compiling it to byte-code, but only to an internal s-expression
format (like a binary tree structure), which can be executed by a special
CPU core fast? Perhaps a small set of primitives are enough, like this:
ftp://ftp.cs.cmu.edu/user/ai/lang/lisp/impl/awk/0.html
Do you know some research, which compares byte-code execution with s-
expression execution? Looks like the old war between RISC (reduced
instruction set CPU) and CISC (complex instruction set CPU), but I think
a Lisp instruction set could be faster and with smaller program sizes
than what is possible with other CISC concepts.
--
Frank Buß, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
| |
| Marco Parrone 2004-08-07, 3:56 pm |
| Frank Buss on Sat, 7 Aug 2004 12:19:21 +0000 (UTC) writes:
> Perhaps it is better to execute some byte code, like the CLISP bytecode:
What about IA32? At the same price, will your new HW run faster than
latest Intel/AMD processors, and a lisp like CMUCL?
--
Marco Parrone <marc0@autistici.org> [0x45070AD6]
| |
| Pascal Bourguignon 2004-08-07, 3:56 pm |
| Marco Parrone <marc0@autistici.org> writes:
> Frank Buss on Sat, 7 Aug 2004 12:19:21 +0000 (UTC) writes:
>
>
> What about IA32? At the same price, will your new HW run faster than
> latest Intel/AMD processors, and a lisp like CMUCL?
That's a good question, because for sequential algorithms, FPGA seems
quite limited in frequency.
For parallel algorithms, like neural networks, that's another
question. They have even quite a number of multipiers, and there's
memory bits spread over the array in addition to memory blocks.
But then, for neural networks, they're overkill, much too configurable.
Now, they should be taken for what they are: prototyping devices. If
you can implement on them an architecture that, relatively, show
better performance, then you may be motivated (and may motivate your
VC) to buy the services of Intel to mass produce a real version of it.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
| |
| Pascal Bourguignon 2004-08-07, 3:56 pm |
| Frank Buss <fb@frank-buss.de> writes:
> Pascal Bourguignon <spam@mouse-potato.com> wrote:
>
>
> Yes, GC should be hardware accelerated, too.
>
>
> Perhaps it is better to execute some byte code, like the CLISP bytecode:
>
> http://clisp.cons.org/impnotes/intr-set.html
>
> but is it really faster than an instruction set which executes Lisp
> without compiling it to byte-code, but only to an internal s-expression
> format (like a binary tree structure), which can be executed by a special
> CPU core fast? Perhaps a small set of primitives are enough, like this:
>
> ftp://ftp.cs.cmu.edu/user/ai/lang/lisp/impl/awk/0.html
Well, I guess it depends whether you want to implement a minimalistic
lisp, a Scheme or a COMMON-LISP.
> Do you know some research, which compares byte-code execution with s-
> expression execution?
I know none, but you can check the difference any time with clisp. Just run:
(time (your-favorite-function))
(compile 'your-favorite-function)
(time (your-favorite-function))
> Looks like the old war between RISC (reduced
> instruction set CPU) and CISC (complex instruction set CPU), but I think
> a Lisp instruction set could be faster and with smaller program sizes
> than what is possible with other CISC concepts.
Given that a Scheme eval+apply hold on one page of Scheme, that's less
than 2 or 3 KB, it should be possible to compile them into 200 KB of
FGPA.
I guess the question is whether the programs you will be processing
will have to manage only symbols and lists, or if they'll work on
something else too, like numbers, strings, arrays, etc. Then a lower
level processor may be more efficient (with compiled code).
Actually we could even have lisp -> FGPA (parallelizing) compilers
that would generate a specific "chip" for each lisp program. You just
have to put the limit between hardware and software somewhere.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
| |
| Barry Margolin 2004-08-07, 3:56 pm |
| In article <CDR-20040807140537@ram.dialup.fu-berlin.de>,
ram@zedat.fu-berlin.de (Stefan Ram) wrote:
> Frank Buss <fb@frank-buss.de> writes:
>
> The IBM 704 had a partial-word instruction to reference the
> "address" (15 Bits) and "decrement" (15 Bits) part of a
> machine location (36 Bits). The names "CAR" and "CDR" have
> been derived from this. So the first LISP implementation
> already had such commands in hardware.
CAR and CDR are basically just ordinary memory accesses. The only
special hardware needed for them is if you want to accelerate fancy
features like CDR-coding (which reduces memory overhead for lists) or
auto-forwarding (which is useful for some GC designs, array adjustments,
CHANGE-CLASS, and object aliasing schemes).
Probably the most significant distinguishing feature of Lisp Machines is
their support for type dispatching. When you invoke an arithmetic
operator, the data is fed in parallel to the fixnum unit and the
floating-point co-processor, and in parallel with this the microcode
checks the type tags. It then either latches the result register from
the appropriate hardware unit, or traps out to a software function that
handles all the other types.
--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
| |
| Rainer Joswig 2004-08-07, 3:56 pm |
| In article <cf2dor$1sf$1@newsreader2.netcologne.de>,
Frank Buss <fb@frank-buss.de> wrote:
> I want to implement a processor core in a Xilinx FPGA
> (http://www.jroller.com/page/fb), which can execute Lisp. I think it should
> be possible to do something like Pico Lisp, which is not a normal compiler,
> but more an interpreter:
>
> http://www.cs.uni-bonn.de/~costanza...ions/Burger.pdf
> http://software-lab.de/ref.html
>
> If the processor knows the concept of a list and perhaps has low-level
> commands for CAR and CDR in hardware, it should be really fast.
>
> But first I want to know how it was solved in other systems, like the
> Symbolics Lisp Machine. Where can I find a hardware description of the
> processor? Any other resources I should read?
See the discussion here:
http://groups.yahoo.com/group/lispmachines/
A project that currently is being in discussion is a virtual
machine for Lisp that would be able to run on bare hardware
and on some host OS. The VM should be portable and thus
not bound to x86 (I hope that my G5 Mac will be able to use it ;-) ).
The target would be a 'simple' OS with some HAL (hardware abstraction
layer) in Common Lisp. Some people already have experience with
similar stuff.
| |
| Frank Buss 2004-08-07, 8:56 pm |
| Pascal Bourguignon <spam@mouse-potato.com> wrote:
> Well, I guess it depends whether you want to implement a minimalistic
> lisp, a Scheme or a COMMON-LISP.
I want to start with a minimalistic lisp, Common Lisp on a 4,320 logic
cell FPGA with 1 MB external RAM would be very difficult :-)
>
> I know none, but you can check the difference any time with clisp.
> Just run:
>
> (time (your-favorite-function))
> (compile 'your-favorite-function)
> (time (your-favorite-function))
this compares only the compiled version and the interpreted version on my
x86 hardware, not for a special Lisp hardware.
> I guess the question is whether the programs you will be processing
> will have to manage only symbols and lists, or if they'll work on
> something else too, like numbers, strings, arrays, etc. Then a lower
> level processor may be more efficient (with compiled code).
why? I think a special Lisp processor can execute normal processing on
numbers as fast as a standard processor (if clocked with the same clock),
but should be able to do special Lisp command faster, like type
dispatching as Barry explained.
> Actually we could even have lisp -> FGPA (parallelizing) compilers
> that would generate a specific "chip" for each lisp program. You just
> have to put the limit between hardware and software somewhere.
Yes, this is possible, because the FPGA is loaded at power on in less
than 1 second from Flash or any other data source, but that's too
complicated for a starting project for me. I want to stay at the Verilog
or VHDL layer first. Perhaps later then I'll write my own gate level
synthesis software, which can do this.
--
Frank Buß, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
| |
| Christopher C. Stacy 2004-08-08, 3:56 am |
| >>>>> On Sat, 7 Aug 2004 11:17:47 +0000 (UTC), Frank Buss ("Frank") writes:
Frank> I want to implement a processor core in a Xilinx FPGA
Frank> (http://www.jroller.com/page/fb), which can execute Lisp. I think it should
Frank> be possible to do something like Pico Lisp, which is not a normal compiler,
Frank> but more an interpreter:
Frank> http://www.cs.uni-bonn.de/~costanza...ions/Burger.pdf
Frank> http://software-lab.de/ref.html
Frank> If the processor knows the concept of a list and perhaps has
Frank> low-level commands for CAR and CDR in hardware, it should be really fast.
CAR/CDR instructions are not in themselves a big deal,
and have been implemented in hardware more than once.
(That's where the names CAR and CDR come from!)
Frank> But first I want to know how it was solved in other systems,
Frank> like the Symbolics Lisp Machine. Where can I find a hardware
Frank> description of the processor? Any other resources I should read?
Googling for "Symbolics Lisp Machine" returns 3,170 hits,
and I see lots of pages and papers there which you should
read if you're interested.
| |
| Christopher C. Stacy 2004-08-08, 3:56 am |
| [color=darkred]
Frank> I want to implement a processor core in a Xilinx FPGA
Frank> (http://www.jroller.com/page/fb), which can execute Lisp. I think it should
Frank> be possible to do something like Pico Lisp, which is not a normal compiler,
Frank> but more an interpreter:
Frank> http://www.cs.uni-bonn.de/~costanza...ions/Burger.pdf
Frank> http://software-lab.de/ref.html
Frank> If the processor knows the concept of a list and perhaps has
Frank> low-level commands for CAR and CDR in hardware, it should be really fast.
CAR/CDR instructions are not in themselves a big deal,
and have been implemented in hardware more than once.
(That's where the names CAR and CDR come from!)
Frank> But first I want to know how it was solved in other systems,
Frank> like the Symbolics Lisp Machine. Where can I find a hardware
Frank> description of the processor? Any other resources I should read?
Googling for "Symbolics Lisp Machine architecture" returns 3,170 hits,
and I see lots of pages and papers there which you should
read if you're interested.
--
| |
| Alexander Burger 2004-08-08, 3:56 am |
| Frank Buss <fb@frank-buss.de> wrote:
> I want to implement a processor core in a Xilinx FPGA
> (http://www.jroller.com/page/fb), which can execute Lisp. I think it should
> be possible to do something like Pico Lisp, which is not a normal compiler,
> but more an interpreter:
Actually, this was my initial intention when I developed Pico
Lisp in the late 80s. To build that virtual machine in hardware.
I soon realized, however, that it wouldn't make much sense.
A hardware implemenation - or implementing the interpreter in
microcode - would probably not be much faster than an
interpreter written in C or assembly, because the interpreter
will completely fit into the processor cache and leave the
bottlenecks with the memory accesses.
The only thing left would be the beauty and simplicity of the
architecture.
> But first I want to know how it was solved in other systems, like the
> Symbolics Lisp Machine. Where can I find a hardware description of the
I believe that these machines were not really "Lisp Machines",
because they had a normal processor architecture with just a few
instructions optimized for compiled Lisp code. And such code is
IMHO not "Lisp", because it was transformed into another
language. I breaks, for example, the fundamental principle of
the equivalence of code and data.
- Alex
--
Software Lab. Alexander Burger
Bahnhofstr. 24a, D-86462 Langweid
abu@software-lab.de, http://www.software-lab.de, +49 821 9907090
| |
| Alexander Burger 2004-08-08, 8:56 am |
| Barry Margolin <barmar@alum.mit.edu> wrote:
> Probably the most significant distinguishing feature of Lisp Machines is
> their support for type dispatching. When you invoke an arithmetic
That's why Pico Lisp supports only three data types, using bits 1 and 2
in each pointer as tag bits (bit 0 is reserved for the garbage
collector):
xxxxxxxxxxxxxxxxxxxxxxxxxxxxx010 Number pointer
xxxxxxxxxxxxxxxxxxxxxxxxxxxxx100 Symbol pointer
xxxxxxxxxxxxxxxxxxxxxxxxxxxxx000 Cell pointer
This results in pointers to the CAR of cells:
cell
|
V
+-----+-----+
| CAR | CDR |
+-----+-----+
and an offset of 4 bytes for symbols, giving direct acces to the
symbol's value cell:
sym
|
V
+-----+-----+
| | | VAL |
+--+--+-----+
| tail
V
Note that this applies to "pure" Pico Lisp. The current production
version differs slightly from the above because of its support for
persistent external symbols as an additional data type.
- Alex
--
Software Lab. Alexander Burger
Bahnhofstr. 24a, D-86462 Langweid
abu@software-lab.de, http://www.software-lab.de, +49 821 9907090
| |
| Rainer Joswig 2004-08-08, 8:56 am |
| In article <2nm3bdF279i0U1@uni-berlin.de>,
Alexander Burger <abu@software-lab.de> wrote:
> Frank Buss <fb@frank-buss.de> wrote:
>
> Actually, this was my initial intention when I developed Pico
> Lisp in the late 80s. To build that virtual machine in hardware.
>
> I soon realized, however, that it wouldn't make much sense.
> A hardware implemenation - or implementing the interpreter in
> microcode - would probably not be much faster than an
> interpreter written in C or assembly, because the interpreter
> will completely fit into the processor cache and leave the
> bottlenecks with the memory accesses.
>
> The only thing left would be the beauty and simplicity of the
> architecture.
>
>
>
> I believe that these machines were not really "Lisp Machines",
> because they had a normal processor architecture with just a few
> instructions optimized for compiled Lisp code.
Hmm. *I* don't believe that last paragraph.
The processors from Symbolics (derived from the earlier CADR)
are described in literature.
Why don't you read the Symbolics 3600 Technical Summary
from 1983, come back here and tell us if you think
the processor architecture that is described there
is a 'normal processor architecture with just a few
instructions optimized for compiled Lisp code'?
Here is the book:
http://bitsavers.org/pdf/symbolics/...mmary_Feb83.pdf
Start with page 79 (page 85 in the PDF): '3600 Hardware: Processor Architecture'
a few things for your kind consideration:
- generally the implementation of data types is optimized
for usage with Lisp (like cdr-coding for lists, ...).
The 3600 processor supported over 30 Lisp data types
in hardware (like symbols, strings, bignums, coroutines,
closures, nil, ...)
- memory words are extended to 36 bits (later to 40) with
4 bits for tags and cdr-coding.
For some data there are additional 4 bits for tags (leaving
28 bits for data).
- tag checking at runtime in hardware
- tag comparison works in parallel to the ALU. The ADD instruction
does an integer add in parallel to tag checking. If the
arguments were in integers, the result is discarded and so on.
- the processor is a stack-oriented machine
(a stack group is: control stack, binding stack, data stack) with stack buffers.
Most instruction get the oprands from the stack and
return the result(s) to the stack.
- the processor has support for (ephemeral) garbage collection
- and lots more
> And such code is
> IMHO not "Lisp", because it was transformed into another
> language.
Machine code on the Symbolics Lisp Machine is not Lisp. That's right.
Though some of the instructions corresponds to some
Lisp functionality.
> I breaks, for example, the fundamental principle of
> the equivalence of code and data.
If the Lisp system uses any kind of compiler, the code that
gets executed is not Lisp, but some machine or byte code.
But we learned to live with that.
>
> - Alex
| |
| Alexander Burger 2004-08-08, 8:56 am |
| Rainer Joswig <joswig@lisp.de> wrote:
> In article <2nm3bdF279i0U1@uni-berlin.de>,
> Alexander Burger <abu@software-lab.de> wrote:
[color=darkred]
> Hmm. *I* don't believe that last paragraph.
Perhaps I said it a little bit too provocatively, but I think it holds
true, especially concerning the later points about machine vs. Lisp
code. It depends on what you mean with "Lisp Machines", machines
executing Lisp (which they are not), or machines with opcodes optimized
for Lisp compilers.
> The processors from Symbolics (derived from the earlier CADR)
> are described in literature.
I'm aware of that literature and had read parts of it.
> - generally the implementation of data types is optimized
> for usage with Lisp (like cdr-coding for lists, ...).
> The 3600 processor supported over 30 Lisp data types
> in hardware (like symbols, strings, bignums, coroutines,
> closures, nil, ...)
> - memory words are extended to 36 bits (later to 40) with
> 4 bits for tags and cdr-coding.
> For some data there are additional 4 bits for tags (leaving
> 28 bits for data).
> - tag checking at runtime in hardware
> - tag comparison works in parallel to the ALU. The ADD instruction
> does an integer add in parallel to tag checking. If the
> arguments were in integers, the result is discarded and so on.
> - the processor is a stack-oriented machine
> (a stack group is: control stack, binding stack, data stack) with stack buffers.
> Most instruction get the oprands from the stack and
> return the result(s) to the stack.
> - the processor has support for (ephemeral) garbage collection
All these points boil down to special opcodes which have to be produced
by the compiler. You could, for example, implement them all in
microcode, or even as subroutines or exception handlers for
unimplemented instructions.
It is just the execution speed that changes. The basic architecture,
with a linear instruction pointer, branches and so on, is just the
normal thing.
A "real" Lisp Machine would directly execute s-expressions, like what
(I think) the OP Frank Buss has in mind.
- Alex
--
Software Lab. Alexander Burger
Bahnhofstr. 24a, D-86462 Langweid
abu@software-lab.de, http://www.software-lab.de, +49 821 9907090
| |
| Christopher C. Stacy 2004-08-08, 8:56 am |
| >>>>> On 8 Aug 2004 07:34:07 GMT, Alexander Burger ("Alexander") writes:
Alexander> Frank Buss <fb@frank-buss.de> wrote:[color=darkred]
Alexander> I believe that these machines were not really "Lisp Machines",
Alexander> because they had a normal processor architecture with just a few
Alexander> instructions optimized for compiled Lisp code. And such code is
Alexander> IMHO not "Lisp", because it was transformed into another
Alexander> language. I breaks, for example, the fundamental principle of
Alexander> the equivalence of code and data.
When people say the proper noun "Lisp Machine", they are generally
referring to the MIT Lisp Machine (eg. the CADR) and the follow-on
machines created by the same people at the commercial spin-offs,
Symbolics and LMI. (Xerox also had Lisp workstations that could
rightly be called "Lisp machines", but around MIT we called those
"D Machines", and I believe that's also what Xerox called them.)
Your point, though, is that "Lisp Machine" was an inaccurate name.
You seem to be asserting that those machines were "normal" and
that they were not well optimized for compiling (executing?) Lisp.
Symbolics Lisp Machines included three different machine architectures:
CADR (the original MIT design), the 3600, and Ivory. I programmed
extensively on all of those, but did not need know much about their
implementation to do so; I'm more familiar with the first and last.
I am mostly interested in Ivory, which was the zenith of the Lisp
Machine architecture. Ivory was also ultimately ported from Symbolics
hardware to software, executing a very high-performance Ivory emulation
(on the only hot 64-bit hardware then available -- the DEC Alpha)
where it was called the VLM ("Virtual Lisp Machine" aka "Open Genera").
While the CADR in particular could be thought of as a general-purpose
machine, it was most certainly designed to be good for executing Lisp.
The later machines reflected more design experience and had even
more optimizations. The architecuture of all of these machines was
unique enough that I would not call any of them "normal", compared
to other CPUs at the time or todays architectures.
Lisp is a general purpose language, in the larger picture relatively
unconcerned with CARs and CDRs, so it is not surprising that a Lisp
Machine is a good general purpose machine. I would take issue with
your suggestion that it is the number of instructions that matters,
while also asking what you counted and what numbers you came up with.
It seems to me that the support for data type (that's a mouthfull),
calling conventions, and GC, are more important overall. But all of
the machines did have instructions for list operations, for example.
I am very unclear on your notion of "equivalence" of code and data;
in particular how this was "broken" by those machines.
Could describe the alternate machine architecture that you have in
mind, show examples of how you would compile it, and contrast that
with how it would be more "optimized for compiling [I assume you
really mean executing] Lisp code" than the realized Lisp Machines
mentioned above? If this is to be a virtual machine, a comparison
with the VLM would be most interesting, especially an analysis of
how the emulator will perform on the targetted real hardware.
I would also be interested in an analysis of your machine architecture
versus the Xerox D Machines (which I know very little about, but which
I suspect had more Lisp machine instructions than the CADR).
| |
| Rainer Joswig 2004-08-08, 8:56 am |
| In article <2nm9lsF2456dU1@uni-berlin.de>,
Alexander Burger <abu@software-lab.de> wrote:
> A "real" Lisp Machine would directly execute s-expressions, like what
> (I think) the OP Frank Buss has in mind.
Then for example OpenMCL (or, say, SBCL) is not a real "Lisp system",
because it does not execute s-expressions. OpenMCL compiles everything
to machine code. The only real Lisp system
would be one that is interpreting s-expressions.
So, I think the concept of a 'real' Lisp Machine is
as interesting and practical as 'Pure Lisp'.
For me, a real Lisp Machine boils down to the following:
- the processor is optimized for Lisp (opcodes, stack architecture,
data types, garbage collection, ...)
- the operating system for this machine is mostly written in Lisp for Lisp.
| |
| Paolo Amoroso 2004-08-08, 8:56 am |
| Frank Buss <fb@frank-buss.de> writes:
> But first I want to know how it was solved in other systems, like the
> Symbolics Lisp Machine. Where can I find a hardware description of the
> processor? Any other resources I should read?
See Bitkeepers.org and the Minicomputer Orphanage.
Paolo
--
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Recommended Common Lisp libraries/tools (Google for info on each):
- ASDF/ASDF-INSTALL: system building/installation
- CL-PPCRE: regular expressions
- UFFI: Foreign Function Interface
| |
| Alexander Burger 2004-08-08, 8:56 am |
| Rainer Joswig <joswig@lisp.de> wrote:
> In article <2nm9lsF2456dU1@uni-berlin.de>,
> Alexander Burger <abu@software-lab.de> wrote:
[color=darkred]
> Then for example OpenMCL (or, say, SBCL) is not a real "Lisp system",
> because it does not execute s-expressions. OpenMCL compiles everything
> to machine code. The only real Lisp system
> would be one that is interpreting s-expressions.
The term "Lisp system" is all right. From practical reasons, compiling a
Lisp source to machine code may have some speed advantages, but in
general I do object to the compilation of Lisp. I tried to explain that
in
http://www.cs.uni-bonn.de/~costanza...ions/Burger.pdf
The term "Lisp Machine" which suggests a machine _consisting_ of Lisp
expressions, not _emuating_ them in another language (machine code).
> So, I think the concept of a 'real' Lisp Machine is
> as interesting and practical as 'Pure Lisp'.
Interesting, yes, and beautiful IMHO.
But I consider Pico Lisp a real Lisp Machine, though each opcode is
implemented in C instead of microcode or hard-wires.
And it is practical, indeed. I use it for almost all my daily work.
- Alex
--
Software Lab. Alexander Burger
Bahnhofstr. 24a, D-86462 Langweid
abu@software-lab.de, http://www.software-lab.de, +49 821 9907090
| |
| Alexander Burger 2004-08-08, 8:56 am |
| Christopher C. Stacy <cstacy@news.dtpq.com> wrote:
> Alexander> I believe that these machines were not really "Lisp Machines",
> Alexander> because they had a normal processor architecture with just a few
> Alexander> instructions optimized for compiled Lisp code. And such code is
> Alexander> IMHO not "Lisp", because it was transformed into another
> Alexander> language. I breaks, for example, the fundamental principle of
> Alexander> the equivalence of code and data.
> Your point, though, is that "Lisp Machine" was an inaccurate name.
Yes.
> You seem to be asserting that those machines were "normal" and
> that they were not well optimized for compiling (executing?) Lisp.
No, I think they were highly optimized for Lisp, probably providing
the fastest execution of Lisp programs at that time.
But they did not execute Lisp (i.e. s-expressions), but an equivalent
program which resulted from a translation (compilation) process.
> Symbolics Lisp Machines included three different machine architectures:
> ...
> While the CADR in particular could be thought of as a general-purpose
> ...
I do not really know the architectures and specialities of these
machines, but from everything I read until now none of them implemented
a Lisp machine in the sense I tried to explain.
This does not mean that these machines were not very good systems, and
perhaps the best you could get to run Lisp programs. They were also very
complicated.
I think the confusion in our discussion arises because I distinguish
between the Lisp _Language_ and a Lisp _Machine_.
> I am very unclear on your notion of "equivalence" of code and data;
> in particular how this was "broken" by those machines.
On those machines code (machine code) is different from data
(s-expressions). You might claim that the original Lisp code is still
around, but it is not the code being executed.
> Could describe the alternate machine architecture that you have in
http://software-lab.de/ref.html
> mind, show examples of how you would compile it, and contrast that
No compilation. That's an important point for me. Actually, what I'm
striving for is a system which is so simple that I can understand every
aspect of it at any time, making it easy for me to extend it in any
direction. Compilation complicates everything considerably.
I use Pico Lisp for my daily work, and it gives me every freedom I
desire.
> with how it would be more "optimized for compiling [I assume you
> really mean executing] Lisp code" than the realized Lisp Machines
Yes.
> mentioned above? If this is to be a virtual machine, a comparison
> with the VLM would be most interesting, especially an analysis of
> how the emulator will perform on the targetted real hardware.
I do not talk about performance. Raw execution speed will always be best
with a compiled Lisp on a modern hardware. But raw execution speed
doesn't matter very often. And if it does, I just put another opcode (a
function written in C) into the virtual machine.
> I would also be interested in an analysis of your machine architecture
> versus the Xerox D Machines (which I know very little about, but which
> I suspect had more Lisp machine instructions than the CADR).
It would be interesting to learn more about that machine.
- Alex
--
Software Lab. Alexander Burger
Bahnhofstr. 24a, D-86462 Langweid
abu@software-lab.de, http://www.software-lab.de, +49 821 9907090
| |
| Rainer Joswig 2004-08-08, 8:56 am |
| In article <2nmi7iF1jun1U1@uni-berlin.de>,
Alexander Burger <abu@software-lab.de> wrote:
> Rainer Joswig <joswig@lisp.de> wrote:
>
>
>
> The term "Lisp system" is all right. From practical reasons, compiling a
> Lisp source to machine code may have some speed advantages, but in
> general I do object to the compilation of Lisp. I tried to explain that
> in
>
> http://www.cs.uni-bonn.de/~costanza...ions/Burger.pdf
>
> The term "Lisp Machine" which suggests a machine _consisting_ of Lisp
> expressions, not _emuating_ them in another language (machine code).
Maybe to you. Not to me. For me it suggests that it is a kind
of computer that can execute Lisp efficiently and sits
on, under or near my desk. I have two of those Lisp
machines to the right of me just now. I can touch them.
>
>
> Interesting, yes, and beautiful IMHO.
>
> But I consider Pico Lisp a real Lisp Machine, though each opcode is
> implemented in C instead of microcode or hard-wires.
I don't. For me a machine is something I can touch. A physical thing. A device.
Wikipedia, sense 1 in wordnet: "A machine is any mechanical or electrical device that transmits
or modifies energy to perform or assist in the performance of tasks."
Pico Lisp is software.
>
> And it is practical, indeed. I use it for almost all my daily work.
>
Nice.
> - Alex
| |
| Alexander Schreiber 2004-08-08, 3:57 pm |
| Rainer Joswig <joswig@lisp.de> wrote:
> In article <cf2dor$1sf$1@newsreader2.netcologne.de>,
> Frank Buss <fb@frank-buss.de> wrote:
>
>
> See the discussion here:
>
> http://groups.yahoo.com/group/lispmachines/
Oh, somebody decided to re-invent the lispm-hackers mailinglist?
http://lists.unlambda.com/mailman/l...o/lispm-hackers
> A project that currently is being in discussion is a virtual
> machine for Lisp that would be able to run on bare hardware
> and on some host OS. The VM should be portable and thus
> not bound to x86 (I hope that my G5 Mac will be able to use it ;-) ).
> The target would be a 'simple' OS with some HAL (hardware abstraction
> layer) in Common Lisp. Some people already have experience with
> similar stuff.
There is currently a Lisp environment running on the bare metal of x86
machines: Movitz.
http://www.common-lisp.net/project/movitz/
Regards,
Alex.
--
"Opportunity is missed by most people because it is dressed in overalls and
looks like work." -- Thomas A. Edison
| |
| Duncan Entwisle 2004-08-08, 3:57 pm |
| In article <cf2dor$1sf$1@newsreader2.netcologne.de>,
Frank Buss <fb@frank-buss.de> wrote:
> I want to implement a processor core in a Xilinx FPGA
> (http://www.jroller.com/page/fb), which can execute Lisp. I think it should
> be possible to do something like Pico Lisp, which is not a normal compiler,
> but more an interpreter:
I'm also considering implementing an Lisp interpreter in hardware. I
appreciate that it's probably not going to be especially efficient, but
I'm sure I'll have fun and learn along the way :-) I'm planning on using
the Xilinx Spartan-3 starter kit.
Two papers that (to my non-expert eyes, on superficial reading :-)
implement hardware interpreters for a LISP are:-
AI Memo No. 514:
"Design of LISP-Based Processors or, SCHEME: A Dielectric LISP or,
Finite Memories Considered Harmful or, LAMBDA: The Ultimate Opcode"
Guy Lewis Steele Jr. and Gerald Jay Sussman.
AI Memo No. 1040:
"Scheme86: A System for Interpreting Scheme"
Andrew A. Berlin and Henry M. Wu.
(I can probably hunt down the exact URL I found those papers if you
really need them, but I don't have them to hand, and they're not too
well hidden.)
From reading about the Lisp Machine, it seems to implement an
architecture that is geared towards executing compiled Lisp code
efficiently.
Anyway, good luck with your project, I hope you enjoy it :-)
Duncan.
| |
| Mark A. Washburn 2004-08-08, 3:57 pm |
| cstacy@news.dtpq.com (Christopher C. Stacy) wrote in message news:<usmay6unz.fsf@news.dtpq.com>...
> Frank> I want to implement a processor core in a Xilinx FPGA
> Frank> (http://www.jroller.com/page/fb), which can execute Lisp. I think it should
> Frank> be possible to do something like Pico Lisp, which is not a normal compiler,
> Frank> but more an interpreter:
>
> Frank> http://www.cs.uni-bonn.de/~costanza...ions/Burger.pdf
> Frank> http://software-lab.de/ref.html
>
> Frank> If the processor knows the concept of a list and perhaps has
> Frank> low-level commands for CAR and CDR in hardware, it should be really fast.
>
> CAR/CDR instructions are not in themselves a big deal,
> and have been implemented in hardware more than once.
> (That's where the names CAR and CDR come from!)
>
> Frank> But first I want to know how it was solved in other systems,
> Frank> like the Symbolics Lisp Machine. Where can I find a hardware
> Frank> description of the processor? Any other resources I should read?
>
> Googling for "Symbolics Lisp Machine architecture" returns 3,170 hits,
> and I see lots of pages and papers there which you should
> read if you're interested.
>
> --
With B16, the 'a' instruction executes CAR.
http://www.jwdt.com/~paysan/b16.html
maw
| |
| Gareth McCaughan 2004-08-08, 3:57 pm |
| Alexander Burger wrote:
> The term "Lisp Machine" which suggests a machine _consisting_ of Lisp
> expressions, not _emuating_ them in another language (machine code).
The term "Lisp Machine" gets its meaning mostly from the large
variety of things called by that name back in the 1980s. None
of them, so far as I know, executed S-expressions directly.
What exactly is wrong with "Lisp Machine" meaning "a machine
whose hardware and OS are adapted for running software in Lisp"?
--
Gareth McCaughan
..sig under construc
| |
| Mark A. Washburn 2004-08-08, 3:57 pm |
| cstacy@news.dtpq.com (Christopher C. Stacy) wrote in message news:<usmay6unz.fsf@news.dtpq.com>...
> Frank> I want to implement a processor core in a Xilinx FPGA
> Frank> (http://www.jroller.com/page/fb), which can execute Lisp. I think it should
> Frank> be possible to do something like Pico Lisp, which is not a normal compiler,
> Frank> but more an interpreter:
>
> Frank> http://www.cs.uni-bonn.de/~costanza...ions/Burger.pdf
> Frank> http://software-lab.de/ref.html
>
> Frank> If the processor knows the concept of a list and perhaps has
> Frank> low-level commands for CAR and CDR in hardware, it should be really fast.
>
> CAR/CDR instructions are not in themselves a big deal,
> and have been implemented in hardware more than once.
> (That's where the names CAR and CDR come from!)
>
> Frank> But first I want to know how it was solved in other systems,
> Frank> like the Symbolics Lisp Machine. Where can I find a hardware
> Frank> description of the processor? Any other resources I should read?
>
> Googling for "Symbolics Lisp Machine architecture" returns 3,170 hits,
> and I see lots of pages and papers there which you should
> read if you're interested.
>
> --
With B16, the 'a' instruction executes CAR.
http://www.jwdt.com/~paysan/b16.html
maw
---
Specifically, any definition of CDR is meaningless without a prior
definition of CAR.
CDR is, therefore, a function resultant of CAR's definition, a B16 CDR
alias is literally '>R RET' , ( feel free to disagree, but I am
telling this /is/ the most correct implementation design ).
Further, maybe this explains why SET-CAR! in Scheme is, technically, a
programming closure violation.
However, SET-CAR! ( or equivalent) machine instruction is required, (
at least at some expression level,) for defining a core Scheme
language compiler or interpreter closure, itself!
SET-CDR!, in theory, doesn't violate Scheme language security.
To implement any Scheme or LISP compliant language in B16 machine code
will require the use of Scheme's SET-CAR! ( or the B16 equivalent
machine instruction '>A' )
Or, alternatively design,
Depending upon ***your*** LISP implementation design decisions,
CAR could be defined as an alias for 'A@'
: CAR A@ ;
then maybe CDR as
: CDR ( --) A SIZE-OF-CAR + >A A@ A ;
, also , I might consider using a list stack and might define
: NEXT-CDR A CDR ;
Or, in a seemingly entirely different direction, define a slightly
more complex object oriented general purpose ( in memory) data
structure, very long instruction word subclass.
maybe,
-- generalized object type --
object-size ( a primitive instruction, maybe?)
object-type
list-object-type-car ( --> pointer to generalized object type)
list-object-type-cdr ( --> pointer to generalized object type)
Good luck with your work.
Regards,
maw
| |
| Alexander Burger 2004-08-08, 3:57 pm |
| Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
> Alexander Burger wrote:
[color=darkred]
> The term "Lisp Machine" gets its meaning mostly from the large
> variety of things called by that name back in the 1980s. None
> of them, so far as I know, executed S-expressions directly.
> What exactly is wrong with "Lisp Machine" meaning "a machine
> whose hardware and OS are adapted for running software in Lisp"?
Hmm, this could be anything ...
Ok, I understand that the term "Lisp Machine" was widely accepted. I
just always had the feeling that it was not appropriate.
> --
> Gareth McCaughan
> .sig under construc
The original question of this thread was whether it makes sense to
implement an s-expression-executor like Pico Lisp in hardware. In a
previous post to this thread I wrote that it wouldn't make much sense,
but now I rather begin to like the idea. Frank, are you going to try it?
- Alex
--
Software Lab. Alexander Burger
Bahnhofstr. 24a, D-86462 Langweid
abu@software-lab.de, http://www.software-lab.de, +49 821 9907090
| |
| Christopher C. Stacy 2004-08-08, 3:57 pm |
| >>>>> On 8 Aug 2004 08:37:12 -0700, Mark A Washburn ("Mark") writes:
Mark> Specifically, any definition of CDR is meaningless
Mark> without a prior definition of CAR.
I think what's important is the definition of a cons cell,
and then you could implement CAR, CDR, or both of them.
For example, on the PDP-10, machine words are 36 bits,
machine pointers are 18 bits, and there are machine
instructions for taking the CAR (HLRZ) and CDR (HRRZ)
quantities into a full word destination.
(The PDP-10 also features addressing modes, stack manipulation,
and other features that make it, not accidently, well suited for Lisp.
It was the main Lisp platform during the heydey decades of Lisp before
Lisp Machines. The PDP-10 also had instructions called LDB and DPB,
by the way, which is where Common Lisp gets those.)
| |
| Paul Wallich 2004-08-08, 3:57 pm |
| Christopher C. Stacy wrote:
>
> Alexander> Frank Buss <fb@frank-buss.de> wrote:
>
> Alexander> I believe that these machines were not really "Lisp Machines",
> Alexander> because they had a normal processor architecture with just a few
> Alexander> instructions optimized for compiled Lisp code. And such code is
> Alexander> IMHO not "Lisp", because it was transformed into another
> Alexander> language. I breaks, for example, the fundamental principle of
> Alexander> the equivalence of code and data.
>
> When people say the proper noun "Lisp Machine", they are generally
> referring to the MIT Lisp Machine (eg. the CADR) and the follow-on
> machines created by the same people at the commercial spin-offs,
> Symbolics and LMI. (Xerox also had Lisp workstations that could
> rightly be called "Lisp machines", but around MIT we called those
> "D Machines", and I believe that's also what Xerox called them.)
Not-entirely-pedantic note: the D-machines (dolphin, dorado,
dandewhatever) were designed to execute any of a number of
virtual-machine instruction sets of which the Interlisp-D code was just
one. With a different bunch of microcode loaded they became Smalltalk or
Mesa machines, for example.
This kind of flexibility (along with the general principle of
turing-equivalence) shows, imo, how incomplete such ideas as "the
equivalence of cade and data" ultimately are. At some point you have to
represent your lisp-stuff in terms of things that are not lisp-stuff, be
it ASCII or Unicode standing in for the characters of s-expressions, or
1's and 0's in a register, or organized collections of charge carriers
or photons. And you will potentially (or even necessarily) be able to do
things with that non-lisp stuff that violate lisp semantics. Towers of
reflection notwithstanding, there's always going to be an
implementation, and picking a particular metric to argue about its
purity seems counterproductive to me.
paul
| |
| rem642b@Yahoo.Com 2004-08-08, 3:57 pm |
| > From: Alexander Burger <abu@software-lab.de>
> A "real" Lisp Machine would directly execute s-expressions
That's sloppy language. A "real" Lisp Machine would directly execute
pointy structures, what is built in memory after an s-expression is fed
as input to READ. You wouldn't ever want to directly execute
s-expressions which are the print representation.
| |
| Christopher C. Stacy 2004-08-08, 8:56 pm |
| >>>>> On Sun, 08 Aug 2004 13:11:48 -0400, Paul Wallich ("Paul") writes:
Paul> Not-entirely-pedantic note: the D-machines (dolphin, dorado,
Paul> dandewhatever) were designed to execute any of a number of
Paul> virtual-machine instruction sets of which the Interlisp-D code was
Paul> just one. With a different bunch of microcode loaded they became
Paul> Smalltalk or Mesa machines, for example.
Yes, and likewise the CADR and 3600 were microcoded.
(Also, the KL model of the PDP-10 was microcoded; the ITS operating
system had some different instructions than the DEC microcode,
but not for anything to do with Lisp.) Actually, lots of computers
were microcoded - we're only talking here about user-writable microcode,
loaded as part of the cold boot sequence. However, unlike the D Machines,
neither the PDP-10 nor Lisp Machine ever had microcode that implemented a
radically different macroinstruction set than was intended. Despite the
fact that they included ("macro") compilers for many other languages
(FORTRAM, C, ADA, Pascal, Prolog, etc.), the Lisp Machines were only
microcoded to execute their Lisp macroinstruction set, as far as I remember.
(Special purpose user microcoded functions aside, the closest thing is that
the 3600, I think, had some microcoded support for Prolog unification.
I don't remember exactly what that was all about though.)
But the D machines were also Smalltalk and Mesa machines!
| |
| Christopher C. Stacy 2004-08-08, 8:56 pm |
| By the way, I left out from my description the Scheme chip;
we didn't call that a "Lisp Machine", although obviously it
was a kind of Lisp Machine. These were never used in actual
workstations at the lab or commercially; they were strictly
research projects in compiler and VLSI technology.
| |
| Julian Stecklina 2004-08-08, 8:56 pm |
| Alexander Burger <abu@software-lab.de> writes:
> The term "Lisp system" is all right. From practical reasons, compiling a
> Lisp source to machine code may have some speed advantages, but in
> general I do object to the compilation of Lisp. I tried to explain that
> in
>
> http://www.cs.uni-bonn.de/~costanza...ions/Burger.pdf
On the second page you claim that "... macros were introduced to
satisfy the needs of compilers." I think you have to explain that
one.
Also you claim that walking S-expressions is not "interpreting". That
is rather odd. To stick with wikipedia: "An interpreter is a computer
program that executes other programs." It does not matter in what form
that other program is stored.
It is also doubtful, whether a typical program spents most of its time
in built-in functions. Allocating storage might be an example, but
with proper type inferencing and "compiler magic" allocated storage
can decrease quite significantly. e.g. when dealing with numbers.
Some paragraphs below you compare Pico Lisps performance to that of
CLISP. Just for the record: CLISP compiles s-exps to byte-code and
interprets that. So by your own argument (where you talk about Java
byte-code) it must be slower than Pico Lisp. Try to compare to CMUCL,
SBCL, MCL ...
By the way: With the list being the only data type for sequences, how
do you implement algorithms that depend on O(1) array access? Several
graph algorithms come to mind...
And what about lexical closures...
I agree that PicoLisp is a very practical approach for some problems,
but it certainly is not for most them.
Regards,
--
____________________________
Julian Stecklina / _________________________/
________________/ /
\_________________/ LISP - truly beautiful
| |
| Julian Stecklina 2004-08-08, 8:56 pm |
| Alexander Burger <abu@software-lab.de> writes:
[Lisp Machines]
> But they did not execute Lisp (i.e. s-expressions), but an equivalent
> program which resulted from a translation (compilation) process.
So why is this bad? Except the one-time overhead of compilation this
"equivalent" code beats "interpreting s-epxressions" hands-down...
Regards,
--
____________________________
Julian Stecklina / _________________________/
________________/ /
\_________________/ LISP - truly beautiful
| |
| Pascal Bourguignon 2004-08-09, 3:56 am |
|
Julian Stecklina <der_julian@web.de> writes:
> By the way: With the list being the only data type for sequences, how
> do you implement algorithms that depend on O(1) array access? Several
> graph algorithms come to mind...
That's easy:
(defun aref (array index)
(do ((result)
(i 0 (1+ i))
(items array (cdr items)))
((= i most-positive-fixnum result) result)
(when (= i index) (setf result (car items)))))
Et hop! O(1).
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
| |
| John Thingstad 2004-08-09, 9:04 am |
| Why bother with a lisp machine now!
They had their place when workstations were underpowered for the job.
Now, even my home PC run's lisp apps fine. If I needed more power I would
run
one of the paralell lisp inplementations for supercomputers. (like the one
created for the conection machine)
I fail to see need for a lisp workstation. Movitz, a lisp OS, is an
alternative if yoy want a all lisp
environment.
On Sun, 08 Aug 2004 09:27:54 GMT, Christopher C. Stacy
<cstacy@news.dtpq.com> wrote:
> Alexander> Frank Buss <fb@frank-buss.de> wrote:
> the
>
> Alexander> I believe that these machines were not really "Lisp
> Machines",
> Alexander> because they had a normal processor architecture with just a
> few
> Alexander> instructions optimized for compiled Lisp code. And such code
> is
> Alexander> IMHO not "Lisp", because it was transformed into another
> Alexander> language. I breaks, for example, the fundamental principle of
> Alexander> the equivalence of code and data.
>
> When people say the proper noun "Lisp Machine", they are generally
> referring to the MIT Lisp Machine (eg. the CADR) and the follow-on
> machines created by the same people at the commercial spin-offs,
> Symbolics and LMI. (Xerox also had Lisp workstations that could
> rightly be called "Lisp machines", but around MIT we called those
> "D Machines", and I believe that's also what Xerox called them.)
>
> Your point, though, is that "Lisp Machine" was an inaccurate name.
> You seem to be asserting that those machines were "normal" and
> that they were not well optimized for compiling (executing?) Lisp.
>
> Symbolics Lisp Machines included three different machine architectures:
> CADR (the original MIT design), the 3600, and Ivory. I programmed
> extensively on all of those, but did not need know much about their
> implementation to do so; I'm more familiar with the first and last.
> I am mostly interested in Ivory, which was the zenith of the Lisp
> Machine architecture. Ivory was also ultimately ported from Symbolics
> hardware to software, executing a very high-performance Ivory emulation
> (on the only hot 64-bit hardware then available -- the DEC Alpha)
> where it was called the VLM ("Virtual Lisp Machine" aka "Open Genera").
>
> While the CADR in particular could be thought of as a general-purpose
> machine, it was most certainly designed to be good for executing Lisp.
> The later machines reflected more design experience and had even
> more optimizations. The architecuture of all of these machines was
> unique enough that I would not call any of them "normal", compared
> to other CPUs at the time or todays architectures.
>
> Lisp is a general purpose language, in the larger picture relatively
> unconcerned with CARs and CDRs, so it is not surprising that a Lisp
> Machine is a good general purpose machine. I would take issue with
> your suggestion that it is the number of instructions that matters,
> while also asking what you counted and what numbers you came up with.
> It seems to me that the support for data type (that's a mouthfull),
> calling conventions, and GC, are more important overall. But all of
> the machines did have instructions for list operations, for example.
>
> I am very unclear on your notion of "equivalence" of code and data;
> in particular how this was "broken" by those machines.
>
> Could describe the alternate machine architecture that you have in
> mind, show examples of how you would compile it, and contrast that
> with how it would be more "optimized for compiling [I assume you
> really mean executing] Lisp code" than the realized Lisp Machines
> mentioned above? If this is to be a virtual machine, a comparison
> with the VLM would be most interesting, especially an analysis of
> how the emulator will perform on the targetted real hardware.
>
> I would also be interested in an analysis of your machine architecture
> versus the Xerox D Machines (which I know very little about, but which
> I suspect had more Lisp machine instructions than the CADR).
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
| |
| Alexander Burger 2004-08-09, 9:04 am |
| Julian Stecklina <der_julian@web.de> wrote:
> On the second page you claim that "... macros were introduced to
> satisfy the needs of compilers." I think you have to explain that
> one.
Perhaps I have to state it the other way round: Macros do not make much
sense in an interpreter, because they are rather inefficient here due to
double evaluation. It is better then to implement the desired
functionality as a function instead of a macro.
Having said that, I _do_ occasionally use Macros also in an interpreter,
because they make the code more readable.
But Lisp compilers depend on them. I don't know the current state of
art, but 20 years ago it used to be so. The compiler did not support all
necessary primitives. It implemented a few of them, and all others were
defined as macros (for example, all conditional branching functions like
'if', 'when' etc. were converted to 'cond').
> Also you claim that walking S-expressions is not "interpreting". That
> is rather odd. To stick with wikipedia: "An interpreter is a computer
> program that executes other programs." It does not matter in what form
> that other program is stored.
Ok, the readers of this group know probably what is meant, but I did
often meet people who were suspicios about an interpreter because they
believed it operates on a textual basis.
Besides this, and more important, is that the term "interpreting"
connotates "explaining" and "searching for a meaning", which is typical
for textual interpreters who have to lookup tokens in a symbol table
(like the Lisp reader). Walking s-expressions involves no searching.
> It is also doubtful, whether a typical program spents most of its time
> in built-in functions. Allocating storage might be an example, but
> with proper type inferencing and "compiler magic" allocated storage
> can decrease quite significantly. e.g. when dealing with numbers.
In Lisp, many built-in functions like list manipulations or bignum
arithmetics do very heavy work, as opposed to a bytecode which typically
only moves a few bits around. Take an extreme but typical example (in
Pico Lisp syntax):
: (mapcar + (1 2 3 4) (5 6 7 8 9))
-> (6 8 10 12)
After 'mapcar' has evaluated its arguments, the whole process runs in
full 'C' speed, no more glue involved.
> Some paragraphs below you compare Pico Lisps performance to that of
> CLISP. Just for the record: CLISP compiles s-exps to byte-code and
> interprets that. So by your own argument (where you talk about Java
> byte-code) it must be slower than Pico Lisp. Try to compare to CMUCL,
> SBCL, MCL ...
When I wrote that, CLISP was the only Lisp I had access to, and I did
not know (or care) what it compiled to.
But this case even supports my opinion that people blindly believe in
(or believe to need) compilers, without checking the results.
I expected, of course, a compiled Lisp to be significantly faster than
Pico Lisp. And this will surely be the case with many other Lisps. But
according to my experiences, the raw speed gain is not worth all the
di vantages. That's what I tried to explain in that paper.
20 years ago I was also a speed fanatic. I coded anything possible in
assembly language. I hope I'm more wise by now ;-)
> By the way: With the list being the only data type for sequences, how
> do you implement algorithms that depend on O(1) array access? Several
> graph algorithms come to mind...
This argument appears very often in such discussions. Do we really need
arrays, vectors and strings, as is often proudly stated about the
benefits of "modern" Lisp?
First of all, it has great advantages to use lists for sequential data,
because of the wealth of list processing functions the language
provides.
Sure, it is inefficient if you want to access the 1000th element in a
List. But how often does that happen? I cannot recall a single case. In
Lisp, you don't iterate over a sequence with an index like e.g. in C or
Java
for (i = 0; i < arr.length; ++i)
... a[i] ...;
but you typically use one of the mapping functions. Or you search the
list sequentially, or perform some other operation while traversing it.
Such a long list more likely smells like a design bug. To handle large
amounts of uniform data, I rather use more structured data like nested
(and thus shorter) lists or trees (also implemented in lists, of
course).
For small amounts of data, the overhead for let's say 'cdddr' or 'nth'
is usually acceptable.
Again, this is again a matter of "execution speed" versus "power to the
programmer" and "ease of handling". I gladly abstain from the first if I
can gain the other two.
> And what about lexical closures...
Admitted, that's a delicate point. But there are conventions in Pico
Lisp. Please read the documentation about transient symbols, and the FAQ
about dynamic binding.
> I agree that PicoLisp is a very practical approach for some problems,
> but it certainly is not for most them.
Perhaps you can give some examples?
Anyway, nobody is forced to use it. There are plenty of useful
programming languages and everybody should use what he thinks most
suited.
> Regards,
> --
> ____________________________
> Julian Stecklina / _________________________/
Ciao,
- Alex
--
Software Lab. Alexander Burger
Bahnhofstr. 24a, D-86462 Langweid
abu@software-lab.de, http://www.software-lab.de, +49 821 9907090
| |
| Alexander Burger 2004-08-09, 9:04 am |
| Julian Stecklina <der_julian@web.de> wrote:
> Alexander Burger <abu@software-lab.de> writes:
> [Lisp Machines]
[color=darkred]
> So why is this bad? Except the one-time overhead of compilation this
> "equivalent" code beats "interpreting s-epxressions" hands-down...
This is bad for several reasons:
1. The resulting program is not necessarily 100% equivalent.
2. Many of my applications consist of plenty of one-time code, typically
GUI components. The file is loaded, executed, produces some side
effects (Applet layout), and is thrown away. A compilation pass would
be counter-productive.
3. The GUI components contain many little s-expressions (function bodies
or just simple lists) which may be later evaluated depending on user
actions like mouse click and button press. I doubt it makes sense to
compile such code fragments, which even cannot be meaningfully
executed outside their dynamic environment.
4. It has great advantages to execute s-expressions. Not so much in
application programming, because the often-cited self-modifying Lisp
programs are rare. But for the development of the Lisp system itself.
I want full control over my programming system. It has to be simple,
so that I can understand and modify every aspect of it.
For example, tracing is done in Pico Lisp by cons'ing a trace symbol
in front of function or method bodies. The debugger (single stepper)
consists of a few dozen lines which constantly modify s-expressions
while they are executed. The same holds for the profiler.
It is all so simple if you dare to abandon the compiler. Many lisp-ish
(in my opinion) programming styles like (3) you don't even consider if
you are caught in monolithic lexical compiler think.
> Regards,
> --
> ____________________________
> Julian Stecklina / _________________________/
> ________________/ /
> \_________________/ LISP - truly beautiful
sincerely,
- Alex
--
Software Lab. Alexander Burger
Bahnhofstr. 24a, D-86462 Langweid
abu@software-lab.de, http://www.software-lab.de, +49 821 9907090
| |
| Carl Shapiro 2004-08-09, 9:04 am |
| "John Thingstad" <john.thingstad@chello.no> writes:
> Why bother with a lisp machine now!
> They had their place when workstations were underpowered for the job.
> Now, even my home PC run's lisp apps fine. If I needed more power I
> would run
> one of the paralell lisp inplementations for supercomputers. (like the
> one created for the conection machine)
> I fail to see need for a lisp workstation. Movitz, a lisp OS, is an
> alternative if yoy want a all lisp
> environment.
Here, here. Keyboards aside, the magic of the Lisp machine resides in
its wonderful intergrated software environment, not in the tricked-out
hardware.
| |
| tfb+google@tfeb.org 2004-08-09, 9:04 am |
|
Barry Margolin wrote:
> Probably the most significant distinguishing feature of Lisp Machines
is
> their support for type dispatching. When you invoke an arithmetic
> operator, the data is fed in parallel to the fixnum unit and the
> floating-point co-processor, and in parallel with this the microcode
> checks the type tags. It then either latches the result register
from
> the appropriate hardware unit, or traps out to a software function
that
> handles all the other types.
This kind of technique should be eminently implementable on modern
CPUs, which generally have more execution units than they know what to
do with and speculative execution. I think the problem with the naive
approach - generate conditional code for all the possibilities, which
the processor would then speculatively execute until it knew the result
of the type test - would be code bloat, but I'm not sure that is a real
problem. I guess that compiler implementors for modern machines
(Duane? The CMUCL-related-implementation people?) could comment more
knowledgably.
My impression is that modern CPUs *are* lisp machines in the sense that
they have parallel type checking units and so forth. These units
happen to be general-purpose ALUs rather than special-purpose units,
but this is a good thing, as it means that the unit is still useful if
you have a compiler which can optimise type checks away in many cases.
Of course there were other things that Lisp CPUs did: fixnums being
less than 32 bits always bugs me on stock HW.
--tim
| |
| Julian Stecklina 2004-08-09, 9:04 am |
| Pascal Bourguignon <spam@mouse-potato.com> writes:
> Julian Stecklina <der_julian@web.de> writes:
>
> That's easy:
>
> (defun aref (array index)
> (do ((result)
> (i 0 (1+ i))
> (items array (cdr items)))
> ((= i most-positive-fixnum result) result)
> (when (= i index) (setf result (car items)))))
>
> Et hop! O(1).
Looks more like O(n) to me.
Regards,
--
____________________________
Julian Stecklina / _________________________/
________________/ /
\_________________/ LISP - truly beautiful
| |
| Pascal Bourguignon 2004-08-09, 9:04 am |
| Julian Stecklina <der_julian@web.de> writes:
> Pascal Bourguignon <spam@mouse-potato.com> writes:
>
>
> Looks more like O(n) to me.
Look again!
For all index in [0 .. (1- (length array))] the exact same number of
operations will be executed. Namely: M increments, M cdr, 2*M =, 1
setf, 1 car.
For all index <0 or >=(length array), the number of operations
executed is only slightly bity bit smaller: M increments, M cdr, 2*M =.
With M the constant: most-positive-fixnum.
O(constant) = O(1).
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
| |
| Julian Stecklina 2004-08-09, 9:04 am |
| Alexander Burger <abu@software-lab.de> writes:
[Compiled code]
> This is bad for several reasons:
>
> 1. The resulting program is not necessarily 100% equivalent.
Your compiler is broken. ;)
> 2. Many of my applications consist of plenty of one-time code, typically
> GUI components. The file is loaded, executed, produces some side
> effects (Applet layout), and is thrown away. A compilation pass would
> be counter-productive.
Many CLs have a compiler and an interpreter, if that really is a
concern to you. They are totally transparent to the user as well. If
at work I get thrown into the debugger because a GUI handler has a
bug, I can fix it and restart the frame. It is meaningless whether
this handler was compiled or not.
> For example, tracing is done in Pico Lisp by cons'ing a trace symbol
> in front of function or method bodies. The debugger (single stepper)
> consists of a few dozen lines which constantly modify s-expressions
> while they are executed. The same holds for the profiler.
Simplicity is nice to have, agreed. But living without strings and
vectors per design...
> It is all so simple if you dare to abandon the compiler. Many lisp-ish
> (in my opinion) programming styles like (3) you don't even consider if
> you are caught in monolithic lexical compiler think.
Why should you consider?
Regards,
--
____________________________
Julian Stecklina / _________________________/
________________/ /
\_________________/ LISP - truly beautiful
| |
| Julian Stecklina 2004-08-09, 9:04 am |
| Alexander Burger <abu@software-lab.de> writes:
> Perhaps I have to state it the other way round: Macros do not make much
> sense in an interpreter, because they are rather inefficient here due to
> double evaluation. It is better then to implement the desired
> functionality as a function instead of a macro.
It is true that you can write some of the more common stuff one does
with macros via functions. But what about :
(defh sum-tree
(?a ?b) -> (+ (sum-tree a)
(sum-tree b))
?a -> a)
This function sums up all all leafs in a tree consting of two-element
lists. And it is declared using a macro that introduced pattern
matching. This is purely user convenience, nothing to do with the
compiler.
(I wrote this macro to play around with predicate logic formulas, but
it is nice for a number of list related things.)
>
> Perhaps you can give some examples?
No convincing examples. :)
> Anyway, nobody is forced to use it. There are plenty of useful
> programming languages and everybody should use what he thinks most
> suited.
Ack.
Regards,
--
____________________________
Julian Stecklina / _________________________/
________________/ /
\_________________/ LISP - truly beautiful
| |
| Frank Buss 2004-08-09, 9:04 am |
| Duncan Entwisle <family*.*entwisle*@*btinternet*.*com> wrote:
> I'm also considering implementing an Lisp interpreter in hardware. I
> appreciate that it's probably not going to be especially efficient,
> but I'm sure I'll have fun and learn along the way :-) I'm planning on
> using the Xilinx Spartan-3 starter kit.
I already have a Spartan-3 starter kit, too, and writing hardware
descriptions in Verilog is not much more difficult than writing programs
in C, so it should be easy to implement it with it.
> AI Memo No. 514:
> "Design of LISP-Based Processors or, SCHEME: A Dielectric LISP or,
> Finite Memories Considered Harmful or, LAMBDA: The Ultimate Opcode"
> Guy Lewis Steele Jr. and Gerald Jay Sussman.
ftp://publications.ai.mit.edu/ai-pu...pdf/AIM-514.pdf
This is exactly the kind of CPU I was thinking of! The article describes
a simple version of Lisp and a "hardware evaluator", which executes a
binary represantation of s-expressions. The last half of the article
describes the implementation (given some background information how long
various details took and who does it, it was a university project) down
to the gate level and placing on the chip area. Fortunately I don't need
to deal with this details, because the Xilinx tools does the chip
synthesis from Verilog without manual help, so I can focus on the
functionality.
> AI Memo No. 1040:
> "Scheme86: A System for Interpreting Scheme"
> Andrew A. Berlin and Henry M. Wu.
ftp://publications.ai.mit.edu/ai-pu...df/AIM-1040.pdf
not very detailed, but with interesting new ideas. Partly based on the
previous article.
I think now I have enough information to implement a little Verilog Lisp
evaluator, which I'll show in a new thread. Thanks for all your comments.
--
Frank Buß, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
| |
| Julian Stecklina 2004-08-09, 9:04 am |
| Pascal Bourguignon <spam@mouse-potato.com> writes:
> With M the constant: most-positive-fixnum.
>
> O(constant) = O(1).
Creative. But useless, nevertheless. :P
Regards,
--
____________________________
Julian Stecklina / _________________________/
________________/ /
\_________________/ LISP - truly beautiful
| |
| Thomas Schilling 2004-08-09, 9:04 am |
| Alexander Burger wrote:
>
> This is bad for several reasons:
>
> 1. The resulting program is not necessarily 100% equivalent.
But it's the purpose of a Lisp implemenetation to create a program that is
100% equivalent to the source code. Otherwise it's a bug.
> 2. Many of my applications consist of plenty of one-time code, typically
> GUI components. The file is loaded, executed, produces some side
> effects (Applet layout), and is thrown away. A compilation pass would
> be counter-productive.
The compilation takes part when you write the code and add it to your lisp
image. So nothing is compiled at runtime unless you use eval. And I doubt
you need that for the mentioned purpose. (Unless you don't have lexical
closures, since you'll hardly eval s-exps input of the user)
> 3. The GUI components contain many little s-expressions (function bodies
> or just simple lists) which may be later evaluated depending on user
> actions like mouse click and button press. I doubt it makes sense to
> compile such code fragments, which even cannot be meaningfully
> executed outside their dynamic environment.
Where're these actions run? On the client or on the server? If they're run
on the server it would even be safer to not store direct code in your gui
but just the function name.
Parsing a list from text isn't slower in a compiled system.
> 4. It has great advantages to execute s-expressions. Not so much in
> application programming, because the often-cited self-modifying Lisp
> programs are rare.
Never heard of. Actually how should this work? First-class macros? Calls
to eval at runtime? I guess the latter.
> But for the development of the Lisp system itself.
That may be.
> I want full control over my programming system. It has to be simple,
> so that I can understand and modify every aspect of it.
>
> For example, tracing is done in Pico Lisp by cons'ing a trace symbol
> in front of function or method bodies. The debugger (single stepper)
> consists of a few dozen lines which constantly modify s-expressions
> while they are executed. The same holds for the profiler.
>
> It is all so simple if you dare to abandon the compiler. Many lisp-ish
> (in my opinion) programming styles like (3) you don't even consider if
> you are caught in monolithic lexical compiler think.
I wouldn't want to miss lexical variables and closures, arrays,
hash-tables, generic functions, structures, etc. just for the sake of a
"real" lisp implementation.
--
,,
\../ / <<< The LISP Effect
|_\\ _==__
__ | |bb| | ________________________________________
_________
| |
| Julian Stecklina 2004-08-09, 9:04 am |
| Thomas Schilling <tjs_ng@yahoo.de> writes:
>
> Never heard of. Actually how should this work? First-class macros?
> Calls to eval at runtime? I guess the latter.
You could have a structure editor that edits the s-exp that a function
definition is made of in place. But then again, you could fire up
Emacs, edit the function and hit C-c C-c...
There are plenty of ways for a program to change parts of itself,
either.
Regards,
--
____________________________
Julian Stecklina / _________________________/
________________/ /
\_________________/ LISP - truly beautiful
| |
| Alexander Burger 2004-08-09, 3:58 pm |
| Julian Stecklina <der_julian@web.de> wrote:
> Alexander Burger <abu@software-lab.de> writes:
> [Compiled code]
[color=darkred]
> Your compiler is broken. ;)
Ok, probably it is no problem nowadays. As you may have noticed, my last
contact with (non-self-written) Lisp was nearly 20 years ago. Most Lisps
at that time used dynamic binding for the interpreter and lexical
binding for the compiler, introducing significant differences.
Then it depends on how you define "equivalent". Identical output for any
given input? I strongly doubt that, considering the complexity of that
matter.
[color=darkred]
> Many CLs have a compiler and an interpreter, if that really is a
> concern to you. They are totally transparent to the user as well. If
> at work I get thrown into the debugger because a GUI handler has a
> bug, I can fix it and restart the frame. It is meaningless whether
> this handler was compiled or not.
Then you have the double divantage of
- a complicated system (because it has to support the compiler)
- and inefficient execution (because the interpreter will run with a
lexical binding strategy to stay compatible with the (now unused)
compiler. Lexical binding is not efficient in an interpreter).
> Simplicity is nice to have, agreed. But living without strings and
> vectors per design...
Where do you absolutely need vectors?
Concerning strings, I agree. Pico Lisp uses Symbols for strings, if that
is enough for you. However, it supports amost no direct access to the
characters, only to the first one, or after you exploded them into a
list. I feel I can live very well with that. After unpacking, you have
the full power of Lisp for manipulating the characters.
[color=darkred]
> Why should you consider?
To bring more fun to programming.
- Alex
--
Software Lab. Alexander Burger
Bahnhofstr. 24a, D-86462 Langweid
abu@software-lab.de, http://www.software-lab.de, +49 821 9907090
| |
| Joe Marshall 2004-08-09, 3:58 pm |
| Frank Buss <fb@frank-buss.de> writes:
> But first I want to know how it was solved in other systems, like the
> Symbolics Lisp Machine. Where can I find a hardware description of the
> processor? Any other resources I should read?
Lisp Machine Progress Report - AI memo 444 (1977)
Alan Bawden, Richard Greenblatt, Jack Holloway, Thomas Knight, David Moon, Daniel Weinreb
Design of LISP-Based Processors[pdf] - AI memo 514 (1979)
Guy Lewis Steele Jr. and Gerald Jay Sussman
CADR - AI memo 528 (1979)
Thomas F. Knight, Jr., David Moon, Jack Holloway, and Guy L. Steele, Jr.
Symbolic language data processing system - US Patent No. 4887235
John T. Holloway, David A. Moon, Howard I. Cannon, Thomas F. Knight, Bruce E. Edwards, Daniel L. Weinreb
Scheme 86 - An Architecture for Microcoding a Scheme Interpreter - AI memo 953 (1988)
Henry M. Wu
Lisp Machine, Inc. K-machine
| |
| nikodemus@random-state.net 2004-08-09, 3:58 pm |
| Alexander Burger <abu@software-lab.de> wrote:
> Perhaps I have to state it the other way round: Macros do not make much
> sense in an interpreter, because they are rather inefficient here due to
> double evaluation. It is better then to implement the desired
> functionality as a function instead of a macro.
In an basic _evaluator_, you mean. An interpreter can "trivially" expand
macros only once should it want to. If you have't read SICP, maybe you
should...
> Besides this, and more important, is that the term "interpreting"
> connotates "explaining" and "searching for a meaning", which is typical
> for textual interpreters who have to lookup tokens in a symbol table
> (like the Lisp reader). Walking s-expressions involves no searching.
Interpreters walk internal data structures, "interpreting" them.
Evaluators are interpreters for parse-trees (the list structure in case of
lisp). SICP-style analyzing interpreters interpret chains of closures by
funcalling them. VM's are interpeters for bytecode. Your CPU is an
interpreter for machine code. The internal data structures themselves may
have more or less resemblance to the original code -- often less then
more.
"Lisp Machine" has a meaning: they existed and the term referred to them.
It may apply to other computers in the future -- and my belief is that
then the operative definition will have more to do with having lisp from
head to toes, and less with hardware support for language. We shall see;
but notice how I indicated that a part of the above statement has no
factual basis beyond my imagination.
"Interpreter" is a word with an accepted meaning. Deciding that only a
single class of interpreters are really interpreters is either stupid or
arrogant.
> But this case even supports my opinion that people blindly believe in
> (or believe to need) compilers, without checking the results.
Funny you should say so. "Why do you see the speck that is in your
brother's eye, but do not notice the log that is in your own eye? Or how
can you say to your brother, `Let me take the speck out of your eye,' when
there is the log in your own eye? You hypocrite, first take the log out of
your own eye, and then you will see clearly to take the speck out of your
brother's eye."
> This argument appears very often in such discussions. Do we really need
> arrays, vectors and strings, as is often proudly stated about the
> benefits of "modern" Lisp?
Yes.
> Again, this is again a matter of "execution speed" versus "power to the
> programmer" and "ease of handling". I gladly abstain from the first if I
> can gain the other two.
This sounds very much like you've been deeply influenced by Paul Graham
and Arc. He may be kook, but he's a smart kook: like he has said, there
will always be applications where there is never enough computing power
available. Those applications also tend to be quite hard, and therefore
very good candidates for lisp -- but with your approach the computation
that would have taken "just" a month will take a years, or several days
instead of an hour, etc.
PG's approach to this same issue is tempered by his understanding of
compilation: he speaks of compiler annotations allowing the "list" to be
laid out and accessed as an array, etc. It may be a pie in the sky, but at
least it's a pie.
Cheers,
-- Nikodemus "Not as clumsy or random as a C++ or Java.
An elegant weapon for a more civilized time."
| |
| Rainer Joswig 2004-08-09, 3:58 pm |
| Alexander Burger <abu@software-lab.de> wrote in message news:<2noui2F30sa2U1@uni-berlin.de>...
> Julian Stecklina <der_julian@web.de> wrote:
>
>
>
> This is bad for several reasons:
>
> 1. The resulting program is not necessarily 100% equivalent.
>
> 2. Many of my applications consist of plenty of one-time code, typically
> GUI components. The file is loaded, executed, produces some side
> effects (Applet layout), and is thrown away. A compilation pass would
> be counter-productive.
>
> 3. The GUI components contain many little s-expressions (function bodies
> or just simple lists) which may be later evaluated depending on user
> actions like mouse click and button press. I doubt it makes sense to
> compile such code fragments, which even cannot be meaningfully
> executed outside their dynamic environment.
>
> 4. It has great advantages to execute s-expressions. Not so much in
> application programming, because the often-cited self-modifying Lisp
> programs are rare. But for the development of the Lisp system itself.
>
> I want full control over my programming system. It has to be simple,
> so that I can understand and modify every aspect of it.
>
> For example, tracing is done in Pico Lisp by cons'ing a trace symbol
> in front of function or method bodies. The debugger (single stepper)
> consists of a few dozen lines which constantly modify s-expressions
> while they are executed. The same holds for the profiler.
>
> It is all so simple if you dare to abandon the compiler. Many lisp-ish
> (in my opinion) programming styles like (3) you don't even consider if
> you are caught in monolithic lexical compiler think.
Alex, it would interest me to know, how your system is different
from other 'normal' interpreters for Lisp?
- is there something different during interpretation? I thought
that the usual interpreter also walks over the internal representation
that the Lisp system uses for s-expressions.
- is it that the source code is represented in the system not as
text in a filesystem, but as internal data structures in
the run-time? This has been done for example with Interlisp-D,
where you edit your code with a structure editor.
one of the above? something else?
Rainer Joswig
| |
| John Thingstad 2004-08-09, 3:58 pm |
| sigh! It never ends..
On 9 Aug 2004 08:50:43 GMT, Alexander Burger <abu@software-lab.de> wrote:
> Julian Stecklina <der_julian@web.de> wrote:
>
> Perhaps I have to state it the other way round: Macros do not make much
> sense in an interpreter, because they are rather inefficient here due to
> double evaluation. It is better then to implement the desired
> functionality as a function instead of a macro.
>
> Having said that, I _do_ occasionally use Macros also in an interpreter,
> because they make the code more readable.
>
> But Lisp compilers depend on them. I don't know the current state of
> art, but 20 years ago it used to be so. The compiler did not support all
> necessary primitives. It implemented a few of them, and all others were
> defined as macros (for example, all conditional branching functions like
> 'if', 'when' etc. were converted to 'cond').
>
>
>
> Ok, the readers of this group know probably what is meant, but I did
> often meet people who were suspicios about an interpreter because they
> believed it operates on a textual basis.
>
> Besides this, and more important, is that the term "interpreting"
> connotates "explaining" and "searching for a meaning", which is typical
> for textual interpreters who have to lookup tokens in a symbol table
> (like the Lisp reader). Walking s-expressions involves no searching.
>
>
>
> In Lisp, many built-in functions like list manipulations or bignum
> arithmetics do very heavy work, as opposed to a bytecode which typically
> only moves a few bits around. Take an extreme but typical example (in
> Pico Lisp syntax):
>
> : (mapcar + (1 2 3 4) (5 6 7 8 9))
> -> (6 8 10 12)
>
> After 'mapcar' has evaluated its arguments, the whole process runs in
> full 'C' speed, no more glue involved.
>
>
>
> When I wrote that, CLISP was the only Lisp I had access to, and I did
> not know (or care) what it compiled to.
>
> But this case even supports my opinion that people blindly believe in
> (or believe to need) compilers, without checking the results.
>
> I expected, of course, a compiled Lisp to be significantly faster than
> Pico Lisp. And this will surely be the case with many other Lisps. But
> according to my experiences, the raw speed gain is not worth all the
> divantages. That's what I tried to explain in that paper.
>
> 20 years ago I was also a speed fanatic. I coded anything possible in
> assembly language. I hope I'm more wise by now ;-)
>
>
>
> This argument appears very often in such discussions. Do we really need
> arrays, vectors and strings, as is often proudly stated about the
> benefits of "modern" Lisp?
>
> First of all, it has great advantages to use lists for sequential data,
> because of the wealth of list processing functions the language
> provides.
>
> Sure, it is inefficient if you want to access the 1000th element in a
> List. But how often does that happen? I cannot recall a single case. In
> Lisp, you don't iterate over a sequence with an index like e.g. in C or
> Java
>
> for (i = 0; i < arr.length; ++i)
> ... a[i] ...;
>
> but you typically use one of the mapping functions. Or you search the
> list sequentially, or perform some other operation while traversing it.
>
> Such a long list more likely smells like a design bug. To handle large
> amounts of uniform data, I rather use more structured data like nested
> (and thus shorter) lists or trees (also implemented in lists, of
> course).
>
> For small amounts of data, the overhead for let's say 'cdddr' or 'nth'
> is usually acceptable.
>
> Again, this is again a | | |