Article

Free access

Let-floating: moving bindings to give faster programs

Authors:

Simon Peyton Jones,

André SantosAuthors Info & Claims

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

Pages 1 - 12

https://doi.org/10.1145/232627.232630

Published: 15 June 1996 Publication History

Abstract

Virtually every compiler performs transformations on the program it is compiling in an attempt to improve efficiency. Despite their importance, however, there have been few systematic attempts to categorise such transformations and measure their impact.In this paper we describe a particular group of transformations --- the "let-floating" transformations --- and give detailed measurements of their effect in an optimizing compiler for the non-strict functional language Haskell. Let-floating has not received much explicit attention in the past, but our measurements show that it is an important group of transformations (at least for lazy languages), offering a reduction of more than 30% in heap allocation and 15% in execution time.

References

[1]

AV Aho, R Sethi & JD Ullman {1986}, Compilers - principles, techniques and ~ools, Addison Wesley.

Digital Library

[2]

AW Appel {1992}, Compiling with continuations, Cambridge University Press.

Digital Library

[3]

Z Ariola, M Felleisen, J Maraist, M Odersky & P Wadler {Jan 1995}, "A call by need lambda calculus," in 21st ACM Symposium on Principles of Programming Languages, San Francisco, ACM.

Digital Library

[4]

DF Bacon, SL Graham gc OJ Sharp {Dec 1994}, "Compiler transformations for high-performance computing," ACM Computing Surveys 26, 345-420.

Digital Library

[5]

C Flanagan, A Sabry, B Duba & M Felleisen {June 1993}, "The essence of compiling with continuations," SIC- PLAN Notices 28, 237-247.

Digital Library

[6]

S Fortune, D Leivant & M O'Donnell{Jan 1983}, "The expressiveness of simple and second-order type structures,'' JACM 30, 151-185.

Digital Library

[7]

P Fradet gc D Le Metayer {Jan 1991}, "Compilation of functional languages by program transformation," A CM Transactions on Programming Languages and Systems 13, 21-51.

Digital Library

[8]

AJ Gill {Jan 1996}, "Cheap deforestation for non-strict functional languages," PhD thesis, Department of Computing Science, Glasgow University.

[9]

P Hudak, SL Peyton Jones, PL Wadler, Arvind, B Boutel, J Fairbairn, J Fasel, M Guzman, K Hammond, J Hughes, T Johnsson, R Kieburtz, RS Nikhil, W Partain &: J Peterson{May 1992}, "Report on the functional programming language HaskeI1, Version 1.2," SIGPLAN Notices 27.

[10]

RJM Hughes {July 1983}, "The design and implementation of programming languages," PhD thesis, Programming Research Group, Oxford.

[11]

R Kelsey {May 1989}, "Compilation by program transformation,'' YALEU/DCS/RR-702, PhD thesis, Department of Computer Science, Yale University.

Digital Library

[12]

R Kelsey 8e P Hudak {Jan 1989}, "Realistic compilation by program transformation," in Proc A CM Conference on Principles of Programming Languages, ACM, 281-292.

Digital Library

[13]

DA Kranz {May 1988}, "ORBIT- an optimising compiler for Scheme," PhD thesis, Department of Computer Science, Yale University.

Digital Library

[14]

DA Kranz, R Kelsey, J Rees, P Hudak, J Philbin & N Adams {1986}, "ORBIT - an optimising compiler for Scheme," in Proc SIGPLAN Symposium on Cornprier Construction, ACM.

Digital Library

[15]

J Launchbury {Jan 1993}, "A natural semantics for lazy evaluation,'' in 20th ACM Symposium on Principles of Programming Languages, Charleston, ACM, 144- 154.

Digital Library

[16]

WD Partain {1993}, "The nofib Benchmark Suite of Haskell Programs," in Functional Programming, Glasgow 1992, J Launchbury & PM Sansom, eds., Workshops in Computing, Springer Verlag, 195-202.

Digital Library

[17]

SL Peyton Jones {1987}, The Implemenia,ion of Functional Programming Languages, Prentice Hall.

Digital Library

[18]

SL Peyton Jones {Apr 1992}, "Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine," Journal of Functional Programming 2, 127-202.

[19]

SL Peyton Jones, CV Hall, K Hammond, WD Partain & PL Wadler {March 1993}, "The Glasgow Haskell compiler: a technical overview," in Proceedings of Joint Framework /or Information Technology Technical Conference, Keele, DTI/SERC, 249-257.

[20]

SL Peyton Jones gc J Launchbury{Sept 1991}, "Unboxed values as first class citizens," in Functional Programming Languages and Computer Architecture, Boston, Hughes, ed., LNCS 523, Springer Verlag, 636-666.

Digital Library

[21]

SL Peyton Jones ~ D Lester {May 1991}, "A modular fullylazy lambda lifter in HASKELL," Software - Practice and Experience 21,479-506.

Digital Library

[22]

SL Peyton Jones & WD Partain {1993}, "Measuring the effectiveness of a simple strictness analyser," in Funciional Programming, Glasgow 1993, K Hammond & JT O'Donnell, eds., Workshops in Computing, Springer Verlag, 201-220.

[23]

SL Peyton Jones & A Santos {1994}, "Compilation by transformation in the Glasgow Haskell Compiler," in Functional Programming, Glasgow 1994, K Hammond, DN Turner g~ PM Sansom, eds., Workshops in Computing, Springer Verlag, 184-204.

[24]

A Santos {Sept 1995}, "Compilation by transformation in non-strict functional languages," PhD thesis, Department of Computing Science, Glasgow University.

[25]

JE Smith {Oct 1988}, "Characterising computer performance with a single number," Communications of the A CM 31, 1202-1207.

Digital Library

Cited By

Freund THamdaoui YSpiwack AGuha A(2021)Union and intersection contracts are hard, actuallyProceedings of the 17th ACM SIGPLAN International Symposium on Dynamic Languages10.1145/3486602.3486767(1-11)Online publication date: 19-Oct-2021
https://dl.acm.org/doi/10.1145/3486602.3486767
Ertel SGoens AAdam JCastrillon JDubach CXue J(2018)Compiling for concise code and efficient I/OProceedings of the 27th International Conference on Compiler Construction10.1145/3178372.3179505(104-115)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3178372.3179505
Maurer LDownen PAriola ZPeyton Jones S(2017)Compiling without continuationsACM SIGPLAN Notices10.1145/3140587.306238052:6(482-494)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062380
Show More Cited By

Index Terms

Let-floating: moving bindings to give faster programs
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types
        Functional languages

Recommendations

Let-floating: moving bindings to give faster programs

Virtually every compiler performs transformations on the program it is compiling in an attempt to improve efficiency. Despite their importance, however, there have been few systematic attempts to categorise such transformations and measure their ...
Scala macros: let our powers combine!: on how rich syntax and static types work with metaprogramming
SCALA '13: Proceedings of the 4th Workshop on Scala

Compile-time metaprogramming has been proven immensely useful enabling programming techniques such as language virtualization, embedding of external domain-specific languages, self-optimization, and boilerplate generation among many others.

In the ...
Fast floating-point processing in Common Lisp

Lisp, one of the oldest higher-level programming languages, has rarely been used for fast numerical (floating-point) computation. We explore the benefits of Common Lisp, an emerging new language standard with some excellent implementations, for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

Copyright © 1996 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 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

SIGPLAN: ACM Special Interest Group on Programming Languages

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

59
Total Citations
View Citations
687
Total Downloads

Downloads (Last 12 months)122
Downloads (Last 6 weeks)20

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Freund THamdaoui YSpiwack AGuha A(2021)Union and intersection contracts are hard, actuallyProceedings of the 17th ACM SIGPLAN International Symposium on Dynamic Languages10.1145/3486602.3486767(1-11)Online publication date: 19-Oct-2021
https://dl.acm.org/doi/10.1145/3486602.3486767
Ertel SGoens AAdam JCastrillon JDubach CXue J(2018)Compiling for concise code and efficient I/OProceedings of the 27th International Conference on Compiler Construction10.1145/3178372.3179505(104-115)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3178372.3179505
Maurer LDownen PAriola ZPeyton Jones S(2017)Compiling without continuationsACM SIGPLAN Notices10.1145/3140587.306238052:6(482-494)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062380
Henriksen TSerup NElsman MHenglein FOancea C(2017)Futhark: purely functional GPU-programming with nested parallelism and in-place array updatesACM SIGPLAN Notices10.1145/3140587.306235452:6(556-571)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062354
Maurer LDownen PAriola ZPeyton Jones SCohen AVechev M(2017)Compiling without continuationsProceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3062341.3062380(482-494)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3062341.3062380
Henriksen TSerup NElsman MHenglein FOancea CCohen AVechev M(2017)Futhark: purely functional GPU-programming with nested parallelism and in-place array updatesProceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3062341.3062354(556-571)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3062341.3062354
Kowalski TAdamus R(2017)Optimisation of language-integrated queries by query unnestingComputer Languages, Systems and Structures10.1016/j.cl.2016.09.00247:P2(131-150)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.cl.2016.09.002
Sergey IVytiniotis DPeyton Jones S(2014)Modular, higher-order cardinality analysis in theory and practiceACM SIGPLAN Notices10.1145/2578855.253586149:1(335-347)Online publication date: 8-Jan-2014
https://dl.acm.org/doi/10.1145/2578855.2535861
Sergey IVytiniotis DPeyton Jones SJagannathan SSewell P(2014)Modular, higher-order cardinality analysis in theory and practiceProceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages10.1145/2535838.2535861(335-347)Online publication date: 11-Jan-2014
https://dl.acm.org/doi/10.1145/2535838.2535861
Wortmann PDuke D(2013)Causality of optimized HaskellACM SIGPLAN Notices10.1145/2578854.250378848:12(141-152)Online publication date: 23-Sep-2013
https://dl.acm.org/doi/10.1145/2578854.2503788
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten