Robert Paige
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.
- 1.A. M. Ben-Amram. What is a "pointer machine"? SIGACT News, 26(2):88-95, June 1995. Google Scholar
Digital Library
- 2.J. Cai, P. Facon, F. Henglein, R. Paige, and E. Schonberg. Type transformation and data structure choice. In B. Moeller, editor, Constructing Programs From Specifications, pages 126-124. North-Holland, Amsterdam, 1991.Google Scholar
- 3.J. Cai and R. Paige. Using multiset discrimination to solve language processing problems without hashing. Theoretical Computer Science, 145(1-2):189-228, July 1995. URL: http: / / cs.nyu.edu / cs / faculty / paige / papers/hash, ps. Google ScholarDigital Library
- 4.J. Cai and R. Paige. Towards increased productivity of algorithm implementation. In Proc. ACM SIGSOFT, pages 71-78, Dec. 1993. Google ScholarDigital Library
- 5.C. Consel and O. Danvy. Tutorial notes on partial evaluation. In 1993 A CM Symposium on Principles of Programming Languages, pages 493-501, 1993. Google ScholarDigital Library
- 6.W. Dowling and J. Gallier. Linear-time algorithms for testing the satisfiability of propositional Horn formulae. J. Logic Programming, 1(3):267-284, 1984.Google ScholarCross Ref
- 7.D. Goyal and R. Paige. The formal reconstruction and improvement of the linear time fragment of Willard's relational calculus subset, to appear in Proc. IFIP TC2 Working Conf. on Algorithmic Languages and Calculi, 1997. URL" http://cs, nyu.edu / phd_stu dents / deepak/lrcs, ps. Google ScholarDigital Library
- 8.R. Paige. Real-time simulation of a set machine on a RAM. In N. Janicki and W. Koczkodaj, editors, Computing and Information, volume II, pages 69- 73. Canadian Scholars' Press, Toronto, May 1989.Google Scholar
- 9.R. Paige. Efficient translation of external input in a dynamically typed language, in B. Pehrson and I. Simon, editors, Technology and Foundations - Information Processing 94, volume 1 of IFIP Transactions A-51, pages 603-608. North-Holland, Amsterdam, Sept. 1994. Conference Record of IFIP Congress 94.Google Scholar
- 10.R. Paige and F. Henglein. Mechanical translation of set theoretic problem specifications into efficient RAM code- a case study. Journal of Symbolic Computation, 4(2):207-232, Aug. 1987. Google ScholarDigital Library
- 11.R. Paige and R. Tarjan. Three efficient algorithms based on partition refinement. SIAM Journal of Computing, 16(6), Dec. 1987. Google ScholarDigital Library
- 12.C. Papadimitriou. Computational Complexity. Addison-Wesley, Reading, Massachusetts, 1994.Google Scholar
- 13.J. Rintanen. Private Communication, 1994.Google Scholar
- 14.j. Schwartz. Automatic data structure choice in a language of very high level. CACM, 18(12):722- 728, Dec 1975. Google ScholarDigital Library
- 15.J. Schwartz. Optimization of very high level languages, parts i, ii. J. of Computer Languages, 1(2, 3):161-218, 1975.Google Scholar
- 16.R. Snodgrass. The Interface Description Language. Computer Science Press, 1989. Google ScholarDigital Library
- 17.K. Snyder. The SETL2 programming language. Technical Report 490, Courant Insititute, New York University, 1990.Google Scholar
- 18.R. Tarjan. Data Structures and Network Algorithms. SIAM, 1984. Google ScholarDigital Library
- 19.R. Wilhelm and D. Maurer. Compiler Design. Addison-Wesley, Reading, Massachusetts, 1995. Google ScholarDigital Library
Index Terms
- High level reading and data structure compilation
Recommendations
Optimizing ETL by a Two-Level Data Staging Method
In data warehousing, the data from source systems are populated into a central data warehouse DW through extraction, transformation and loading ETL. The standard ETL approach usually uses sequential jobs to process the data with dependencies, such as ...
High level compilation for fine grained FPGAs
FCCM '97: Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing MachinesThe authors present an integrated tool set to generate highly optimized hardware computation blocks from a C language subset. By starting with a C language description of the algorithm, they address the problem of making FPGA processors accessible to ...
Comments