Ask HN: Modern Lisp (Scheme) CPU?

https://news.ycombinator.com/item?id=7706952

by rthomas6 • 12 years ago

12 6 12 years ago

news.ycombinator.com

Would it be possible/useful to design a CPU with a Scheme dialect as its machine language? My idea for this is in the comments (It's too long for this text box).

rthomas6• 12 years ago

I've started working through SICP in my free time [1], and I'm an electrical/computer engineer who looks at HDL and hardware all day at work. I haven't worked through this idea so it may not be possible or useful (this is most likely), but it seems to me that a simple lisp itself could be the machine code of a massively parallel CPU architecture, with minimal compilation.

Scope in Scheme is built into the language in an explicit way. The SICP Scheme dialect contains very few constructs to implement as instructions. My basic idea is to have many many simple processor units that evaluate only a given scope of an s-expression. For instance, starting from the beginning of an expression, core A reads the first operator and starts executing it on the following data. We continue to perform that operation until either encountering "([operator]", which engages a new core (let's call it core B) and toggles some kind of flag/register to notify this core to expect a result from core B, or ")", upon which we output the result, given we're not waiting on something below to finish.

Now where this gets awesome is the core A in the example above can continue to execute at its own scope level while waiting for a result, and kick off any other lower-scope expressions it finds along the way. Assuming the order of the data does not matter (it usually doesn't!) a given core only has to idle when it's reached the end of its own scope and is waiting on a lower level.

For example, let's say we have:

  (define (fib n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (fib (- n 1))
                   (fib (- n 2))))))

  (fib 5)

Right now I'm thinking a function definition will simply compile into an address label. So execution would really begin with (fib 5). Then we get to cond, which is really just a sequence of conditional branches. Even here we can probably have two separate cores evaluate (= n 0) and (= n 1) simultaneously. Even though order matters in this case, perhaps we could come up with some way to keep track of it.

Anyway, then the fun part begins. A core evaluates + and starts waiting, and two other cores evaluate (fib (- 5 1)) and (fib (- 5 2)), which means that in turn, two more cores are dispatched to evaluate (- 5 1) and (- 5 2). They return 4 and 3, and the two other cores both branch to the fib function, one with 4 in its personal register, and one with 3. And so on. The result of this for this function is that, handwaving away the conditional for now, and assuming lower levels of scope are able to be "skipped over" when being read, (fib n) as written is calculated in linear time, and with a normal processor it's exponential time (c^n).

With this architecture, the "stack" would just be the number of cores. I don't know if this is an efficient use of hardware, but I think the cool thing about it would be it would make a lot of programs execute more in parallel, as written.

[1] I'm only at the end of chapter 1 though. Progress is slow but already rewarding.

qbrass• 12 years ago

You'll probably be interested in the Lambda Papers. http://library.readscheme.org/page1.html

You may also be interested in the Connection Machine thesis. http://dspace.mit.edu/handle/1721.1/14719

read• 12 years ago

I loved this idea! Check out the Lisp machine that ended up implementing a parallelization similar to what you are describing.

http://en.wikipedia.org/wiki/Lisp_machine

Is there a way to get in touch with you? I'd be happy to help with the software. Or at least, the definition of a Lisp that's shorter than the current Lisp.

I also noticed there are tools that can convert from C to an FPGA (in Verilog?) Does this mean that if someone where to write a short Lisp interpreter in C one of these tools could convert it into a hardware specification?

sparkie• 12 years ago

Have you looked at some of the existing literature in this area? Lisp based processors were developed and researched in the 70s and 80s, mainly at the MIT AI lab.

Some reading:

The Lambda papers: http://library.readscheme.org/page1.html

A lisp processor for C.ai: http://repository.cmu.edu/cgi/viewcontent.cgi?article=2977&c...

CONS: http://bitsavers.trailing-edge.com/pdf/mit/cons/CONS_Nov1974...

CADR: http://dspace.mit.edu/handle/1721.1/5718

SCHEME-79: http://dspace.mit.edu/handle/1721.1/6334

Implementation of a list processing machine: http://not.meko.dk/MIT-LISP-MACHINE-tk-sm-79.pdf

The CURRY chip: http://carlo-hamalainen.net/stuff/p122-ramsdell_The-CURRY-Ch...

Just found a bunch more reading resources indexed here: http://www.ugcs.caltech.edu/~weel/lispm.php

There's much more to read if you search around - and some more modern stuff, as it is still a topic of interest among some hackers. It'd probably help to look around and collaborate with other people working on similar ideas.

I'm interested, but I don't know nearly enough about hardware yet to actively participate. I've been trying to find the time for it - just finished reading a book on VHDL and practising the basics, but I've got too many other projects on to give it my full attention.

jonjacky• 12 years ago

Here are some projects that put new Lisp machine architectures on FPGAs:

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

brudgers• 12 years ago

Chuck Moore's GreenArrays chips for Forth might be a source for inspiration.

http://www.infoq.com/presentations/power-144-chip?utm_source...

Ask HN: Modern Lisp (Scheme) CPU?

Related Stories