Risultato di memoizing debole della funzione multiparametro in OCaml

Question

Sto cercando un modo per memoizzare i risultati di una funzione OCaml f che richiede due parametri (o più, in generale). Inoltre (e questa è la parte difficile), voglio che la mappa sottostante questo processo dimentichi del tutto un risultato se uno dei valori per i due parametri è garbage collection.

Per una funzione che richiede esattamente un argomento, questo può essere fatto con il modulo Weak e il suo functor Make in modo semplice. Per generalizzare questo a qualcosa che può memoizzare le funzioni di arità superiore, una soluzione ingenua è creare una mappa debole da tuple di valori a valori di risultato. Ma questo non funzionerà correttamente rispetto alla garbage collection, poiché la tupla di valori esiste solo nell'ambito della funzione di memoization, non il codice client che chiama f. In effetti, il riferimento debole sarà alla tupla, che verrà raccolta dopo la memoizzazione (nel peggiore dei casi).

C'è un modo per farlo senza reimplementare Weak.Make?

Hash-consing è ortogonale alle mie esigenze ed è, in effetti, non proprio desiderabile per i miei valori.

Grazie!

Answer 1

Invece di indicizzazione da parte tuple si potrebbe avere una struttura ad albero. Avresti una tabella debole indicizzata dal primo parametro di funzione le cui voci sono tabelle secondarie deboli. Le tabelle secondarie dovrebbero essere indicizzate dal secondo parametro di funzione e contenere i risultati memorizzati. Questa struttura dimenticherà i risultati della funzione memoizzata non appena il parametro di funzione è GCed. Tuttavia, le tabelle secondarie verranno mantenute fino a quando il primo parametro di funzione è attivo. A seconda delle dimensioni dei risultati della tua funzione e della distribuzione di diversi primi parametri, questo potrebbe essere un compromesso ragionevole.

Non l'ho ancora provato. Sembra anche abbastanza ovvio.

Answer 2

Un'idea è quella di eseguire la propria raccolta dei rifiuti.

Per semplicità, supponiamo che tutti gli argomenti abbiano lo stesso tipo k.

Oltre alla tabella debole principale contenente i risultati memoizzati con k * k, creare una tabella secondaria secondaria contenente argomenti singoli di tipo k. L'idea è di scansionare il tavolo principale una volta ogni tanto e rimuovere i binding che non sono più ricercati. Questo viene fatto cercando gli argomenti nella tabella secondaria; quindi se qualcuno di loro è andato rimuovi la rilegatura dalla tabella principale.

(Disclaimer: non ho ancora testato questo, ma non può funzionare o ci può essere soluzioni migliori)

Answer 3

So che questa è una vecchia domanda, ma i miei colleghi hanno recentemente sviluppato una libreria di calcolo incrementale, chiamata Adapton, in grado di gestire questa funzionalità. È possibile trovare il codice here. Probabilmente vuoi usare il funtore LazySABidi (gli altri sono per il benchmarking). Puoi cercare nella cartella Applicazioni esempi su come usare la libreria. Fammi sapere se hai altre domande.