Mutation

[Chris Bitmead uid]

I think the better way is that arrays are generated by a small number
of well defined algorithms which create the array mutable, initialise
it, and then freeze it.

Thus we would have something like map-car-returning-array, which is
like map-car except that it returns an array.

If you encapsulate most of the interesting algorithms in STL style,
then the user of the algorithm to generate the array, doesn't have to
know or care by what means the array came in being. He will never know
that the map-car-returning-array actually cheated for efficiency
reasons.

>The problem with functional objects is indeed functional arrays.  You
>have to have some way to initialize them.  One way to do this is to
>have them start life as mutable arrays, and then at some point you
>'freeze' them into immutable arrays.  The problem with this approach
>is that it 'surprises' the person still holding onto a pointer to the
>old 'mutable' array.  These semantics are very unpleasant because they
>violate the constancy of type.
>
>Another approach is to create a brand new functional array by copying
>an existing mutable array.  This solves the problem of bad semantics,
>but forces you to throw away and GC a perfectly good mutable array for
>every immutable array.  So we have good semantics, but bad performance.
>
>The third approach walks the tight-rope between the previous two
>approaches.  The array starts life as a _linear_ array, which is
>mutated in-place in order to initialize it.  Since linear objects
>aren't recovered by the GC, the linear object's storage can be
>immediately 'recycled' (by 'freezing') as the functional array itself,
>which is already conveniently initialized.  Furthermore, since it is a
>linear object, there cannot possibly be any other pointers to the
>object, so good semantics are preserved.