Article

Free access

Listlessness is better than laziness: Lazy evaluation and garbage collection at compile-time

Author:

Philip WadlerAuthors Info & Claims

LFP '84: Proceedings of the 1984 ACM Symposium on LISP and functional programming

Pages 45 - 52

https://doi.org/10.1145/800055.802020

Published: 06 August 1984 Publication History

PDF eReader

References

[1]

Backus, J. Can programming be liberated from the VonNeuman style? A functional style and its algebra of programs (Turing award lecture). Communications of the ACM, 21(8):613-641, August, 1978.

Digital Library

Google Scholar

[2]

Boyer, R. S., and Moore, J. S. Proving theorems about Lisp functions. Journal of the ACM, 22(1):129-144, January, 1975.

Digital Library

Google Scholar

[3]

Boyer, R. S., and Moore, J. S. A Computational Logic. Academic Press, New York, 1979.

Google Scholar

[4]

Burstall, R. M., and Darlington, J. A transformation system for developing recursive programs. Journal of the ACM, 24(1):44-67, January, 1977.

Digital Library

Google Scholar

[5]

Clark, K., and Darlington, J. Algorithm classification through synthesis. Computer Journal, 23(1):61-65, February, 1980.

Google Scholar

[6]

Feather, M. S. A system for assisting program transformation. ACM Transactions on Programming Languages and Systems, 4(1):1-20, January, 1982.

Digital Library

Google Scholar

[7]

Floyd, R. W. The paradigms of programming (Turing award lecture). Communications of the ACM, 22(8):455-460, August, 1979.

Digital Library

Google Scholar

[8]

Friedman, D. P., and Wise, D. S. Cons should not evaluate its arguments. In Michaelson and Milner (editors), Automata, Languages, and Programming, 257-284, Edinburgh University Press, 1976.

Google Scholar

[9]

Henderson, P., and Morris, J. H. A lazy evaluator. In 3'rd Symposium on Principals of Programming Languages, 95-103, ACM, Atlanta, GA, 1976.

Digital Library

Google Scholar

[10]

Hughes, J. M. The design and implementation of programming languages. D.Phil. Thesis, Oxford University, 1984.

Google Scholar

[11]

Kieburtz, R. B., and Schultis, J. Transformations of FP program schemes. In Conference on Functional Programming Languages and Computer Architecture, 41-48, ACM, October, 1981.

Digital Library

Google Scholar

[12]

Knuth, D. E. Structured programming with go to statements. ACM Computing Surveys, 6(4):261-302, December, 1974.

Digital Library

Google Scholar

[13]

Kowalski, R. Algorithm &equil; Logic + Control. Communications of the ACM, 22(7), July, 1979.

Digital Library

Google Scholar

[14]

Lesk, M. E. Lex - a lexical analyzer generator. Technical report, Bell Labs, Murray Hill, NJ, 1975.

Google Scholar

[15]

Manna, Z., and Waldinger, R. Synthesis: Dreams &equil;> Programs. IEEE Trans. Software Engineering, SE-5(4):157-164, July, 1979.

Google Scholar

[16]

Patterson, M. S., and Hewitt, C. E. Comparative schematology. Project MAC Conference on Concurrent Systems and Parallel Computation, Wood's Hole, MA, 1970. Also, AI Memo 21, AI Lab, MIT.

Digital Library

Google Scholar

[17]

Ritchie, D. M., and Thompson, K. L. The Unix time-sharing system. Communications of the ACM, 17(7), July, 1974.

Digital Library

Google Scholar

[18]

Scherlis, W. L. Program improvement by internal specialization. In 8'th Symposium on Principals of Programming Languages, 41-49, ACM, Williamsburg, VA, January, 1981.

Digital Library

Google Scholar

[19]

Steele, G. L., Jr. Debunking the expensive procedure call myth, or, Procedure call implementations considered harmful, or, LAMBDA: the ultimate goto. In Proc. ACM Annual Conference, 153-162, Seattle, WA, October 1977.

Digital Library

Google Scholar

[20]

Turner, D. A. Recursion equations as a programming language. In Darlington, et al (editors), Functional Programming and Its Applications, Cambridge University Press, 1981.

Google Scholar

[21]

Turchin, V. F., Nirenberg, R. M., and Turchin, D. V. Experiments with a supercompiler. ACM Symposium on Lisp and Functional Programming, Pittsburgh, PA, August, 1982.

Digital Library

Google Scholar

[22]

Wadler, P. L. Applicative style programming, program transformation, and list operators. In Conference on Functional Programming and Computer Architecture, 25-32, ACM, October, 1981.

Digital Library

Google Scholar

[23]

Wadler, P. L. Listlessness is better than laziness. PhD thesis, Carnegie-Mellon University, 1984.

Digital Library

Google Scholar

[24]

An improved Prolog implemenation which optimizes tail-recursion. Dept. of AI Research Report 141, University of Edinburgh, 1980.

Google Scholar

[25]

Waters, R. C. A method for analyzing loop programs. IEEE Trans. on Software Engineering, SE-5(3):237-247, May, 1979.

Digital Library

Google Scholar

Cited By

View all

Lorenzen ALeijen DSwierstra WLindley S(2024)The Functional Essence of Imperative Binary Search TreesProceedings of the ACM on Programming Languages10.1145/36563988:PLDI(518-542)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656398
Leijen DLorenzen A(2023)Tail Recursion Modulo Context: An Equational ApproachProceedings of the ACM on Programming Languages10.1145/35712337:POPL(1152-1181)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571233
DANVY O(2023)Folding left and right matters: Direct style, accumulators, and continuationsJournal of Functional Programming10.1017/S095679682200015633Online publication date: 14-Feb-2023
https://doi.org/10.1017/S0956796822000156
Show More Cited By

Index Terms

Listlessness is better than laziness: Lazy evaluation and garbage collection at compile-time
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Complete Laziness: a Natural Semantics

Lazy evaluation (or call-by-need) is widely used and well understood, partly thanks to a clear operational semantics given by Launchbury. However, modern non-strict functional languages do not use plain call-by-need evaluation: they also use ...
Laziness without all the hard work: combining lazy and strict languages for teaching
FDPE '05: Proceedings of the 2005 workshop on Functional and declarative programming in education

Students have trouble understanding the difference between lazy and strict programming. It is difficult to compare the two directly, because popular strict languages and popular lazy languages differ in their syntax, in their type systems, and in other ...
From functional logic programs to purely functional programs preserving laziness
IFL'08: Proceedings of the 20th international conference on Implementation and application of functional languages

Functional logic languages extend the setting of functional programming by non-deterministic choices, free variables and narrowing.

Most existing approaches to simulate logic features in functional languages do not preserve laziness, i.e., they can only ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

LFP '84: Proceedings of the 1984 ACM Symposium on LISP and functional programming

August 1984

364 pages

ISBN:0897911423

DOI:10.1145/800055

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: 06 August 1984

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 30 of 109 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
1,367
Total Downloads

Downloads (Last 12 months)166
Downloads (Last 6 weeks)29

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lorenzen ALeijen DSwierstra WLindley S(2024)The Functional Essence of Imperative Binary Search TreesProceedings of the ACM on Programming Languages10.1145/36563988:PLDI(518-542)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656398
Leijen DLorenzen A(2023)Tail Recursion Modulo Context: An Equational ApproachProceedings of the ACM on Programming Languages10.1145/35712337:POPL(1152-1181)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571233
DANVY O(2023)Folding left and right matters: Direct style, accumulators, and continuationsJournal of Functional Programming10.1017/S095679682200015633Online publication date: 14-Feb-2023
https://doi.org/10.1017/S0956796822000156
Gautier TLe Guernic PBesnard LTalpin J(2023)The polychronous model of computation and Kahn process networksScience of Computer Programming10.1016/j.scico.2023.102958228(102958)Online publication date: Jun-2023
https://doi.org/10.1016/j.scico.2023.102958
Pfenning FPruiksma K(2023)Relating Message Passing and Shared Memory, Proof-TheoreticallyCoordination Models and Languages10.1007/978-3-031-35361-1_1(3-27)Online publication date: 15-Jun-2023
https://doi.org/10.1007/978-3-031-35361-1_1
Zhang QLi HWan XSkitmore MSun H(2020)An Intelligent Waste Removal System for Smarter CommunitiesSustainability10.3390/su1217682912:17(6829)Online publication date: 22-Aug-2020
https://doi.org/10.3390/su12176829
Shaikhha ASchleich MGhita AOlteanu DMars JTang LXue JWu P(2020)Multi-layer optimizations for end-to-end data analyticsProceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3368826.3377923(145-157)Online publication date: 22-Feb-2020
https://dl.acm.org/doi/10.1145/3368826.3377923
Shaikhha AFitzgibbon APeyton Jones SVytiniotis DTrinder POancea C(2017)Destination-passing style for efficient memory managementProceedings of the 6th ACM SIGPLAN International Workshop on Functional High-Performance Computing10.1145/3122948.3122949(12-23)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3122948.3122949
O’Donnell JHall C(2016)Pointlessness is Better than ListlessnessA List of Successes That Can Change the World10.1007/978-3-319-30936-1_13(234-248)Online publication date: 25-Mar-2016
https://doi.org/10.1007/978-3-319-30936-1_13
Fisler KCutts QSimon BDorn B(2014)The recurring rainfall problemProceedings of the tenth annual conference on International computing education research10.1145/2632320.2632346(35-42)Online publication date: 28-Jul-2014
https://dl.acm.org/doi/10.1145/2632320.2632346
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

Complete Laziness: a Natural Semantics

Laziness without all the hard work: combining lazy and strict languages for teaching

From functional logic programs to purely functional programs preserving laziness