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) {
// ...
}
Great that you can remember something like that, even the most C++
programmers don't know that either it is right or wrong.
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
I can understand Peter using Matrix just for example but still i have to
say.
A small vector/matrix with an extra field to memoize things perform likely
worse than their usual implementations.
That small extra field might just destroy any alignments, optimizations,
which are scarier than the computation itself.
--
Using Opera's revolutionary email client: http://www.opera.com/mail/
