Weak-Memoizing Ergebnis der Multi-Parameter-Funktion in OCaml

Question

Ich bin auf der Suche nach einer Möglichkeit, die Ergebnisse einer OCaml-Funktion f Memo, die zwei Parameter (oder mehr, im Allgemeinen). Zusätzlich (und das ist der schwierige Teil) möchte ich, dass die diesem Prozess zugrunde liegende Map ein Ergebnis ganz vergisst, wenn einer der beiden Werte für die beiden Parameter "Garbage Collected" ist.

Für eine Funktion, die genau ein Argument benötigt, kann dies mit dem Modul und seinem Make Funktor auf einfache Art und Weise durchgeführt werden. Um dies auf etwas zu verallgemeinern, das höherwertige Funktionen beschreiben kann, besteht eine naive Lösung darin, eine schwache Abbildung von Tupeln von Werten zu Ergebniswerten zu erstellen. Dies funktioniert jedoch nicht ordnungsgemäß in Bezug auf die Garbage Collection, da das Tupel der Werte nur innerhalb des Bereichs der Memo-Funktion existiert, nicht der Client-Code, der f aufruft. In der Tat wird die schwache Referenz auf das Tupel sein, das direkt nach der Memo-Erfassung (im schlimmsten Fall) Müll gesammelt wird.

Gibt es eine Möglichkeit, dies zu tun, ohne Weak.Make erneut zu implementieren?

Hash-Consing ist orthogonal zu meinen Anforderungen und ist in der Tat nicht wirklich wünschenswert für meine Werte.

Danke!

Answer 1

Statt Indizierung durch Tupeln Sie eine Baumstruktur haben könnte. Sie hätten eine schwache Tabelle, die durch den ersten Funktionsparameter indiziert wird, dessen Einträge sekundäre, schwache Tabellen sind. Die sekundären Tabellen würden durch den zweiten Funktionsparameter indiziert und enthielten die protokollierten Ergebnisse. Diese Struktur wird die protokollierten Funktionsergebnisse vergessen, sobald einer der beiden Funktionsparameter auf GCed gesetzt ist. Die sekundären Tabellen selbst bleiben jedoch erhalten, solange der erste Funktionsparameter aktiv ist. Abhängig von den Größen Ihrer Funktionsergebnisse und der Verteilung der verschiedenen ersten Parameter könnte dies ein vernünftiger Kompromiss sein.

Ich habe dies auch nicht getestet. Auch es scheint ziemlich offensichtlich.

Answer 2

Eine Idee ist es, Ihre eigene Garbage Collection durchzuführen.

Der Einfachheit halber nehmen wir an, dass alle Argumente den gleichen Typ haben k.

Erstellen Sie eine sekundäre schwache Tabelle, die einzelne Argumente des Typen k enthält, neben der schwachen Haupttabelle, die die Memo-Ergebnisse enthält, die von k * k getastet werden. Die Idee ist, die Haupttabelle ab und zu zu durchsuchen und die nicht mehr gewünschten Bindungen zu entfernen. Dies geschieht durch Nachschlagen der Argumente in der Sekundärtabelle; Wenn einer von ihnen weg ist, entfernst du die Bindung aus der Haupttabelle.

(Disclaimer: Ich habe nicht getestet, es kann nicht funktionieren, oder es können bessere Lösungen sein)

Answer 3

Ich weiß, dass dies eine alte Frage ist, aber meine Kollegen haben kürzlich eine inkrementelle Berechnungsbibliothek namens Adapton entwickelt, die mit dieser Funktionalität umgehen kann. Sie können den Code here finden. Wahrscheinlich möchten Sie den LazySABidi-Funktor verwenden (die anderen dienen zum Benchmarking). Sie können im Ordner Anwendungen nach Beispielen für die Verwendung der Bibliothek suchen. Lass es mich wissen, wenn du weitere Fragen hast.