Inherited const when you need to mutate

[H. S. Teoh]

On Tue, Jul 10, 2012 at 05:39:45PM +0200, David Piepgrass wrote:
[...]
> The difficulty, in case you missed it, is that somebody else (the
> Object class) says that certain functions are const, but in certain
> cases we really, really want to mutate something, either for
> efficiency or because "that's just how the data structure works". If
> a data structure needs to mutate itself when read, yeah, maybe its
> functions should not be marked const, but quite often the "const" is
> inherited from Object or some interface that (quite reasonably, it
> would seem) expects functions that /read stuff/ to be const.
> 
> And yet we can't drop const from Object or such interfaces, because
> there is other code elsewhere that /needs/ const to be there.
> 
> So far I have no solution to the dilemma in mind, btw. But the idea
> someone had of providing two (otherwise identical) functions, one
> const and one non-const, feels like a kludge to me, and note that
> anybody with an object would expect to be able to call the const
> version on any Object.

I think the trouble comes from conflating logical const with actual,
bitwise, memory-representation const. Logical const is what C++ provides
(or tries to, anyway). It's a way of saying that the object will not
_visibly_ change, but says nothing about its underlying representation.
So the object may be changing state internally all the time, but to the
outside world it looks like it's not changing.

D's const, however, is a _physical_ const. It's saying that the
underlying representation of the object will not change, and therefore
it will not visibly change either. This is a much stronger guarantee,
but unfortunately, that also narrows its scope. It cannot handle the
case where the object needs to change internally while still retaining
the outward appearance of non-change.

Conceptually, there shouldn't be any problem: if your object is one of
those that changes internally but not visibly, then in D's viewpoint
it's the same as a mutable object (which it is, physically speaking).

However, the trouble comes when parts of the D runtime need certain
guarantees, for example, a built-in hash function may expect that taking
the hash of an object shouldn't change its state. Logically speaking,
it's OK for the object's toHash method to change it (say, by caching a
value that takes a long time to compute). But the D runtime wants to
give _guarantees_ that nothing unexpected will happen. And so it
requires toHash to be const. That way, even a rogue object method will
not be able to change it (not without breaking the type system, anyway),
and the runtime will be able to give strong guarantees that yes,
literally _nothing_ will cause unexpected mutation to the object when
you call its toHash method. But requiring toHash to be const means that
you cannot cache the results of an expensive computation, and so certain
things that would work with a logical const system don't work in D.

So the bottom line boils down to, we want logical const for some
objects, but D doesn't have logical const. Imagining that it does only
breaks the type system and any guarantees the language provides. Whether
we _should_ have logical const in D is, of course, something to be
discussed, but the main objection against that is that it's not
enforceable. What constitutes a "non-visible" change of state? It's not
possible to tell without solving the halting problem, unfortunately. An
object's state can be extremely complex, with only a certain subset of
state changes being visible. There's no feasible way for the compiler to
figure this out automatically, and so you end up with the C++ const,
which can be cast away anytime, anyday, and therefore is pretty much
useless except in theory. All it takes is for _one_ function to be const
incorrect, and you have a hole in which supposedly immutable objects get
changed when they aren't supposed to.


[...]
> I was referring to a potential port from C#, which has no const. My
> particular data structure (a complex beast) contains a mutable tree of
> arbitrary size, which the user can convert to a conceptually immutable
> tree in O(1) time by calling Clone(). This marks a flag in the root
> node that says "read-only! do not change" and shares the root between
> the clones. At this point it should be safe to cast the clone to
> immutable. However, the original, mutable-typed version still exists.
> As the user requests changes to the mutable copy in the future, parts
> of the tree are duplicated to avoid changing the immutable nodes, with
> one exception: the read-only flag in various parts of the original,
> immutable tree will gradually be set to true.
[...]

Yeah, this is logical const. Unfortunately, D doesn't have logical
const.


T

-- 
In a world without fences, who needs Windows and Gates? -- Christian Surchi