Lisp in hardware

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?

--
Frank Buß, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

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 shoul
d
> 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.

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.

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

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]

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.

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.

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 ***

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 shoul
d
> 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.

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