When I look up "stack machine" I often get stuff like the JVM that uses a stack for data, but it still uses an array to store its instructions.

I would like to find out more about machines whose programs are stacks. For example, executing the command at the top of the stack by default removes the element at the top of the stack, and the program execution ends when the instruction stack is empty.

I'm afraid that this might be a silly question, but I have no idea what else these may be called.

I would like to know what the implementation of such a machine would look like (for example, how control flow might be handled on such a machine, how expressive the instruction set might be, etc.). A link to a Wikipedia page or some other reference would be really cool too.

While Forth, JVM bytecode, and others are heavily "stack-based", their program memory is not because the executable is always "there" like in a constant array, and if you want to branch to a different location you simply adjust the program counter.

On the other hand, in the hypothetical machine with a stack-instruction set you always execute the next instruction on the top of the stack. As Winston suggests, conditionals could be implemented by pushing various instructions onto the instruction stack.

For instance, you could have a PRINTFOR instruction that takes the number from the top of the data stack and puts that many PRINT instructions at the top of the execution stack.

For instance, if your original program was (in Forth style):


At some point you will have:

Program Stack: PRINTFOR

Data Stack: 2 3 1

Then you will have:

Program Stack: PRINT PRINT

Data Stack: 3 1

And you will see


on stdout.

I was curious as to what a "fully featured language" that takes on this kind of approach might look like.

@Mark Booth, I might just be asking an impractical question, and I might only have thought of this because of my inexperience. I'll try to explain why I wanted such an architecture.

I had worked through the Lex and Yacc tutorial Lex & Yacc Tutorial by Tom Niemann.

When I got to the part where he implements the calculator on a hypothetical stack-based machine, I spent some time implementing a VM myself.

However, I felt that at a couple of points the design could be easier for me to implement. In order to manage control flow, the machine uses some form of goto, and label. However, this would mean that in order to run an instruction, my machine would have to be aware of all the goto's all over the place. In some sense each instruction wouldn't be "context-free", and I was afraid this was bound to be more work than the alternative.

Instead of using a label, I could have goto take an instruction location (or an offset) so that I could simply set the pc to goto's operand. But this still seemed kind of messy to me. It still felt like the goto had to "know" stuff about the other instructions (and where they were) and the implementation could be cleaner.

I thought putting the operands on a stack was really cool, because it took away a lot of choices I didn't really care about when I dealt with registers. I figured maybe somebody has done something similar for instruction memory.

The benefit of such a system might be that each instruction is in some sense, "context-free", that is, when I implement the individual instructions, I don't have to worry about how many instructions there are, all I have to worry about are what the previous instructions have done (that is, the result of the data stack(s)), and what the instructions in the future are going to do (that is, the stuff left on the instruction stack). An interesting consequence would be that even in the middle of a while loop, all instructions you are going to perform in the future is considered an instruction "down the stack". i.e.

If I have:

int x = 0;
while (True) {
  if (x > 100) break;

The "print" statement is physically placed below the "x++" statement, and it gets executed after the "x++" statement. However, when we reach the "print" statement, it can't forget about all the instruction that came before it. We still have to remember that the while loop closes the ending brace.

Furthermore, we don't know exactly which of the previous statements we are going to execute. In a stack-based instruction set, we can forget any instruction that has come before, and simply claim "We're going to do everything that's left in the instruction stack." This way it also becomes easier to see a program as the composition of other programs.

I'm afraid that some experienced coders might find that this really silly, because the design might end up imposing severe limitations that can only be overcome by doing things the old way, or I'm just making the classic way of implementing a VM harder than it is. However if this is the case, it would be cool if you could leave some comments to help me understand. On the other hand, I'm having trouble on how the idea might blow into a full instruction set, so even if it were possible, I'm not sure how it might be done.

  • 3
    Are you asking about the FORTH language? It has a virtual machine that's pretty stack-centric. – S.Lott Jan 20 '12 at 1:13
  • I wouldn't really group this question amongst "practical, answerable questions based on actual problems that you face" (see the FAQ). This question seems to be suggesting a theoretical processor architecture that would (IIUIC) be incredibly difficult to implement, let alone implement efficiently. I have certainly never seen this sort of architecture suggested before. – Mark Booth Jan 20 '12 at 15:41
  • That remind me Push down automaton. – AProgrammer Jan 20 '12 at 19:12
  • This is looking less and less like a question. What exact question do you want an answer to? As it is, your question is just really vague and not a good fit for here. – Winston Ewert Jan 21 '12 at 3:15
  • I had actually hoped someone might suggest an implementation that's already out there, but I guess that if an implementation is out there, then it is probably pretty well hidden... – math4tots Jan 21 '12 at 4:46

Well, I suppose you could make the program a stack.

Calling a function would push the code for that function onto the stack.

Conditionals could be implemented by selecting from two different lists to push onto the stack.

With conditions + recursion you've got everything you need in terms of logic flow.

I don't know anybody that has done this, and I don't know you would do it, but I guess you could.

| improve this answer | |
  • 1
    Cat or Joy could be implemented this way easily – SK-logic Jan 20 '12 at 8:58

The closest is probably Malbolge.

Malbolge is a public domain esoteric programming language invented by Ben Olmstead in 1998, named after the eighth circle of hell in Dante's Inferno, the Malebolge.

The peculiarity of Malbolge is that it was designed to be the most difficult and esoteric programming language. However, several of the tricks used to make understanding it difficult can be simplified away.

| improve this answer | |
  • 1
    Should have been a comment maybe ? – Matthieu Jan 20 '12 at 1:47
  • what happened to intercal? – user1249 Jan 20 '12 at 19:08
  • For those of not familiar with Malbolge, could you explain? – Winston Ewert Jan 21 '12 at 3:16

The most prominent ones I can think of are Forth, PostScript (seriously) and Factor.

If you want to try them out

  • Factor is implemented on the big 3 OSes,
  • GForth is available for Linux, Cygwin and I think there's a build for OS X somewhere, but the language is mostly used for embedded programming. Also, here's a (surprisingly short) tutorial that takes the form of implementing an HTTP server in Forth.
  • PostScript is available pretty damn much everywhere (even if you can't find an interpreter on your machine, chances are your printer speaks it). References(pdf warning) are available.
| improve this answer | |
  • Writing directly in Postscript made my brain bleed (seriously). – Peter Rowell Jan 20 '12 at 2:31
  • @Peter - Yeah... It's interesting, but a much lower level of abstraction than I'm used to dealing with for typesetting. – Inaimathi Jan 20 '12 at 3:25
  • If you're serious about it, you write a library that gives you the abstractions you want, just as in any other language. – Donal Fellows Jan 20 '12 at 20:05
  • @Donal - That is a true statement. – Inaimathi Jan 21 '12 at 1:46
  • @DonalFellows, I prefer it when somebody has already written my abstractions – Winston Ewert Jan 21 '12 at 3:16

From a CPU point of view, the closest architecture I know of to what you describe is the transputer. It used a pair of stacks instead of data registers, but from your first edit I see that's not what you are looking for. However, the transputer instruction set also used a prefix mechanism for it's op-codes, like a mini instruction stack where complex instructions were built up by pushing values into an operand register.

All machine code instructions on the transputer were 8bits long. These instructions were composed of a 4 bit operand and a 4 bit operation. The 31 most used instructions could be executed with 1 byte. If you wanted to access less frequently used instructions you would use a prefix instruction to load additional nibbles into the higher order bits of the operand register, just like pushing bits of the operation onto an operation stack.

This had the interesting effect that transputer instruction set was effectively huffman encoded, resulting in very small executables. Unfortunately it also meant that the most popular implementations of the transputer architecture (T2/4/800 series) only instructions which could be encoded in a single byte could run in a single cycle. when highly pipe-lined super-scaler CPU's came along, the transputers stack based architecture really couldn't take advantage in the same way as traditional CISC and RISC architectures could.

Many of these problems were solved in the design for the T9000 in the 1990's, but this CPU took so to develop that it had been overtaken by other technologies before it went into production. It turned out that the benefit of smaller object code was too slight to make much of an impact on real-world performance (amongst other issues).

| improve this answer | |
  • I wonder how much hard it would be to implement an instruction-per-cycle machine with an instruction set like that of the Transputer? Use two 64-bit instruction registers, along with a partial 128-bit barrel shifter to convert an appropriate up-to-64-bit slice of code into a 40-bit decoded instruction. Such hardware wouldn't be free, but it shouldn't be too hard to achieve single-cycle execution. – supercat Aug 22 '14 at 19:00
  • 2
    That's pretty much what the T9000 did: An interesting addition was the grouper which would collect instructions out of the cache and group them into larger packages of 4 bytes to feed the pipeline faster. Groups then completed in a single cycle, as if they were single larger instructions working on a faster CPU. – Mark Booth Aug 27 '14 at 12:06

I seem to remember the ZPU is a stack based processor. It has an open source core, GCC toolchain, etc.

Have a look and see if it is what you are talking about or if it is array-based.

| improve this answer | |
  • Maybe it's because English is not my native language, but frankly, I find that final paragraph outright confusing. Would you be willing to clarify it? – user Jan 20 '12 at 9:06
  • p-code is still array based code even though it is stack oriented – user1249 Jan 20 '12 at 19:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.