research-article

Types are calling conventions

Authors:

Maximilian C. Bolingbroke,

Simon L. Peyton JonesAuthors Info & Claims

Haskell '09: Proceedings of the 2nd ACM SIGPLAN symposium on Haskell

Pages 1 - 12

https://doi.org/10.1145/1596638.1596640

Published: 03 September 2009 Publication History

Abstract

It is common for compilers to derive the calling convention of a function from its type. Doing so is simple and modular but misses many optimisation opportunities, particularly in lazy, higher-order functional languages with extensive use of currying. We restore the lost opportunities by defining Strict Core, a new intermediate language whose type system makes the missing distinctions: laziness is explicit, and functions take multiple arguments and return multiple results.

Supplementary Material

JPG File (typesarecallingconventionsonvimeo.jpg)

Download
20.76 KB

MP4 File (typesarecallingconventionsonvimeo.mp4)

Download
98.28 MB

References

[1]

A. P. Black, M. Carlsson, M. P. Jones, D. Kieburtz, and J. Nordlander. Timber: a programming language for real-time embedded systems. Technical Report CSE-02-002, Oregon Health&Science University, 2002.

Digital Library

[2]

S. Marlow and S. Peyton Jones. How to make a fast curry: push/enter vs eval/apply. In International Conference on Functional Programming, pages 4--15, September 2004.

[3]

J. Launchbury. A natural semantics for lazy evaluation. In Principles of Programming Languages, pages 144--154. ACM, January 1993.

Digital Library

[4]

S. Peyton Jones, W. D Partain, and A. Santos. Let-floating: moving bindings to give faster programs. In International Conference on Functional Programming, 1996.

Digital Library

[5]

S. Peyton Jones and John Launchbury. Unboxed values as first class citizens in a non-strict functional language. In Functional Programming Languages and Computer Architecture, pages 636--666. Springer, 1991.

Digital Library

[6]

M. Sulzmann, M. Chakravarty, S. Peyton Jones, and K. Donnelly. System F with type equality coercions. In ACM SIGPLAN International Workshop on Types in Language Design and Implementation (TLDI'07). ACM, 2007.

Digital Library

[7]

J. Girard. The system F of variable types, fifteen years later. Theoretical Computer Science, 45(2):159--192, 1986.

Digital Library

[8]

S. Peyton Jones and A. Santos. A transformation--based optimiser for Haskell. Science of Computer Programming, 32(1-3):3--47, September 1998.

Digital Library

[9]

A. Gill and G. Hutton. The worker/wrapper transformation. Journal of Functional Programming, 19(2):227--251, March 2009.

Digital Library

[10]

C. Baker-Finch, K. Glynn, and S. Peyton Jones. Constructed product result analysis for haskell. Journal of Functional Programming, 14(2):211--245, 2004.

Digital Library

[11]

N. Benton, A. Kennedy, and G. Russell. Compiling standard ML to Java bytecodes. In International Conference on Functional Programming, pages 129--140, New York, NY, USA, 1998. ACM.

Digital Library

[12]

M. Serrano and P. Weis. Bigloo: A portable and optimizing compiler for strict functional languages. In International Symposium on Static Analysis, pages 366--381, London, UK, 1995. Springer--Verlag.

Digital Library

[13]

A. Appel. Compiling with Continuations. Cambridge University Press, 1992.

Digital Library

[14]

S. Peyton Jones, M. Shields, J. Launchbury, and A. Tolmach. Bridging the gulf: a common intermediate language for ML and Haskell. In Principles of Programming Languages, pages 49--61, New York, NY, USA, 1998. ACM.

Digital Library

[15]

U. Boquist. Code Optimisation Techniques for Lazy Functional Languages. PhD thesis, Chalmers University of Technology, April 1999.

[16]

K. Faxen. Flow Inference, Code Generation, and Garbage Collection for Lazy Functional Languages. PhD thesis, KTH Royal Institute Of Technology, June 1997.

[17]

B. Rudiak-Gould, A. Mycroft, and S. Peyton Jones. Haskell is not not ML. In European Symposium on Programming, 2006.

Digital Library

[18]

J. Hannan and P. Hicks. Higher-order uncurrying. Higher Order Symbolic Computation, 13(3):179--216, 2000.

Digital Library

[19]

J. Hannan and P. Hicks. Higher-order arity raising. In International Conference on Functional Programming, pages 27--38, New York, NY, USA, 1998. ACM.

Digital Library

[20]

Z. Dargaye and X. Leroy. A verified framework for higher-order uncurrying optimizations. March 2009.

[21]

S. Peyton Jones. Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine. Journal of Functional Programming, 2:127--202, April 1992.

[22]

T. Altenkirch and N. Oury. PiSigma: A core language for dependently typed programming. 2008.

[23]

T. Brus, M. van Eekelen, M. van Leer, and M. Plasmeijer. Clean -- a language for functional graph rewriting. Functional Programming Languages and Computer Architecture, pages 364--384, 1987.

Digital Library

Cited By

Downen PSullivan ZAriola ZPeyton Jones SEisenberg R(2019)Making a faster Curry with extensional typesProceedings of the 12th ACM SIGPLAN International Symposium on Haskell10.1145/3331545.3342594(58-70)Online publication date: 8-Aug-2019
https://dl.acm.org/doi/10.1145/3331545.3342594
Ureche VBurmako EOdersky M(2014)Late data layoutACM SIGPLAN Notices10.1145/2714064.266019749:10(397-416)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660197
Ureche VBurmako EOdersky MBlack AMillstein T(2014)Late data layoutProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660197(397-416)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660197
Show More Cited By

Index Terms

Types are calling conventions
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types
        Functional languages

Recommendations

Kinds are calling conventions

A language supporting polymorphism is a boon to programmers: they can express complex ideas once and reuse functions in a variety of situations. However, polymorphism is pain for compilers tasked with producing efficient code that manipulates concrete ...
Making a faster Curry with extensional types
Haskell 2019: Proceedings of the 12th ACM SIGPLAN International Symposium on Haskell

Curried functions apparently take one argument at a time, which is slow. So optimizing compilers for higher-order languages invariably have some mechanism for working around currying by passing several arguments at once, as many as the function can ...
Double-Ended Bit-Stealing for Algebraic Data Types

Algebraic data types are central to the development and evaluation of most functional programs. It is therefore important for compilers to choose compact and efficient representations of such types, in particular to achieve good memory footprints for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Haskell '09: Proceedings of the 2nd ACM SIGPLAN symposium on Haskell

September 2009

148 pages

ISBN:9781605585086

DOI:10.1145/1596638

Program Chair:
Stephanie Weirich
University of Pennsylvania, USA

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 September 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP '09

Sponsor:

ICFP '09: ACM SIGPLAN International Conference on Functional Programming

September 3, 2009

Edinburgh, Scotland

Acceptance Rates

Overall Acceptance Rate 57 of 143 submissions, 40%

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

9
Total Citations
View Citations
344
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Downen PSullivan ZAriola ZPeyton Jones SEisenberg R(2019)Making a faster Curry with extensional typesProceedings of the 12th ACM SIGPLAN International Symposium on Haskell10.1145/3331545.3342594(58-70)Online publication date: 8-Aug-2019
https://dl.acm.org/doi/10.1145/3331545.3342594
Ureche VBurmako EOdersky M(2014)Late data layoutACM SIGPLAN Notices10.1145/2714064.266019749:10(397-416)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660197
Ureche VBurmako EOdersky MBlack AMillstein T(2014)Late data layoutProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660197(397-416)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660197
Liu HGlew NPetersen LAnderson T(2013)The Intel labs Haskell research compilerACM SIGPLAN Notices10.1145/2578854.250377948:12(105-116)Online publication date: 23-Sep-2013
https://dl.acm.org/doi/10.1145/2578854.2503779
Liu HGlew NPetersen LAnderson TShan C(2013)The Intel labs Haskell research compilerProceedings of the 2013 ACM SIGPLAN symposium on Haskell10.1145/2503778.2503779(105-116)Online publication date: 23-Sep-2013
https://dl.acm.org/doi/10.1145/2503778.2503779
Schrijvers TMycroft A(2010)Strictness meets data flowProceedings of the 17th international conference on Static analysis10.5555/1882094.1882121(439-454)Online publication date: 14-Sep-2010
https://dl.acm.org/doi/10.5555/1882094.1882121
Schrijvers TMycroft A(2010)Strictness Meets Data FlowStatic Analysis10.1007/978-3-642-15769-1_27(439-454)Online publication date: 2010
https://doi.org/10.1007/978-3-642-15769-1_27
Bergstrom LReppy J(2009)Arity raising in manticoreProceedings of the 21st international conference on Implementation and application of functional languages10.5555/1929087.1929093(90-106)Online publication date: 23-Sep-2009
https://dl.acm.org/doi/10.5555/1929087.1929093
Dijkstra AFokker JSwierstra SWeirich S(2009)The architecture of the Utrecht Haskell compilerProceedings of the 2nd ACM SIGPLAN symposium on Haskell10.1145/1596638.1596650(93-104)Online publication date: 3-Sep-2009
https://dl.acm.org/doi/10.1145/1596638.1596650

View Options

Get Access

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents