1
$\begingroup$

I asked this question specifically about why the JVM has a separate area for local variables: https://stackoverflow.com/q/76086392/1463507

It was answered satisfactorily within the scope of the question, but it made me realise my real question is actually not what I asked, but rather this:

Is it possible to compile procedural code down to relatively "pure" stack operations, i.e. such that they don't need to reference values arbitrarily deep down in the stack?

My only experience with stack-based languages are not Turing complete ones, but constrained to RPN calculators. With those, I have yet to find a nested arithmetic expression that cannot be evaluated with a very limited stack depth, as long as the subexpression evaluations are sequenced cleverly.

I suspect if I had more experience with Forth I could use that experience to intuit the answer, but I don't, so I turn to you! Is there some easy example or obvious property of procedural languages that prevent them from being compiled to pure stack operations?

$\endgroup$
2
  • $\begingroup$ By "arbitrarily deep", do you mean "anywhere" ? Andwhy do you use the term "pure" ? $\endgroup$
    – user16034
    Commented Apr 27, 2023 at 7:39
  • $\begingroup$ How do you "compile" loops (while / for / gotos ) if you only allow push/pop operations? If the stack is only used for holding values and the control is still procedural (or state-based), then there is no need for a stack at all: 3 (unlimited) variables (2 with some caveats) + control are enough to execute any program. $\endgroup$
    – Vor
    Commented Apr 27, 2023 at 13:22

2 Answers 2

1
$\begingroup$

No. You need a heap, for dynamically sized data structures like linked lists, trees, graphs, etc. You can't simulate that with a stack in the way you're looking for.

(I am assuming that each element stored in the stack is fixed size, e.g., 64 bits, and that each operation can only look at the top 2 elements of the stack, say, and only a finite amount of additional memory, say 16 registers of 64-bit values.)

The justification comes from the separation between pushdown automata and Turing machines: there are things that can be computed with a Turing machine or a RAM model machine that cannot be computed by a pushdown automata.

$\endgroup$
4
  • 1
    $\begingroup$ Two stacks will also do it. The intuition here is that popping an element from one stack and pushing it on the other is equivalent to moving the head on a Turing machine. $\endgroup$
    – Pseudonym
    Commented Apr 28, 2023 at 11:46
  • 2
    $\begingroup$ @Pseudonym, yup! But the question doesn't ask about two stacks. It asks about one stack. $\endgroup$
    – D.W.
    Commented Apr 28, 2023 at 18:18
  • 1
    $\begingroup$ Might be worth noting that the "conceptual theorem" here is exactly the strict inclusion of languages recognized by PDAs and Turing Machines: en.wikipedia.org/wiki/Pushdown_automaton $\endgroup$
    – cody
    Commented May 30, 2023 at 19:07
  • 1
    $\begingroup$ @cody, good point! I've added that to my answer. Thank you. $\endgroup$
    – D.W.
    Commented May 30, 2023 at 20:31
0
$\begingroup$

Conceptually, you can always copy the local variables to the new stack frame upon entering a block, and copy back upon exit. So if you give no other constraint, the answer is yes, you can live with the last stack frame.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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