Implementation

In order to implement the algorithms efficiently in Prolog, it is important to use efficient data-structures. In particular, we use an implementation of (non-updatable) arrays based on the N+K trees of [16, pp.142-145] with N=95 and K=32. On top of this datastructure, a hash array is implemented using the SICStus library predicate term_hash/4 which constructs a key for a given term. In such hashes, a value in the underlying array is a partial list of key-value pairs; thus collisions are resolved by chaining. This provides efficient access in practice, although such arrays are quite memory-intensive: care must be taken to ensure that the deterministic algorithms indeed are implemented without introducing choice-points during runtime.