A programming environment with purely stack-based memory? [closed]

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

开发者_运维问答

This question does not appear to be about programming within the scope defined in the help center.

Closed 9 years ago.

Improve this question

Many programming languages and Operating Systems have means of providing dynamic memory: new, malloc, etc.

What-if: a program is restricted by using only stacks, with predefined (i.e. compile-time) sizes, stacks cannot grow or shrink dynamically.

All data is "inside", or "on", these stacks. The program consists of stack manipulations: given a reasonable amount of registers and operations (let's say Intel IA-32, for the sake of specificity).

What are the limitations of using this hypothetical system? (e.g. what algorithmic problems can be solved, and which ones can't?)

For instance: can this program practically do networking, I/O, cryptography or (G)UI?

---

In the theory of computation, such computers would still be Turing equivalent (at least in the sense that real RAM computers are... even they have a limit to the amount of memory). A machine with two stacks (of arbitrary, though perhaps not infinite) capacity would suffice.

Note: this is for expressing algorithms, not doing I/O. Really, with finite memory, you can't accept non-regular languages (I.e. Solve all algorithmic problems)... Meaning that your hypothetical computer, and real computers, can only accept regular languages (and only certain ones of those!) if finite memory is assumed. Since we have lots of memory, this problem is normally ignored.

---

If your program's memory is limited to a fixed set of stacks (and, I'm assuming, registers), then the behavior of the program can be determined solely from the PC register and the tops of all of these stacks. Since these stacks have a predetermined fixed size, you could simulate the behavior of the entire system as a finite automaton. In particular:

1. The automaton has a single state for every possible configuration of the bits of these stacks plus the registers. This might make the automaton exponentially huge, but it's still finite.

2. The automaton has transitions between two different states if, if the program were in the first state, the program would execute an instruction that would change memory in a way that caused it to look like the memory configuration in the second state.

Consequently, your program could be no stronger than a DFA. The sequence of transitions through its states could thus be described using a regular language, so your program could not, for example, print out balanced series of parentheses, or print out all the prime numbers, etc.

However, it is substantially weaker than a DFA. If all memory has to be stored in finitely many stacks, then you can't run the program on inputs any larger than all of the stacks put together (since you wouldn't have space to store the input). Consequently, your program would essentially work by being a DFA that begins in one of many possible states corresponding to the initial configuration of the stacks. Thus your program could have only finitely many possible sequences of behaviors.