Re: Framed Stack vs. Two Stack Architecture

Avatar wrote:


> We are implementing a stack-based VM for a small interpretive
> language. I am currently investigating stack architectures and would
> like to better understand the advantages / dis-advantages of a
> framed-stack vs. two stack approach.


Personally, two stack is the better approach as you are keeping the
evaluation sematics seperate from the control semantics.


My own work and research is using two stacks within a heap where all
values in the universe of discourse has an associated type. This allows
multiple processes to each have there own stacks that do not interfere
with each other (to the extent that any memory remains in the heap)


Reference the programming language FORTH or FACTOR for information on
implementation technigues.


> I understand that the JVM architecture implements a framed-stack: one
> frame per activation record (method call) with an embedded operand
> stack. So essentially they have rolled the execution stack and operand
> stack into one. Right?


This is the same techniques I was taught nearly 30 years ago.


> I also understand that there are architectures (although I have been
> unable to find a reference implementation for this) that maintain two
> separate stacks: a execution (control) stack for function calls, and a
> separate data stack for (bytecode) instruction evaluation.


Again any FORTH machine or implementation keeps the evaluation and
control seperate (even if the control stack doesn't exist as per FORTH
semantics).


> The language we are implementing is dynamic in nature (dynamic typing
> and alllows for on-the-fly code evaluation) so we would not have the
> advantage that the JVM has in knowing the max stack depth (operand


Any language that allows recursion (unless tail call elimination is
used - even there not all recursive calls will allow tail call
elimination - programmer interference) cannot guarantee the maximum
stack size as this will only be determined by the "correctness of the
routines" and the parameters supplied. The only thing that could
possibly be known is the maximum size of any particular frame size.
Certainly not the size of the stack containing the frames.


> stack) at compile time. At any point code can be evaluated on-the-fly
> within a function. Which I am guessing would eliminate the
> stacked-frame approach? As the frames need to be allocated to a
> certain size (can't grow based upon the demands for operand stack
> space).


Having had to deal with both techniques over the years my preference is
to have two stacks.

Return to the comp.compilers page.
Search the comp.compilers archives again.