Re: Framed Stack vs. Two Stack Architecture

Avatar wrote:


> Hello,
>
> 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.


Framed-stack is much more compatible with efficient code generation;
i.e. it maps to native call instructions.


> 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?
>
> 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.


Right. See e.g.
Eliot Miranda,
"BrouHaHa- A portable Smalltalk interpreter",
Conference proceedings on Object-oriented programming systems, languages
and applications, Pages 354 - 365, ACM, 1987.


But I wouldn't go this way again. There really isn't that much to be
lost in complexity from going to a single stack approach, and in the end
its simpler.


> 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
> stack) at compile time.


This is not so. Smalltalk has full dynamic typing and on-the-fly code
generation (both at the source-to-bytecode level and in many VMs from
bytecode-to-native-code). The max stack depth per frame is determined
by the compiler when it compiles Smalltalk source to bytecoded methods.
    The JIT can also compute max stack depth in native code given the
bytecode.


> 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).


The stack does not have to be a single contiguous structure. Instead
one can organize it as a (potentially growable) set of pages, each of
which supports some number of frames, if one bounds the maximum frame
size. This constraint is reasonable in a modular language such as an
OO one where functions are typically small (hundreds of lines being
the maximum). Even if one doesn't want to limit the maximum size of a
function abstractly, a larger function can always be broken down into
smaller ones using closures.


Smalltalk implementations typically use a lisp-like Spaghetti stack
abstraction where method activations are apparently represented by
"Contexts" and a stack of activations as a linked list of Contexts. The
VM then transparently maps these contexts down onto real stack frames,
deferring context creation until the system attempts to access stack
frames as objects. This allows one to "page" activations between a pool
of stack pages and the object heap.


See
L. Peter Deutsch,
"Building Control Structures in the Smalltalk-80 System",
in BYTE Magazine Special Issue on Smalltalk,
pp 322-346, Vol. 6, #8, August 1981, McGraw-Hill.


L. Peter Deutsch, Allan M. Schiffman,
"Efficient Implementation of the Smalltalk-80 System",
11th Annual Symposium on Principles of Programming Languages,
pp. 297-302, January 1984, ACM.


Eliot Miranda
"Context Management in VisualWorks 5i"
OOPSLA '99 Workshop on Simplicity, Performance and Portability in
Virtual Machine Design, November 1999, Denver, CO.
http://wiki.cs.uiuc.edu/VisualWorks/DOWNLOAD/papers/oopsla99-contexts.pdf


(which has other references on stack, management)


HTH
--
_______________,,,^..^,,,____________________________
Eliot Miranda Smalltalk - Scene not herd
[I'd think the choice of framed vs. unframed stack would depend on the
warts of the local instruction set and whether a routine is a
leaf. -John]

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