Logical const in D

Question

D has two types of constness: immutable variables are ones that were declared immutable, and always will be immutable, while const variables are simply read only versions of an object.

Logical const is when a function is marked as const, but allows write access to one or more member variables. The typical use of this is for lazy evaluation, e.g. (in C++)

struct Matrix
{
  double determinant() const
  {
    if ( m_dirty )
    {
      m_determinant = /* expensive calculation */;
      m_dirty = false;
    }
    return m_determinant;
  }

  void set(int i, int j, double x) { m_dirty = true; ...; }

  mutable bool m_dirty;
  mutable double m_determinant;
};

Here, determinant() is const, but can still modify m_dirty and m_determinant due to them being marked as mutable.

The D const(FAQ) says that D2 doesn't support logical const because of the weak guarantee that it provides, which is a hinderance to writing concurrent programs, and makes certain optimisations more difficult.

I completely understand the concern, but what if we need logical const?

Consider the case above with the Matrix class, but without caching (and any need for logical const). Also imagine that this class is used all over my codebase, and is mostly accessed through const references.

Now consider that profiling has revealed that the determinant() function is a bottleneck in the code, and furthermore it is usually accessed repeatedly with its value rarely changing i.e. caching, as above, would be a perfect optimisation.

How can I do that without logical const? Going all over my codebase changing const references to non-const references is not an option (for obvious reasons).

What options do I have (if any)?

Phony

If "expensive computation" can be expressed as a pure function, then the compiler could do caching for you. – Cavie

@he_the_great: I don't believe it does, though. The problem with "sufficiently smart compiler" solutions is they frequently fail to exist. :P – Ywis

@he_the_great: No, it can't. As you can see, caching requires knowing when the data has changed. The only way this can happen is if the compiler were to add a boolean flag to my Matrix as I have above. The compiler is not allowed to add arbitrary data to your structures. Also, as DK says, it simply doesn't do it anyway. I'm not interested in "could". – Phony

@Peter, No, it would not need to know when the data changes because you call it with the data every time. Caching would not be in your struct but a part of a call to the function, or that is the intent. As the compiler does not cache, I did not provide this as an answer. But caching is one of the goals for having immutable pure functions. – Cavie

@he_the_great: How can you cache as part of the call to the function? If two different functions, F and G call determinant() on the same Matrix without changes to the Matrix, how can they independently know that they can use the same cached value? – Phony

It wouldn't be determinant() that would be cached. If you called something like calc_m_determinant(int i, int j, double x) pure {}, then that function could be cached for previous calls based on the values passed in. I don't know how this is supposed to be done, but it was been mentioned as something that is possible. – Cavie

It can't be done, not without some quite significant memory overhead at least. And besides, as I said before, I'm not particularly interested what some magic compiler might do -- no compiler does this, and that's all that matters. – Phony

Bringing in the Godwins law of language debates; IIRC the kind of caching that is being considered has been available in Lisp for decades. – Burrill

why do you need determinant() to be const ? – Priestly

Because I want functions with const references to a Matrix to be able to find its determinant. – Phony

Answer 1

I think that it would be appropriate to post the basic conclusions of the recent thread on this topic on the D newsgroup here, so that those who don't track that list can still get the appropriate answer.

D's const is not logical const. It is transitive and fully const. The language does not technically support logical const. The language does not define any way to mutate a const object.

And actually, C++ doesn't have logical const either. Using mutable and casting away const-ness allows you to totally circumvent const, such that, technically-speaking, const doesn't actually guarantee anything except that the you aren't calling any non-const functions on a const variable. The fact that const functions are actually const and don't screw with your variables is completely held together by convention. Now, most programmers don't go around casting away const-ness left and right and making everything mutable, so in practice, it's quite useful, but it not only can be completely circumvented, but the lanuage specifically gives you defined means of doing so. In C++ mutable and casting away const are well-defined and supported by the language.

D doesn't do that. D's const is actually const. Casting away const on a variable and then altering it is undefined. There is no mutable. D's const has real guarantees (as long as you don't do anything undefined like cast away const on something and then mutate it). This is important, not only because the compiler guarantees for D are much stronger than those for C++, but because immutable variables can't be altered in any way shape or form. They could be in read-only memory, and who knows what horrid things would happen if you tried to cast away immutability and alter such a variable (a segfault would likely be the nicest thing that could happen). And since a const variable could actually refer to immutable data, casting away const to alter a variable or allowing for const variables to somehow be altered would be bad, to say the least. So, the language doesn't allow it.

Now, as BCS points out, D is a pragmatic language. You can cast away const, at which point you could alter the variable. So, for instance, you could have a variable which was used to cache the return value of a const function (presumably with that cache being invalidated if the state of the object changed) and cast away const to change it. As long as the variable in question is not actually immutable, it will work. However, this is undefined behavior. Once you do it, you're on your own. You're bypassing the type system and the compiler's guarantees. You are the one responsible for making sure that you don't do it on an immutable object or otherwise screw up what the compiler normally gurantees. So, if you need to do it, you can, but you're stepping out into the Wild West, and it's up to you to make sure that you aren't mutating what you shouldn't.

Given that casting away const will work as long as the variable doesn't actually refer to immutable data, it is possible to create a Mutable template to essentially get what mutable gives you in C++ (so, it'll do the casting away of const-ness for you). he_the_great gives an example of such a template in his answer. But using such a template is still undefined behavior. Using it on an object which is actually immutable is going to cause problems. You, the programmer, must make sure that it's used correctly.

So, D makes it technically possible to have logical const by casting away const, but in order to do it, you have to step outside of what the compiler guarantees by bypassing the type system, and you must make sure that you don't misuse it and mutate variables which shouldn't/can't be mutated, or your code will have problems - segfaults quite possibly being the least among them.

EDIT: I forgot to mention the one proposed solution which does not break the type system. As long as you're willing to forgoe purity, you can use a global variable of some variety (be it at module scope, a class variable, or a struct variable) to hold your cached values. The const function can freely use and mutate the global variables, so it can be used in lieu of the missing mutable. That does mean, however, that the function can't be pure, which could also be a big problem. It is, however, a way to have a const function still be able to mutate the data that it needs to without breaking the type system.

Harwilll

"Given that casting away const will work as long as the variable doesn't actually refer to immutable data" - Is this given? I know it is probably true in current compilers, but I'm pretty sure it's still undefined behaviour, which makes it a non-option as far as I'm concerned. – Phony

It's a given for dmd. I'd be very surprised if it ever didn't work with any D compiler. However, it is undefined. So, it's expected to work, and it should work, but technically-speaking, there's nothing that guarantees that it will always work for all D compilers. But if you want to mutate a member variable of a const object, it's the only way that you can do it. – Harwilll

Well some where talking about the possibility of automatic parallelisation using the guarantees that const provides. Personally, I don't think that's possible, but if it is, and it does happen then I would rather my program stayed intact when the change is made. – Phony

Const doesn't really provide enough guarantees for much on that front (except perhaps when combined with pure), but it's generally immutable that you need when dealing with multiple threads. But if your functions were truly logical const, then the purity factor shouldn't pose a problem, since the result wouldn't have changed anyway. Given the nature of const, it's hard to believe that casting away const on an object in mutable memory would ever stop working (especially if it's not pure), but if you want to avoid even the possibility, then it makes sense to avoid casting away const. – Harwilll

Why are you advertising that const in D provides strong guarantees unlike C++'s (documentation) const, and then advertising a way to hack around that? Surely, as Peter Alexander pointed out, lconst (or some type of logical const) is needed. My view is that const-ness properties of functions get pretty complicated (e.g. sometimes D needs non-const, const and immutable versions of the same function) and shouldn't be managed by programmer, though granted we don't have much of an alternative. – Envelop

There are all kinds of difficulties in providing logical const with any kind of real guarantees, so the odds of any such thing being added to the language itself are low. The programmer can already do it on their own in the sense that they can mark a function as logically const in the documentation but have it be mutable. And I'm not arguing that someone should use an external variable to get around const - if nothing else because it breaks purity. I'm just pointing out that if you're willing to break purity, it is a way to cache stuff. – Harwilll

Answer 2

I haven't touched D2 in ages, so you might want to double-check what I say. :)

I'm not sure you really have any good options. D's const and immutable are significantly stronger than C/C++'s, so casting them away isn't an option. You've explicitly ruled out changing your usage of const in your code.

You could cache the result of the operation in a global hashtable keyed on the matrix value itself. That will work for any combination of const/immutable. The problem with that, of course, is that D doesn't have the fastest hashtables in the world and computing the hash could be slow. Maybe pre-compute the hash when creating the matrix.

The other option would be to compute the determinant eagerly when the value changes.

Aside from that, I can't think of anything else. The problem, really, is that you're asking the compiler to protect you with const and then trying to break out of it. The "proper" solution is probably to just not use const. :P

Ywis

That's what I fear: D has may const so strong that it has become unusable, so instead of having C++'s weak guarantees, you have no guarantees at all because no one can use it (Phobos doesn't even use it) – Phony

@Peater: I would disagree about it being unusable. The problem only comes up when something ends up being defined as const when it isn't really const. – Burrill

But, because of the viral effect of const, making one function non-const usually makes lots of functions non-const. As soon as determinant() becomes non-const, all functions that call it on a const Matrix have to change to use a non-const Matrix, which means that all function that pass a non-const Matrix to those functions now need a non-const Matrix etc. etc... It propogates throughout the whole codebase, and good luck trying to write generic functions... – Phony

@Peter: I thought that was what I said. In your example, the only reason to make determinant() non const is if you want it to do something to an instance that can't be done to a const instance; i.e. the instance is not in fact const. At that point you have something being defined as const when it isn't really const; thus you are in the exact case where I said the problem comes up. – Burrill

Things change if you add logical const but IIRC there is little if anything that can be gained by having that as a language construct that can't be had from a library implementation. The guarantee that can be had from the language feature version are just too weak. – Burrill

The thing is though, determinant() is still const -- it's just a different type of const (logical const vs. binary const). To users of determinant, there is no difference between the logical and binary const versions (calling determinant doesn't actually change any observable state). – Phony

Btw, what do you mean by having logical const as a library implementation? – Phony

You could create a LogicalConstMatrix type which can be created from a Matrix but doesn't provide any logically mutable methods. Not terribly convenient, but the major point here is that attempting to shoe-horn logical const on to D2's binary const is just not going to work. – Ywis

@Peter a caching determinant function is not const because it modifies the object. It might be logical const, but that is something differnt. As to a library logical const: It should be possible to construct a proxy object type that caches whateve methods you want. -- Also could you please use the @username feature? blog.stackoverflow.com/2010/01/new-improved-comments-with-reply It makes it way easier for people to find your responses. – Burrill

Answer 3

Being a pragmatic language, D has the ability to cast away const if you really need to. I think the following should work:

class M {
  bool set;
  real val;

  real D() const {
    if(!set) {
      M m = cast(M)this;
      m.val = this.some_fn();
      m.set = true;
    }
    return this.val;
  }
}

Burrill

If I remember the spec, the result of the above is explicitly undefined. The problem is that it might be immutable in read-only memory. The reason it's undefined is that it could very well crash your program. Edit: <digitalmars.com/d/2.0/const3.html> explicitly states that casting away const or immutable is possible but invalid. – Ywis

Yes it is undefined because under any given situation it could be reasonable to modify or in read-only memory. However, if you can verify yourself that the data will be mutable i.e. you won't have immutable references to your class and be calling D(), then it will not be an issue. – Cavie

The issue about read only memory can be worked around by making the type impossible to construct at compile time. That would force all instances in to read/write memory and there you go. Alternately, make the compile time construction path pre-compute the value to be cached at which point the code will never cast away const on all the instance that end up in read only memory. – Burrill

Pathological case: manually allocate the object to a fresh page of memory, then tell the OS to write-protect the page. Ta-da: runtime ROM. :D – Ywis

@DK: At that point you are well beyond what the type system ever claimed to support. – Burrill

Answer 4

I highly suggest BCS's answer as it is simple and safe as long as an immutable/const Matrix is not created.

Another option that helps to make even immutable/const objects remain valid is this Mutable Template. Or at least that is the intent. There are comments about the concerns.

With this template, it is required that modification is done to a referenced type and not a value in a const function. This means pointers are used and require space to be allocated for each Matrix. This also makes it harder to create an immutable/const Matrix that won't segfault, maybe there is a way to do it nicely but I only know of one for classes.

struct Matrix
{
    double determinant() const
    {
        if ( *m_dirty )
        {
            *m_determinant = 646.363; /* expensive calculation */;
            *m_dirty = false;
        }
        return *m_determinant;
    }

    void set(int i, int j, double x) { *m_dirty = true; }

    Mutable!(bool*) m_dirty;
    Mutable!(double*) m_determinant;
};

Cavie

Answer 5

To mimic logical const from C++ in D you can use inheritance for classes:

class ConstMatrix
{
public:
    double det() { // not marked as const!
        /* ... caching code ... */
    }
    /* ... the rest of the logically const interface ... */
}

class Matrix : ConstMatrix
{
public:
    void set( int row, int col, double val ) {
        /* ... */
    }
    /* ... the non-logically const interface ... */
}

In the ConstMatrix class implementation you won't have any compiler checks unless you put const qualifiers onto the function signatures. However, you will get const correctness for client code, if you use ConstMatrix for logically constant matrices.

For structs you can use the alias technique to accomplish the same:

struct ConstMatrix 
{
    /* logically const bla bla blub */
}

struct Matrix
{
public:
    alias m this;

    /* non-const bla bla blub */
private:
    ConstMatrix m;
}

For class types you can build other classes or structs with logical const correctness in the following way:

class ConstBiggerClass
{
private:
    ConstMatrix m;
}

class BiggerClass : ConstBiggerClass
{
private:
    Matrix m;
}

This way the compiler will check const correctness for you. However, you'll need an extra data member. For class type members in class types, an alternative would be to provide a member function which returns the data member with the right constness:

class ConstBiggerClass
{
public:
    void someLogicallyConstFunction( /*...*/ ) { /* ... */ }
protected:
    abstract ConstMatrix getMatrix();
}

class BiggerClass : ConstBiggerClass
{
public:
    void someMutableFunction( /*...*/ ) { /*...*/ }
protected:
    Matrix getMatrix() { return m; }
private:
    Matrix m;
}

Dyer