Implementing Sets with Hash Tables in Declarative Languages

Programming languages using set as the core data collection have two interesting features: first lots of people have experience, from many different fields, in representing problems as relations between sets and then sets are a suit structure for exploiting data parallelism. This paper presents a technique for implementing sets in a Logic Programming System. It is based on hash-tables and is aimed to a Subset Abstract Machine for the Subset Equational Language. First a brief overview about the SEL language, the SAM and the general architecture of a Connection Machine System, chosen for a parallel implementation of the abstract machine, is presented, then dynamic hashing and its use in the sequential SAM will be detailed. Eventually the extension of hashing to the parallel implementation of SAM is outlined and some conclusions are drawn.