A poorly remembered result of a multi-parameter function in OCaml

Question

I am looking for a way to remember the results of an OCaml f function that takes two parameters (or more, in general). Also (and this is the hard part), I want the card underlying this process to completely forget the result if either of the values ​​for these two parameters is garbage collection.

For a function that takes exactly one argument, this can be done using the Weak module and its Make functor in a simple way. To generalize this to what memoize functions of higher clarity can do, the naive solution is to create a weak map from tuples of values ​​for the result values. But this will not work correctly with respect to garbage collection, since a tuple of values ​​exists only within the framework of the memoization function, and not for client code that calls f . In fact, a weak link will be to a tuple that will collect garbage immediately after memoization (in the worst case).

Is there a way to do this without re-implementing Weak.Make ?

Hash-consing is orthogonal to my requirements and, in fact, is not very desirable for my values.

Thanks!

Answer 1

Instead of indexing by tuples, you can have a tree structure. You will have one weak table indexed by the first parameter of the function whose records are secondary weak tables. Secondary tables will be indexed by the second parameter of the function and contain memoized results. This structure will forget the results of the memoized function as soon as the parameter of the GCed function. However, the secondary tables themselves will remain until the first parameter of the function is active. Depending on the size of the results of your function and the distribution of the various first parameters, this may be a reasonable compromise.

I have not tested this either. It also seems pretty obvious.

Answer 2

One idea is to do your own garbage collection.

For simplicity, suppose that all arguments are of the same type k .

In addition to the main weak table containing memoized results with the key k * k , create a secondary weak table containing single arguments of type k . The idea is to check the main table from time to time and remove the bindings that are no longer needed. This is done by looking for arguments in the secondary table; then if any of them are gone, you will remove the binding from the main table.

(Disclaimer: I have not tested this, it may not work, or there may be better solutions)

Answer 3

I know this is an old question, but my colleagues recently developed an incremental computing library called Adapton that can handle this functionality. Here you can find the code here . You probably want to use the LazySABidi functor (others for benchmarking). You can see examples of using the library in the Applications folder. Let me know if you have more questions.