[ScottBurson]

No reply from Simon, but for the record, here's how I would do it. The Julia representation of a matrix would be a pair of an array and an override map, a functional map which is initially empty. Pointwise functional update returns a new matrix with a new value in one cell; the implementation returns a new pair of the same array and a new override map, computed as the previous override map functionally updated with the new mapping ((i, j) -> x). Pointwise access looks in the override map first, and if it finds no mapping there, looks in the array.

When you want to perform a matrix operation, like multiplication, that for efficiency needs to operate on a plain array, here's what you do. First, if the override map is empty, you can use the array as it is. Otherwise, you make a new copy of the array, then iterate through the override map, storing each value in the array at the specified coordinates. Then you write the pointer to the copied and updated array into the array slot of the original pair. Yes, this modifies a nominally immutable object, but critically, it does so in a way that doesn't change its semantics. Finally you write, into the override-map slot of the original pair, a pointer to the canonical empty map. Now you can pass the array to your matrix multiply routine, or whatever.

The two writes don't even require locking in a multithreaded situation, though on many architectures there will need to be a memory barrier instruction between them, so another thread can't read the two writes in the wrong order. Given that, the worst that can happen is that another thread sees the updated array but the original override map, whereupon it will make a redundant copy of the array and redundantly apply the updates to it, doing a little extra work but producing an identical array.

[StefanKarpinski]

This design seems workable for vectorized operations where the overhead of the override map can be amortized away (like matmul). The problem lies with scalar operations on individual array elements. Most high-level, dynamic languages don't bother themselves with those operations and instead encourage programmers only to use predefined, vectorized kernels. Julia isn't like that, however. A key property of the language is that you can write low-level C-style code with for/while loops, operating on individual array elements – and get C-like performance. The overhead of an overlaid structure like you describe becomes fatal in this situation since you pay for it with every element you touch. There may be clever compiler optimizations that can claw back some of that overhead – but one of the design principles of Julia is to avoid needing clever tricks in the first place. Instead, do the straightforward fast thing. In this case, that dictates standard C-style contiguous-memory mutable arrays – there's just nothing that can match their raw performance.

[ScottBurson]

Ah, I see. Yes, I was imagining something more like Numpy.

So -- just thinking out loud here -- in order to use a design like the one I've proposed, you would have to make the "flatten" operation user-visible; it would look like a type conversion from a functional matrix to a bare array. Then the user's algorithm could run on the array, and once they were out of the hot section, they could, if they so chose, convert it back to a functional matrix.

If I personally were going to write Julia code, I think I would like things to work this way. Not only am I accustomed to functional semantics, and generally prefer it, but I'm also used to switching modes (even writing mixed algorithms in which some collections are functional and some are imperative). But I can see the argument that that might be a little too much complexity for your target audience.

[StefanKarpinski]

> Ah, I see. Yes, I was imagining something more like Numpy.

Understandable. The approach and philosophy is very different, however. Julia feels much more like dynamically typed C++ than it does like Python with heterogeneous arrays added on.

> you would have to make the "flatten" operation user-visible

This seems like it would be a method of the `convert` function. Built-in types are barely special at all in Julia, so you could – and people have [1] – make purely function analogues of any data structures you like and use all the usual operations on them. One can even allow mutation when necessary, but just make the non-mutating operations sufficiently efficient that mutation is rarely necessary.

A fair amount of mathematical code does typically work in two distinct phases:

1. construction/mutation phase – vectors and matrices are constructed and mutated to setup the problem;

2. computation phase – vectors and matrices are used in computations, typically in a purely functional manner, where each operation creates a new objects (e.g. `Z = sqrtm(2X + Y^2)`).

Unfortunately, purely functional collections don't help much with either of these phases: the first phase is inherently full of mutation and typically quite local, so the drawbacks of mutation are limited; the second phase is already inherently functional but doesn't need functional data structures. What you really need in the second phase is escape analysis that is clever enough to figure out that it can reuse temporaries.

[1] https://github.com/JuliaCollections/FunctionalCollections.jl