Shortcut deforestation in calculational form

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Shortcut deforestation in calculational form

Full text

Pdf (760 KB)

Source

Functional Programming Languages and Computer Architecture archive
Proceedings of the seventh international conference on Functional programming languages and computer architecture table of contents

La Jolla, California, United States

Pages: 306 - 313

Year of Publication: 1995

ISBN:0-89791-719-7

Authors

Akihiko Takano	Hitachi Advanced Research Lab, Hatoyama, Saitama 350-03, Japan
Erik Meijer	Utrecht University, PO Box 80089, 3508 TB Utrecht, The Netherlands

Sponsors

IFIP WG 2.8 : IFIP WG 2.8
SIGPLAN: ACM Special Interest Group on Programming Languages
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 43, Citation Count: 32

Additional Information:

references cited by 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/224164.224221 What is a DOI?

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.

	BD77	R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
	BM94	Richard Bird , Oege de Moor, Relational program derivation and context-free language recognition, A classical mind: essays in honour of C. A. R. Hoare, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1994
	Chi92	Wei-Ngan Chin, Safe fusion of functional expressions, Proceedings of the 1992 ACM conference on LISP and functional programming, p.11-20, June 22-24, 1992, San Francisco, California, United States
	FNT91	Yoshihiko Futamura , Kenroku Nogi , Akihiko Takano, Essence of generalized partial computation, Theoretical Computer Science, v.90 n.1, p.61-79, Nov. 1991 [doi>10.1016/0304-3975(91)90299-H]
	Fok92	M.M. Fokkinga. Law and Order m Algorithmics. PhD thesis, Universiteit Twente, February 1992.
	FSZ94	L. Fegaras, T. Sheard, and T. Zhou. Improving programs which recurse over multiple inductive structures. In PEPM '9~.
	GLPJ93	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]
	Jeu93	J. Jeuring. Theories for Algorithm Calculation. PhD thesis, University of Utrecht, February 1993.
	Mee86	L. Meertens. Algorithmics- towards programming as a mathematical activity. In Proceedings o/ the C WI Symposium on Mathematics and Computer Science, pages 289-334. North-Holland, 1986.
	Mee92	L. Meertens. Paramorphisms. Formal Aspects oj: Computing, 4(5):413-424, 1992.
	Mei92	E. Meijer. Calculating Compilers. PhD thesis, University of Nijmegen, February 1992.
	Mei94	E. Meijer. Acid rain theorem. Submitted for publication, 1994.
	MFP91	Erik Meijer , Maarten Fokkinga , Ross Paterson, Functional programming with bananas, lenses, envelopes and barbed wire, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.124-144, June 1991, Cambridge, Massachusetts, United States
	SF93	Tim Sheard , Leonidas Fegaras, A fold for all seasons, Proceedings of the conference on Functional programming languages and computer architecture, p.233-242, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165216]
	SGJ94	Morten Heine Sørensen , Robert Glück , Neil D. Jones, Towards Unifying Partial Evaluation, Deforestation, Supercompilation, and GPC, Proceedings of the 5th European Symposium on Programming: Programming Languages and Systems, p.485-500, April 11-13, 1994
	Sør94	Morten Heine Sørensen, Grammar-Based Data-Flow Analysis to Stop Deforestation, Proceedings of the 19th International Colloquium on Trees in Algebra and Programming, p.335-351, April 11-13, 1994
	Tak91	Akihiko Takano, Generalized partial computation for a lazy functional language, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.1-11, June 17-19, 1991, New Haven, Connecticut, United States
	TNT82	Valentin F. Turchin , Robert M. Nirenberg , Dimitri V. Turchin, Experiments with a supercompiler, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.47-55, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802134]
	Tur86	Valentin F. Turchin, The concept of a supercompiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.292-325, July 1986 [doi>10.1145/5956.5957]
	Wad88	P. Wadler. Deforestation. In ESOP '88, Nancy, France, volume 300 of LNCS. Springer-Verlag, March 1988.
	Wad89	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]

CITED BY 32

	Zhenjiang Hu , Hideya Iwasaki , Masato Takechi, Formal derivation of efficient parallel programs by construction of list homomorphisms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.444-461, May 1997
	Zhenjiang Hu , Masato Takeichi , Wei-Ngan Chin, Parallelization in calculational forms, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.316-328, January 19-21, 1998, San Diego, California, United States
	Manuel M. T. Chakravarty , Gabriele Keller, Functional array fusion, ACM SIGPLAN Notices, v.36 n.10, October 2001
	Akihiko Takano , Zhenjiang Hu , Masato Takeichi, Program transformation in calculational form, ACM Computing Surveys (CSUR), v.30 n.3es, Sept. 1998
	H. Seidl , M. H. Sørensen, Constraints to stop higher-order deforestation, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.400-413, January 15-17, 1997, Paris, France
	Zhenjiang Hu , Hideya Iwasaki , Masato Takeichi, Deriving structural hylomorphisms from recursive definitions, ACM SIGPLAN Notices, v.31 n.6, p.73-82, June 15, 1996
	Olaf Chitil, Typer inference builds a short cut to deforestation, ACM SIGPLAN Notices, v.34 n.9, p.249-260, Sept. 1999
	Michael Sperber , Peter Thiemann, Two for the price of one: composing partial evaluation and compilation, ACM SIGPLAN Notices, v.32 n.5, p.215-225, May 1997
	P. Christopher Staecker, Hyflofusion: harnessing the power of acid rain, Journal of Computing Sciences in Colleges, v.16 n.4, p.296-298, 2001
	Zhenjiang Hu , Hideya Iwasaki , Masato Takeichi , Akihiko Takano, Tupling calculation eliminates multiple data traversals, ACM SIGPLAN Notices, v.32 n.8, p.164-175, Aug. 1997
	Josef Svenningsson, Shortcut fusion for accumulating parameters & zip-like functions, ACM SIGPLAN Notices, v.37 n.9, p.124-132, September 2002
	Susumu Nishimura, Fusion with stacks and accumulating parameters, Proceedings of the 2004 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.101-112, August 24-25, 2004, Verona, Italy
	Patricia Johann, A Generalization of Short-Cut Fusion and its Correctness Proof, Higher-Order and Symbolic Computation, v.15 n.4, p.273-300, December 2002
	Neil Ghani , Patricia Johann , Tarmo Uustalu , Varmo Vene, Monadic augment and generalised short cut fusion, ACM SIGPLAN Notices, v.40 n.9, September 2005
	Atsushi Ohori , Isao Sasano, Lightweight fusion by fixed point promotion, ACM SIGPLAN Notices, v.42 n.1, January 2007
	Shin-ya Katsumata , Susumu Nishimura, Algebraic fusion of functions with an accumulating parameter and its improvement, ACM SIGPLAN Notices, v.41 n.9, September 2006
	Janis Voigtländer , Patricia Johann, Selective strictness and parametricity in structural operational semantics, inequationally, Theoretical Computer Science, v.388 n.1-3, p.290-318, December, 2007
	Patricia Johann , Eelco Visser, Warm fusion in Stratego: A case study in generation of program transformation systems, Annals of Mathematics and Artificial Intelligence, v.29 n.1-4, p.1-34, 2000
	Geoff W. Hamilton, Higher Order Deforestation, Fundamenta Informaticae, v.69 n.1-2, p.39-61, January 2006
	Patricia Johann , Janis Voigtländer, The Impact of seq on Free Theorems-Based Program Transformations, Fundamenta Informaticae, v.69 n.1-2, p.63-102, January 2006
	Patricia Johann, On proving the correctness of program transformations based on free theorems for higher-order polymorphic calculi, Mathematical Structures in Computer Science, v.15 n.2, p.201-229, April 2005
	Duncan Coutts , Roman Leshchinskiy , Don Stewart, Stream fusion: from lists to streams to nothing at all, ACM SIGPLAN Notices, v.42 n.9, September 2007
	Ralf Hinze, THEORETICAL PEARL Church numerals, twice!, Journal of Functional Programming, v.15 n.1, p.1-13, January 2005
	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
	Graham Hutton, A tutorial on the universality and expressiveness of fold, Journal of Functional Programming, v.9 n.4, p.355-372, July 1999
	Claus Jürgensen , Heiko Vogler, Syntactic composition of top-down tree transducers is short cut fusion, Mathematical Structures in Computer Science, v.14 n.2, p.215-282, April 2004
	Patricia Johann, Short cut fusion is correct, Journal of Functional Programming, v.13 n.4, p.797-814, July 2003
	Peter A. Jonsson , Johan Nordlander, Positive supercompilation for a higher order call-by-value language, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Patricia Johann , Neil Ghani, Foundations for structured programming with GADTs, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Janis Voigtländer, Proving correctness via free theorems: the case of the destroy/build-rule, Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 07-08, 2008, San Francisco, California, USA
	Alberto Pardo , João Paulo Fernandes , João Saraiva, Shortcut fusion rules for the derivation of circular and higher-order monadic programs, Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation, January 19-20, 2009, Savannah, GA, USA
	Shin-ya Katsumata , Susumu Nishimura, Algebraic fusion of functions with an accumulating parameter and its improvement, Journal of Functional Programming, v.18 n.5-6, p.781-819, September 2008