This is unfortunate, because it could potentially be a very useful if every single atom of data came with a built-in list of previous states, with timestamps, and with an identifier for the code/process that last changed the state.

Obviously, this is usually what debuggers try to do. But there's no reason why something like this couldn't be built into a language.

(Yes, it would be slow. No, it wouldn't be that slow if done right. It wouldn't even have to be slower than many other standard practices. But yes, it could potentially use a lot of memory unless given a cutoff. Even so...)

CS generally still seems stuck in the "memory is a line pigeonholes" model, and immutability seems to be a crude memory management hack, not a complete state control solution.

I sometimes wonder if a lot of the issues with state are caused by the fact that languages have extremely limited tools for dealing explicitly with representations of historical causality and past/present/future, and not because state itself is inherently evil.

Well, it depends on which version control system we're imagining. In my mind, the immutable data-structure approach is like git, and I think what you're imagining is more like CVS.

Consider: immutability by itself doesn't enforce versioning; it just makes the state-of-the-world equivalent to state-of-the-root-pointers-of-your-heap, because the pointed-to things cannot change. (I.e., referential transparency.) So it pushes the versioning up to whatever agents manage the root pointers. This is sort of like git: you build an immutable DAG, and you have mutable HEAD pointers that move around in it. (The difference is that git has one HEAD for the tree while this world has one HEAD per global or stack-local root.) When you have a reference, you have a snapshot of the world in time that will never change.

Your "each slot has a list of previous states" is more like CVS in that it versions each "file" separately. This is also useful, but for a different reason: sometimes you really do want that history as a first-class concept. You can derive the per-file history in a git-like system too but it involves some computation. (And coming back from the analogy, in such a memory-management scheme, you would need to formalize the changes to root pointers into some sort of transaction system.)

All of that said, I think what you describe would be really useful for debugging, albeit probably pretty expensive (each store instruction touches an undo log?). Time-reversible debuggers may have done something like this?

http://debug.elm-lang.org/