7 ms·

Stack Computers: the new wave (1989)

98 points by JoachimS 4y ago

digdugdirk 4y ago
Not sure if this quite counts for what I'm asking, but: Is there a good list of "fundamentally new" types of computing paradigms over time? I'd love to see what paradigms branched off of others, what reached dead ends and why, etc.
- xhevahir 4y ago
  There's this chart: http://666-bits.blogspot.com/2007/08/principal-programming-paradigms.html?m=1 http://666-bits.blogspot.com/2007/08/principal-programming-p...
- 7thaccount 4y ago
  I've seen some chart like this before. For example, APL started the array family that has APL, J, A+, K, Kona...etc. Algol started the procedural family of Algol, Fortran, Basic...etc. Lisp started the family of lisp languages...and so on. The taxonomy is convoluted and not quite that neat though.
buescher 4y ago
Koopman's more recent "Better Embedded System Software" is a great overview of its subject.
metalforever 4y ago
I had this guy as a professor and he was great.
- LAC-Tech 4y ago
  Would love to hear more about this. The stack machines book is the only computer architecture book I've read cover to cover.
rwmj 4y ago
The conventional view is that stack computers didn't scale because they're very demanding in memory bandwidth - every operations ends up reading 2 operands from memory and perhaps writing one result back. Which is of course exactly the wrong thing because registers got much faster than RAM. But they're also elegantly small. Are there any stack computers used today, perhaps in systems where slow speed is not a problem but ultra small size (and code size) is an advantage? I only see https://en.wikipedia.org/wiki/ZPU_(microprocessor) https://en.wikipedia.org/wiki/ZPU_(microprocessor) (2008) - 442 LUTs(!).
- rahen 4y ago
  When Burroughs started experimenting with stack processors in their B5000 computer, they didn't do it for code size but the ability to use high level languages first, going as far as to hide assembly language to the user. Compilers are fairly straightforward to write on such an architecture, and can produce reasonably fast machine code in one pass. A register based CPU make this quite more complex, and is indeed a more performant but less elegant approach than a stack based CPU. This later inspired HP for the HP 3000 and then its RPN calculators, as well as other, lesser known machines. Nowadays I think I've only seen this with the JVM (to reduce the IL size) and a couple MCUs.
  - retrac 4y ago
    Stack-based VMs are more common than just the JVM. Python and Ruby's bytecodes are stack-oriented. Stack machines are also still common for compilers where "good enough" code is acceptable. As you say, it's relatively easy to write a code generator for a stack machine.
    - int_19h 4y ago
      CIL (.NET bytecode) is also stack-based, and perhaps the most interesting modern incarnation as well, because it is sufficiently full featured - pointers w/arithmetic, unions, stackalloc etc - to be a target for a C compiler.
dang 4y ago
Related: Stack Computers: the new wave (1989) - https://news.ycombinator.com/item?id=12237539 https://news.ycombinator.com/item?id=12237539 - Aug 2016 (28 comments) Stack Computers: the new wave (1989) - https://news.ycombinator.com/item?id=8657654 https://news.ycombinator.com/item?id=8657654 - Nov 2014 (3 comments) Stack Computers: the new wave (1989) - https://news.ycombinator.com/item?id=4620423 https://news.ycombinator.com/item?id=4620423 - Oct 2012 (37 comments)
pohl 4y ago
This reminds me that it's been a while since I've checked in on the belt machine that Ivan Godard & friends were working on at Mill Computing. It looks like their website has change a bit since I last looked: https://millcomputing.com/ https://millcomputing.com/
bmitc 4y ago
Does anyone know of the state of the art of stack and symbolic CPUs? I'm reading a few books that address stack computers and also symbolic CPUs, ones which may run things like Forth, Prolog, and Lisp directly on the CPU (or more directly rather than via abstractions sitting on top of Von Neumann architectures). The ideas in the books, such as those in A High Performance Architecture for Prolog, seem important and useful, but it's hard to tell if they aren't useful in today's modern age or if they simply fell out of favor or interest. In today's age with FGPAs, ASICs, RISC-V, etc., it seems ripe territory for custom CPU development, but about the only thing I know of that is along the lines of the above is the GreenArrays GA144 chip. https://www.greenarraychips.com/ https://www.greenarraychips.com/
- abecedarius 4y ago
  25 years old, but http://bernd-paysan.de/4stack.html http://bernd-paysan.de/4stack.html sounded interesting at the time.
- tdeck 4y ago
  There were a bunch of Java chips in the early 2000s, and ARM cores with a subset of the JVM instruction set. https://en.m.wikipedia.org/wiki/Java_processor https://en.m.wikipedia.org/wiki/Java_processor https://en.m.wikipedia.org/wiki/Jazelle https://en.m.wikipedia.org/wiki/Jazelle
manholio 4y ago
I wonder how soon we will have microarchitectures that are purely the result of some deep learning algorithms optimizing for performance and compilability of high level languages. We would be able to prove them correct - that they correctly execute the code and have no exploitable bugs - but we will have almost no idea how exactly they achieve said performance.
- mlyle 4y ago
  I don't think we really know how to learn code generation techniques and prove them correct, yet. That would be, in general, a really neat and useful trick.
  - batmanturkey 4y ago
    What, divide in half and compare?
- batmanturkey 4y ago
  I can’t find the link atm, but the reference was a self-optimized circuit that achieved xyz objective but the actual fpga bitstream was a p&r nightmare of latches and impossible simplifications taking advantage of phantom this and inductive that all accidentally and due to proximity but measured results and feedback and such. Totally specific and local, down to clock skew usage, whatever, no one understood it… will have to find the link…
  - manholio 4y ago
    That sounds about right. Why bother with a clock anyway, asynchronous is the way of the hardware samurai. Although it should be fuzzed a bit with signal and power noise, to kill those "solutions" that only work due to a lucky photo-resist error that manifests itself at exactly 3.03V.
mud_dauber 4y ago
I worked with Phil back in the day at Harris Semi on their RTX architecture. AFAIK it was used on a couple of space probes due to small size, consistent code execution, and (I think) the ability to offer a rad-hard design for space. Forth was the language of choice. I wish it could come back, because it was such a neat mind exercise.
shrubble 4y ago
The old Byte magazine's special edition that covered Modula-2 described the Lilith workstation as a stack machine CPU. It's on archive.org .

98 points by JoachimS 4y ago

Not sure if this quite counts for what I'm asking, but: Is there a good list of "fundamentally new" types of computing paradigms over time? I'd love to see what paradigms branched off of others, what reached dead ends and why, etc.

xhevahir 4y ago
There's this chart: http://666-bits.blogspot.com/2007/08/principal-programming-paradigms.html?m=1 http://666-bits.blogspot.com/2007/08/principal-programming-p...
7thaccount 4y ago
I've seen some chart like this before. For example, APL started the array family that has APL, J, A+, K, Kona...etc. Algol started the procedural family of Algol, Fortran, Basic...etc. Lisp started the family of lisp languages...and so on. The taxonomy is convoluted and not quite that neat though.

buescher 4y ago

Koopman's more recent "Better Embedded System Software" is a great overview of its subject.

metalforever 4y ago

I had this guy as a professor and he was great.

LAC-Tech 4y ago
Would love to hear more about this. The stack machines book is the only computer architecture book I've read cover to cover.

rwmj 4y ago

The conventional view is that stack computers didn't scale because they're very demanding in memory bandwidth - every operations ends up reading 2 operands from memory and perhaps writing one result back. Which is of course exactly the wrong thing because registers got much faster than RAM. But they're also elegantly small. Are there any stack computers used today, perhaps in systems where slow speed is not a problem but ultra small size (and code size) is an advantage? I only see https://en.wikipedia.org/wiki/ZPU_(microprocessor) https://en.wikipedia.org/wiki/ZPU_(microprocessor) (2008) - 442 LUTs(!).

rahen 4y ago
When Burroughs started experimenting with stack processors in their B5000 computer, they didn't do it for code size but the ability to use high level languages first, going as far as to hide assembly language to the user. Compilers are fairly straightforward to write on such an architecture, and can produce reasonably fast machine code in one pass. A register based CPU make this quite more complex, and is indeed a more performant but less elegant approach than a stack based CPU. This later inspired HP for the HP 3000 and then its RPN calculators, as well as other, lesser known machines. Nowadays I think I've only seen this with the JVM (to reduce the IL size) and a couple MCUs.
- retrac 4y ago
  Stack-based VMs are more common than just the JVM. Python and Ruby's bytecodes are stack-oriented. Stack machines are also still common for compilers where "good enough" code is acceptable. As you say, it's relatively easy to write a code generator for a stack machine.
  - int_19h 4y ago
    CIL (.NET bytecode) is also stack-based, and perhaps the most interesting modern incarnation as well, because it is sufficiently full featured - pointers w/arithmetic, unions, stackalloc etc - to be a target for a C compiler.

dang 4y ago

Related: Stack Computers: the new wave (1989) - https://news.ycombinator.com/item?id=12237539 https://news.ycombinator.com/item?id=12237539 - Aug 2016 (28 comments) Stack Computers: the new wave (1989) - https://news.ycombinator.com/item?id=8657654 https://news.ycombinator.com/item?id=8657654 - Nov 2014 (3 comments) Stack Computers: the new wave (1989) - https://news.ycombinator.com/item?id=4620423 https://news.ycombinator.com/item?id=4620423 - Oct 2012 (37 comments)

pohl 4y ago

This reminds me that it's been a while since I've checked in on the belt machine that Ivan Godard & friends were working on at Mill Computing. It looks like their website has change a bit since I last looked: https://millcomputing.com/ https://millcomputing.com/

bmitc 4y ago

Does anyone know of the state of the art of stack and symbolic CPUs? I'm reading a few books that address stack computers and also symbolic CPUs, ones which may run things like Forth, Prolog, and Lisp directly on the CPU (or more directly rather than via abstractions sitting on top of Von Neumann architectures). The ideas in the books, such as those in A High Performance Architecture for Prolog, seem important and useful, but it's hard to tell if they aren't useful in today's modern age or if they simply fell out of favor or interest. In today's age with FGPAs, ASICs, RISC-V, etc., it seems ripe territory for custom CPU development, but about the only thing I know of that is along the lines of the above is the GreenArrays GA144 chip. https://www.greenarraychips.com/ https://www.greenarraychips.com/

abecedarius 4y ago
25 years old, but http://bernd-paysan.de/4stack.html http://bernd-paysan.de/4stack.html sounded interesting at the time.
tdeck 4y ago
There were a bunch of Java chips in the early 2000s, and ARM cores with a subset of the JVM instruction set. https://en.m.wikipedia.org/wiki/Java_processor https://en.m.wikipedia.org/wiki/Java_processor https://en.m.wikipedia.org/wiki/Jazelle https://en.m.wikipedia.org/wiki/Jazelle

manholio 4y ago

I wonder how soon we will have microarchitectures that are purely the result of some deep learning algorithms optimizing for performance and compilability of high level languages. We would be able to prove them correct - that they correctly execute the code and have no exploitable bugs - but we will have almost no idea how exactly they achieve said performance.

mlyle 4y ago
I don't think we really know how to learn code generation techniques and prove them correct, yet. That would be, in general, a really neat and useful trick.
- batmanturkey 4y ago
  What, divide in half and compare?
batmanturkey 4y ago
I can’t find the link atm, but the reference was a self-optimized circuit that achieved xyz objective but the actual fpga bitstream was a p&r nightmare of latches and impossible simplifications taking advantage of phantom this and inductive that all accidentally and due to proximity but measured results and feedback and such. Totally specific and local, down to clock skew usage, whatever, no one understood it… will have to find the link…
- manholio 4y ago
  That sounds about right. Why bother with a clock anyway, asynchronous is the way of the hardware samurai. Although it should be fuzzed a bit with signal and power noise, to kill those "solutions" that only work due to a lucky photo-resist error that manifests itself at exactly 3.03V.

mud_dauber 4y ago

I worked with Phil back in the day at Harris Semi on their RTX architecture. AFAIK it was used on a couple of space probes due to small size, consistent code execution, and (I think) the ability to offer a rad-hard design for space. Forth was the language of choice. I wish it could come back, because it was such a neat mind exercise.

shrubble 4y ago

The old Byte magazine's special edition that covered Modula-2 described the Lilith workstation as a stack machine CPU. It's on archive.org .