You Cannot Correctly Represent Change Without Immutability | Hacker News Reader

You Cannot Correctly Represent Change Without Immutability

tapestryjava.blogspot.se

62 pointsDanielRibeiro19 comments

I'm glad the idea of taming mutability is finally becoming somewhat mainstream. A while back, I wrote a post about the problems caused by the assignment statement that I'm still proud of. Back then, I didn't know about Clojure, and it seemed no one outside the FP crew cared about that problem.

http://loup-vaillant.fr/articles/assignment

This sort of ignores the fact that most modern databases use MVCC style row versioning - they only "forget" that the leaf was once attached to the tree when it doesn't actually matter any more, and actually use exactly immutable type state in the interim.

It is important for our celebrity driven tech culture for each generation to "invent" (or 'rediscover' more generously) extant (and far more rigorous) work by the workers of prior generations.

In which modern MVCC databases can you ask the results of a query if it had been made 1000 transactions before I started this transaction? MVCC is great for dealing with the problems caused by mutability with Concurrency. Datomic takes versioning and immutability a good bit farther than that.

I guess I read more into the last paragraph than I should have; it portrays the simple problem of read write concurrency as if nobody solved it yet. It was a really bad way for the author to end the post because it confuses what was written before.

Mind you, creating audit / history tables to allow querying of past state is an extremely common and very standard database pattern too. Though I will admit I have encountered systems where more than half the tables were being audit logged so it's interesting to think about a database where that was effectively the default.

This notion of change seems to conflate a lot of ideas. Knowing that something has changed is different than being able to replay the change. And once you have a system that cares so much about time haven't you given away half of the programming advantage of functional programming? Sure, there may be immutability, but you trade that for having to manage state explicitly in immutable objects. That just sounds like a whole new class of "race conditions" (you passed me this state object, but someone else just created that state object with the same identity).

It does seem to mix a lot together. And the title is easily proved wrong. You can store data as a live object and a linked list of diffs to go further back in time. This is how the git pack file and many backup systems work.

That is just an efficient way to store the original object and linked list of diffs to get to the current object (assuming accessing the current object is more popular). Note that if you store the original and the diffs, those things are all immutable.

Indeed, that is how git works in general – recording changes as immutable commits, and having one or more heads which point to the new immutable commit.

Right, you can flip it to make everything immutable, but then accessing the current object is O(t).

And then you have SourceSafe

I understood that git stores snapshots, and not diffs. At least conceptually.

Conceptually it's snapshots. At the lower level of pack files it's diffs.

It does both.

Musing:

The deeper question that Rich Hickey does not seem to have addressed is whether a 1 to 1 mapping between 'reality' and 'systemic models' is in fact generally beneficial.

Right now, the focus is on "productivity" e.g. producer (read: programmer) concerns and creating a practical model of concurrency that is accessible to the general programming workforce, but there are other concerns that reach into very unlikely areas of (overall social) concerns e.g. energy use, that are affected by this decision to focus on reducing programmer pain (instead of minimizing use of resources, for example).

An alternative future for the field is a future where a very select subset of "programmers" are tasked with building systems according to a semantic model that is not an analog of the "real world", or perhaps a deeper mapping of "real world" that is closer to quantum reality (e.g. probable states of things) than a classical world view, and such professionals will get compensated for their (strange) comprehension of reality given that it may save businesses using their systems money. Such systems will certainly manifest in their outer layers models that map to "real world" e.g. a banking interface and attendant "real world issues" such as "when did this thing change?" and that is why MVCC was invented and we may well discuss "immutability", "state" and "identity", but may entirely do away with such (possibly) quixotic efforts in the innards of the system.

Does having a co-ordinated view of changes across a system also require some kind of notion of time? (At the least, a tick whenever some kind of changes happen?).

Are there any insights to be gained over comparing this idealised view of time and physical time?

e.g. I don't really see that relativity comes into play but could it/should it?

There could be some kind of analogue for how changes spread around a distributed system, which is limited by the effective propogation speed of the system.

Do we run into some kind of underlying law of distributed systems about the inability to have a reliable, cross-system change-based "tick"? (e.g. could that be a consequence of the CAP theorem? http://en.wikipedia.org/wiki/CAP_theorem)

Not really you can keep objects locked independently.

  A->A(30)->A(29)...A(0)
  B->B(20)->B(19)...B(0)

start adding a new A; start adding a new B; Finish adding a new A; Finish adding a new B; Verify B; Verify A;

  A->A(31)->A(30)->A(29)...A(0)
  B->B(21)->B(20)->B(19)...B(0)

Now keep A and B's states stored on different machines and they become completely independent with no concept of time or ticks being introduced.

As to an actual example of this in use think bank accounts in an MMO, you might want a transaction log, but you don't necessarily care about time-stamps all that much.

Regarding your second question, I suggest reading this classic article by Leslie Lamport: http://www.google.com/url?sa=t&rct=j&q=&esrc=s&#...

Thanks, that's a great paper (above link is timing out, I got it from this page):

http://research.microsoft.com/en-us/um/people/lamport/pubs/p...

I believe this is the Clojure/West talk from which Hickey is being quoted:

http://www.infoq.com/presentations/The-Design-of-Datomic

Reply on news.ycombinator.com