By definition, the result of a pure function should only depend on its arguments. It is this property of pure functions that gives us the capability to 'cache' the result of a function. In turn, cached results can later be re-used.
So how does a 'function' cache work?
When we are about to call a function, we first check if we already have called the same function with exactly the same arguments. If not, we add the function call (key) and its result (value) to the cache. Otherwise, we just return the result from the cache.
Such caching scheme is called 'memoization'. With memoization, naive algorithms can be turned from exponential into lineair, with the fibonacci function as the canonical example.
But naive memoization has a problem. If we don't clean entries from the cache, the cache will accumulate all function calls and their results.
To combat such indefinite growth, one can apply various eviction schemes to clean the memoization cache. For instance, we can decide to evict cached items that are 'Least Recently Used' (LRU). Unfortunately, LRU complicates the static analysis of runtime complexity. Even worse, LRU can turn the improved linear algorithm back into an exponential one.
In this post I propose a new 'eviction' scheme that is based on cached computational traces. I've coined this as: "forgetful memoization through computational traces".
Remember that, in SPREAD, every value keeps a strong reference to its origin. Here is the canonical example:
((1 ++ 2) ** (3 ++ 4)) ~> [([(1 ++ 2) ~> 3] ** [(3 ++ 4) ~> 7]) ~> [(3 ** 7) ~> 21]]
So we have the value 21 that has a back reference to its origin. When 21 becomes non-reachable, it would be a candidate for garbage collection, together (with the reference to) its origin. But if 21 is still reachable, we can potentially re-use parts of its computational trace.
Let's say that we would want to compute 3 ++ 4. Because 21 (indirectly) holds a reference to (3 ++ 4) ~> 7 we don't need to recompute: we just return the result 7.
But how do we gain access to (3 ++ 4) ~> 7? We achieve this through the use of a (very) weak reference map. In this map, both the key (the function call) and the value (the function result) are weakly referenced.
That means that a map entry will be evicted when either its key or its value is not strongly referenced. In essence, the weak map acts as an index on computational traces. By using weak references, computational traces will be evicted from the index when they are garbage collected.