Re: Questions about Bytecode

Christopher Diggins <cdiggins@gmail.com>
26 Apr 2007 09:38:48 -0400

          From comp.compilers

Related articles
[7 earlier articles]
Re: Questions about Bytecode DrDiettrich1@aol.com (Hans-Peter Diettrich) (2007-04-23)
Re: Questions about Bytecode haberg@math.su.se (2007-04-23)
Re: Questions about Bytecode chris.dollin@hp.com (Chris Dollin) (2007-04-23)
Re: Questions about Bytecode gah@ugcs.caltech.edu (glen herrmannsfeldt) (2007-04-25)
Re: Questions about Bytecode Peter_Flass@Yahoo.com (Peter Flass) (2007-04-26)
Re: Questions about Bytecode cdiggins@gmail.com (Christopher Diggins) (2007-04-26)
Re: Questions about Bytecode cdiggins@gmail.com (Christopher Diggins) (2007-04-26)
| List of all articles for this month |

From: Christopher Diggins <cdiggins@gmail.com>
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 <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


Post a followup to this message

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