Shortcut fusion rules for the derivation of circular and higher-order monadic programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Shortcut fusion rules for the derivation of circular and higher-order monadic programs

Full text

Pdf (480 KB)

Source

ACM/SIGPLAN Workshop Partial Evaluation and Semantics-Based Program Manipulation archive
Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation table of contents

Savannah, GA, USA

SESSION: Program transformation I table of contents

Pages 81-90

Year of Publication: 2009

ISBN:978-1-60558-327-3

Authors

Alberto Pardo	Universidad de la Republica, Montevideu, Uruguay
João Paulo Fernandes	Universidade do Minho & Universidade Atlâântica, Braga, Portugal
João Saraiva	Universidade do Minho, Braga, Portugal

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): 48, 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/1480945.1480958 What is a DOI?

ABSTRACT

Functional programs often combine separate parts using intermediate data structures for communicating results. These programs are modular, easier to understand and maintain, but suffer from inefficiencies due to the generation of those gluing data structures. To eliminate such redundant data structures, some program transformation techniques have been proposed. One such technique is shortcut fusion, and has been studied in the context of both pure and monadic functional programs.

Recently, we have extended standard shortcut fusion: in addition to intermediate structures, the program parts may now communicate context information, and it still is possible to eliminate those structures. This is achieved by transforming the original function composition into a circular program. This new technique, however, has been studied in the context of purely functional programs only. In this paper, we propose an extension to this new form of fusion, but in the context of monadic programming: we derive monadic circular programs from strict ones, maintaining the global effects. Later, the circularities in the derived programs are traded by high-order definitions, using a well-known program transformation technique. We finally obtain very efficient deforested programs.

An important feature of our extensions is that they can be uniformly defined for a wide class of data types and monads, using generic calculation rules.

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	Samson Abramsky , Achim Jung, Domain theory, Handbook of logic in computer science (vol. 3): semantic structures, Oxford University Press, Oxford, 1995
	2	Richard Bird, Introduction to Functional Programming, Pearson Education, 1998
	3	Richard Bird , Oege de Moor, Algebra of programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
	4	Richard S. Bird. Using circular programs to eliminate multiple traversals of data. Acta Inf, 21:239--250, 1984.
	5	O. Chitil. Type-inference based deforestation of functional programs. PhD thesis, RWTH Aachen, October 2000.
	6	R. Cockett and D. Spencer. Strong Categorical Datatypes I. In R.A.C. Seely, editor, International Meeting on Category Theory 1991, volume 13 of Canadian Mathematical Society Conference Proceedings, pages 141--169, 1991.
	7	Oege de Moor , Simon L. Peyton Jones , Eric Van Wyk, Aspect-Oriented Compilers, Proceedings of the First International Symposium on Generative and Component-Based Software Engineering, p.121-133, September 28-30, 1999
	8	Levent Erkök , John Launchbury, A recursive do for Haskell, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.29-37, October 03, 2002, Pittsburgh, Pennsylvania [doi>10.1145/581690.581693]
	9	João Paulo Fernandes , Alberto Pardo , João Saraiva, A shortcut fusion rule for circular program calculation, Proceedings of the ACM SIGPLAN workshop on Haskell workshop, September 30-30, 2007, Freiburg, Germany [doi>10.1145/1291201.1291216]
	10	João Paulo Fernandes , João Saraiva, Tools and libraries to model and manipulate circular programs, Proceedings of the 2007 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 15-16, 2007, Nice, France [doi>10.1145/1244381.1244399]
	11	N. Ghani and P. Johann. Short Cut Fusion of Recursive Programs with Computational Effects. In Symposium on Trends in Functional Programming (TFP 2008), 2008.
	12	Jeremy Gibbons, Calculating functional programs, Algebraic and coalgebraic methods in the mathematics of program construction, Springer-Verlag New York, Inc., New York, NY, 2002
	13	A. Gill. Cheap Deforestation for Non-strict Functional Languages. PhD thesis, Department of Computing Science, University of Glasgow, UK, 1996.
	14	Andrew Gill , John Launchbury , Simon L. Peyton Jones, A short cut to deforestation, Proceedings of the conference on Functional programming languages and computer architecture, p.223-232, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165214]
	15	Dennis Kugler Harald Baier and Marian Margraf. Elliptic Curve Cryptography Based on ISO 15946. Technical Report TR-03111, Federal Office for Information Security, 2007.
	16	Graham Hutton , Erik Meijer, Monadic parsing in Haskell, Journal of Functional Programming, v.8 n.4, p.437-444, July 1998 [doi>10.1017/S0956796898003050]
	17	Patricia Johann , Janis Voigtländer, Free theorems in the presence of seq, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.99-110, January 14-16, 2004, Venice, Italy
	18	C. Manzino and A. Pardo. Short Cut Fusion of Monadic Programs. In Brazilian Symposium on Programming Languages (SBLP), 2008.
	19	Alberto Pardo, Generic Accumulations, Proceedings of the IFIP TC2/WG2.1 Working Conference on Generic Programming, p.49-78, July 11-12, 2002
	20	Alberto Pettorossi and Andrzej Skowron. The lambda abstraction strategy for program derivation. In Fundamenta Informaticae XII, pages 541--561, 1987.
	21	Doaitse Swierstra. Tutorial on attribute grammars. In Generative Programming and Component Engineering, 1993.
	22	S. D. Swierstra, Arthur Baars, and Andres Loh. The UU-AG attribute grammar system.
	23	Akihiko Takano , Erik Meijer, Shortcut deforestation in calculational form, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.306-313, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224221]
	24	Janis Voigtländer, Using circular programs to deforest in accumulating parameters, Proceedings of the ASIAN symposium on Partial evaluation and semantics-based program manipulation, p.126-137, September 12-14, 2002, Aizu, Japan [doi>10.1145/568173.568187]
	25	Janis Voigtlander. Semantics and pragmatics of new shortcut fusion rules. In FLOPS '08: Proceedings of the 2008 International Symposium on Functional and Logic Programming, pages 163--179. Springer-Verlag, 2008.
	26	Philip Wadler, Theorems for free!, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.347-359, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99404]
	27	William Waite , Uwe Kastens , Anthony M. Sloane, Generating Software from Specifications, Jones and Bartlett Publishers, Inc., 2007
	28	Eric Van Wyk , Lijesh Krishnan , Derek Bodin , Eric Johnson , August Schwerdfeger , Phil Russell, Tool Demonstration: Silver Extensible Compiler Frameworks and Modular Language Extensions for Java and C, Proceedings of the Sixth IEEE International Workshop on Source Code Analysis and Manipulation, p.161, September 27-29, 2006 [doi>10.1109/SCAM.2006.32]