Logical const

[bearophile]

Peter Alexander:

> So, without logical const, how are D users supposed to provide lazy
> evaluation and memoization in their interfaces, given that the interface
> should *seem* const, e.g.
> 
> class Matrix
> {
>    double getDeterminant() const { /* expensive calculation */ }
> }
> 
> If it turns out that getDeterminant is called often with the raw matrix
> data remaining unchanged, how can we add caching to this class without
> rewriting the const-ness of all code that touches it?
> 
> And how do we write generic code when it's practically impossible to
> determine const-ness from a glance? e.g. getDeterminant looks like it
> should be const, but wouldn't be if it had caching, so writing generic
> code that uses getDeterminant would be very difficult.

I am not expert about this, so take this cum grano salis. This topic is a mess, but I have some ideas:

1) A type system a cost, because it gives rigidity and troubles, but it gives you something back. I I think D const/immutable/pure give you enough back only if you look at them with the eyes of functional programming. This means that their full potential (and return of investiment) will be visible only when a D compiler/implementation will manage multicores efficiently, revealing one of the true advantages of functional programming. It will take some years at best.


2) Time ago Andrei has shown me articles that explain what's good to put inside a class/struct and what's good to leave outside as free module-level function, in a C++/D-like language. In this case I think the determinant() is better to be free, because it's a generic algorithm that often doesn't need to know how the matrix is implemented. So if you leave it outside the class, you may use it (in theory) on other implementations of matrices too. So this is a possibly good design:

class Matrix {
    // ...
}

pure double determinant(M)(const M mat) if (IsMatrix!M) {
    // ...
}

Or maybe even:

pure double determinant(M)(const M mat) if (IsSquareMatrix!M) {
    // ...
}


Then you want to cache determinant() because it performs a long computation. One way to solve it is to use a simple memoize(), or implement determinant() as opCall of a little struct that performs the memoization. Memoization requires lot of memory and it needs a bit of time to compare the input data with the memoized keys.

If you don't want to waste too much memory in caching data for the memoization, then you may create an immutable matrix, and then compute its determinant only once and store it somewhere... The memoization may be smart and store the determinant of parts of the input data, and don't compute it again if only part of the input changes.

The memoization saves you most of the re-computation time, but it costs you some memory. If you don't want to pay both the re-computation time and the memory costs used by the memoization, then you need to not use const/immutable/pure (as done in Python) and keep the semantics of the code in your head instead of encoded in the type system (because as I have said D2 type system is designed for functional programming, and C++-style const is not good enough for functional programming). Otherwise you have to punch holes in the type system, and cast away constness where you want, but this is a dangerous solution.


3) If you look at your program with functional programming eyes, in Haskell the language solves your problem with lazyness managed almost transparently by the language (so computations are performed just in time), automatic memoization (so it often computes your determinant only once), and immutability (so you have an immutable view of the matrix, even if the data structure itself that implements the matrix may be able to support a kind of "versioning", so when you want to change few of its elements it doesn't copy of the whole matrix).


4) It will be good to have some way to memoize functions in D. But currently there is no way to create a memoizing function that is pure. Function purity and transitive immutability go along in pairs, so I think D will need, as Haskell, some way to perform a pure memoization. To do this you need "logical purity" :-) A way to solve this is to add a built-in @memoize usable only on strongly pure functions. So you will have:

class Matrix {
    // ...
}

@memoize pure double determinant(M)(const M mat) if (IsMatrix!M) { // strongly pure
    // ...
}

If a built-in strongly pure @memoize is not possible or desired, then you need something like a @trusted_pure to implement it manually and hope the programmer is not doing something wrong...

Sorry for the confused answer, I am not good enough about this yet. *lights a candle for Peyton-Jones*

Bye,
bearophile