www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Pure memoization, and more

reply "bearophile" <bearophileHUGS lycos.com> writes:
Threads like "Why D const is annoying" show that there is desire 
for logical immutability, for pure memoization, etc. I'd like the 
memoization of a pure function to be pure still.

This is a closely related group of problems (including "pointer 
equality, external pointers, finalizers, and weak pointers") 
surely present in functional languages too, so (with a bit of 
help from a person of the "Lambda The Ultimate" blog) I have 
found two papers that show some ideas and solutions.

"Stretching the storage manager: weak pointers and stable names 
in Haskell" (1999), by Simon Peyton Jones, Simon Marlow, and 
Conal Elliot:
http://community.haskell.org/~simonmar/papers/weak.pdf
http://research.microsoft.com/apps/pubs/default.aspx?id=67497

"Observable sharing for functional circuit description" (1999), 
by Koen Claessen, David Sands (this looks less related, but the 
authors face the same class of problems):
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.4053

Probably there are other papers on this topic, with solutions 
that don't require breaking purity or immutability in user code.

Bye,
bearophile
May 03 2012
parent reply "David Nadlinger" <see klickverbot.at> writes:
On Thursday, 3 May 2012 at 15:50:36 UTC, bearophile wrote:
 Threads like "Why D const is annoying" show that there is 
 desire for logical immutability, for pure memoization, etc. I'd 
 like the memoization of a pure function to be pure still.

If you are performing a »logically pure« operation which can't be proven to be so due to the limits of the type system, you can always just use a cast in the implementation. David
May 03 2012
parent "bearophile" <bearophileHUGS lycos.com> writes:
David Nadlinger:

 If you are performing a »logically pure« operation which 
 can't be proven to be so due to the limits of the type system, 
 you can always just use a cast in the implementation.

casts are dangerous, better to avoid them where possible. Those papers try to avoid unsafe casts in user code and libraries. Bye, bearophile
May 03 2012