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

[Kevin Reid]

On May 22, 2006, at 0:40, Mark S. Miller wrote:
> 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 ...

I like "intern". It is almost exactly the appropriate concept.

It is not quite a perfect fit, in that interning usually incorporates  
the construction of an object.

Log from #erights:
[07:08] kpreid: Riastradh: ... MarkM suggests ... calling the non- 
transparent kind of memoization "interning"
[07:08] kpreid: I agree that it matches my concept of interning; does  
it yours? is it an acceptable generalization?
[12:17] Riastradh: kpreid, hmmm.  I think I'd disagree about using  
interning here -- interning doesn't imply anything about mutability.
[13:00] Riastradh: kpreid, also, I'd say `interning' only if it  
intrinsically has to do with the construction of new objects in the  
first place.
[13:03] Riastradh: No, I still think memoization is the best term  
regardless of whether the condition is DeepFrozen or DeepPassByCopy.
<http://meme.b9.com/cview.html?channel=erights&date=060522>


However, it's the best name we have so far. For now, it will be in E- 
on-CL under that name, but as a mode of 'memoize' rather than a  
separate import name.

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

I'd noticed this property but not the similarity.

The inability to keep a limited-size cache is one possible reason one  
might not want "intern"'s behavior.

-- 
Kevin Reid                            <http://homepage.mac.com/kpreid/>