skip to main content
10.1145/1328408.1328436acmconferencesArticle/Chapter ViewAbstractPublication PagespepmConference Proceedingsconference-collections
research-article

Heap recycling for lazy languages

Published: 07 January 2008 Publication History

Abstract

Pure functional programming languages preclude destructive updates of heap-allocated data. In such languages, all newly computed algebraic values claim freshly allocated heap space, which typically causes idiomatic programs to be notoriously inefficient when compared to their imperative and impure counterparts. We partly overcome this shortcoming by considering a syntactically light language construct for enabling user-controlled in-place updates of algebraic values. The resulting calculus, that is based on a combination of type-based uniqueness and constructor analysis, is guaranteed to maintain referential transparency and is fully compatible with existing run-time systems for nonstrict, pure functional languages.

References

[1]
Erik Barendsen and Sjaak Smetsers. Conventional and uniqueness typing in graph rewrite systems. In R. K. Shyamasundar, editor, Foundations of Software Technology and Theoretical Computer Science, 13th Conference, Bombay, India, December 15--17, 1993, Proceedings, volume 761 of Lecture Notes in Computer Science, pages 41--51. Springer-Verlag, 1993.
[2]
Richard Bird. Introduction to Functional Programming using Haskell. Prentice Hall, London, 2nd edition, 1998.
[3]
Urban Boquist. Code Optimization Techniques for Lazy Functional Languages. PhD thesis, Chalmers University of Technology and Goeteborg University, 1999.
[4]
Urban Boquist and Thomas Johnsson. The GRIN project: A highly optimising back end for lazy functional languages. In Werner E. Kluge, editor, Implementation of Functional Languages, 8th International Workshop, IFL'96, Bad Godesberg, Germany, September 16--18, 1996, Selected Papers, volume 1268 of Lecture Notes in Computer Science, pages 58--84. Springer-Verlag, 1997.
[5]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. Introduction to Algorithms. The MIT Press, Cambridge, Massachusetts, 2nd edition, 2001.
[6]
Luís Damas and Robin Milner. Principal type-schemes for functional programs. In Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages, Albuquerque, New Mexico, January 1982, pages 207--212. ACM Press, 1982.
[7]
Edsko de Vries, Rinus Plasmeijer, and David Abrahamson. Uniqueness typing redefined. In Zoltán Horváth, Viktória Zsók, and Andrew Butterfield, editors, Implementation and Application of Functional Languages, 18th International Workshop, IFL 2006, Budapest, Hungary, September 4--6, 2006, Revised Selected Papers, volume 4449 of Lecture Notes in Computer Science, pages 181--198. Springer-Verlag, 2007.
[8]
Gudjón Gudjónsson and William H. Winsborough. Compile-time memory reuse in logic programming languages through update in place. ACM Transactions on Programming Languages and Systems (TOPLAS), 21(3):430--501, 1999.
[9]
Jurriaan Hage, Stefan Holdermans, and Arie Middelkoop. A generic usage analysis with subeffect qualifiers. In Ralf Hinze and Norman Ramsey, editors, Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP 2007, Freiburg, Germany, October 1--3, 2007, pages 235--246. ACM Press, 2007.
[10]
Martin Hofmann. A type system for bounded space and functional in-place update. Nordic Journal of Computing, 7(4):258--289, 2000.
[11]
Martin Hofmann and Steffen Jost. Static prediction of heap space usage for first-order functional programs. In Conference Record of POPL 2003: The 30th SIGPLAN--SIGACT Symposium on Principles of Programming Languages, New Orleans, Louisiana, January 15--17, 2003, pages 185--197. ACM Press, 2003.
[12]
Thomas P. Jensen and Torben Æ. Mogensen. A backwards analysis for compile-time garbage collection. In Neil D. Jones, editor, sium on Programming, Copenhagen, Denmark, May 15--18, 1990, Proceedings, volume 432 of Lecture Notes in Computer Science, pages 227--239. Springer-Verlag, 1990. ESOP'90, 3rd European Symposium on Programming, Copenhagen, Denmark, May 15--18, 1990, Proceedings, volume 432 of Lecture Notes in Computer Science, pages 227--239. Springer-Verlag, 1990.
[13]
Mark P. Jones. Qualified Types: Theory and Practice. Cambridge University Press, Cambridge, 1994.
[14]
Simon B. Jones and Daniel Le Métayer. Compile-time garbage collection by sharing analysis. In FPCA '89 Conference on Functional Programming and Computer Architecture. Imperial College, London, England, 11--13 September 1989, pages 54--74. ACM Press, 1989.
[15]
John Launchbury. A natural semantics for lazy evaluation. In Conference Record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston, South Carolina, January 1993, pages 144--154. ACM Press, 1993.
[16]
John Launchbury and Simon Peyton Jones. State in Haskell. Lisp and Symbolic Computation, 8(4):293--341, 1995.
[17]
Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17(3):348--375, 1978.
[18]
Simon Peyton Jones, editor. Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, Cambridge, 2003.
[19]
Rinus Plasmeijer and Marco van Eekelen. Concurrent Clean language report--version 1.3. Technical Report CSI--R9816, University of Nijmegen, 1998.
[20]
Philip Wadler. Monads for functional programming. In Johan Jeuring and Erik Meijer, editors, Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques, Baestad, Sweden, May 24--30, 1995, Tutorial Text, volume 925 of Lecture Notes in Computer Science, pages 24--52. Springer-Verlag, 1995.

Cited By

View all
  • (2018)Extended Memory ReuseProceedings of the 30th Symposium on Implementation and Application of Functional Languages10.1145/3310232.3310242(107-118)Online publication date: 5-Sep-2018
  • (2015)Thunk recycling for lazy functional languagesProceedings of the 30th Annual ACM Symposium on Applied Computing10.1145/2695664.2695693(2079-2086)Online publication date: 13-Apr-2015
  • (2015)Polyvariant Cardinality Analysis for Non-strict Higher-order Functional LanguagesProceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation10.1145/2678015.2682536(139-142)Online publication date: 13-Jan-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PEPM '08: Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation
January 2008
214 pages
ISBN:9781595939777
DOI:10.1145/1328408
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 January 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. compile-time garbage collection
  2. lazy functional programming
  3. type-based program analysis

Qualifiers

  • Research-article

Conference

PEPM08
PEPM08: Partial Evaluation and Program Manipulation
January 7 - 8, 2008
California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)1
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2018)Extended Memory ReuseProceedings of the 30th Symposium on Implementation and Application of Functional Languages10.1145/3310232.3310242(107-118)Online publication date: 5-Sep-2018
  • (2015)Thunk recycling for lazy functional languagesProceedings of the 30th Annual ACM Symposium on Applied Computing10.1145/2695664.2695693(2079-2086)Online publication date: 13-Apr-2015
  • (2015)Polyvariant Cardinality Analysis for Non-strict Higher-order Functional LanguagesProceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation10.1145/2678015.2682536(139-142)Online publication date: 13-Jan-2015
  • (2010)Making "stricterness" more relevantProceedings of the 2010 ACM SIGPLAN workshop on Partial evaluation and program manipulation10.1145/1706356.1706379(121-130)Online publication date: 19-Jan-2010
  • (2010)Making "stricterness" more relevantHigher-Order and Symbolic Computation10.1007/s10990-011-9079-723:3(315-335)Online publication date: 1-Sep-2010
  • (2008)Uniqueness Typing SimplifiedImplementation and Application of Functional Languages10.1007/978-3-540-85373-2_12(201-218)Online publication date: 1-Apr-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media