Logical const

[so]

> 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/