# Early BASIC memory management

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.

• Slight correction about the memory map. The operating system was in ROM along with BASIC at the top of memory. The zeroth page was a bunch of pointers and variables used by the OS and BASIC. It's best to think of page zero as a very slow extra register file. Page 1 was the hardware stack. Pages 2 and 3 were used for OS and BASIC variables. On the PET the BASIC program started on page 4 and could stretch with its variables etc up to the end of page 127 (if you had the RAM). Pages 128 - 131 were the screen (40 column model) – JeremyP Jul 24 at 8:49

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.

• Thank you. That has reawakened many memories and some of that detail is coming back. The one bit that I don't recall is a neat handling of out of memory. However, considering your evident knowledge, I am happy to accept that it is my memory that is deficient. – badjohn Aug 5 '18 at 20:41
• @badjohn since BASIC in generals, as well as MS-BASIC, did considerable vary between different machines adaption, there might still be some ... or rather a lot ... quirks your memory is based on. And no, my knowledge isn't so evident - in fact, I like RC also, because there are many good people looking for loopholes and errors in my answers. Part of the fun to see where my memory is wrong. – Raffzahn Aug 5 '18 at 20:45
• The versions of old Basic that I had the most experience with were the PET 2001 and the C64. Obviously they shared a lot but I cannot be sure which memories applied to just one of them. Above, @Blrfl seems to suggest that the PET did not handle out of memory neatly. I remember the "fun" of squeezing programs into the 8kB of the PET. Single character variable names for the reason that you mention and also to make the program text smaller. I also remember the sometimes difficult choice of integer or floating point for variables. – badjohn Aug 5 '18 at 21:22
• Did MS BASIC tokenize on the fly? I was under the impression it only tokenized during the RUN, and that was one of the major differences between MS and things like Atari and BBC BASIC. – Maury Markowitz Aug 7 '18 at 15:57
• @MauryMarkowitz All (classic) BASICs (except Tiny that is) do tokenize each line when entered. After all, why postpone that process and waste memory for full text storage? They just differ on how tokens get recognized and how non token text is handled. – Raffzahn Aug 7 '18 at 17:32

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.

• So, the PET would probably just crash? That fits my memory. No clear consistent error, just crazy results. I am less sure whether the C64 shared this behaviour. – badjohn Aug 5 '18 at 20:00
• The C64 used CBM BASIC v2.0, which was used on pretty early PET computers, just not the original PET 2001. In fact, later PET machines had an upgraded BASIC - v3.5 and I think v4.0. – Brian H Aug 5 '18 at 20:21
• PET BASIC also checked see if there was room for allocating things. See all the code that jumps to the OMERR label in the source code you linked. – Ross Ridge Aug 5 '18 at 21:36
• @RossRidge Silly me, looking for a comment with the word "memory" in it. :-) – Blrfl Aug 5 '18 at 22:36

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.

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.

• IIRC On ZX the editor itself prevent corruption by not allowing adding new line and interpreter too by breaking program with Out of memory error message (was hard to port/modify some tape games to floppy due to this). However Peek/Poke had no limits and also any asm routine had no memory protection from the OS... – Spektre Aug 5 '18 at 13:04
• I remember a friend extolling the virtues of the Sinclair Spectrum over the C64. One point was that although only 48kB, there was actually more memory available to Basic. I don't recall if better handling of out of memory was another virtue. – badjohn Aug 5 '18 at 15:07
• @badjohn one could change the system variable IIRC RAMTOP with Poke to achieve such things but the result was often unstable ... The only memory protection was done by HW as the OS was inside ROM which could not be rewritten... – Spektre Aug 5 '18 at 20:21