www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Re: Logical const

reply bearophile <bearophileHUGS lycos.com> writes:
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
Nov 28 2010
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
bearophile wrote:

 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.




While const/etc. has many advantages in concurrent programming, your statement 
vastly undervalues its primary utility. That utility is it provides the user 
with a powerful tool with which to understand and reason about his programs.

C++ const does not have either of those utilities. C++ const is an unenforcable 
convention, and offers no guarantees. Logical constness is a convention, not 
anything that is statically checkable in C++.

To emphasize, logical constness is simply not a feature of the C++ type system.
Nov 28 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Walter Bright:


 While const/etc. has many advantages in concurrent programming, your statement 
 vastly undervalues its primary utility. That utility is it provides the user 
 with a powerful tool with which to understand and reason about his programs.



I see. I haven't written large programs that use transitive const/immutable
yet, so I have to accept your word :-) Thank you for your answer.

Bye,
bearophile
Nov 28 2010
prev sibling parent reply so <so so.do> writes:
 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/
Nov 29 2010
parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 30/11/10 6:21 AM, so wrote:

 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.



This may be true for this particular case, but has no bearing on the 
discussion in general.
Nov 30 2010