4 ms·

Ask HN: How many logic gates would it take to implement a small Lisp language?

7 points by nyellin 15y ago

This question was posted to r/lisp and went unanswered. I am hoping someone from HN might be more knowledgable.

tluyben2 15y ago
To figure that out, you would have to try it. I guess you Googled and found some interesting things like; http://www.frank-buss.de/lispcpu/ http://www.frank-buss.de/lispcpu/ but no answer to your question. So get out your pen & paper and build one :)
_0ffh 15y ago
Unfortunately the question is, strictly speaking, unanswerable. The best one could do is come up with a specific design and estimate the number of gates needed, and then one couldn't be sure exactly how suboptimal the design in question is, regarding gate count. One of the most basic design choices is probably how much and which work to do using dedicated logic, and how much to do using general purpose logic and microcode. One may get an idea of the order of magnitude of gates required by taking a minimal CPU core (say, the j1 core from http://excamera.com/sphinx/fpga-j1.html http://excamera.com/sphinx/fpga-j1.html), writing a minimal lisp interpreter on that core, and adding the gates needed to store the interpreter to the number of gates used for the core. This is left as an exercise for the reader.
- tluyben2 15y ago
  I would and have suggested, to take basic logic gates and create a 'simple lisp' (what is that actually?) on top of those. It'll take you 'a while', but it's definitely possible and after that you can simply count the logic gates you used. Strictly speaking the question is wrong ; what is a simple lisp, what features are required etc etc, then it's answerable by actually designing it from scratch with logic gates. Of course it also will depend on how good you are at actually implementing such basic systems; I've seen CPUs built from logic gates in college which had wildly different numbers of gates between the teams. You can do a crap job with anything ;) Still you would have an indication.
  - _0ffh 15y ago
    Yeah, that's basically doing the whole thing using specialised "lisp circuitry". Approaching the task from the other extreme, by just implementing the interpreter in microcode, would be much simpler - and I doubt that the end result would differ wildly in the number of gates used. I think this is basically a kind of minimal description length problem. And yes, you can do a crap job with anything ;) Edit: Btw. LISP 1.5 for the IBM 704 seems to be something like 10k lines of assembly code.
adatta02 15y ago
http://lambda-the-ultimate.org/node/3583 http://lambda-the-ultimate.org/node/3583 might be a good starting point assuming that an implementation of lambda calculus qualifies as a LISP (it should).

7 points by nyellin 15y ago

This question was posted to r/lisp and went unanswered. I am hoping someone from HN might be more knowledgable.

To figure that out, you would have to try it. I guess you Googled and found some interesting things like; http://www.frank-buss.de/lispcpu/ http://www.frank-buss.de/lispcpu/ but no answer to your question. So get out your pen & paper and build one :)

_0ffh 15y ago

Unfortunately the question is, strictly speaking, unanswerable. The best one could do is come up with a specific design and estimate the number of gates needed, and then one couldn't be sure exactly how suboptimal the design in question is, regarding gate count. One of the most basic design choices is probably how much and which work to do using dedicated logic, and how much to do using general purpose logic and microcode. One may get an idea of the order of magnitude of gates required by taking a minimal CPU core (say, the j1 core from http://excamera.com/sphinx/fpga-j1.html http://excamera.com/sphinx/fpga-j1.html), writing a minimal lisp interpreter on that core, and adding the gates needed to store the interpreter to the number of gates used for the core. This is left as an exercise for the reader.

tluyben2 15y ago
I would and have suggested, to take basic logic gates and create a 'simple lisp' (what is that actually?) on top of those. It'll take you 'a while', but it's definitely possible and after that you can simply count the logic gates you used. Strictly speaking the question is wrong ; what is a simple lisp, what features are required etc etc, then it's answerable by actually designing it from scratch with logic gates. Of course it also will depend on how good you are at actually implementing such basic systems; I've seen CPUs built from logic gates in college which had wildly different numbers of gates between the teams. You can do a crap job with anything ;) Still you would have an indication.
- _0ffh 15y ago
  Yeah, that's basically doing the whole thing using specialised "lisp circuitry". Approaching the task from the other extreme, by just implementing the interpreter in microcode, would be much simpler - and I doubt that the end result would differ wildly in the number of gates used. I think this is basically a kind of minimal description length problem. And yes, you can do a crap job with anything ;) Edit: Btw. LISP 1.5 for the IBM 704 seems to be something like 10k lines of assembly code.

adatta02 15y ago

http://lambda-the-ultimate.org/node/3583 http://lambda-the-ultimate.org/node/3583 might be a good starting point assuming that an implementation of lambda calculus qualifies as a LISP (it should).