Constraints to stop higher-order deforestation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constraints to stop higher-order deforestation

Full text

Pdf (1.13 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Paris, France

Pages: 400 - 413

Year of Publication: 1997

ISBN:0-89791-853-3

Authors

H. Seidl	FB IV, Informatik, Universität Trier, D-54286 Trier, Germany
M. H. Sørensen	Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen ø, Denmark

Sponsors

L'Ecole des Mines de Paris : L'Ecole des Mines de Paris
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Ctr Natl de la Recherche Sci :
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 25, Citation Count: 6

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/263699.263758 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.

	1	Zena M. Ariola , John Maraist , Martin Odersky , Matthias Felleisen , Philip Wadler, A call-by-need lambda calculus, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.233-246, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199507]
	2	H. P. Barendregt, Lambda calculi with types, Handbook of logic in computer science (vol. 2): background: computational structures, Oxford University Press, Inc., New York, NY, 1993
	3	R. Bird. Using circular programs to eliminate multiple traversals of data. Acta Informatica, 21:239-250, 1984.
	4	D. Bjorner , Neil D. Jones , A. P. Ershov, Partial Evaluation and Mixed Computation: Proceedings of the IFIP TC2 Workshop, Gammel Avernaes, Denmark, 18-24 Oct., 1987, Elsevier Science Inc., New York, NY, 1988
	5	A. Bondorf. Self-Applicable Partial Evaluation. PhD thesis, Department of Computer Science, Universty of Copenhagen, 1990. DIKU-Rapport 90/17.
	6	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]
	7	W.-N. Chin. Automatic Methods for Program 7#annformation. PhD thesis, Imperial College, University of London, 1990.
	8	G. W. Hamilton , S. B. Jones, Extending Deforestation for First Order functional Programs, Proceedings of the 1991 Glasgow Workshop on Functional Programming, p.134-145, August 12-14, 1991
	9	W.-N. Chin. Fully lazy higher-order removal. In Proceeding of the A CM SIGPLAN Syposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 38-47, 1992. Yale University technical report YALEU/DCS/RR-909.
	10	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
	11	W.-N. Chin. Safe fusion of functional expressions II: Further improvements. Journal of Functional Programming, 4(4):515-555, 1994.
	12	W.-N. Chin and J. Darlington. Higher-order removal transformation technique for functional programs. In Australian Computer Science Conference, volume 14,1 of Australian CS Comm., pages 181-194, 1992.
	13	Wei-Ngan Chin , Siau-Cheng Khoo, Better Consumers for Deforestation (Extended Abstract), Proceedings of the 7th International Symposium on Programming Languages: Implementations, Logics and Programs, p.223-240, September 20-22, 1995
	14	J. Darlington. An experimental program transformation and synthesis system. Artificial 1nteUigence, 16:1- 46, 1981.
	15	Martin S. Feather, A System for Assisting Program Transformation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.1-20, Jan. 1982 [doi>10.1145/357153.357154]
	16	L. Fegaras, T. Sheard, and T. Zhou. Improving programs which recurse over multiple inductive structures. In Proceeding o.f the A CM SIGPLAN Syposium on Partial Evaluation and Semantics.Based Program Manipulation, 1994.
	17	A. Ferguson and P.L. Wadler. When will deforestation stop? In Glasgow Workshop on Functional Programming, pages 39-56, 1988.
	18	A.J. Gill. Cheap Deforestation .for Non-strict Functional Languages. PhD thesis, Department of Computing Science, Glasgow University, 1996.
	19	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]
	20	A.J. Gill and Simon L. Peyton Jones. Cheap deforestation in practice: An optimiser for Haskell. In IFIP, pages 581-586, 1994.
	21	G. Hamilton. Compile.Time Optimisations of Storage Usage in Lazy Functional Programs. PhD thesis, University of Stirling, 1993.
	22	G. Hamilton. Extending first order deforestation. Technical Report TR 95-06, Department of Computer Science, Keele University, 1995.
	23	G. W. Hamilton, Higher Order Deforestation, Proceedings of the 8th International Symposium on Programming Languages: Implementations, Logics, and Programs, p.213-227, September 24-27, 1996
	24	G. W. Hamilton , S. B. Jones, Extending Deforestation for First Order functional Programs, Proceedings of the 1991 Glasgow Workshop on Functional Programming, p.134-145, August 12-14, 1991
	25	G. Hamilton and S.B. Jones. Transforming programs to eliminate intermediate structures. In Workshop on Static Analysis of Equational, Punctional and Logic Programming Languages, BIGRE 74, pages 182-188, 1991.
	26	Nevin Heintze, Set-based analysis of ML programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.306-317, June 27-29, 1994, Orlando, Florida, United States
	27	Fritz Henglein, Type inference with polymorphic recursion, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.2, p.253-289, April 1993 [doi>10.1145/169701.169692]
	28	J.R. Hindley. The principal type scheme of an object in combinatory logic. 7#nsactions of the American Mathematical Society, 146:29--60, 1969.
	29	John Hughes, Why functional programming matters, Research topics in functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	30	N.D. Jones. Flow analysis of lazy higher-order functional programs. In S. Abramsky and C. Hankin, editors, Abstract Interpretation of Declarative Language, chapter 5. Ellis Horwood, London, 1987.
	31	Richard B. Kieburtz , Jonathan Shultis, Transformations of FP program schemes, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.41-48, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806761]
	32	John Launchbury , Tim Sheard, Warm fusion: deriving build-catas from recursive definitions, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.314-323, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224223]
	33	Z. Manna and R. Waldinger. Synthesis: Dreams ffi> programs. 1EBB 7~ansations on Software Engineering, 5(4):157-164, 1979.
	34	Simon Marlow , Philip Wadler, Deforestation for Higher-Order Functions, Proceedings of the 1992 Glasgow Workshop on Functional Programming, p.154-165, July 06-08, 1992
	35	S.D. Maxlow. Deforestation for Higher-Order Functional Languages. PhD thesis, University of Glasgow, 1996.
	36	R. Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348-375, 1978.
	37	Alan Mycroft, Polymorphic Type Schemes and Recursive Definitions, Proceedings of the 6th Colloquium on International Symposium on Programming, p.217-228, April 17-19, 1984
	38	Jens Palsberg, Closure analysis in constraint form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.47-62, Jan. 1995 [doi>10.1145/200994.201001]
	39	Jens Palsberg , Patrick O'Keefe, A type system equivalent to flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.4, p.576-599, July 1995 [doi>10.1145/210184.210187]
	40	David Sands, Proving the Correctness of Recursion-Based Automatic Program Transformations, Proceedings of the 6th International Joint Conference CAAP/FASE on Theory and Practice of Software Development, p.681-695, May 22-26, 1995
	41	David Sands, Total correctness by local improvement in program transformation, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.221-232, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199485]
	42	David Sands, Proving the correctness of recursion-based automatic program transformations, Theoretical Computer Science, v.167 n.1-2, p.193-233, Oct. 30, 1996
	43	David Sands, Total correctness by local improvement in the transformation of functional programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.2, p.175-234, March 1996 [doi>10.1145/227699.227716]
	44	Helmut Seidl, Least Solutions of Equations over N, Proceedings of the 21st International Colloquium on Automata, Languages and Programming, p.400-411, July 11-14, 1994
	45	Helmut Seidl, Integer Constraints to Stop Deforestation, Proceedings of the 6th European Symposium on Programming Languages and Systems, p.326-340, April 22-24, 1996
	46	P. Sestoft. Automatic call unfolding in a partial evaluator. In Bjcrner et al. {4}, pages 485-506.
	47	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]
	48	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
	49	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]
	50	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]
	51	David A. Turner, Research topics in functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	52	Philip Wadler, Applicative style programming, program transformation, and list operators, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.25-32, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806759]
	53	Philip. Wadler, Listlessness is better than laziness II: composing listless functions, on Programs as data objects, p.282-305, April 1986, Copenhagen, Denmark
	54	Philip. Wadler, Listlessness is better than laziness II: composing listless functions, on Programs as data objects, p.282-305, April 1986, Copenhagen, Denmark
	55	Philip Wadler, Deforestation: transforming programs to eliminate trees, Proceedings of the Second European Symposium on Programming, p.231-248, January 1988, Nancy, France
	56	Philip Wadler, Deforestation: transforming programs to eliminate trees, Theoretical Computer Science, v.73 n.2, p.231-248, June 22, 1990

CITED BY 6

	G. W. Hamilton, Extending higher-order deforestation: transforming programs to eliminate even more trees, Trends in functional programming, Intellect Books, Exeter, UK, 2002
	Christian Fecht , Helmut Seidl, Propagating differences: an efficient new fixpoint algorithm for distributive constraint systems, Nordic Journal of Computing, v.5 n.4, p.304-329, Winter 1998
	Clemens Grelck , Sven-Bodo Scholz, Merging compositions of array skeletons in SAC, Parallel Computing, v.32 n.7, p.507-522, September 2006
	G. W. Hamilton, Distillation: extracting the essence of programs, Proceedings of the 2007 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 15-16, 2007, Nice, France
	Wei-Ngan Chin , Siau-Cheng Khoo , Neil Jones, Redundant Call Elimination via Tupling, Fundamenta Informaticae, v.69 n.1-2, p.1-37, January 2006
	Geoff W. Hamilton, Higher Order Deforestation, Fundamenta Informaticae, v.69 n.1-2, p.39-61, January 2006