GC and map

GC and map

[Christophe Raffalli]

Hello,

I would like to implement the feature described bellow ... I think this is impossible in the current
state of OCaml, but I may be wrong, so if someone can help ...

'a map is the type of a functional map from int to 'a (I do not care about the internal 
representation, except that performance would matter a little too)

set is the type for set of int (here again representation do no matter that much)

All maps can only appear in structure of type
environment = { accessible_keys : set; map : 'a map }
(this is possible to enforce with abstract type)

Then I would like the GC to behave like this :

  Let m be of type 'a map and alive. Assume it appears only in the following alive environment
{ accessible_keys = a1; map = m }
{ accessible_keys = a2; map = m }
...
{ accessible_keys = an; map = m }

Then, I would like the GC to remove all bindings in m for integers not present in a1 ... an.
It would even be better if values associated to these bindings where not even scanned by the GC, but 
I think this is much more difficult.

Any Idea (purely in OCaml or in C) ?

This would be possible in C if in the "struct custom_operations" there was a "scan" function to scan 
values inside an allocated custom block. This function would be very similar to the serialize 
function ... Anyway I would prefer a pure OCaml solution.


-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------

Re: [Caml-list] GC and map

[Daniel Bünzli]

Can't you just use weak hash tables [1] in some way to implement that ?

Best,

Daniel

[1] <http://caml.inria.fr/pub/docs/manual-ocaml/libref/Weak.html>

Re: [Caml-list] GC and map

[Christophe Raffalli]

Daniel Bünzli wrote:
> Can't you just use weak hash tables [1] in some way to implement that ?
> 

In fact, to make it simpler, I want weak key functional map.

That is functional map where binding are GC-collected when the key is no 
more accessible by the GC. I did not present it this way, because this 
requires equal key to be physically equal which does not fit with 
functional map, but this is not a real problem in my case.

If I remember well previous investigations, it is tricky and ugly but 
possible to implement weak key imperative hash table from the poor weak 
array of OCaml.

But weak key functional map seems impossible (I have no proof ;-).

The use for that is to try it for an evaluator for a toy functional 
language where the key are variable names and the maps hold the value of 
the variables. I do not want to simplify maps by hand where some 
variables do not exists in specific closure and I had like the GC to do it.

Actually, this approach is not the one use in OCaml: when closures are 
build by OCaml, specific environments are build with only the required 
variables to make sure there is no memory leak. In my approach, you can 
share environments between many closures, but the scan of the 
environment by the GC is much more complex (not sure this is really a 
gain anyway)

> Best,
> 
> Daniel
> 
> [1] <http://caml.inria.fr/pub/docs/manual-ocaml/libref/Weak.html>