[e-lang] Non-transparent memoization: is this safe?

[Mark S. Miller]

Kevin Reid wrote:
> On May 17, 2006, at 22:06, Mark S. Miller wrote:
>> Kevin Reid wrote:
>>> Is it OK to consider safe a memoizer which instead memoizes results
>>> if they are just DeepFrozen?  [...]
> (Another consequence: If the memoizer also enforces that all calls  
> and results /are/ DeepFrozen, as opposed to passing them on without  
> caching, then all calls to the memoized object are truly constant.)

I think this calls for two separate abstractions:

1) The current memoizer, where memoize(F) acts like F.

2) A memoizer-like abstraction, perhaps "intern", with both of the differences 
you suggest above:
a) it replays/interns DeepFrozen results, even if they're selfish and would 
have been different.
b) it requires the result to be DeepFrozen.

A symptom that #2 is different from #1 is that #1 can use a cache which can 
forget things, since the difference between a cache miss and a cache hit is 
unobservable. The table in #2 cannot forget. Therefore, #2 is doing something 
more like interning than like caching. Like the Java ClassLoader, the 
import__uriGetter is indeed obligated to remember, in order to provide its 
clients shared selfish identities.

-- 
Text by me above is hereby placed in the public domain

     Cheers,
     --MarkM