Re: [Caml-list] Immutable cyclic data structures via a

["blue storm" <bluestorm.dylc@gmail.com>]

On 12/14/08, Francois Pottier <Francois.Pottier@inria.fr> wrote:
> On Sat, Dec 13, 2008 at 07:47:46PM -0600, Edgar Friendly wrote:
>> ExtLib (and thus batteries) uses your unmute (called [inj]) for
>> converting a mutable list into the normal immutable list.  The definition:
>
> This is, in principle, unsound. The compiler could (if it were more
> agressive)
> assume that a value of type 'a list is unaffected by a function call,
> whereas,
> if the list is really mutable, it could actually be written to by the call.

That could be an issue if an immutable list was mutated by the
library. Extlib uses mutability to build new mutable lists, to have
for example a cheap tail-recursive map (you can destructively cons new
cells at the end of the mutable list). The new list is then converted
in constant time to an usual unmutable list, wich is returned by the
function. The reference to the original mutable list is lost, and pure
lists are never converted back.

The mutable list stays inside the function boundary and, assuming the
function is correctly written, there is no observable mutability.