Article

Free access

Deriving structural hylomorphisms from recursive definitions

Authors:

Zhenjiang Hu,

Hideya Iwasaki,

Masato TakeichiAuthors Info & Claims

ICFP '96: Proceedings of the first ACM SIGPLAN international conference on Functional programming

Pages 73 - 82

https://doi.org/10.1145/232627.232637

Published: 15 June 1996 Publication History

PDF eReader

Abstract

In functional programming, small programs are often glued together to construct a complex program. Program fusion is an optimizing process whereby these small programs are fused into a single one and intermediate data structures are removed. Recent work has made it clear that this process is especially successful if the recursive definitions are expressed in terms of hylomorphisms. In this paper, we propose an algorithm which can automatically turn all practical recursive definitions into structural hylomorphisms making program fusion be easily applied.

References

[1]

R.S. Bird and O. de Moor. Relational program derivation and context-free language recognition. In A.W. Roscoe, editor, A Classical Mind, pages 17-35. Prentice Hall, 1994.

Digital Library

Google Scholar

[2]

W. Chin. Safe fusion of functional expressions. In Proc. Conference on Lisp and Functwnal Programming, San Francisco, California, June 1992.

Digital Library

Google Scholar

[3]

M. Fokkinga. Law and Order in Algorithmics. Ph.D thesis, Dept. INF, University of Twente, The Netherlands, 1992.

Google Scholar

[4]

L. Fegaxas, T. Sheard, and T. Zhou. Improving programs which recurse over multiple inductive structures. In Proc. PEPM'9d, June 1994.

Google Scholar

[5]

A. Gill, J. Launchbury, and S.P. Jones. A short cut to deforestation. In Proc. Conference on Functwnal Programming Languages and Computer Architecture, pages 223-232, Copenhagen, June 1993.

Digital Library

Google Scholar

[6]

Z. Hu, H. Iwasaki, and M. Takeichi. Making recursions manipulable by constructing mediotypes. Technical Report METR 95-04, University of Tokyo, 1995. (URL: http://www.ipl.t.uto kyo.a c.j p/~ hu / pub / MET R95-04. ps.gz).

Google Scholar

[7]

R.B. Kieburtz and J. Lewis. Algebraic design language. OGI Technical Report 94-002, Oregon Graduate Institution of Sci. and Tech., 1994.

Digital Library

Google Scholar

[8]

J. Launchbury and T. Sheard. Warm fusion: Deriving build-catas from recursive definitions. In Proc. Conference on Functional Programming Languages and Computer Architecture, pages 314- 323, La Jolla, California, June 1995.

Digital Library

Google Scholar

[9]

G. Malcolm. Data structures and program trans~ formation. Science of Computer Programming, (14):255-279, August 1990.

Digital Library

Google Scholar

[10]

E. Meijer, M. Fokkinga, and R. Paterson. Functional programming with bananas, lenses, envelopes and barbed wire. In Proc. Conference on Functional Programming Languages and Computer Architecture (LNCS 523), pages 124-144, Cambridge, Massachuetts, August 1991.

Digital Library

Google Scholar

[11]

T. Sheard and L. Fegaras. A fold for all seasons. In Proc. Conference on Functional Programming Languages and Computer Architecture, pages 233- 242, Copenhagen, June 1993.

Digital Library

Google Scholar

[12]

M. Takeichi. Partial parametrization eliminates multiple traversals of data structures. Acta Informatica, 24:57-77, 1987.

Digital Library

Google Scholar

[13]

A. Takano and E. Meijer. Shortcut deforestation in calculational form. In Proc. Conference on Functional Programming Languages and Computer Architecture, pages 306-313, La Jolla, California, June 1995.

Digital Library

Google Scholar

[14]

P. Wadler. Deforestation: Transforming programs to eliminate trees. In Proc. E$OP (LNCS 300), pages 344-358, 1988.

Digital Library

Google Scholar

Cited By

View all

Saito MIwasaki HKawabata HKomiya TVazou NMorris J(2024)Controlling Computation Granularity through Fusion in Improving Floating-Point NumbersProceedings of the 17th ACM SIGPLAN International Haskell Symposium10.1145/3677999.3678281(83-96)Online publication date: 29-Aug-2024
https://dl.acm.org/doi/10.1145/3677999.3678281
Ji RZhao YPolikarpova NXiong YHu Z(2024)Superfusion: Eliminating Intermediate Data Structures via Inductive SynthesisProceedings of the ACM on Programming Languages10.1145/36564158:PLDI(939-964)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656415
ZHANG HTANG WXIE RWANG MHU Z(2023)Contract lenses: Reasoning about bidirectional programs via calculationJournal of Functional Programming10.1017/S095679682300005933Online publication date: 6-Nov-2023
https://doi.org/10.1017/S0956796823000059
Show More Cited By

Index Terms

Deriving structural hylomorphisms from recursive definitions

Recommendations

Deriving structural hylomorphisms from recursive definitions

In functional programming, small programs are often glued together to construct a complex program. Program fusion is an optimizing process whereby these small programs are fused into a single one and intermediate data structures are removed. Recent work ...
Recursive Schema Definitions in Object-Z
ZB '00: Proceedings of the First International Conference of B and Z Users on Formal Specification and Development in Z and B

Unlike Z, Object-Z allows schemas to be defined recursively. This enables mutual and self recursive structures, commonly occurring in object-oriented programs, to be readily specified. In this paper, we provide a fixed point interpretation of such ...
Recursive definitions of partial functions and their computations
Proceedings of ACM conference on Proving assertions about programs

The object of this paper is to present a syntactic and semantic model for recursive definitions, and to study the relation between their computed functions and their fixpoints. The recursive definitions that we consider are syntactic generalizations of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICFP '96: Proceedings of the first ACM SIGPLAN international conference on Functional programming

June 1996

273 pages

ISBN:0897917707

DOI:10.1145/232627

Chairman:
Robert Harper
Carnegie Mellon Univ., Pittsburgh, PA
,
Editor:
Richard L. Wexelblat

ACM SIGPLAN Notices Volume 31, Issue 6
June 15, 1996
273 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/232629
Chairmen:
Robert Harper
Carnegie Mellon Univ., Pittsburgh, PA
,
Richard L. Wexelblat
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICFP96

Sponsor:

SIGPLAN

ICFP96: International Conference on Functional Programming

May 24 - 26, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

ICFP '96 Paper Acceptance Rate 25 of 83 submissions, 30%;

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
605
Total Downloads

Downloads (Last 12 months)120
Downloads (Last 6 weeks)18

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Saito MIwasaki HKawabata HKomiya TVazou NMorris J(2024)Controlling Computation Granularity through Fusion in Improving Floating-Point NumbersProceedings of the 17th ACM SIGPLAN International Haskell Symposium10.1145/3677999.3678281(83-96)Online publication date: 29-Aug-2024
https://dl.acm.org/doi/10.1145/3677999.3678281
Ji RZhao YPolikarpova NXiong YHu Z(2024)Superfusion: Eliminating Intermediate Data Structures via Inductive SynthesisProceedings of the ACM on Programming Languages10.1145/36564158:PLDI(939-964)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656415
ZHANG HTANG WXIE RWANG MHU Z(2023)Contract lenses: Reasoning about bidirectional programs via calculationJournal of Functional Programming10.1017/S095679682300005933Online publication date: 6-Nov-2023
https://doi.org/10.1017/S0956796823000059
Hinze RWu NGibbons J(2015)Conjugate Hylomorphisms -- OrACM SIGPLAN Notices10.1145/2775051.267698950:1(527-538)Online publication date: 14-Jan-2015
https://dl.acm.org/doi/10.1145/2775051.2676989
Hinze RWu NGibbons JRajamani SWalker D(2015)Conjugate Hylomorphisms -- OrProceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages10.1145/2676726.2676989(527-538)Online publication date: 14-Jan-2015
https://dl.acm.org/doi/10.1145/2676726.2676989
Hu ZHughes JWang M(2015)How functional programming matteredNational Science Review10.1093/nsr/nwv0422:3(349-370)Online publication date: 13-Jul-2015
https://doi.org/10.1093/nsr/nwv042
Hamana MFiore MJärvi JMu S(2011)A foundation for GADTs and inductive familiesProceedings of the seventh ACM SIGPLAN workshop on Generic programming10.1145/2036918.2036927(59-70)Online publication date: 18-Sep-2011
https://dl.acm.org/doi/10.1145/2036918.2036927
Morihata AMatsuzaki KChakravarty MHu ZDanvy O(2011)Balanced trees inhabiting functional parallel programmingProceedings of the 16th ACM SIGPLAN international conference on Functional programming10.1145/2034773.2034791(117-128)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034773.2034791
Morihata AMatsuzaki K(2011)Balanced trees inhabiting functional parallel programmingACM SIGPLAN Notices10.1145/2034574.203479146:9(117-128)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034574.2034791
Morihata AMatsuzaki K(2010)Automatic parallelization of recursive functions using quantifier eliminationProceedings of the 10th international conference on Functional and Logic Programming10.1007/978-3-642-12251-4_23(321-336)Online publication date: 19-Apr-2010
https://dl.acm.org/doi/10.1007/978-3-642-12251-4_23
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Deriving structural hylomorphisms from recursive definitions

Recursive Schema Definitions in Object-Z

Recursive definitions of partial functions and their computations