An embedded declarative data transformation language

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An embedded declarative data transformation language

Full text

Pdf (600 KB)

Source

International Conference on Principles and Practice of Declarative Programming archive
Proceedings of the 11th ACM SIGPLAN conference on Principles and practice of declarative programming table of contents

Coimbra, Portugal

SESSION: Logic programming table of contents

Pages 171-182

Year of Publication: 2009

ISBN:978-1-60558-568-0

Author

Paul Tarau

University of North Texas, Denton, TX, USA

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 3, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1599410.1599432 What is a DOI?

ABSTRACT

We introduce a logic programming framework for data type transformations based on isomorphisms between elementary data types (natural numbers, finite functions, sets and permutations, digraphs, DAGs, hypergraphs, etc.) and automatically derived extensions to hereditarily finite universes through ranking/unranking operations.

An embedded higher order combinator language provides any-to-any encodings automatically.

Applications range from stream iterators on combinatorial objects and uniform generation of random instances to succinct data representations and serialization of Prolog terms.

The self-contained source code of the paper, as generated from a literate Prolog program, is available at http://logic.cse.unt.edu/tarau/research/2009/pISO.zip

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alexander Abian and Samuel Lamacchia. On the consistency and independence of some set-theoretical constructs. Notre Dame Journal of Formal Logic, X1X (1): 155--158, 1978.
	2	Wilhelm Friedrich Ackermann. Die Widerspruchsfreiheit der allgemeinen Mengenlhere. Mathematische Annalen, (114): 305--315, 1937.
	3	Patrick Cégielski and Denis Richard. Decidability of the theory of the natural integers with the cantor pairing function and the successor. Theor. Comput. Sci., 257 (1-2): 51--77, 2001.
	4	Gregory J. Chaitin. A theory of program size formally identical to information theory. J. Assoc. Comput. Mach, 22: 329--340, 1975.
	5	Koen Claessen and John Hughes. Testing monadic code with quickcheck. SIGPLAN Notices, 37 (12): 47--59, 2002.
	6	Agostino Dovier, Carla Piazza, and Alberto Policriti. Comparing Expressiveness of Set Constructor Symbols. In Frontiers of Combining Systems, pages 275--289, 2000.
	7	K. Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik, 38: 173--198, 1931.
	8	Juris Hartmanis and Theodore P. Baker. On simple goedel numberings and translations. In Jacques Loeckx, editor, ICALP, volume 14 of Lecture Notes in Computer Science, pages 301--316. Springer, 1974. ISBN 3-540-06841-4. URL http://dblp.uni-trier.de/db/conf/icalp/icalp74.html#HartmanisB74.
	9	Laszlo Kalmar. On the reduction of the decision problem. first paper. ackermann prefix, a single binary predicate. The Journal of Symbolic Logic, 4 (1): 1--9, mar 1939. ISSN 0022-4812.
	10	Richard Kaye and Tin Lock Wong. On Interpretations of Arithmetic and Set Theory. Notre Dame J. Formal Logic Volume, 48 (4): 497--510, 2007.
	11	Laurence Kirby. Addition and multiplication of sets. Math. Log. Q., 53 (1): 52--65, 2007.
	12	Donald Knuth. The Art of Computer Programming, Volume 4, draft, 2006. http://www-cs-faculty.stanford.edu/~knuth/taocp.html.
	13	Donald E. Knuth. The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1997. ISBN 0201896842.
	14	John R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992. ISBN 0-262-11170-5.
	15	Ming Li and Paul Vitányi. An introduction to Kolmogorov complexity and its applications. Springer-Verlag New York, Inc., New York, NY, USA, 1993. ISBN 0-387-94053-7.
	16	Saunders Mac Lane. Categories for the Working Mathematician. Springer-Verlag, New York, NY, USA, 1998.
	17	Roberto Mantaci and Fanja Rakotondrajao. A permutations representation that knows what "eulerian" means. Discrete Mathematics & Theoretical Computer Science, 4 (2): 101--108, 2001.
	18	Conrado Martinez and Xavier Molinero. Generic algorithms for the generation of combinatorial objects. In Branislav Rovan and Peter Vojtas, editors, MFCS, volume 2747 of Lecture Notes in Computer Science, pages 572--581. Springer, 2003.
	19	John McCarthy. Recursive functions of symbolic expressions and their computation by machine, part i. Commun. ACM, 3 (4): 184--195, 1960. ISSN 0001-0782. http://doi.acm.org/10.1145/367177.367199.
	20	Erik Meijer and Graham Hutton. Bananas in Space: Extending Fold and Unfold to Exponential Types. In FPCA, pages 324--333, 1995.
	21	Jayadev Misra. Powerlist: a structure for parallel recursion. ACM Transactions on Programming Languages and Systems, 16: 1737--1767, 1994.
	22	Lawrence C. Paulson. A Concrete Final Coalgebra Theorem for ZF Set Theory. In Peter Dybjer, Bengt Nordström, and Jan M. Smith, editors, TYPES, volume 996 of Lecture Notes in Computer Science, pages 120--139. Springer, 1994. ISBN 3-540-60579-7.
	23	Jozef Pepis. Ein verfahren der mathematischen logik. The Journal of Symbolic Logic, 3 (2): 61--76, jun 1938. ISSN 0022-4812.
	24	Carla Piazza and Alberto Policriti. Ackermann Encoding, Bisimulations, and OBDDs. TPLP, 4 (5-6): 695--718, 2004.
	25	Stephen Pigeon. Contributions à la compression de données. Ph.d. thesis, Université de Montréal, Montréal, 2001.
	26	Julia Robinson. General recursive functions. Proceedings of the American Mathematical Society, 1 (6): 703--718, dec 1950. ISSN 0002-9939.
	27	Arnold L. Rosenberg. Efficient pairing functions -- and why you should care. International Journal of Foundations of Computer Science, 14 (1): 3--17, 2003.
	28	Moto-o Takahashi. A Foundation of Finite Mathematics. Publ. Res. Inst. Math. Sci., 12 (3): 577--708, 1976.
	29	Paul Tarau. Declarative Combinatorics: Isomorphisms, Hylomorphisms and Hereditarily Finite Data Types in Haskell, January 2009. http://arXiv.org/abs/0808.2953, unpublished draft, 104 pages.
	30	Paul Tarau. Declarative Combinatorics in Prolog: ShapeShifting Data Objects with Isomorphisms and Hylomorphisms. In Manuel Carro and Bart Demoen, editors, Proceedings of CICLOPS 2008, 8th International Colloquium on Implementation of Constraint and LOgic Programming Systems, pages 107--123, December 2008. URL http://clip.dia.fi.upm.es/Conferences/CICLOPS-2008/CICLOPS-2008-proceedings.pdf.
	31	Jean Vuillemin. Digital algebra and circuits. In Nachum Dershowitz, editor, Verification: Theory and Practice, volume 2772 of Lecture Notes in Computer Science, pages 733--746. Springer, 2003. ISBN 3-540-21002-4.
	32	Jean Vuillemin. A unifying look at data structures. phCommun. ACM, 23 (4): 229--239, 1980.
	33	Jean Vuillemin. On circuits and numbers. IEEE Trans. Computers, 43 (8): 868--879, 1994.
	34	D.H.D. Warren. Higher-order extensions to Prolog -- are they needed? In D. Michie, J. Hayes, and Y.H. Pao, editors, Machine Intelligence 10. Ellis Horwood, 1981.