Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Stephen Dolan <stephen.dolan@cl.cam.ac.uk>]

On Mon, Sep 29, 2014 at 10:00 PM, Gabriel Scherer
<gabriel.scherer@gmail.com> wrote:
>> Please, don't do that hack ! The compiler assumes immutable data are not
>> mutated and optimise knowing that.
>
> My understanding was that it is unsafe to Obj.magic an immutable data
> structure into a mutable one (one mental model is that immutable data  might
> be allocated in read-only memory, although that's not what the current
> implementation does), but that on the contrary it is safe to Obj.magic a
> mutable data-structure into an immutable one. The Obj.magic-using code for
> List.map, implemented in Extlib and inherited by Batteries, is careful to
> use an unsafe cast in exactly the second situation. This is a feature that
> other languages (eg. Mezzo) safely provide.

This trick is unsound in our implementation of multicore OCaml: the
system assumes that immutable objects only point to older objects, and
thus that a shared immutable object cannot point to a private
immutable object. This can be hacked around (we have a similar hack
for recursive immutable objects), but the point is that such tricks
are fragile and depend on very implementation-specific behaviour.

Even in single-threaded OCaml, this trick is broken by quite
reasonable compiler optimisations (although not ones that OCaml does
today). For instance, if ocamlopt were to perform alias analysis and
optimise based on the results, the first thing the alias analyser
would do is conclude that references to immutable and mutable fields
do not alias. This would allow it to swap the order of references to
the immutable and mutable fields, and after inlining would mean that
the cons cell is read before it is initialised.

Stephen