The lost art (Was: The VAX is running

[Jim Battle]

Pete Turnbull wrote:
...
> Garbage collection isn't as trivial as one might think.

I'm not sure if I'm the "one" you are addressing.  :-)  I am aware that 
there are many theses written on the subject.  The "best" allocation and 
garbage collection algorithm to use is very domain specific.

In the restricted case of MS BASIC, GC isn't very difficult.  The root 
of all live strings are known, unlike, say C, where you can't tell which 
things are pointers, or even if you know it is a pointer, you don't know 
if the pointer is valid.

In MS BASIC, all strings are rooted in one of two places: a simple 
variable table, or the string evaluation stack, as I described before. 
No heuristics are required, just a simple linear sweep.  New strings are 
simply allocated from the single, unfragmented chunk of memory at the 
end of the string pool.  (I don't recall if the end is in lower or 
higher address of that range though).  There is no attempt to have an 
intelligent allocator or to coalesce dead fragments (as they aren't 
known to be dead until GC time).

> There's a 
> trade-off between space and time, 

... and complexity

like in the simple example I gave.