Revisiting catamorphisms over datatypes with embedded functions (or, programs from outer space)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Revisiting catamorphisms over datatypes with embedded functions (or, programs from outer space)

Full text

Pdf (1.20 MB)

Source

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

St. Petersburg Beach, Florida, United States

Pages: 284 - 294

Year of Publication: 1996

ISBN:0-89791-769-3

Authors

Leonidas Fegaras	Department of Computer Science and Engineering, Oregon Graduate Institute of Science & Technology, 20000 N.W. Walker Road P.O. Box 91000, Portland, OR
Tim Sheard	Department of Computer Science and Engineering, Oregon Graduate Institute of Science & Technology, 20000 N.W. Walker Road P.O. Box 91000, Portland, OR

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 34, Citation Count: 23

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/237721.237792 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	Richard S. Bird , Oege de Moor, Solving Optimisation Problems with Catamorphism, Proceedings of the Second International Conference on Mathematics of Program Construction, p.45-66, June 29-July 03, 1992
	2	A. Church. A Formulation of the Simple Theory of Types. Journal of Symbolic Logic, 5:56-68, 1940.
	3	L. Fegaras, T. Sheard, and T. Zhou. Improving Programs" which Recurse over Multiple Inductive Structures. In A CM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, Orlando, Florida, pp 21-32, June 1994.
	4	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]
	5	G. Malcolm, Data structures and program transformation, Science of Computer Programming, v.14 n.2-3, p.255-279, Oct. 1990 [doi>10.1016/0167-6423(90)90023-7]
	6	Grant Malcolm, Homomorphisms and Promotability, Proceedings of the International Conference on Mathematics of Program Construction, 375th Anniversary of the Groningen University, p.335-347, June 26-30, 1989
	7	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
	8	Erik Meijer , Graham Hutton, Bananas in space: extending fold and unfold to exponential types, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.324-333, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224225]
	9	G. Nadathur and D. Miller. Higher-Order Logic Programming. In D. Gabbay, C. Hogger, and A. Robinson, editors, Handbook of Logic in Artificial Intelligence and Logic Programming. Oxford University Press, 1995. To appear.
	10	R. Paterson. Control Structures from Types. Unpublished draft. Available by anonymous ftp from ~tp-ala. doc. ic. ac. uk/pub/papers/R. Paterson/folds. dvi, 1994.
	11	Laurence C. Paulson, ML for the working programmer, Cambridge University Press, New York, NY, 1991
	12	F. Pfenning , C. Elliot, Higher-order abstract syntax, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.199-208, June 20-24, 1988, Atlanta, Georgia, United States
	13	Chris Reade, Elements of functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
	14	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]
	15	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 23

	Tim Sheard, A type-directed, on-line, partial evaluator for a polymorphic language, ACM SIGPLAN Notices, v.32 n.12, p.22-35, Dec. 1997
	Jeremy Gibbons , Geraint Jones, The under-appreciated unfold, ACM SIGPLAN Notices, v.34 n.1, p.273-279, Jan. 1999
	Geoffrey Washburn , Stephanie Weirich, Boxes go bananas: encoding higher-order abstract syntax with parametric polymorphism, ACM SIGPLAN Notices, v.38 n.9, p.249-262, September 2003
	Valery Trifonov , Bratin Saha , Zhong Shao, Fully reflexive intensional type analysis, ACM SIGPLAN Notices, v.35 n.9, p.82-93, Sept. 2000
	Carsten Schurmann , Joelle Despeyroux , Frank Pfenning, Primitive recursion for higher-order abstract syntax, Theoretical Computer Science, v.266 n.1-2, p.1-57, 09/06/2001
	Jean-Louis Giavitto , Olivier Michel, Declarative definition of group indexed data structures and approximation of their domains, Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.150-161, September 05-07, 2001, Florence, Italy
	Franklyn Turbak , J. B. Wells, Cycle therapy: a prescription for fold and unfold on regular trees, Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.137-149, September 05-07, 2001, Florence, Italy
	Mizuhito Ogawa , Zhenjiang Hu , Isao Sasano, Iterative-free program analysis, ACM SIGPLAN Notices, v.38 n.9, p.111-123, September 2003
	Martin Erwig, Functional programming with graphs, ACM SIGPLAN Notices, v.32 n.8, p.52-65, Aug. 1997
	Neil Ghani , Patricia Johann , Tarmo Uustalu , Varmo Vene, Monadic augment and generalised short cut fusion, ACM SIGPLAN Notices, v.40 n.9, September 2005
	Louis-Julien Guillemette , Stefan Monnier, Type-Safe Code Transformations in Haskell, Electronic Notes in Theoretical Computer Science (ENTCS), v.174 n.7, p.23-39, June, 2007
	Stephanie Weirich, Type-safe run-time polytypic programming, Journal of Functional Programming, v.16 n.6, p.681-710, November 2006
	Louis-Julien Guillemette , Stefan Monnier, A type-preserving closure conversion in haskell, 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
	Martin Erwig, Inductive graphs and functional graph algorithms, Journal of Functional Programming, v.11 n.5, p.467-492, September 2001
	Peter Thiemann, Combinators for program generation, Journal of Functional Programming, v.9 n.5, p.483-525, September 1999
	Adam Chlipala, Parametric higher-order abstract syntax for mechanized semantics, ACM SIGPLAN Notices, v.43 n.9, September 2008
	Aaron Stump, Imperative LF Meta-Programming, Electronic Notes in Theoretical Computer Science (ENTCS), 199, p.149-159, February, 2008
	Geoffrey Washburn , Stephanie Weirich, Boxes go bananas: Encoding higher-order abstract syntax with parametric polymorphism*, Journal of Functional Programming, v.18 n.1, p.87-140, January 2008
	Louis-Julien Guillemette , Stefan Monnier, A type-preserving compiler in Haskell, ACM SIGPLAN Notices, v.43 n.9, September 2008
	Ralf Hinze , Andres Löh, Generic programming in 3D, Science of Computer Programming, v.74 n.8, p.590-628, June, 2009
	Tillmann Rendel , Klaus Ostermann , Christian Hofer, Typed self-representation, ACM SIGPLAN Notices, v.44 n.6, June 2009
	Edwin Westbrook , Aaron Stump , Evan Austin, The calculus of nominal inductive constructions: an intensional approach to encoding name-bindings, Proceedings of the Fourth International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice, August 02-02, 2009, Montreal, Quebec, Canada