Persistent vectors

Simulating mutation by creating a new object is reasonable for CLOS objects, but it is terrible idea for persistent vectors. The large amount of copying would be bad enough, but algorithms that rely on growable vectors (by calling vector-push) will change from linear to quadratic in space. That's a disaster.

We simulate mutation by replacing an entry in the object-map. This forces the granularity of mutation to be the same as the granularity of the object-map. In other words, we cannot update just a single item in a vector because there is no object-map entry referring to just that item.

So why not fix that? The obvious solution is to allocate a contiguous set of object-ids. Easy enough, but if we want to "grow" the vector we'll have a problem. The vector storage itself can easily be moved, but the range of object-ids that map to the vector cannot easily be extended.

My solution was to change how object-ids and the object-map work. The object-map maps integers to persistent objects. Conceptually, the object-map itself is a vector. If we add an orthogonal index to object-map it becomes a 2-dimensional array. Now we can place vectors in the map and assign them a single primary index and map the secondary indices on to the vector elements. Vectors can grow (or shrink) without changing their primary index.

Now that we have persistent vectors that we can mutate, we can create mutable persistent cons cells (just a 2-element vector) and mutable persistent hash tables.