GC for pure functions -- implementation ideas

[Don]

Fawzi Mohamed wrote:
> 
> On 16-apr-11, at 22:49, Timon Gehr wrote:
> 
>> [...]
>> The problem is, that inside a non-leaky pure function the general case 
>> for dynamic
>> allocations might be just as complicated as in other parts of the program.

Yes, but that only matters if that function is both extremely 
memory-inefficient AND long-lived. In which case you can fall back to 
the normal GC (or even a dedicated pure GC). I don't think you ever lose 
anything.

> indeed, this is exactly what I wanted to write, yes in some cases, one 
> can get away with simple stack like, or similar but it breaks down very 
> quickly.
> In fact GC were introduced by functional languages, because they are 
> kind of needed for them, already that should hint to the fact that 
> functional, or pure languages are not intrinsically easier to collect.

I find that *impossible* to believe. Note also that you are equating 
"functional" = "pure" in the D sense, which is not true.
Firstly, functional languages generate *enormous* amounts of garbage. D 
does not. Secondly, non-leaky pure functions are rare in functional 
programming languages. I think we are in new territory here.
> 
> What can be useful is allowing one to add a set of pools, that then can 
> be freed all at once.
> Having several pools is also what is needed to remove the global lock in 
> malloc, so that is definitely the way to go imho.
> Then one can give the control of these extra pools to the programmer, so 
> that it is easy use a special pool for a part of the program and then 
> release a lot of objects at once. Even then one should put quite some 
> thought into it (for example about static/global objects that might be 
> allocated for caching purposes).
> A strictly pure function returning a value without pointers gives 
> guarantees, but as soon as some caching (even behind the scenes) goes 
> on, then things will fail. If a separate pool is used consistently for 
> cached or shared objects one should be able to allow even caching.
> All this comes back again to having several pools, showing how useful 
> such a primitive is.
> 
> Fawzi
>