Memoization of Mutable Objects

Memoization is an optimization that consists of caching the results of functions to avoid recomputations of repeated calls. This technique is natively built into some programming languages and implemented as a design pattern in others. Yet, in spite of its popularity, memoization has limitations. In particular, mutable objects cannot be cached, because if a memoized object is mutated, then this modification might have an effect on all the memoized instances of it. This paper presents a technique to address this constraint by using shared-ownership pointers to distinguish between memoized and non-memoized objects. If a memoized object is modified, then this object is removed from the memoization table, and all its aliases are updated through the shared pointer. We have implemented this technique into the runtime environment of the Hush programming language. Our implementation incurs no penalty on non-memoized objects and adds minimum overhead to cached ones. To demonstrate the correctness of this approach, we have formalized it in the Alloy modeling language. This specification certifies that a memoized object remains so unless it is modified.