skip to main content
10.1145/2535838.2535887acmconferencesArticle/Chapter ViewAbstractPublication PagespoplConference Proceedingsconference-collections
research-article

Profiling for laziness

Published:08 January 2014Publication History

ABSTRACT

While many programmers appreciate the benefits of lazy programming at an abstract level, determining which parts of a concrete program to evaluate lazily poses a significant challenge for most of them. Over the past thirty years, experts have published numerous papers on the problem, but developing this level of expertise requires a significant amount of experience.

We present a profiling-based technique that captures and automates this expertise for the insertion of laziness annotations into strict programs. To make this idea precise, we show how to equip a formal semantics with a metric that measures waste in an evaluation. Then we explain how to implement this metric as a dynamic profiling tool that suggests where to insert laziness into a program. Finally, we present evidence that our profiler's suggestions either match or improve on an expert's use of laziness in a range of real-world applications.

Skip Supplemental Material Section

Supplemental Material

d2_right_t5.mp4

References

  1. H. Abelson, G. J. Sussman, and J. Sussman. Structure and Interpretation of Computer Programs. MIT Press, 1984. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. C. Barski. Land of Lisp. No Starch Press, 2011.Google ScholarGoogle Scholar
  3. S. Chang. Laziness by need. In Proc. 22nd ESOP, pages 81--100, 2013. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. C. Clack and S. L. Peyton Jones. Strictness analysis -- a practical approach. In Proc. 2nd FPCA, pages 35--49, 1985. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. R. Ennals and S. Peyton Jones. Optimistic evaluation: an adaptive evaluation strategy for non-strict programs. In Proc. 8th ICFP, pages 287--298, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. K.-F. Faxén. Cheap eagerness: speculative evaluation in a lazy functional language. In Proc. 5th ICFP, pages 150--161, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. M. Felleisen, R. B. Findler, and M. Flatt. Semantics Engineering with PLT Redex. MIT Press, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. R. B. Findler, S. Guo, and A. Rogers. Lazy contract checking for immutable data structures. In Proc. 19th IFL, pages 111--128, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. M. Flatt and PLT. Reference: Racket. Technical Report PLT-TR-2013-1, PLT Inc., 2013. http://racket-lang.org/tr1/.Google ScholarGoogle Scholar
  10. R. Hinze and R. Paterson. Finger trees: a simple general-purpose data structure. In J. Funct. Program., pages 197--217, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. P. Hudak, J. Hughes, S. P. Jones, and P. Wadler. A history of Haskell: being lazy with class. In Proc. 3rd HOPL, pages 12--1--12--55, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. J. Hughes. Why functional programming matters. Comp. J., 32:98--107, 1989. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. D. Leijen and E. Meijer. Parsec: direct style monadic parser combinators for the real world. TR UU-CS-2001-35, Utrecht University, 2001.Google ScholarGoogle Scholar
  14. J.-W. Maessen. Eager Haskell: resource-bounded execution yields efficient iteration. In Proc. Haskell Workshop, pages 38--50, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. F. Morandat, B. Hill, L. Osvald, and J. Vitek. Evaluating the design of the R language. In Proc. 26th ECOOP, pages 104--131, 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. A. Mycroft. Abstract interpretation and optimising transformations for applicative programs. PhD thesis, University of Edinburgh, 1981.Google ScholarGoogle Scholar
  17. C. Okasaki. Purely Functional Data Structures. Cambridge University Press, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. B. O'Sullivan, D. Stewart, and J. Goerzen. Real World Haskell. O'Reilly Media, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. G. D. Plotkin. Call-by-name, call-by-value and the λ-calculus. Theor. Comput. Sci., 1:125--159, 1975.Google ScholarGoogle ScholarCross RefCross Ref
  20. K. E. Schauser and S. C. Goldstein. How much non-strictness do lenient programs require? In Proc. 7th FPCA, pages 216--225, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. P. Wadler. How to replace failure by a list of successes. In Proc. 2nd FPCA, pages 113--128, 1985. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. G. Xu, N. Mitchell, M. Arnold, A. Rountev, E. Schonberg, and G. Sevitsky. Finding low-utility data structures. In Proc. 31st PLDI, pages 174--186, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Profiling for laziness

      Recommendations

      Comments

      Login options

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

      Sign in
      • Published in

        cover image ACM Conferences
        POPL '14: Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
        January 2014
        702 pages
        ISBN:9781450325448
        DOI:10.1145/2535838

        Copyright © 2014 ACM

        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 the author(s) 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: 8 January 2014

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • research-article

        Acceptance Rates

        POPL '14 Paper Acceptance Rate51of220submissions,23%Overall Acceptance Rate824of4,130submissions,20%

        Upcoming Conference

        POPL '25

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader