Lisp CPU

[TD-Linux]

This would be interesting, but it looks like it has been barely started - the CPU is barely what I would call a CPU, let alone a Lisp interpreter.

Verilog isn't a programming language (it tries to be, unfortunately). For synthesis, it is a hardware description language. Someday I'll write up some decent Verilog tutorials because there aren't any good ones on the Internet.

[jff]

My thoughts exactly. When I saw "Perhaps the Verilog language is not so good, because some nice standard language featuers (forever-loop etc.) are missing in the Xilinx-Tools.", I had flashbacks to VHDL class, students writing loops and then wondering why they couldn't synthesize the code. You have to get yourself into a hardware mindset, thinking about clocks and state machines and enable lines rather than infinite loops.

[iso8859-1]

Won't you help us write this one: https://en.wikibooks.org/wiki/Programmable_Logic/Verilog ?

[alain94040]

Let me know when you do so, I can help.

[theon144]

Please do! I've wanted to learn FPGAs for years now, never really got around to it because it's really so niche there's not that much quality tutorials.

[feider]

Just let us know when you have writen some tutorials - Im waiting :)

[mhewett]

You need to look at The Architecture of Symbolic Machines by Peter Kogge. It contains a machine you can implement. I have implemented it in the Jatha LISP interpreter ( http://sourceforge.net/projects/jatha/ ).

[jff]

I'd like to point out that the code he has on there isn't a Lisp CPU and I don't think will even work in a real FPGA. I don't know Verilog, just VHDL, but that business in the INIT state looks sketchy to say the least. Even if it does work, it just loads a few instructions into memory & executes them; these instructions blink an LED on the board. The Lisp architecture is barely described beyond a few sparse notes about a tagged memory arch (not implemented).

I'm not attacking the original author; these look like personal notes as he explores an FPGA and realizes that hardware design is complicated. But don't get your hopes up on this being... well, anything.

[simias]

yeah it's definitely not synthesizable in its current state, not to mention that he's going to have a bad time if he messes with the clock the way he does in this code (the way he generates his slowClock, unless his tools are clever enough to recognize this pattern and do the right thing).

It's a cool project though, but if I were him I'd learn the language with some simpler and smaller designs, maybe some stuff he'll be able to re-use in his final CPU.

As it is it reads a bit like someone who wants to write a kernel in C while not understanding how pointers work.

[ChuckMcM]

This was started back in 2004 and the last update was in 2007 apparently [1], not a lot of the content changed. Building CPUs in FPGAs is fun, a lot of the demo boards available these days already have memory and often either an SD card type interface or some sort of NAND flash attached. A good place to start if your interested is fpgacpu.org ( not exactly a 'live' site but there is good info in there ) or opencores.org.

[1] http://web.archive.org/web/*/http://www.frank-buss.de/lispcp...

[jonjacky]

These more recent projects also made Lisp machines in FPGAs. It looks like they got further than the original post here:

LispmFPGA (2008) http://www.aviduratas.de/lisp/lispmfpga/

https://groups.google.com/forum/?fromgroups=#!topic/comp.lan...

IGOR (2008) http://opencores.org/project,igor

https://www.flickr.com/photos/kaitorge/sets/7215760944571932...

[wes-exp]

I'd like to see a modern CPU that handles dynamic typing in hardware. Registers can store values as well as the type, e.g. 32 value bits and a few type bits. Basic arithmetic like addition can automatically compare the type bits and just do the right thing with a single instruction (fixnum add, float add, bignum add, etc.).

Would this be cool or am I dreaming?

[Rusky]

Not quite dynamic typing, but the Mill CPU stores a lot of metadata in-CPU (which is lost when written to memory)- things like size, vector width, validity of the value (as opposed to faulting immediately) or ALU status bits (overflow, zero). The particular interpretation of the bits is still left up to the opcode used, but it does enable some neat tricks that vaguely remind me of dynamic typing.

http://millcomputing.com/topic/metadata/

[stefanu]

That reminds me SOAR[1] (from 1984): Smalltalk on a RISC

Smalltalk on a RISC (SOAR) is a simple, Von Neumann computer that is designed to execute the Smalltalk-80 system much faster than existing VLSI microcomputers. The Smalltalk-80 system is a highly productive programming environment but poses tough challenges for implementors: dynamic data typing, a high level instruction set, frequent and expensive procedure calls, and object-oriented storage management. SOAR compiles programs to a low level, efficient instruction set. Parallel tag checks permit high performance for the simple common cases and cause traps to software routines for the complex cases. Parallel register initialization and multiple on-chip register windows speed procedure calls. Sophisticated software techniques relieve the hardware of the burden of managing objects. We have initial evaluations of the effectiveness of the SOAR architecture by compiling and simulating benchmarks, and will prove SOAR's feasibility by fabricating a 35,000-transistor SOAR chip. These early results suggest that a Reduced Instruction Set Computer can provide high performance in an exploratory programming environment.

[1] http://dl.acm.org/citation.cfm?id=808182

[eudox]

I'm pretty sure it was already done in the Symbolics Lisp Machine.

[gfour]

You may be interested in this article: "Tagged architecture: How compelling are its advantages?", http://dl.acm.org/citation.cfm?doid=327070.327153 (unfortunately behind a paywall).

[read]

Dynamic typing in hardware seems like one of the best kept secrets. It's probably easier for a software guy to think of adding dynamic typing in hardware than it does a hardware guy to want to program in a dynamic language.

[rjsw]

There is support for tagged arithmetic in 32-bit SPARC CPUs.

[Brashman]

It sounds feasible, but I believe you would also have to augment data values in memory with this type. Every 32 bits in memory would also need a few bits associated with it for type and the memory buses would need to be widened to move these around.

[stcredzero]

I've spoken personally to VM implementers, and yes, it would be very cool and useful besides, and yes, you are still perhaps dreaming.

[TazeTSchnitzel]

Wouldn't a "Lisp CPU" be like the one in the classic Lisp Machines, which didn't execute Lisp directly, but were optimised for executing it?

[rjsw]

The ideas on the web page are closer to the Scheme-79 chip [1] than a Lisp Machine.

[1] http://dspace.mit.edu/handle/1721.1/6334

[peaton]

I am not an expert, but I am definitely thinking the same thing.

[swetland]

Jeff's LispMicrocontroller is another example of this sort of thing (but a bit further along, it seems): https://github.com/jbush001/LispMicrocontroller

[adrianm]

This looks like a really fun project. I'd be interested in any good Verilog resources anyone can recommend. Also, does anyone know if there is there an affordable way to get components you design manufactured on a small scale? (Not in the thousands of units, I mean.)

[peaton]

FPGAs are definitely the way to go. They are cheap and reprogrammable. One awesome devboard is the Zedboard. It includes 2 (?) ARM cores and a 28nm FPGA.

[daveloyall]

I'm not familiar with Verilog. I wonder if something like this[1] would be a useful tool in this developer's belt.

1: http://www.cs.colby.edu/djskrien/CPUSim/

[listic]

What are the good convenient and modern FPGA's good for a modern computer?

I'm not sure what I'm asking here, really. I would ask for a PCE-Express board, but I've switched to a laptop as my main machine, with external monitor, keyboard and mouse when in home/office. I guess a PCE-Express board that could in principle be used in a rack-mount server would be useful.

[wmf]

Probably a Zedboard.

[Brashman]

As written, that INIT section is really going to limit clock speed. I also don't understand why currentState is double clocked.

[scott_wilson46]

It's not going to limit clock speed, its just not going to work. To write multiple values to different ram locations (considering a ram has at most two ports) would require you to stay in the INIT state for 9 cycles and do something like:

  INIT:
    begin
    if (count == 9) begin
      next_count == 0;
      nextState = `EVALUATE;
    end
    else 
      next_count == count + 1;
    case (count)
      0: begin ram_wr_addr = count; ram_wr_data = `CMD_LED_ON; ram_wr_en = 1; end
      1: begin ram_wr_addr = count; ram_wr_data = `CMD_LOAD_NEXT_TO_ACCU; ram_wr_en = 1; end
      etc....
    end

usually you have a ram module that takes an address and some write_data, wr_en, etc rather than accessing the array directly.

[joelby37]

Using double-edge clocking usually comes from a misunderstanding about how FPGA timing works. When you look at a waveform in a simulator, it's intuitive to think that you would need to change states at opposite edges to guarantee setup time. The synthesis tools will actually guarantee that setup times are met even if you use the same clock edge, though.

Also, the use of a clock divider in this way is bad practice and another trap for beginners. Use clock that are on global clock lines, and use a clock enable to slow things down.

[moron4hire]

It always surprises me to see these sorts of projects NOT based on Racket. I guess that is the danger of Scheme, it's so easy to reimplement the base language that everyone is doomed to spending lifetimes reimplementing the standard libraries.

[stcredzero]

Perhaps the next "next Java" or "next C++" had better focus on also being a more or less universal platform, such that the reimplementation of standard libraries becomes a thing of the past? The CLR strove to be this, but this didn't take off because of its association with Microsoft.

The "designed to be hosted" structure of Clojure points the way to how this could be approached. Stallman's designs for Scheme and GUILE are along these lines as well.

[JoshTriplett]

There are quite a few Scheme implementations, and Racket isn't necessarily the obvious choice. However, it does surprise me to see a reimplementation rather than using at least one of the existing implementations.

[michaelmike]

I'm not exactly sure Racket existed when this project was created. Furthermore, Racket is non-standard. Which is really the issue with Scheme. Prior to Racket there were SLIB and SRFIs. Which are still non-standard, but at least more universal.