Early BASIC memory management

Question

Can anyone verify or correct my memory here?

Long ago, I had access to a Commodore PET which I think had 8kB of memory. Also slightly less long ago, I had a Commodore 64 with its "elephatine" 64kB. Of course, not all of that was easily accesible through Basic but that is not the subject of this question.

My memory is that the O/S (for want of a better name) occupied the lowest memory followed by the code of your Basic program. Variables were allocated at the highest available address. So, as you wrote longer programs and used more variables, the two converged in the middle. I don't recall any protection, eventually the two would meet and crazy things would happen.

Answer 1

My memory is that the O/S (for want of a better name) occupied the lowest memory followed by the code of your Basic program. Variables were allocated at the highest available address. So, as you wrote longer programs and used more variables, the two converged in the middle

You're right - well, BASICly (SCNR).

I don't recall any protection,

Yes, there is. If variables and program collide an 'out of memory error' will occure.

eventually the two would meet and crazy things would happen.

No, there are no crazy things to happen. Or better, they only do if programmers tried to outsmart the interpreter and failed.

---

Long story:

(Disclaimer: This is mainly about MS-Basics, as used for the Commodores, but most other behave similar)

To understand the mechanics it's useful to differentiate memory management between program editing and runtime. And what's free memory means during either. Also that this is only about the memory available to BASIC (*1), not total system memory.

Case A) Editing.

Here the whole memory is used by the editor to compose the program in tokenized form. A line is entered into the line buffer (*2) and from there handed to be converted to tokenized line. If there's enough room to accommodate the line, it will be entered, otherwise an error is signalled. During editing no variables are stored. Whenever editing happens, existing variables are usually destroyed.

Case B) Runtime

Basic creates variables only dynamic during runtime and starts out with no variable memory assigned. Whenever a variable gets assigned (used) first time according space is reserved. If no space can be allocated, again an error (out of memory) is signalled and the program is halted.

During runtime the program text is considered static, which allows BASIC to handle the free area (between the last stored BASIC line and highmem) from both 'ends'. Numeric variables and arrays grow from bottom up, while strings grow top down. Since this is done dynamic and strings changing in length may lead to free areas inbetween used strings, the runtime will, when running out of memory between the two blocks, first look to compress the string area to regain this space (*3), and, if unsuccessful, it'll break with an out of memory error.

Special Case of a Stopped Program

When a program gets stopped, either through a STOP command, or any error, it stays with the actual memory configuration regarding program and variables intact, allowing to inspect either. If the break was due a STOP or an recoverable error its execution might be continued via CONT. Even after changing some variables. In contrast, changing any part of the program will disable this due destruction of the variable tables and/or pointers therefore. A CONT command will usually now result in a can't continue error.

Conclusion

While it is possible to write a program so large that there is no room left vor even a single variable, BASIC is safe against collision between program and variable data.

---

Remarks

• Programs that use much of the space and do a lot of string handling will constantly run into garbage collection and slow down a lot. If they run at all.

• It is one of the basic problems with BASIC variable handling that variables stay present after invocation until the end of a program run. So it's rather helpful to reuse variable the same variables as often as possible (i, j, k and so on) in different parts of a program - which then of course adds complexity and potential conflicts.

• Original MS-BASIC garbage collection is rather poorly scaling on large programs, thus improved string handlers where great tools to add. Other BASICs did start out with already way improved garbage collectors - or even variable handling that avoided much need for garbage collection by producing less pollution than MS BASICS did.

• Other BASICs also added mechanics that did allow to change program text during a break so a continuation was possible even after editing an offending line.

---

*1 - Available to BASIC is not the same as accessible by a basic program. Of course a program written in BASIC can access all memory via certain functions (like PEEK or POKE), but there we talk about what BASIC as an application accesses. Here (free) memory is one chunk that contains all program and variables, growing from either end, much like described in the question.

*2 - Residing outside the memory area. Like at $200 for an Apple or Commodore PET (only 80 bytes max for the PET, 250 for the Apple)

*3 - Called a Garbage Collection.

Answer 2

What protection there was depended on whose BASIC interpreter you were running.

Applesoft BASIC had a check surrounding most things that pushed the limits of what had been allocated and would trigger an OUT OF MEMORY error if there was going to be a collision. You can see this in action in the source code by looking at the code preceding jumps to MEMERR and calls to CHKMEM.

A quick look through the PET BASIC sources with some help from a commenter reveals that it does similar checks for FOR loops, GOSUB and in the formula evaluator.

Answer 3

A typical MS-BASIC interpreter would allow configuration of two key addresses: the start and end of the memory space it was allowed to use. The tokenized BASIC program was always expected to start one byte after the bottom address. The interpreter would then maintain and update a few additional addresses:

• The end of the BASIC program text and start of variables
• The end of variables and start of arrays
• The end of arrays
• The start of the space used for strings

Any time a BASIC program is edited, it would update the end pointer above, and copy it to the pointers for ends of variables and arrays. It would update the start of string space to the end of memory.

Adding a variable will move any existing arrays so as to make room for the new variable. Creating a new string will cause it to be stored immediately preceding all existing strings and move the "start of string space" pointer to compensate. Before any action is performed that would push pointers closer together, the system checks to see if they would collide. If so, the system will initiate a "garbage collection" function by resetting the "start of string space" pointer to the end of memory and then iterating the "cleanup one string" function until it can't find any string to clean up.

To clean up one string, the interpreter will search through all variables and arrays to find the string with the highest address that is below the "start of string space" pointer. If it doesn't find any, the routine exits. Otherwise, it will then copy the highest string it found just below the "start of string space" address, update that pointer appropriately, and finally search through all variables and arrays, replacing any references to the old address with the new one. After doing all that, it will loop back to handle the next string.

Note that this approach is very memory-efficient, but slow. For each run-time generated string that needs to be kept, the system will have to perform a scan through every variable and every element of every string array to find the string to keep, and a second scan to correct all references to the old one so they identify the new one instead.

Answer 4

I never spent much time using MS BASIC like the commodore systems, but for the Sinclair systems I'm most familiar with your description is essentially correct, except that I believe variables were stored immediately after the program and were moved whenever the program length changed. The machine code stack was at the top of memory (growing down from an address that could be controlled with the CLEAR statement), and that could corrupt the variables if it got too large.

However for a 6502 system, the machine code stack is unlikely to be a source of corruption - the 6502 stack can only exist in the 100-1FF hex range so is always below the location of any BASIC code in memory.