Re: Questions about Bytecode

Christopher Diggins <>
26 Apr 2007 09:38:48 -0400

          From comp.compilers

Related articles
[7 earlier articles]
Re: Questions about Bytecode (Hans-Peter Diettrich) (2007-04-23)
Re: Questions about Bytecode (2007-04-23)
Re: Questions about Bytecode (Chris Dollin) (2007-04-23)
Re: Questions about Bytecode (glen herrmannsfeldt) (2007-04-25)
Re: Questions about Bytecode (Peter Flass) (2007-04-26)
Re: Questions about Bytecode (Christopher Diggins) (2007-04-26)
Re: Questions about Bytecode (Christopher Diggins) (2007-04-26)
| List of all articles for this month |

From: Christopher Diggins <>
Newsgroups: comp.compilers
Date: 26 Apr 2007 09:38:48 -0400
Organization: Compilers Central
References: 07-04-06107-04-071 07-04-097
Keywords: interpreter, VM
Posted-Date: 26 Apr 2007 09:38:48 EDT

On Apr 23, 5:53 am, Chris Dollin <> 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 ( ) and Cat
( ) 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

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

Post a followup to this message

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