High Level Reading and Data Structure Compilation

Abstract

In [Paige89], it was shown how to simulate a set machine in real-time on a RAM that provides cursor or even only pointer access to data. The underlying assumption was that the establishment of efficient data structures would be provided by some 'client' program. In the current paper, we fill in the gap by presenting a linear-time high level reading method that translates external input in string form into data structures that facilitate such real-time simulation. The algorithm builds the data structures for a much richer type system than what appeared in [Paige94], and is powerful enough to support our reading algorithm itself in an efficient way. Consequently, it equips a high level set-theoretic language with I/O, without the loss of computational transparency.This work alleviates the burden of creating low-level data structures manually, and builds the internal pointer-based inputs required by most pointer algorithms [Ben-Amram95] from the external string representation.