Hash tables in prolog

Question

I was solving a puzzle in prolog the other day and realized that were I using another programming language, I would have made use of a hash table/dictionary, but as far as I know this isn't really possible in prolog.

So my first question is are there any prologs that support a dictionary-like data structure with the performance characteristics of a hash table?

Secondly, it occurred to me that since most prologs use a hash table to store predicates, I could write a wrapper predicate to assert and retract facts, creating a dictionary interface which would leverage the underlying hash table of predicates. But would I get the performance characteristics of a hash table, or would the the interface add overheads that would reduce the performance?

Answer 1

I just found out that:

SWI-Prolog version 7 introduces dicts as an abstract object with a concrete modern syntax and functional notation for accessing members and as well as access functions defined by the user.

The syntax is as follows:

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

See Dicts: structures with named arguments for the details.

Note that :

• These are first-class citizens of the language
• Semantics of unification between dicts may change in the future
• The ./2 operator, formerly used for cons-ing, has been repurposed to access dict members via an expressions like point{x:1,y:2}.x
• Dicts can be destructively modified but this is not recommended, being "non-logical", not to mention non-functional.
• The current underlying implementation is "a compound term using the functor dict. The first argument is the tag. The remaining arguments create an array of sorted key-value pairs"

The time-complexity of operations of the present (2019) implementation is given in the SWI Prolog manual under "5.4.5: Implementation Notes about dicts":

Dicts are currently represented as a compound term using the functor dict. The first argument is the tag. The remaining arguments create an array of sorted key-value pairs. This representation is compact and guarantees good locality. Lookup is order log( N ), while adding values, deleting values and merging with other dicts has order N. The main disadvantage is that changing values in large dicts is costly, both in terms of memory and time.

Future versions may share keys in a separate structure or use a binary trees to allow for cheaper updates. One of the issues is that the representation must either be kept cannonical or unification must be extended to compensate for alternate representations.

And also

The SWI-Prolog dicts are built-ins and an SWI-Prolog extension. An alternative is library(assoc), providing maps based on AVL trees via a library (thus available in other implementations, possibly).

Answer 2

Some Prolog environments have Association lists, which can be used to create and edit a dictionary:

• SWI-Prolog
• SICStus Prolog

Edit:

You might be able to get better performance by implementing predicates in foreign languages, for example:

• SWI-Prolog Java or C++
• GNU Prolog C interface
• SICStus C, C++ and Java/.Net.

Answer 3

I'm not a Prolog guy (just an outside observer) but I found this:

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

when I searched for "prolog finite map balanced trees". It says it's an alternative implementation of association lists.

(Why I thought of this: In Haskell, a purely functional language, instead of association lists or hash tables, it is common to use trees for (persistent) dictionaries or finite maps. Lookups are also O(log(N)). See Data.Map for some references on implementing maps with balanced trees.)