Compact serialization of Prolog terms (with catalan skeletons, cantor tupling and Gödel numberings)
Paul Tarau · Theory and Practice of Logic Programming · 2013
Abstract We describe a compact serialization algorithm mapping Prolog terms to natural numbers of bit-sizes proportional to the memory representation of the terms. The algorithm is a ‘no bit lost’ bijection, as it associates to each Prolog term a unique natural number and each natural number corresponds to a unique syntactically well-formed term. To avoid an exponential explosion resulting from bijections mapping term trees to natural numbers, we separate the symbol content and the syntactic skeleton of a term that we serialize compactly using a ranking algorithm for Catalan families. A novel algorithm for the generalized Cantor bijection between ${\mathbb{N}$ and ${\mathbb{N}$ k is used in the process of assigning polynomially bounded Gödel numberings to various data objects involved in the translation.