Wynik słabej zapamiętywania funkcji wieloparametrowej w OCaml

Question

Poszukuję sposobu na zapamiętanie wyników funkcji OCaml f, która pobiera dwa parametry (lub więcej, ogólnie). Ponadto (i to jest trudna część), chcę, aby mapa leżąca u podstaw tego procesu całkowicie zapomniała o wyniku, jeśli jedna z wartości dwóch parametrów jest zbierana.

Dla funkcji, która przyjmuje dokładnie jeden argument, można to zrobić za pomocą modułu Weak i jego funktora Make w prosty sposób. Aby uogólnić to na coś, co może zapamiętać funkcje o wyższej sile, naiwnym rozwiązaniem jest utworzenie słabej mapy z krotek wartości do wartości wynikowych. Ale to nie zadziała poprawnie w odniesieniu do zbierania śmieci, ponieważ krotka wartość istnieje tylko w zakresie funkcji zapamiętywania, a nie kod klienta, który wywołuje f. W rzeczywistości słabym odniesieniem będzie krotka, która będzie zbiorem śmieci zaraz po zapamiętywaniu (w najgorszym przypadku).

Czy istnieje sposób, aby to zrobić bez ponownego wdrażania Weak.Make?

Hash-consing jest ortogonalny do moich wymagań i tak naprawdę nie jest tak naprawdę pożądany dla moich wartości.

Dzięki!

Answer 1

Zamiast indeksowania przez krotki można mieć strukturę drzewa. Będziesz miał jedną słabą tabelę indeksowaną przez pierwszy parametr funkcji, którego wpisy są drugorzędnymi słabymi tabelami. Tabele pomocnicze zostaną zindeksowane przez drugi parametr funkcji i będą zawierać wyniki zapamiętane. Ta struktura zapomni zapamiętane wyniki funkcji, gdy tylko parametr funkcji zostanie ustawiony na GCed. Jednak same tabele wtórne zostaną zachowane, o ile pierwszy parametr funkcji jest aktywny. W zależności od wielkości wyników funkcji i rozkładu różnych pierwszych parametrów może to być rozsądnym kompromisem.

Tego też nie przetestowałem. Również wydaje się to dość oczywiste.

Answer 2

Jednym z pomysłów jest wykonanie własnego zbioru śmieci.

Dla uproszczenia załóżmy, że wszystkie argumenty mają ten sam typ: k.

Poza główną słabą tabelą zawierającą wyniki z pamięci z kluczem oznaczone k * k, utwórz dodatkową słabą tabelę zawierającą pojedyncze argumenty typu k. Chodzi o to, aby od czasu do czasu przeskanować główny stół i usunąć wiązania, które nie są już potrzebne. Odbywa się to poprzez wyszukiwanie argumentów w tabeli dodatkowej; wtedy jeśli któryś z nich zniknie, usuniesz powiązanie z głównego stołu.

(Zastrzeżenie: Nie testowałem tego, ale może nie działać lub mogą istnieć lepsze rozwiązania)

Answer 3

Wiem, że to stare pytanie, ale moi koledzy opracowali ostatnio dodatkową bibliotekę obliczeniową o nazwie Adapton, która może obsłużyć tę funkcję. Możesz znaleźć kod here. Prawdopodobnie chcesz użyć funktora LazySABidi (pozostałe służą do testowania wydajności). Możesz zajrzeć do folderu Aplikacje, aby zapoznać się z przykładami korzystania z biblioteki. Daj mi znać, jeśli masz więcej pytań.