Re: in defense of GC

[Markus E Leypold <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de>]

Ray Blaak <rAYblaaK@STRIPCAPStelus.net> writes:

> Markus E Leypold <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de> writes:
>> BTW, you've been discussing (with ... I don't remember) the possibilty
>> of switching GC off. My idea (even with ML-like languages) was always
>> to define a subset of the language which the compiler can implement
>> with a stack only. 
>
> Does that automatically preclude any access types, unbounded strings, etc.,
> then? That would be quite a limited language.

Not necessarily. It precludes any _handling_ of stuff in a way that
doesn't allow the compiler to de-allocate memory when leaving the
scope. Basically the compiler would look at what happens and instead
of using heap allocated (GC'ed) memory it would use 'Controlled'
memory (in Ada parlance).


And BTW: AFAIK that has already been done once for some obscure subset of ML.

>
> That would simplify GC right off the bat. Maybe it wouldn't be needed at all,
> right there.

:-).


>> One advantage of that would be that one could start out with code that
>> requires GC, but is "obviously" correct and then transform in
>> correctness preserving steps it into code that doesn't require
>> GC. Both implementations could be tested against each other, at least
>> as far as their computational function goes, not the real time
>> capabilities that are perhaps only possessed by the 2nd variant.
>
> My reaction is to not trust testing only to gain the measure of confidence
> needed. You must be able to prove the the equivalence well enough.

Right. Therefore (in the case where more trust is needed) the proof of
euivalence by equivalence transformations (for a suitable definition
of equivalence).

> Also, if the non-GC version was realtime, why wouldn't the first one be? 

Because the interfaces change. Only the data processing provided is
equivalent, but the way data is passed and retrieved, changes.

> Where is the difference in behaviour? If you have no heap, then
> wouldn't execution should be equivalently predictable in either
> case?

I'll try to make up a simple, but not necessarily good example. This
is not about runtime GC but about going from GC to manual memory
management, but I hope it will serve. The programs concatenate 2
strings:

With GC (naive implementation)

   let concat1 (s1:string) (s1:string) = s1 ^ s2;;

With manual MM.

  let concat2  (s1:string) (s2:string) (result: string ref) = 

      result := Some (s1 ^ s2)

I realize this might not be the beste example, since I just made it
up. But the idea is, that (string ref) is (by the compiler) translated
into a char* and that result := ... actually becomes a malloc() plus a
copying of memory. some_var := None would compile to explicit
deallocation (pointer is overwritten with null).

Both functions are equivalent (they concatenate strings), but the
second would not be required to work in a GC'ed environment.

Similarily, I think, it might be possible to avoid malloc() if
everything is done in static or local buffers.

Regards -- Markus