Re: Questions about Bytecode

On Apr 23, 5:53 am, Chris Dollin <chris.dol...@hp.com> wrote:
> Bison wrote:
> > And as a final side note, is it more common to see one stack or two
> > stack machines. What benefits do they have?
>
> It's a bit tricky to implement languages like Pop11 with a single
> stack, since it needs two -- one for the call stack, one for the
> value stack. (In Pop11 [1], these two are decoupled, which gives
> you a whole bunch of powerful idioms and the opportunity for the
> occasional brainbreaker.)


Even stack-based languages with only one stack like Joy (
http://www.latrobe.edu.au/philosophy/phimvt/joy.html ) and Cat
( http://www.cat-language.com ) require a second stack to implement
the "dip" combinator. The "dip" combinator (or something similar) is
critical to Turing completeness, and has the following semantics:
- take a function off the stack
- then take the next item off temporarily
- now execute the function on the rest of the stack
- finally push the temporarily removed item back on the stack.
The temporary removal requires a stack, so that dip can be called from
dip.


This is related to the fact that all single stack push-down automata
(PDA) (and equivalent computation machines) are not turing-complete.
So a turing complete language will either have an explicit second
stack, or must provide some mechanism to emulate one.


Christopher Diggins
http://www.cdiggins.com

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