Inherited const when you need to mutate

[David Piepgrass]

On Monday, 9 July 2012 at 16:02:38 UTC, Timon Gehr wrote:
> On 07/09/2012 05:00 PM, H. S. Teoh wrote:
>> On Mon, Jul 09, 2012 at 01:44:24PM +0200, Timon Gehr wrote:
>>> On 07/09/2012 08:37 AM, Adam Wilson wrote:
>>>> Object is now const-correct throughout D. This has been a 
>>>> dream for many of you. Today it is a reality.
>>>
>>> PITA. Forced const can severely harm a code base that wants 
>>> to be flexible -- it leaks implementation details and is 
>>> infectuous.
>> [...]
>>
>> Can you give an explicit example of code that is harmed by 
>> const
>> correctness?
>
> 1.
>
> Most code that gives amortized complexity guarantees, eg:
>
> interface Map(K, V){
>     V opIndex(K k) const;
>     // ...
> }
>
> class SplayTree(K, V) : Map!(K, V) {
>     // ???
> }
>
> 2.
>
> - hash table
> - opApply compacts the table if it is occupied too sparsely, in 
> order
>   to speed up further iteration.
> - toString iterates over all key/value pairs by the means of 
> opApply.
>
> Clearly, toString cannot be const in this setup.
>
> 3.
>
> Often, objects can cache derived properties to speed up the 
> code. With
> 'const-correctness' in place, such an optimization is not 
> transparent
> nor doable in a modular way.

I guess D does not have 'mutable' (like C++) to override const on 
methods? Caching anything slow-to-compute is my typical use case, 
and I know a hashtable design where the getter will move whatever 
value at finds to the front of a hash collision chain.

Oh, and this is interesting, I implemented a B+tree-like data 
structure* in C# that supports O(1) cloning. It marks the root as 
"frozen", making it copy-on-write. In order to clone in O(1), the 
children are not marked as frozen until later, when someone 
actually wants to mutate one of the copies. A user can also make 
the tree immutable in O(1) time and freely make mutable copies of 
it. This use case is pretty complex, so if I port this to D, I'd 
probably just cast away const/immutable where necessary. C#, of 
course, has no const so it was never a concern there.

*it's actually way fancier than that, I should really write a 
CodeProject article on it.

Of course, the trouble is, you can call any const method on an 
immutable object, so any const method that mutates needs to be 
thread safe. Many uses of C++ 'mutable' are thread-safe (e.g. 
most platforms guarantee atomic pointer-size writes, right? So 
two threads can cache the same int or two equivalent class 
instances, and it doesn't matter who wins)... but many other 
cases are not (e.g. the hashtable).

This is not a solved problem, is it. Ideas?