Re: BASIC OS for the PC

Hello Michał,

* On Wed, Dec 21, 2016 at 07:41:32PM +0100 Michał Pleban wrote:
 
> I am still not sure that garbage collection is the corect term here. At
> the top of the Wikipedia article, it says:
> 
> "The garbage collector attempts to reclaim memory occupied by objects
> that are no longer in use by the program."
> 
> That's not really what the BASIC does. In Java, Perl etc. you have
> reference counts for objects.

Well, kinda.

We have to make sure we speak about the some type of objects here.

In (CBM-/MS-)BASIC, we have two types of objects:

1. more-or-less static ones: That is, each numeric variable or array
   variable allocates some bytes (7 byte for each variable, 2 or 5 byte
   for each array object, as well as some "overhead" for each array)

2. more-or-less dynamic ones: Here, only the strings are affected.

(CBM-/MS-) BASIC decided that there is no benefit in doing a GC for the static
objects (no. 1). As these are only generated if a responding variable or
array is used, it is highly unlikely that one would not need them
anymore, thus, a GC is not needed. In fact, the interpreter cannot
safely determine if they are needed anymore. The only possibility would
be that the user nulls the numeric variables, assigns an empty string to
a string variable, or null or empties every element of a numeric or
string array. Another option would be to use something like "erase" in
order to delete an array, but that would not be an automtic GC anymore.

Thus, the only objects that are worth to be GCed are the string
variables themselves. The GC in the CBM BASIC goes through all the byte
in the string area and looks if these are used. If not, they are
considered garbage and overwritten, adjusting the pointers to the
strings that are still needed.

That's exactly what a GC would do. Have a look, for example, at the Böhm
collector (https://www.hboehm.info/gc/). That one, too, would not
collect the static variables (cf. no. 1 above). Of course, in C and C++,
they are "more" static than in BASIC as the compiler would pre-allocate
space for them, unlike the BASIC interpreter, that only allocates memory
for them as soon as they are used. This is, however, more a specific
difference because of the interpreter implementation in contrast to a
typical compiler implementation.


> What happens, however, is that the variable can change its length so it
> may leave some space after it (if it shrinks) or be moved away to a
> different location in memory (if it grows) again leaving a chunk of free
> space.

Well, in fact, CBM BASIC (at least, up until BASIC2 for the C64) never
leaves some space after if the string variable shrinks. It *always*
copies the new variable to a new location, leaving a chunk of free space
that is an object (the former string variable) that is not used anymore.

> This is a natural process and again has nothing to do with
> garbage collection.

I tend to totally disagree, see above. ;)

> The process then needs to be run which compacts the
> variables so that these small unused chunks are joined together to form
> one large chunk. It involves moving the variables to new memory
> locations but it does not free any "unused" space - the space is free
> already, it is just moved around in memory.

You are missing one point: While from a outside view, the space is
already free, the BASIC interpreter does not know yet which space is
unused! It must collect these "unused" bytes by moving memory around in
order to be able to use it again, that is, in order to make it free
again.

Thus, from the interpreter's point of view, the memory is not free,
but it contains some unused data - "garbage".


Other GC do the same, btw. For example, in C, you can have heap
fragmentation so that your allocation cannot be fulfilled, as you do not
have a large enough memory chunk available, but with the "compaction",
it would be possible to do you allocation. A "copying collector" (cf.
https://www.hboehm.info/gc/complexity.html) help in this case, as it not
only searches for unused memory regions, but also compacts them, like
the BASIC GC does.

Best regards
Spiro.

-- 
Spiro R. Trikaliotis
http://www.trikaliotis.net/

       Message was sent through the cbm-hackers mailing list