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
next sibling parent "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
prev sibling 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