Call pattern analysis for functional logic programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Call pattern analysis for functional logic programs

Full text

Pdf (405 KB)

Source

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

Valencia, Spain

SESSION: Theory & semantics table of contents

Pages 67-78

Year of Publication: 2008

ISBN:978-1-60558-117-0

Author

Michael Hanus

Institut für Informatik, CAU 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): 5, Downloads (12 Months): 26, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

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/1389449.1389459 What is a DOI?

ABSTRACT

This paper presents a new program analysis framework to approximate call patterns and their results in functional logic computations. We consider programs containing nonstrict, nondeterministic operations in order to make the analysis applicable to modern functional logic languages like Curry or TOY. For this purpose, we present a new fixpoint characterization of functional logic computations w.r.t. a set of initial calls. We show how programs can be analyzed by approximating this fixpoint. The results of such an approximation have various applications, e.g., program optimization as well as verifying safety properties of programs

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	E. Albert, G. Puebla, and M. Hermenegildo. An abstract interpretation-based approach to mobile code safety. Electronic Notes in Theoretical Computer Science, 132:113--129, 2005.
	2	M. Alpuente, M. Comini, S. Escobar, M. Falaschi, and S. Lucas. Abstract diagnosis of functional programs. In Proc. of the 12th Int'l Workshop on Logic-Based Program Synthesis and Transformation (LOPSTR 2002), pages 1--16. Springer LNCS 2664, 2002.
	3	Sergio Antoy, Optimal Non-deterministic Functional Logic Computations, Proceedings of the 6th International Joint Conference on Algebraic and Logic Programming, p.16-30, September 03-05, 1997
	4	Sergio Antoy , Michael Hanus, Compiling Multi-Paradigm Declarative Programs into Prolog, Proceedings of the Third International Workshop on Frontiers of Combining Systems, p.171-185, March 22-24, 2000
	5	S. Antoy and M. Hanus. Overlapping rules and logic variables in functional logic programs. In Proceedings of the 22nd International Conference on Logic Programming (ICLP 2006), pages 87--101. Springer LNCS 4079, 2006.
	6	Sergio Antoy , Rachid Echahed , Michael Hanus, A needed narrowing strategy, Journal of the ACM (JACM), v.47 n.4, p.776-822, July 2000 [doi>10.1145/347476.347484]
	7	Franz Baader , Tobias Nipkow, Term rewriting and all that, Cambridge University Press, New York, NY, 1998
	8	D. Bert and R. Echahed. Abstraction of conditional term rewriting systems. In Proc. of the 1995 International Logic Programming Symposium, pages 147--161. MIT Press, 1995.
	9	Didier Bert , Rachid Echahed , Bjarte M. Østvold, Abstract Rewriting, Proceedings of the Third International Workshop on Static Analysis, p.178-192, September 22-24, 1993
	10	Staffan Bonnier , Jan Maluszynski, Towards a Clean Amalgamation of Logic Programs with External Procedures, Proceedings of the 1st International Workshop on Programming Language Implementation and Logic Programming, p.20-34, May 16-18, 1988
	11	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, 2007a.
	12	B. Braβel and F. Huch. The Kiel Curry system KiCS. In Proc. 17th International Conference on Applications of Declarative Programming and Knowledge Management (INAP 2007) and 21st Workshop on (Constraint) Logic Programming (WLP 2007), pages 215--223. Technical Report 434, University of Würzburg, 2007b.
	13	Maurice Bruynooghe, A practical framework for the abstract interpretation of logic programs, Journal of Logic Programming, v.10 n.2, p.91-124, Feb. 1991 [doi>10.1016/0743-1066(91)80001-T]
	14	José Miguel Cleva , Javier Leach , Francisco J. López-Fraguas, A logic programming approach to the verification of functional-logic programs, Proceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.9-19, August 24-26, 2004, Verona, Italy [doi>10.1145/1013963.1013969]
	15	Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
	16	P.W. Dart and J. Zobel. A regular type language for logic programs. In F. Pfenning, editor, Types in Logic Programming, pages 157--187. MIT Press, 1992.
	17	Nachum Dershowitz , Jean-Pierre Jouannaud, Rewrite systems, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	18	Rachid Echahed , Jean-Christophe Janodet, Admissible graph rewriting and narrowing, Proceedings of the 1998 joint international conference and symposium on Logic programming, p.325-340, August 1998, Manchester, United Kingdom
	19	J.P. Gallagher and M. Bruynooghe. The derivation of an algorithm for program specialisation. New Generation Computing, 9(3/4):305--334, 1991.
	20	J.C. González-Moreno, M.T. Hortalá-González, F.J. López-Fraguas, and M. Rodríguez-Artalejo. An approach to declarative programming based on a rewriting logic. Journal of Logic Programming, 40:47--87, 1999.
	21	M. Hanus. Multi-paradigm declarative languages. In Proceedings of the International Conference on Logic Programming (ICLP 2007), pages 45--75. Springer LNCS 4670, 2007.
	22	M. Hanus. Call pattern analysis for functional logic programs. Technical report 0803, Christian-Albrechts-Universität Kiel, 2008.
	23	M. Hanus. The integration of functions into logic programming: From theory to practice. Journal of Logic Programming, 19&20:583--628, 1994.
	24	Michael Hanus, A unified computation model for functional and logic programming, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.80-93, January 15-17, 1997, Paris, France [doi>10.1145/263699.263710]
	25	M. Hanus (ed.). Curry: An integrated functional logic language (vers. 0.8.2). Available at http://www.informatik.uni-kiel.de/~curry, 2006.
	26	Neil D. Jones , Nils Andersen, Flow analysis of lazy higher-order functional programs, Theoretical Computer Science, v.375 n.1-3, p.120-136, May, 2007 [doi>10.1016/j.tcs.2006.12.030]
	27	Neil D. Jones , Alan Mycroft, Data flow analysis of applicative programs using minimal function graphs, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.296-306, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512672]
	28	Francisco Javier López-Fraguas , Jaime Sánchez Hernández, TOY: A Multiparadigm Declarative System, Proceedings of the 10th International Conference on Rewriting Techniques and Applications, p.244-247, July 02-04, 1999
	29	Francisco J. López-Fraguas , Juan Rodríguez-Hortalá , Jaime Sánchez-Hernández, A simple rewrite notion for call-time choice semantics, Proceedings of the 9th ACM SIGPLAN international conference on Principles and practice of declarative programming, July 14-16, 2007, Wroclaw, Poland [doi>10.1145/1273920.1273947]
	30	N. Mitchell and C. Runciman. A static checker for safe pattern matching in Haskell. In Trends in Functional Programming, volume 6, pages 15--30. Intellect, 2007.
	31	J.M. Molina-Bravo and E. Pimentel. Modularity in functional-logic programming. In Proc. of the Fourteenth International Conference on Logic Programming (ICLP'97), pages 183--197. MIT Press, 1997.
	32	Flemming Nielson , Hanne R. Nielson , Chris Hankin, Principles of Program Analysis, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
	33	Simon Peyton Jones, Call-pattern specialisation for Haskell programs, Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, October 01-03, 2007, Freiburg, Germany
	34	John C. Reynolds, Definitional interpreters for higher-order programming languages, Proceedings of the ACM annual conference, p.717-740, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800194.805852]
	35	Philip Wadler, How to declare an imperative, ACM Computing Surveys (CSUR), v.29 n.3, p.240-263, Sept. 1997 [doi>10.1145/262009.262011]
	36	D.H.D. Warren. Higher-order extensions to Prolog: are they needed? In Machine Intelligence 10, pages 441--454, 1982.
	37	Will Winsborough, Multiple specialization using minimal-function graph semantics, Journal of Logic Programming, v.13 n.2-3, p.259-290, July 1992 [doi>10.1016/0743-1066(92)90033-Y]