Set functions for functional logic programming

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Set functions for functional logic programming

Full text

Pdf (412 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: Integration of paradigms table of contents

Pages 73-82

Year of Publication: 2009

ISBN:978-1-60558-568-0

Authors

Sergio Antoy	Portland State University, Portland, OR, USA
Michael Hanus	Christian-Albrechts-University of Kiel, Kiel, Germany

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 7, 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.1599420 What is a DOI?

ABSTRACT

We propose a novel approach to encapsulate non-deterministic computations in functional logic programs. Our approach is based on set functions that return the set of all the results of a corresponding ordinary operation. A characteristic feature of our approach is the complete separation between a usually-non-deterministic operation and its possibly-non-deterministic arguments. This separation leads to the first provably order-independent approach to computing the set of values of non-deterministic expressions. The proof is provided within the framework of graph rewriting in constructor-based systems. We propose an abstract implementation of our approach and prove its independence of the order of evaluation. Our approach solves easily and naturally problems mishandled by current implementations of functional logic languages.

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	S. Antoy. Definitional trees. In H. Kirchner and G. Levi, editors, Proceedings of the Third International Conference on Algebraic and Logic Programming, pages 143--157, Volterra, Italy, September 1992. Springer LNCS 632.
	2	S. Antoy. Optimal non-deterministic functional logic computations. In Proceedings of the Sixth International Conference on Algebraic and Logic Programming (ALP'97), pages 16--30, Southampton, UK, September 1997. Springer LNCS 1298.
	3	S. Antoy. Constructor-based conditional narrowing. In Proceedings of the Third ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, pages 199--206, Florence, Italy, 2001. ACM Press.
	4	S. Antoy. Evaluation strategies for functional logic programming. Journal of Symbolic Computation, 40(1):875--903, 2005.
	5	S. Antoy and B. Braßel. Computing with subspaces. In PPDP '07: Proceedings of the 9th ACM SIGPLAN international conference on principles and practice of declarative programming, pages 121--130, New York, NY, USA, 2007. ACM.
	6	S. Antoy and M. Hanus. Declarative programming with function patterns. In 15th Int'nl Symp. on Logic-based Program Synthesis and Transformation (LOPSTR 2005), pages 6--22, London, UK, September 2005. Springer LNCS 3901.
	7	S. Antoy and M. Hanus. Overlapping rules and logic variables in functional logic programs. In Twenty Second International Conference on Logic Programming, pages 87--101, Seattle, WA, August 2006. Springer LNCS 4079.
	8	S. Antoy, M. Hanus, J. Liu, and A. Tolmach. A virtual machine for functional logic computations. In Proc. of the 16th International Workshop on Implementation and Application of Functional Languages (IFL 2004), pages 108--125, Lubeck, Germany, September 2005. Springer LNCS 3474.
	9	Sergio Antoy. Evaluation strategies for functional logic programming. In Bernhard Gramlich and Salvador Lucas, editors, Electronic Notes in Theoretical Computer Science, volume 57. Elsevier Science Publishers, 2001.
	10	F. Baader and T. Nipkow. Term Rewriting and All That. Cambridge University Press, 1998.
	11	M. Bezem, J.W. Klop, and R. de Vrijer (eds.). Term Rewriting Systems. Cambridge University Press, 2003.
	12	B. Braßel, M. Hanus, and F. Huch. Encapsulating non-determinism in functional logic computations. Journal of Functional and Logic Programming, 2004(6):1--28, 2004.
	13	B. Braßel and F. Huch. On a tighter integration of functional and logic programming. In Proc. APLAS 2007, pages 122--138. Springer LNCS 4807, 2007.
	14	B. Brassel and F. Huch. The Kiel Curry System KiCS. In Dietmar Seipel, Michael Hanus, and Armin Wolf, editors, Applications of Declarative Programming and Knowledge Management, pages 195--205, Springer LNAI 5437, 2009.
	15	R. Echahed and J.-C. Janodet. On constructor-based graph rewriting systems. Technical Report 985-I, IMAG, 1997. Available at http://www-lsr.imag.fr/Les.Publications/c-graph-rewriting.ps.
	16	Rachid Echahed. Inductively sequential term-graph rewrite systems. In Graph Transformations, 4th International Conference, ICGT 2008, Leicester, United Kingdom, volume 5214 of Lecture Notes in Computer Science, pages 84--98. Springer, 2008.
	17	J.C. González Moreno, F.J. López Fraguas, M.T. Hortalá González, and M. Rodríguez Artalejo. An approach to declarative programming based on a rewriting logic. The Journal of Logic Programming, 40:47--87, 1999.
	18	M. Hanus, S. Lucas, and A. Middeldorp. Strongly sequential and inductively sequential term rewriting systems. Information Processing Letters, 67(1):1--8, 1998.
	19	M. Hanus and F. Steiner. Controlling search in declarative programs. In Principles of Declarative Programming (Proc. Joint International Symposium PLILP/ALP'98), pages 374--390. Springer LNCS 1490, 1998.
	20	M. Hanus (ed.). Curry: An integrated functional logic language (vers. 0.8.2). Available at http://www.curry-language.org, 2006.
	21	M. Hanus (ed.). PAKCS 1.9.1: The Portland Aachen Kiel Curry System. Available at http://www.informatik.uni-kiel.de/ pakcs, 2008.
	22	G. Huet and J.-J. Lévy. Computations in orthogonal term rewriting systems. In J.-L. Lassez and G. Plotkin, editors, Computational logic: essays in honour of Alan Robinson. MIT Press, Cambridge, MA, 1991.
	23	H. Hussmann. Nondeterministic algebraic specifications and nonconfluent rewriting. Journal of Logic Programming, 12:237--255, 1992.
	24	F.J. López-Fraguas and J. Sánchez-Hernández. A proof theoretic approach to failure in functional logic programming. Theory and Practice of Logic Programming, 4(1):41--74, 2004.
	25	W. Lux. An abstract machine for the efficient implementation of Curry. In H. Kuchen, editor, Workshop on Functional and Logic Programming, Arbeitsbericht No. 63. Institut für Wirtschaftsinformatik, Universität Münster, 1998.
	26	W. Lux. Implementing encapsulated search for a lazy functional logic language. In Proc. 4th Fuji Intl. Symposium on Functional and Logic Programming (FLOPS '99), pages 100--113. Springer LNCS 1722, 1999.
	27	M.J. O'Donnell. Equational Logic as a Programming Language. MIT Press, 1985.
	28	J. Sánchez-Hernández. Constructive failure in functional-logic programming: From theory to implementation. Journal of Universal Computer Science, 12(11):1574--1593, 2006.
	29	C. Schulte and G. Smolka. Encapsulated search for higher-order concurrent constraint programming. In Proc. of the 1994 International Logic Programming Symposium, pages 505--520. MIT Press, 1994.
	30	N. Wirth. Algorithms and Data Structures. Prentice Hall, 1976.