Re: [Ocaml-lib-devel] A start on a functional array module

[Diego O. F. P. <Die...@et...>]

    Bonjour,

> > Isn't O(1) access possible with a different kind of functional array
> > structure?  One where the "head revision" of the array is stored as an
> > array, and previous "versions" are stored as a list of differences.
>
> How do you know when someone else has made a change to the array, and you
> no longer have the most recent version?  The "someone else" might be a
> different thread, or it might just be a different function.  Also, the
> most recent version might be garbage, and you might have different
> "branchs" of the same data structure.

Version array have to be stamped. The stamp is a global value hence
anyone can know if the cache he is using reflects the most recent
version of the array.

The problems faced with stamping are :
- tree-like stamp structure (what if an other worker still uses an old
version of the array in a read-write way ?)
- garbage collection (there is always a pointer to a value since you
need to be able to restore it in a cache. How will the GC know that it
is a 'restoration' pointer and not a 'user' one) ?

Many implementations allow only read operations on old versions not to
have to cope with the first problem. The second problem is usually
faced with a kind of reference counting.

You can have a look to Martin Erwig's ML implementation of his
Functional Graph Library to have an examples of (list) version arrays.

Most of the work of Melissa O'Neill is to try to solve the stamp and
garbage-collection problems. The binary tree part being almost
obvious.


        Diego Olivier