Memoization cache contract 2026-10-13
For a terminating pure function, a reusable entry must record its correct completed result, and equal memoization keys must imply equal results throughout the entry's memoization cache lifetime. Reusing that result must also preserve the behavior callers require. These conditions separate correctness from speed: a complete key can be correct even if it rarely repeats.
A procedure using deterministic computation can still have a required side effect. If a procedure returns and appends an audit record on every call, serving the second call from a table preserves the numerical answer but skips the second record. Likewise, if each call promises a fresh mutable list, returning the same stored mutable list changes observable sharing and allows a caller to damage later answers. Plain result reuse is unsuitable for those contracts.[ref]
functools — Higher-order functions and operations on callable objects (Python 3.14 documentation). Python documentation, functools.lru_cache: paragraph warning against functions with side effects, distinct mutable results, or impure time/random results
Completion matters for recursion. Suppose computing key needs key , and computing needs . A table containing only completed answers has no answer to return for the second ; remembering completed values does not make this directed cycle terminate. Marking a key
ACTIVE before descending detects re-entry, as in spreadsheet dependency evaluation, but detection is not a solution of the circular equations. If computation fails, clear its active mark and do not publish an unfinished value. The example using Fibonacci numbers avoids this issue through a strictly decreasing argument.The call counts above assume sequential execution and no eviction. Concurrent requests for an absent key can both begin evaluation before either publishes its result; keeping a table coherent alone does not ensure one body execution per key.[ref]
functools — Higher-order functions and operations on callable objects (Python 3.14 documentation). Python documentation, functools.cache and functools.lru_cache: thread-safe cache updates can still allow repeated evaluation before completion
Memoization cache lifetime 2026-10-14
A memoization cache lifetime is the interval over which retained entries are available and valid. One table per top-level request shares recursive subproblems within that request; keeping a table between requests also allows the warm and incremental examples. Clearing it loses those savings. Evicting a correct answer can preserve correctness for a terminating pure function, while forcing recomputation; changing an input without invalidating an obsolete answer can break correctness.
Specify who owns the table, when context changes invalidate it, and how long keys and results occupy computer memory. In a concrete implementation, retained references can keep arguments and answers alive until removal or clearing.[ref]
functools — Higher-order functions and operations on callable objects (Python 3.14 documentation). Python documentation, functools.lru_cache: cache_clear and retention of argument and return-value references until eviction or clearing
The memoization promise is conditional reuse of valid completed answers, not an automatic guarantee of freshness, termination or bounded computer memory.// Target: computer-science.bigb