The C Stack in interpreters - why?

I am trying to understand why the C stack is used in interpreters
rather than an explicity built stack on the heap?  Up until now I
presumed that the explicit stack was how everyone did it, then I
learned that, apparently the way a lot of bytecode interpreters work
is to recursively call themselves whenever a
procedure/routine/method/whaterver is called.

Things I have been able to learn so far:

(1) A lot of languages use the C stack
(2) A lot of people complain about it and point out all of the
limitations of it.

Can someone tell me why the C stack is so often used instead of
explicit?  People are willing to re-write entire interpreters in order
to get rid of the C stack (i.e. stackless python), so why do people use
the C stack for interpreters to begin with?

I am writing an interpreter and I need to know the best way to proceed
on this issue.  I WOULD like to be able to embed my interpreter in C
programs and I WOULD like to be able to call C from my language.

Thanks!

MC

(snip)

> [Are there really systems with a hardware stack that C doesn't use?
> I've never seen one. -John]

How about ESA/390, with the PC and BAKR instructions?

All the compilers I know of use BALR, BASR, or BASSM, and if
they didn't they wouldn't be able to call languages that did.

(For those who don't know ESA/390, the standard OS/390 linkage is a
linked list, logically but not physically a stack.)

-- glen
[Sheesh.  The ESA/390 stack is a hack intended for programs in
different protection domains to call each other in a way that's
lighter weight than a full operating system run-program call.  All
normal languages still use BASR or, on zSeries BRAS or BRASL. Having
squinted at a bunch of on-line manuals, it appears that you can tell
the C and C++ compilers to do hardware stack calls with a #pragma or
in C++ extern "OS" { int foo(); }.  So there. -John]

Marko Mäkelä <Marko.Makela@HUT.FI> wrote:

>John> Are there really systems with a hardware stack that C doesn't use?
>John> I've never seen one.
>
>The 6502 has only 256 bytes of stack.  The CC65 compiler
>(http://www.cc65.org/) uses a separate parameter stack in order to
>save the precious hardware stack space for return addresses.  The
>compiler also has to emulate 16-bit registers using zero page memory
>locations.
>
>Now you have seen one. :-)

Life is complete.  I can die now.  Thank you.

>[Oh, right.  How 'bout if I say I never saw a C compiler pass up the
>opportunity to use a usable hardware stack. -John]
^^^^^^
Please, please.  You should use the correct terminology.  Let me
reword that for you:
The 6502 does not have a *real*[1] stack.

[1] Not to be  with floating-point, especially by FORTRAN
programmers.

Sincerely,

Gene Wirchenko

glen herrmannsfeldt  <gah@ugcs.caltech.edu> wrote:
> 
>
>How about ESA/390, with the PC and BAKR instructions?
>
>All the compilers I know of use BALR, BASR, or BASSM, and if
>they didn't they wouldn't be able to call languages that did.
>
>(For those who don't know ESA/390, the standard OS/390 linkage is a
>linked list, logically but not physically a stack.)
>
>[Sheesh.  The ESA/390 stack is a hack intended for programs in
>different protection domains to call each other in a way that's
>lighter weight than a full operating system run-program call.  All
>normal languages still use BASR or, on zSeries BRAS or BRASL. Having
>squinted at a bunch of on-line manuals, it appears that you can tell
>the C and C++ compilers to do hardware stack calls with a #pragma or
>in C++ extern "OS" { int foo(); }.  So there. -John]

We can now have a happy time arguing over what the One True Linkage
(and One True Stack) in that system is.  I vote for LINK, but the
moderator will probably rule that I am obsolete and should be put
down.

Few of the Cambridge compilers used standard linkage (this was back in
the BAL/BALR days), on the grounds of unsuitability and cost, though
they almost all used BAL/BALR.  I did some testing, and found some
advantages in not even using them (i.e. using LA and BC), as was done
by some specialist assemblers, but never saw a genuine compiler use
that method.

I was working in Santa Teresa at the time the double linkage was
dropped, and argued that it should be left as an option, but didn't
win.  It was one of the most useful software engineering techniques
that I know of, because it vastly increased the chances of locating a
bug that had trashed the stack.

Regards,
Nick Maclaren.
[Gee, I always liked ATTACH because then you could have race
conditions.  So, speaking of obsolete, let me take a look, on a /30
BALR took 18us, BR took 9, LA took 17, so BALR won there.  On a /67,
BALR was 1.2us, BASR was 1.43us, BR 1.1us, LA 0.9us.  BALR and BASR
still won. -John]

On 15 May 2005 16:12:22 -0400, Gene Wirchenko <gene@abhost.us> wrote:

>The 6502 does not have a *real*[1] stack.
>
>[1] Not to be  with floating-point, especially by FORTRAN
>programmers.

If I can find my copy of Apple ][ Lisp, I will fire up my old Apple ][
and create a stack named *real*.

What do you consider a real stack?  The 6502 stack had a hardware
incremented address register, dedicated push/pop access instructions
and automatic push/pop of PC and status registers upon
entering/leaving a subroutine.

To be sure, the 6502 stack wasn't the most convenient thing to use ...
it was too small, it had a fixed address range, it had neither
top-relative addressing nor framing, did I mention it was too small
.... but if it wasn't a real stack then I don't know what one is.

George

nmm1@cus.cam.ac.uk (Nick Maclaren) writes:
|>
|> Few of the Cambridge compilers used standard linkage (this was back in
|> the BAL/BALR days), on the grounds of unsuitability and cost, though
|> they almost all used BAL/BALR.  I did some testing, and found some
|> advantages in not even using them (i.e. using LA and BC), as was done
|> by some specialist assemblers, but never saw a genuine compiler use
|> that method.
|>
|> [Gee, I always liked ATTACH because then you could have race
|> conditions.  So, speaking of obsolete, let me take a look, on a /30
|> BALR took 18us, BR took 9, LA took 17, so BALR won there.  On a /67,
|> BALR was 1.2us, BASR was 1.43us, BR 1.1us, LA 0.9us.  BALR and BASR
|> still won. -John]

Excessively naive calculation.  2/10 :-)

My tests were on a 370/165, but the principles were more general,
and the gain of LA/BC was not direct but in the extra flexibility
that it allowed.  Yes, simply replacing BALR/BAL by LA/BR/B was a
loser, but that was obviously unlikely to help.  There was the
obvious one that it gave better code generation to tail recursion
removal and common constructions like:

IF (JOE) CALL FRED
x = (bert ? 1.23 : alf());

But it also simplified the generation of inline parameter lists
(whether of arguments or debugging information), with the resulting
improvement in cache and (more importantly) TLB utilisation.  Note
that allowing WRITABLE data there was always a loser.  I did some
investigations on the Fortran linkage, and could speed it up by a
factor of 2-3 just by cleaning it up and designing it for 1970s
systems.

Regards,
Nick Maclaren.
[Cache?  TLB?  Tail recursion?  You didn't say you were using all
that newfangled stuff.  Time to retire under my rock, now. -John]

Real, but limited. Makes life interesting if you implement thread
support, as I saw a couple of years ago for a very popular cordless
telephone chip. Yes, very surprisingly, it has an enhanced 6502.
Besides, assembly is virtually the only way to go with 6502s anyway
since you have to be awfully careful with memory management. Frankly,
I still enjoyed doing it after all these years and the result got shot
off the back of the shuttle 2.5 years back (STS-113)

Back to the poster's original topic: if you don't use a stack, you
have to manage stack frames. PL/I does this, I suspect, because it fit
older segmented architectures better. So, if you don't want to
growstack(), you'll have to allocframe() and deal with other
issues. As another poster pointed out, managing call frames
potentially enables a raft of other feature.

However, managing a stack-based frame is essentially managing a call
frame. The principal difference is that a stack is contiguous and has
push/pop semantics. Thus, you can't necessarily move data around or
connect/reconnect nonadjacent stack frames without doing some
accounting.

-scooter