|
Hi Has anyone considered building LISP machine? I know that RISC is the orthodox religion of the day, but it seems to me that it might be fun to build a small LISP engine. The hardest part would be a garbage collector. Comments anyone? -jc |
|
|
lisp machine anyone?
Started by ●May 19, 2003
Reply by ●May 21, 20032003-05-21
|
Campbell, John wrote: > Hi > Has anyone considered building LISP machine? I know that > RISC is the orthodox religion of the day, but it seems to me that > it might be fun to build a small LISP engine. The hardest part > would be a garbage collector. Comments anyone? -jc Garbage collection is a high level function. Somebody did write about a simple lisp CPU years ago. 1985? Ben. |
Reply by ●May 21, 20032003-05-21
|
Campbell, John wrote: > Has anyone considered building LISP machine? I know that > RISC is the orthodox religion of the day, but it seems to me that > it might be fun to build a small LISP engine. The hardest part > would be a garbage collector. Comments anyone? -jc First, whether RISC is the religion of the day is debatable, at least outside FPGA CPUs. The P4/Athlon of the day is one of the fastest available microprocessors, but it's implementation is not RISC by any meassure and the complexity far outweights the dataflow, Lisp machine, etc of the hayday. In fact, the complexity of those day machines is nothing that couldn't conviently be realized in an FPGA. I'd love to play with a Lisp/Smalltalk/Haskell/etc (HL from now on) FPGA machine. In fact I have two ideas for a graph reduction machine for non-strict (~ lazy) functional programming language, such as Haskell. One based on a traditional STG abstract machine, the other on Lennarts BigWord machine. I trust you noticed the old PhD thesis on the MIT Lisp machine that appeared on comp.arch some weeks ago. There was many interesting idea there, although priorities for modern system have change a bit (memory is slow but plentiful, nearly the opposite of those days). I've rambled long enough, but let me add why I think a HL machine might be fun even in these days of 3GHz PCs. The fact is that high-level languages are pretty much memory limited on these systems anyway, bandwidth and especially latency wise, and it's not hard to drive a 200 MHz DDR from an FPGA, so memory performance is pretty much at parity, modulo those fat 1+ MB caches. Contrary to software mappings to existing architectures, all the advanced tagging schemes and complitated nodes handling can be done almost for free in an FPGA due the the parallel nature. CDR coding comes to mind as an example: tag bits are allocated in cons cells to indicate that the CDR is really the first word in the tail, and not a pointer to the tail. That trick can save up to half the memory (and thus memory bandwidth) but is excessively expensive to do in a software implementation. Lennart's machine has cool ideas for graph reduction. Jecel has been playing with Smalltalk and Self FPGA machines for years now and has some good ideas on his site: http://www.merlintec.com:8080/software/3 FPGAs are fun! /Tommy |
Reply by ●May 21, 20032003-05-21
|
>From: "Campbell, John" <> >Reply-To: >To: <> >Subject: [fpga-cpu] lisp machine anyone? >Date: Mon, 19 May 2003 13:25:14 -0600 > >Hi >Has anyone considered building LISP machine? I know that >RISC is the orthodox religion of the day, but it seems to me that >it might be fun to build a small LISP engine. The hardest part >would be a garbage collector. Comments anyone? -jc It's something I've often thought about. Symbolics actually put a LISP Machine on a chip, called Ivory. Sussman and some of his students put Scheme onto a custom chip. Leon -- Leon Heller, G1HSM Tel: +44 1424 423947 Email: My web page: http://webspace.webring.com/people/jl/leon_heller/ _________________________________________________________________ It's fast, it's easy and it's free. Get MSN Messenger today! http://www.msn.co.uk/messenger |
Reply by ●May 21, 20032003-05-21
|
>From: Tommy Thorn <> >Reply-To: >To: >Subject: Re: [fpga-cpu] lisp machine anyone? >Date: Wed, 21 May 2003 00:44:17 -0700 > >Campbell, John wrote: > > Has anyone considered building LISP machine? I know that > > RISC is the orthodox religion of the day, but it seems to me that > > it might be fun to build a small LISP engine. The hardest part > > would be a garbage collector. Comments anyone? -jc > >First, whether RISC is the religion of the day is debatable, at least >outside FPGA CPUs. The P4/Athlon of the day is one of the fastest >available microprocessors, but it's implementation is not RISC by any >meassure and the complexity far outweights the dataflow, Lisp machine, >etc of the hayday. > >In fact, the complexity of those day machines is nothing that couldn't >conviently be realized in an FPGA. > >I'd love to play with a Lisp/Smalltalk/Haskell/etc (HL from now on) FPGA >machine. In fact I have two ideas for a graph reduction machine for >non-strict (~ lazy) functional programming language, such as Haskell. >One based on a traditional STG abstract machine, the other on Lennarts >BigWord machine. > I had a look inside a LISP Machine once; it used lots of AMD bit-slice chips on a very large PCB, with similar size PCBs for the memory, stacked one above the other. It belonged to a consultant who had it in his living room, his maintenance contract probably cost as much as many people were actually earning at the time. The whole CPU would fit into a Spartan-II, I would think. Leon -- Leon Heller, G1HSM Tel: +44 1424 423947 Email: My web page: http://webspace.webring.com/people/jl/leon_heller/ _________________________________________________________________ On the move? Get Hotmail on your mobile phone http://www.msn.co.uk/msnmobile |
Reply by ●May 21, 20032003-05-21
|
Tommy Thorn wrote: > I've rambled long enough, but let me add why I think a HL machine might > be fun even in these days of 3GHz PCs. The fact is that high-level > languages are pretty much memory limited on these systems anyway, > bandwidth and especially latency wise, and it's not hard to drive a 200 > MHz DDR from an FPGA, so memory performance is pretty much at parity, > modulo those fat 1+ MB caches. Contrary to software mappings to > existing architectures, all the advanced tagging schemes and complitated > nodes handling can be done almost for free in an FPGA due the the > parallel nature. CDR coding comes to mind as an example: tag bits are > allocated in cons cells to indicate that the CDR is really the first > word in the tail, and not a pointer to the tail. That trick can save up > to half the memory (and thus memory bandwidth) but is excessively > expensive to do in a software implementation. Lennart's machine has > cool ideas for graph reduction. Jecel has been playing with Smalltalk > and Self FPGA machines for years now and has some good ideas on his > site: http://www.merlintec.com:8080/software/3 > > FPGAs are fun! TTL is more fun! The problem with lisp and other list langauges is that lists are still binary primitives.[head][tail] How ABOUT trinary lists for a change. Somewhere here they had trinary sorts. http://www.trinary.cc/ |
Reply by ●May 21, 20032003-05-21
|
Tommy Thorn wrote: > In fact I have two ideas for a graph reduction machine for > non-strict (~ lazy) functional programming language, such as Haskell. > One based on a traditional STG abstract machine, the other on > Lennarts BigWord machine. I had in mind starting out with Lispkit (from Peter Henderson's "Functional Programming Application and Implementation"). Lispkit is a very small lisp with, if I remember correctly, lazy evaluation. I once (15 years ago) did a lisp compiler for the PC that evolved from Lispkit. So its a starting point I've used before. Eventually I'd like to experiment with alternative list structure transparent to the software. > I trust you noticed the old PhD thesis on the MIT Lisp machine that > appeared on comp.arch some weeks ago. Actually, no, I missed that. A quick search didn't succeed either. can you give me a pointer? >FPGAs are fun! Couldn't agree more. -jc |
Reply by ●May 21, 20032003-05-21
|
Campbell, John wrote: > I had in mind starting out with Lispkit (from Peter Henderson's > "Functional Programming Application and Implementation"). Lispkit > is a very small lisp with, if I remember correctly, lazy evaluation. > I once (15 years ago) did a lisp compiler for the PC that evolved > from Lispkit. So its a starting point I've used before. I don't know Lispkit, but writing an abstract machine for Lisp is really trivial. It's still easy for Lisps with static Scope, like Scheme (why anyone would use dynamic scope today is beyond me), see fx. John C. Reynolds landmark paper "Definitional Interpreters for Higher-Order Programming Languages" from 1972, or the reprint ftp://ftp.cs.cmu.edu/user/jcr/defint.ps.gz. Writing an efficient one (ie., with a flat environment) is harder, but not too hard. Unfortunately, none of the textbooks I've ever seen covers how to. Xavier Leroy's "The ZINC experiment: an economical implementation of the ML language." is quite excellent and the refined version he applies in O'Caml is even better. His machine is tuned for Caml's (wonderful) use of curried functions which you wouldn't need for Scheme, so it could even be simplified. My own PocketHaskell (not finished, nor published) is kind of a cross between Xavier's refined machine and the STG machine of the Glasgow Haskell Compiler of a few years back. I have a demo of the (very fast) abstract machine running on my PalmPilot (alas, sans GC), but the compiler isn't exactly production quality. > Eventually I'd like to experiment with alternative list structure > transparent to the software. Obviously you know that experimenting with a software model is orders of magnitude easier than with a hardware implementation (even FPGA). >>I trust you noticed the old PhD thesis on the MIT Lisp machine that >>appeared on comp.arch some weeks ago. > > Actually, no, I missed that. A quick search didn't succeed either. > can you give me a pointer? Argh. I vaguely recall that it was a temporary link, so I've put it up on my site (temporarily as well): http://not.meko.dk/MIT-LISP-MACHINE-tk-sm-79.pdf [8.9MB]. Beware that my server on an DSL - that is 256 kbps upstream, so it's slow. Enjoy, Tommy |
