Tablas hash en prolog

Question

Estaba resolviendo un acertijo en prolog el otro día y me di cuenta de que si utilizaba otro lenguaje de programación, habría utilizado una tabla/diccionario hash, pero hasta donde sé, esto no es realmente posible en prolog.

Así que mi primera pregunta es: ¿hay algún prólogo que admita una estructura de datos tipo diccionario con las características de rendimiento de una tabla hash?

En segundo lugar, se me ocurrió que la mayoría de los prólogos usan una tabla hash para almacenar predicados, podría escribir un predicado envoltorio para afirmar y retractar hechos, creando una interfaz de diccionario que aprovecharía la tabla hash subyacente de predicados. Pero, ¿obtendré las características de rendimiento de una tabla hash, o la interfaz agregará gastos generales que reducirían el rendimiento?

Answer 1

simplemente descubrí que:

SWI-Prolog versión 7 introduce predice como un objeto abstracto con una sintaxis moderna de hormigón y la notación funcional para acceder a los miembros y así como las funciones de acceso definidos por el usuario.

La sintaxis es la siguiente:

Tag{Key1:Value1, Key2:Value2, ...}

Ver Dicts: structures with named arguments para los detalles.

Tenga en cuenta que:

• These are first-class citizens of the language
• Semántica de unificación entre dicts puede cambiar en el futuro
• El operador ./2, anteriormente utilizado por contra-ción, se ha reutilizado para tener acceso a los miembros dict a través de expresiones como un point{x:1,y:2}.x
• Dicts can be destructively modified pero esto no es recomendable, por ser "no lógico", por no hablar de no funcional.
• The current underlying implementation es "un término compuesto usando el funtor dict. El primer argumento es la etiqueta. Los argumentos restantes crear una matriz de pares de valores clave ordenados" así

Prolog alcanza a los muchos idiomas con una tipo de datos "mapa" que han surgido durante los últimos 10 años (por ejemplo, maps in Clojure).

Answer 2

Algunos entornos Prolog tienen Asociación enumera, que se puede utilizar para crear y editar un diccionario:

• SWI-Prolog
• SICStus Prolog

Editar:

Usted podría ser capaz de obtener bett er el rendimiento mediante la implementación de los predicados en idiomas extranjeros , por ejemplo:

• SWI-Prolog Java o C++
• GNU Prolog C interface
• SICStus C, C++ y Java/.Net.

Answer 3

Yo no soy un tipo Prolog (sólo un observador externo), pero encontré esto:

http://www.sics.se/sicstus/docs/4.0.7/html/sicstus/lib_002davl.html

cuando buscaba "Prolog mapa finita árboles equilibrados". Dice que es una implementación alternativa de listas de asociaciones.

(Por qué pensé en esto: en Haskell, un lenguaje puramente funcional, en lugar de listas de asociaciones o tablas hash, es común usar árboles para diccionarios (persistentes) o mapas finitos. Las búsquedas también son O (log (N)). Consulte Data.Map para obtener algunas referencias sobre la implementación de mapas con árboles balanceados.)

Answer 4

En SICStus Prolog, utilice las bibliotecas assoc o avl.

Answer 5

Los siguientes comentarios frente a su pregunta en un orden que va aproximadamente desde "más específica" a "más general".

En primer lugar, hacer frente a su comentario concreto:

habría hecho uso de una tabla hash/diccionario, pero por lo que sé que esto no es realmente posible en Prolog.

Todas las implementaciones de Prolog serias le permiten modificar destructivamente los términos de Prolog, usando por ejemplo setarg/3. Usando arg/3 y setarg/3 le da O (1) el acceso a cada argumento de un término, que es suficiente para implementar una tabla hash exactamente como en otros idiomas, asumiendo que su sistema no pone límites arbitrarios en los términos de arities.

No es una buena idea hacerlo usted mismo, ya que debe tener en cuenta la copia inesperada y el uso compartido de términos en todos los términos. En cambio, confíe en las bibliotecas para hacerlo.

¿Qué bibliotecas? Lo segundo es lo que otros han escrito: En lugar de hash bibliotecas, utilice bibliotecas basadas en árboles como library(assoc), library(avl) etc. Estos no son tan eficientes como los hashes en el caso promedio, pero:

• que a menudo son eficientes
suficiente
• escalan muy predecible: las operaciones más importantes son siempre en O (log (n)).

También como otros han escrito, modificaciones destructivas son incompatibles con la programación lógica, y las bibliotecas de árboles tienen la enorme ventaja de que pueden ser implementadas en ISO   Prolog y de una manerapura   con asintóticamente eficiencia óptima.

Por último, las extensiones de diccionario de SWI-Prolog son no conformes ISO, ni siquiera sintácticamente, y por lo tanto no conformes portátil para sistemas Prolog! Consulte comments de Ulrich Neumerkel para saber cómo se puede agregar un punto infijo de una manera conforme a ISO.