Thursday, July 18, 2013

What about...

John Cowan said:
The arguments passed to `make-instance` are the sum total of the information needed to create the instance in its initial state.

Since you require that instances be transitively immutable, the initial state is the only state.

If you have those arguments squirreled away, then you can create another instance in the exact same initial state.
That's the basic argument. It's demonstrably false.
(setq foo (make-instance 'test-class))

(test-class/name foo)
So the game begins. I point out a trivial technicality, you adjust for it.
The arguments passed to `make-instance` combined with the appropriate
defaults from the initargs are the sum total of the information needed
to create the instance in its initial state.

Well, that's wrong, too. As Dan Lentz pointed out, "What about any stateful behavior encoded into the objects class?"

I'm pretty sure you ultimately win. But by the time I run out of objections your argument is going to be a patchwork quilt of exceptions, special cases, "implementation artifacts", "things that might be technically wrong, but can never make a real difference", etc. etc.

This doesn't inspire much confidence in our proof.

Mr. Lentz also asked:
Couldn't it just have trapped the out of date schema version in shared-initialize and dispatched it off to update-instance-for-redefined-class?

I don't know. When we bring an object from the store, it isn't really an instance yet.


John Cowan said...

Is not the class an argument passed to make-instance? So you grab out of the class whatever you need to save away. Q.E.D. again.

Again, the transitive immutability must extend to the class as well.

Joe Marshall said...

I think we can cover it by saying that the transitive immutability has to extend to everything we save. But isn't that a circular argument? Everything we save had better be immutable because it cannot reflect changes. (Aren't we trying to model changes at some point?)

Also, the phrase "whatever you need to save away" is a bit vague for a proof. That's like saying the proof is valid provided you satisfy "whatever you need" to make it so. Granted.

Dan Lentz suggested "maybe the class maintains an atomic counter for assigning instance IDs or, slots with allocation other than that of instance. In fact, there are these "quasi-stateful" elements kicking around in the implementation. But since they are not semantically part of the object state, they don't count.

I concede your argument, though (with the modification that we have to override shared-initialize rather than make-instance). I just think it isn't so obvious when you start getting into the details.

Unknown said...

I just had a look at Arthur Lemmons' Rucksack, which contains the most comprehensive and deterministic treatment of schema evolution I've come across. The essence of his solution seems to be maintenance of a schema table that is automatically updated on finalize-inheritance with version, all persistent slot names, and changed slot names: added and deleted. When an instance of the given class is restored, it is automatically updated to reflect any changes that are derived from the most current version it's class found in this table. It is handled during the course of update-instance-for-redefined-class :after allocate-instance.

One thing I noticed is that the slot-values are assigned by the slot-definition-initfunction which is a closure that preserves the lexical environment as it existed in the context of the class definition. This is something I think raises other questions about the QED-ness of the conclusion that the initargs are the sum-total representation of the instance, but maybe, like you said, this is a technical detail that doesn't amount to a practical concern in this scenario.

I do think the term immutability is being thrown around a bit here somewhat in denial of the reality that what we are in the very process of doing is mutating the instance. Is immutability even the goal? I mean, yes the wbtree is persistent in the sense that older versions of an object are never overwritten, but that doesn't preclude us from representing changes to an object in subsequent updates to the tree and expressing its value at a given point in time as MVCC. Any given version of the object is immutable, but the object itself can model mutability without detracting from that.

There are an interesting series of papers by Andreas Paepcke which describe some of the issues encountered and experience gained during the course of his work developing PCLOS that you might be interested in (if you haven't come across them already). IIRC, one is called "pCLOS: Stress Testing CLOS -- experiencing the meta object protocol"


Joe Marshall said...

Dan Lentz said I do think the term immutability is being thrown around a bit here somewhat in denial of the reality that what we are in the very process of doing is mutating the instance.
I disagree. The backing store is opened in append-only mode. It simply is not possible to change the data once it is written. No CLOS object we create has mutators. Where is the mutation?

Unknown said...

I think you covered the basic intent of my comment in your subsequent post "faking mutability". There isn't really a semantic difference between what I mean by "a different version of the same object" and what you are saying is a different object. It is just some different terminology leaking in from one of my own projects where I also have implemented (much more limited concept of) change controlled CLOS objects. Coincidentally, also using WTTREE.

I'm still looking through your pnode.lisp but offhand do you remember what you used for your weight-balancing parameters? (In the papers I've read these have been called delta and gamma). I'm basically looking to see if you are using the "revised, non-variant weight balance" algorithm described by Hirai/Yamomoto, in which case delta would be 3 and gamma would be 2. There was an interesting paper in which they derived these fixnum parameters, as opposed to the irrationals published in the original (non-variant) algorithm. They have a github repo for the source:

Joe Marshall said...

Hirai and Yamamoto wrote that long after, so I'm using Adams's values. I never delete a node, so it is a question of retaining balance during insertion.