Article

Free access

A composition approach to time analysis of first order lazy functional programs

Authors:

FPCA '89: Proceedings of the fourth international conference on Functional programming languages and computer architecture

Pages 157 - 165

https://doi.org/10.1145/99370.99382

Published: 01 November 1989 Publication History

PDF eReader

References

[1]

G~rard Berry. Stable models of typed lambda-calculi. In Proc. 5th Coll. on Automata Langages and Programming, LNCS 62, Springer Verlag, 1978.

Digital Library

Google Scholar

[2]

Bror Bjerner. Time Compleziiy of Programs in Type Theory. Ph.D. thesis, Dept. of Computer Science, University of GSteborg, G5teborg, Sweden, January 1989.

Google Scholar

[3]

Per Martin-L5f. Constructive Mathematics and Computer Programming. In Logic, Methodology and Philosophy of Science, V}, 1979, pages 153-175, North-Holland, 1982.

Google Scholar

[4]

Philip Wadler. Strictness Analysis Aids Time Analysis. Technical Report, Oxford University, England, July 1987.

Google Scholar

[5]

Ben Wegbreit. Mechanical Program Analysis. Comm. A CM, 18,9:528-539, 1975.

Digital Library

Google Scholar

Cited By

View all

Xia LIsrael LKramarz MColtharp NClaessen KWeirich SLi Y(2024)Story of Your Lazy Function’s Life: A Bidirectional Demand Semantics for Mechanized Cost Analysis of Lazy ProgramsProceedings of the ACM on Programming Languages10.1145/36746268:ICFP(30-63)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674626
Hackett JHutton G(2019)Call-by-need is clairvoyant call-by-valueProceedings of the ACM on Programming Languages10.1145/33417183:ICFP(1-23)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341718
Handley MHutton G(2019)Improving HaskellTrends in Functional Programming10.1007/978-3-030-18506-0_6(114-135)Online publication date: 24-Apr-2019
https://doi.org/10.1007/978-3-030-18506-0_6
Show More Cited By

Index Terms

A composition approach to time analysis of first order lazy functional programs
1. Theory of computation

Recommendations

Automatic amortised analysis of dynamic memory allocation for lazy functional programs
ICFP '12: Proceedings of the 17th ACM SIGPLAN international conference on Functional programming

This paper describes the first successful attempt, of which we are aware, to define an automatic, type-based static analysis of resource bounds for lazy functional programs. Our analysis uses the automatic amortisation approach developed by Hofmann and ...
Flow analysis of lazy higher-order functional programs

In recent years much interest has been shown in a class of functional languages including HASKELL, lazy ML, SASL/KRC/MIRANDA, ALFL, ORWELL, and PONDER. It has been seen that their expressive power is great, programs are compact, and program manipulation ...
Automatic amortised analysis of dynamic memory allocation for lazy functional programs
ICFP '12

This paper describes the first successful attempt, of which we are aware, to define an automatic, type-based static analysis of resource bounds for lazy functional programs. Our analysis uses the automatic amortisation approach developed by Hofmann and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FPCA '89: Proceedings of the fourth international conference on Functional programming languages and computer architecture

November 1989

395 pages

ISBN:0897913280

DOI:10.1145/99370

Chairman:
Joseph E. Stoy

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: 01 November 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

FPCA89

Sponsor:

SIGPLAN
IFIP WG 2.8
SIGARCH

FPCA89: The International Conference on Functional Programming Languages & Computer Architectures

September 11 - 13, 1989

Imperial College, London, United Kingdom

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
557
Total Downloads

Downloads (Last 12 months)88
Downloads (Last 6 weeks)3

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Xia LIsrael LKramarz MColtharp NClaessen KWeirich SLi Y(2024)Story of Your Lazy Function’s Life: A Bidirectional Demand Semantics for Mechanized Cost Analysis of Lazy ProgramsProceedings of the ACM on Programming Languages10.1145/36746268:ICFP(30-63)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674626
Hackett JHutton G(2019)Call-by-need is clairvoyant call-by-valueProceedings of the ACM on Programming Languages10.1145/33417183:ICFP(1-23)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341718
Handley MHutton G(2019)Improving HaskellTrends in Functional Programming10.1007/978-3-030-18506-0_6(114-135)Online publication date: 24-Apr-2019
https://doi.org/10.1007/978-3-030-18506-0_6
Simões HVasconcelos PFlorido MJost SHammond K(2012)Automatic amortised analysis of dynamic memory allocation for lazy functional programsACM SIGPLAN Notices10.1145/2398856.236457547:9(165-176)Online publication date: 9-Sep-2012
https://dl.acm.org/doi/10.1145/2398856.2364575
Simões HVasconcelos PFlorido MJost SHammond KThiemann PFindler R(2012)Automatic amortised analysis of dynamic memory allocation for lazy functional programsProceedings of the 17th ACM SIGPLAN international conference on Functional programming10.1145/2364527.2364575(165-176)Online publication date: 9-Sep-2012
https://dl.acm.org/doi/10.1145/2364527.2364575
Seidel DVoigtländer J(2011)Improvements for FreeElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.57.757(89-103)Online publication date: 4-Jul-2011
https://doi.org/10.4204/EPTCS.57.7
Trinder PCole MHammond KLoidl HMichaelson G(2011)Resource analyses for parallel and distributed coordinationConcurrency and Computation: Practice and Experience10.1002/cpe.189825:3(309-348)Online publication date: 22-Dec-2011
https://doi.org/10.1002/cpe.1898
Danielsson N(2008)Lightweight semiformal time complexity analysis for purely functional data structuresACM SIGPLAN Notices10.1145/1328897.132845743:1(133-144)Online publication date: 7-Jan-2008
https://dl.acm.org/doi/10.1145/1328897.1328457
Danielsson NNecula GWadler P(2008)Lightweight semiformal time complexity analysis for purely functional data structuresProceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/1328438.1328457(133-144)Online publication date: 7-Jan-2008
https://dl.acm.org/doi/10.1145/1328438.1328457
Ghica D(2005)Slot gamesACM SIGPLAN Notices10.1145/1047659.104031340:1(85-97)Online publication date: 12-Jan-2005
https://dl.acm.org/doi/10.1145/1047659.1040313
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

Automatic amortised analysis of dynamic memory allocation for lazy functional programs

Flow analysis of lazy higher-order functional programs

Automatic amortised analysis of dynamic memory allocation for lazy functional programs