From elsewhere:


It looks like it's enough to evaluate an expression with deeply nested subexpressions to use up a fair amount of stack:
PRINT (1+(1+(1+(1+(1+(1+(1+(1+(1+(1+(1)))))))))))
or even just
PRINT 1+((((((((((((1))))))))))))

So I'd conclude that the BBC Basic interpreter uses a recursive evaluation tactic which puts data as well as addresses on the 6502 stack. It looks like the evaluator allows up to 16 levels of parenthesis.

I have to admit that for me, programming on commercially available systems (OSI, Apple, etc.) led to some bad habits. I tend to avoid using Page Zero and the stack as much as I would if starting from scratch. Coexisting with BASIC and/or DOS with limited documentation, you never could be sure about things.

Jim

Well, as evidenced in the other thread about modularity, the stack in the 6502 isn't leveraged for call frames, at least in machine language, like on other processors. So, in that sense, it makes sense that "normally", and 6502 stack isn't used much. There was a Forth chip that I think was limited to a depth of 20, for example. And I think Garth has said that he's not seen his work go down below 8 or 12 or something like that.

But our stacks tend to be reserved for addresses, and not data, particularly not static data unless many other systems. Since the stack is such a limited resource, historically developers look for alternatives.

In contrast, you could look at UCSD Pascal, where essentially the entire system is one huge stack. It pushes EVERYTHING on to it, and since it's "pass by value", they can be big things, including 256 byte Sets, large records, etc. UCSD even pushes new code on to the stack.

About Pascal: I've heard that in the past; but doesn't that make for a lot of time wasted moving lots of large items to and from the stack? Or is it more like Forth's dictionary which is last-on-first-off in the sense of new compilation and FORGET, but which normally uses the page-1 hardware stack as a return stack and a ZP area for a parameter stack, independently of the dictionary?

Ed's example above is amusing in its need for some optimization, except that it's probably just to make the point, and numbers could be replaced with different floating-point numbers (which I suppose the "1" is anyway) and the operators could be replaced with a mix. These could be put on virtual stacks though, eliminating much of the need for deep page-1 hardware stack usage. Floating-point numbers could be stacked in pages 2 and above, never needing the addressing modes that are particular to ZP like addresses need.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Not only does that sort of evaluation gobble up stack at a rapid rate, so do nested FOR-NEXT loops, GOSUBs, DO-loops, etc. In the Commodore 128, BASIC 7.0 was so stack-hungry a separate 512 byte run-time stack was implemented, unlike the C-64's BASIC 2.0, which used the hardware stack.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Pascal isn't that much different from other high level languages, like C.

Specifically, in this case, they're both pass by value. For normal scalars, this isn't really a big deal: characters, integers, etc. Floats would push the entire value (8 bytes, depending on the FP implementation). But if you pass in a record (a struct in C), then the entire thing gets copied to the stack, where it's operated upon by the procedure. On exit, the SP is reset and all of that space is released.

Clearly this encourages passing in pointers to things, rather than the things themselves. Now, in Pascal, you can specify pass by reference:

In this case, "y" would be modified. VS:

"y" would still be modified, but it's tied to the scope of the procedure and doesn't affect the parameter that's called in to the procedure.

The curious part of UCSD is that if your procedure invoked a segment procedure (which is like an overlay), that wasn't loaded yet, it would actually load from disk and "push" the code on to the stack. You could visualize the working memory of UCSD as the dictionary in FORTH. But it has 2 parts, the stack, and the heap. In UCSD the stack would grow upward in memory, while the heap would grow down, until one ran in to the other and you "run out of memory". The heap was mostly used for dynamic memory allocation using the crude mark and release capability in the early UCSD (vs the malloc/free concept in C). Mark simply bumped the heap pointer, release set it back.

The overlay thing isn't really a problem, you can don't put calls to segment procedures in a tight loop.

If you use deeply nested procedure calls in BBC Basic then I seem to remember that it periodically frees up space buy copying it to a software stack growing down from the top of RAM.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

I've been rummaging through a PDF of Mark Plumbley's book "BASIC ROM User Guide" - it's got a lot of detail about Basic's internals, and its use of STACK and HEAP - as you say, STACK is at the top, just below HIMEM, and HEAP is at the bottom, just after the Basic program, at TOP. Or LOMEM. (See here: http://beebwiki.mdfs.net/BASIC_memory_usage)

It seems that while Basic does check for excessive nesting of FOR, PROC, GOSUB, it doesn't check for excessive parentheses. That seems dodgy, but presumably it's rarely a problem. Looks like each nested level of parentheses uses 14 bytes of stack.

I suspect what would happen if parentheses were nested too deeply is BASIC would realize it was running out of stack space during the evaluation and would report an error to that effect. In BASIC 2.0 on the Commodore 64, you'd get a ?FORMULA TOO COMPLEX error.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

According to the book there's no check - it wraps the stack and runs off who knows where. Empirically I'm seeing the No such variable error, but that doesn't tell us either way.

Ouch!

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!