2012-04-07 1 views
7

Estoy buscando una forma de memorizar los resultados de una función OCaml f que toma dos parámetros (o más, en general). Además (y esta es la parte difícil), quiero que el mapa subyacente de este proceso olvide por completo un resultado si cualquiera de los valores de los dos parámetros es basura.Resultado débil de la función de multiparamétrico en OCaml

Para una función que toma exactamente un argumento, esto se puede hacer con el módulo Weak y su funcionador Make de una manera directa. Para generalizar esto a algo que pueda memorizar funciones de mayor aridad, una solución ingenua es crear un mapa débil a partir de tuplas de valores para generar valores. Pero esto no funcionará correctamente con respecto a la recolección de basura, ya que la tupla de valores solo existe dentro del alcance de la función de memorización, no del código de cliente que llama al f. De hecho, la referencia débil será para la tupla, que será recogida de basura inmediatamente después de la memorización (en el peor de los casos).

¿Hay alguna manera de hacerlo sin volver a implementar Weak.Make?

El hash-consing es ortogonal a mis requisitos y, de hecho, no es realmente deseable para mis valores.

Gracias!

Respuesta

3

En lugar de la indexación de tuplas que podría tener una estructura de árbol. Tendría una tabla débil indexada por el primer parámetro de función cuyas entradas son tablas débiles secundarias. Las tablas secundarias serían indexadas por el segundo parámetro de función y contendrían los resultados memorizados. Esta estructura olvidará los resultados de la función memorizada tan pronto como cualquiera de los parámetros de la función sea GCed. Sin embargo, las tablas secundarias se conservarán siempre que el primer parámetro de función esté activo. Dependiendo de los tamaños de los resultados de su función y la distribución de los primeros parámetros diferentes, esto podría ser una compensación razonable.

No he probado esto, tampoco. También parece razonablemente obvio.

+0

Puedo ver cómo la recolección de basura del primer valor del parámetro daría como resultado la liberación de la tabla correspondiente para el segundo parámetro.Sin embargo, GCing un valor en una tabla para el segundo parámetro no hace nada para su padre (si se usa el módulo 'Débil'), incluso si el mapa resultante está vacío. Por supuesto, esto se puede hacer escaneando activamente el contenido del mapa y eliminando cualquier primera clave de parámetro que se asigne a tablas vacías. – Nikos

+0

Derecha, como dije, la tabla secundaria no se recogerá hasta que se libere el primer parámetro. Pero el valor de retorno memorado se recolectaría (me parece). –

3

Una idea es realizar su propia recolección de basura.

Para simplificar, supongamos que todos los argumentos tienen el mismo tipo k.

Además de la tabla débil principal que contiene los resultados memorizados codificados por k * k, cree una tabla débil secundaria que contenga argumentos únicos del tipo k. La idea es escanear la tabla principal de vez en cuando y eliminar los enlaces que ya no se desean. Esto se hace buscando los argumentos en la tabla secundaria; luego, si alguno de ellos se va, quita el enlace de la tabla principal.

(Negación: No he probado esto, ya que puede no funcionar o puede haber mejores soluciones)

+0

Buen punto. Quizás solo se necesita una tabla, una que tenga tuplas de referencias débiles como claves y que sea basura personalizada recopilada de vez en cuando siempre que desaparezca cualquier referencia débil en la tupla de la clave. ¿Se puede hacer esto a través de finalizadores? – Nikos

1

Sé que esta es una pregunta antigua, pero mis colegas han desarrollado recientemente una biblioteca de cálculo incremental, llamada Adapton, que puede manejar esta funcionalidad. Puede encontrar el código here. Probablemente desee utilizar el funcionador LazySABidi (los demás son para evaluación comparativa). Puede buscar en la carpeta de aplicaciones ejemplos de cómo usar la biblioteca. Avísame si tienes más preguntas.

Cuestiones relacionadas