Article

Free access

Bridging the gulf: a common intermediate language for ML and Haskell

Authors:

Simon Peyton Jones,

John Launchbury,

Andrew TolmachAuthors Info & Claims

POPL '98: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 49 - 61

https://doi.org/10.1145/268946.268951

Published: 21 January 1998 Publication History

Abstract

Compilers for ML and Haskell use intermediate languages that incorporate deeply-embedded assumptions about order of evaluation and side effects. We propose an intermediate language into which one can compile both ML and Haskell, thereby facilitating the sharing of ideas and infrastructure, and supporting language developments that move each language in the direction of the other. Achieving this goal without compromising the ability to Compile as good code as a more direct route turned out to be much more subtle than we expected. We address this challenge using monads and unpointed types, identify two alternative language designs, and explore the choices they embody.

References

[1]

Z Ariola, M Felleisen, J Maraist, M Odersky & P Wadler {1995}, "A call by need lambda calculus,'~ in 22nd A CM Symposium on Principles of Programming Languages, San Erancisco, ACM, Jan 1995, 233-246.

Digital Library

[2]

N Benton & PL Wadler {1996}, ~Linear logict monads and the lambda calculus," in Proceedings of trio 11th IEEE Symposium on Logic in Computer Science, Brunswick, New Jersey, IEEE Press, July 1996.

Digital Library

[3]

M Blume & AW Appel {1997}, "Lambda-splitting: a higherorder approach to cross-module optimizution~s in Proc International Conference on Functional Programming~ Amsterdam~ ACM~ June 1997~ 112-124,

Digital Library

[4]

1% Cockett & T Fukushim~{1992}, "About Chazity," Tit 92/480/18, Department of Computer Science~ Un|- versity of Calgary, June 1992.

[5]

DP Friedman & DS Wise {1976}, "CONS should not evaluate its arguments," Automata, Langu, ge#~ and Programming~ July 1976, 257-281.

[6]

A Gill, J Launchbury & SL Peyton Jones I1993}, "A short cut to deforestation," in Proc Functional Programming Languages and Computer Architecture, Copenhagen, ACM, 3une 1993, 223-232.

Digital Library

[7]

3-Y Girard {1990}, "The System F of variable types: fifteen years later,~ in Logical Foundations of b'~nctional Programming, G ttuet, ed., Addison-Wesley, 1990.

Digital Library

[8]

T Hagino {1987}, '% Categorical Programming Language,'~ Phi) thesis, Department of Computer Science, University of Edinburgh, I987.

Digital Library

[9]

1% Harper & JC Mitchell {1993}, "On the type s~ructure of Standard ML," ACM Transact/o~s on Programruing Languages and Systems lJ(2), April 1993~ 21t-252.

Digital Library

[10]

tt Harper & G Morrisett {1995}, "Compiling polymorphism using intensional type anaiygs," in 22nd ACM Symposium on Principles of Programming Languages, San F~ancisco, ACM, Jan 1995, 130-141.

Digital Library

[11]

R Harper & C Stone ~1997}, "A type-theoretic semantics for Standard ML 1996," Department of Computer Science, Carnegie Mellon University~ 1997.

[12]

BT Howard{1996}, ~Inductive, co-inductive, and pointed types," in Proc International Conference on Phnc. tional Programming~ PhitadeJphia~ ACM~ May 1995.

Digital Library

[13]

MP Jones{t094}, "Dictionary-free overloading by par{~ial evaluation," in A GM SIGPLAN Workshop on Par. tiaI Evaluation and Semantics-Based Program Manipulation (PEPM), Orlando, Florida, ACM, 3un~ I994.

[14]

MP Jones {1998}, 'qIsing parameterized signatures to express modular structure," in 23rd ACM Symposium on Principles of Programming Languages, St Petersburg Beach, Florida, ACM, Jan 1996, 68-78.

Digital Library

[15]

R Jones {1992}, "Tail recursion without space leaks," Journal of Fanctional Programming 2{1), Jan 1992, 73-80.

[16]

J Lannchbury & G Baraki {1996}, ~{epresenting Demand by Partial Projections," Journal of Functional Programming 6(4), 1996.

[17]

J Launchbury & R Paterson {1996}, "Parametricity and unboxing with tmpointed types," in European Symposium on Programming (ESOP'96), LinkSping, Sweden, Springer Verlag LNCS 1058, Jan 1996.

Digital Library

[18]

J Launchbury & SL Peyton Jones {1995}, ~State in Haskell," Lisp and Symbolic Computation8(4), Dec 1995, 293-342.

Digital Library

[19]

X Leroy {1992}, ~Jnboxed objects and polymorphic t~ping,~ in 19~h ACM Symposium on Principles of Programming Languages, Albuquerque, ACM, Jan 1992.

Digital Library

[20]

R Milner & M Torte {1990}, The definition of Standard ML, MIT Press, 1990.

Digital Library

[21]

JC Mitchell & AR Meyer {1985}, "Second-order logical relations," in Logics of Programs, R Parikh, ed., Springer Verlag LNCS 193, 1985.

Digital Library

[22]

E Moggi {1991}, "Notions of computation and monads,~ Information and Computation93, 1991, 55-92.

Digital Library

[23]

C Okasaki {1996}, 'CPurely functional data structures," PhD thesis, CMU-CS-96-177, Department of Computer Science, Carnegie Mellon University, Sept 1996.

Digital Library

[24]

J Paterson, K Hammond, L Augnstsson, B Boutel, W Burton, J Fasel, AD Gordon, RJM Hughes, P Hudak, T Johnsson, MP Jones, E Meijer, SL Peyton Jones, A Reid & PL Wadler {1997}, '~HaskelI 1.4: a non-strict, purely functional language," Available at http://- haskell.org, April 1997.

[25]

SL Peyton Jones {1996}, "Compilation by transformation: a report from the trenches," in European Symposi,m on Programming (ESOP'96), Link6ping, Sweden, Springer Verlag LNCS 1058, Jan 1996, 18-44.

Digital Library

[26]

SL Peyton Jones, AJ Gordon & SO Finne{1996}, "Concurrent Haskell," in 23rd A CM Symposium on Principles of Programming Languages, St Petersburg Beach, Florida, ACM, Jan 1996, 295-308.

Digital Library

[27]

SL Peyton Jones & J Launchbury{1991}, "Unboxed values as first class citizens," in Fanctional Programming Languages and Computer Architecture (FPGA'91), Boston, Hughes, ed., LNCS 523, Springer Verlag, Sept 1991, 636-666.

Digital Library

[28]

SL Peyton Jones & E Meijer {1997}, "Henk: a typed intermediate language," in ACM Workshop on Types in Compilation, Amsterdam, 1% Harper & R Muller, eds., June 1997.

[29]

SL Peyton Jones, WE) Partain & A Santos{1996}, "Letfloating: moving bindings to give faster progrmns," in Proe International ConFerence on Functional Programming, Philadelphia, ACM, May 1996.

Digital Library

[30]

SL Peyton Jones & PL Wadler{1993}, "Imperative functional programming," in 20th'ACM Symposium on Principles of Programming Languages (POPL'93), Charleston, ACM, Jan 1993, 71-84.

Digital Library

[31]

AM Pitts {1996}, 'T~elational properties of domains," Information and Computation 127, 1996, 66-90.

[32]

JC Reynolds{1983}, ~Types, abstraction and parametric polymorphism," in Information Processing 83, I~A Mason, ed., North-Holland, 1983, 513-523.

[33]

A Sabry{1997}, '~hat is a purely functional language," Journal of Fanctional Programming(to appear), 1997.

Digital Library

[34]

A Sabry & PL Wadler {1996}, "A reflection on call-by-value," in Proc International Conference on Functional Programming, Philadelphia, ACM, May 1996, 13- 24.

Digital Library

[35]

Z Shao {1997a}, '~Flexible representation analysis,~ in Proc International Conference on Fhnctional Programruing, Amsterdam, ACM, June 1997.

Digital Library

[36]

Z Shao {1997b}, "An Overview of the FLINT/ML compiler," in ACM Workshop on Types in Compilation, Amsterdam, R Harper & 1% Muller, ads., June 1997.

[37]

Z Shao & AW Appd{1995}, ~'A type-based compiler for Standard ML," in SIGPLAN Symposium on Programming Language Design and Implementation (PLDI'95), La Jolla, ACM, June 1995, 116-129.

Digital Library

[38]

D Tarditi, G Morrisett, P Chang, C Stone, R Harper & P Lee {1996}, 'q'IL: A Type-Directed Optimizing Compiler for ML," in SIGPLAN Sympos/um on Programming Language Design and Implementation (PIy, DI'96), Philadelphia, ACM, May 1996.

Digital Library

[39]

M Torte {1990}, "Type inference for polymorphic references," Information and Computation89(1), Nov 1990.

Digital Library

[40]

A Tolmach & D Oliva{1997}, "From ML to Ada(!?!)," Department of Computer Science and Engineering, Oregon Graduate Institute (and submitted to Journal of Functional Programming), 1997.

[41]

DA Turner {1995}, "Elementary strong functional programming," in Fhnctional Programming Languages in Education, Nigmegen, Springer Verlag LNCS 1022, Dec 1995.

Digital Library

[42]

PL Wadler {I989}, "Theorems for free!:~ in Fourth In~erna- $ional Conference on Fanc~lonal Progra~mi, g and Computer Architecture, London, MacQueen, ed., Addison Wesley, 1989.

Digital Library

[43]

PL Wadler{1992a}, "Comprehending monads," Mathematical Structures in Computer Science 2, 1992, 461- 493.

[44]

PL Wadler{1992b}, ~The essence of functional programming," in 19th ACM Symposium on Prindples of Programming Languages, Albuquerque, ACM, Jan 1992, 1-14.

Digital Library

Cited By

Prott KTeegen FChristiansen J(2023)Embedding Functional Logic Programming in Haskell via a Compiler PluginPractical Aspects of Declarative Languages10.1007/978-3-031-24841-2_3(37-55)Online publication date: 8-Jan-2023
https://doi.org/10.1007/978-3-031-24841-2_3
Hanus MPrott KTeegen F(2022)A Monadic Implementation of Functional Logic ProgramsProceedings of the 24th International Symposium on Principles and Practice of Declarative Programming10.1145/3551357.3551370(1-15)Online publication date: 20-Sep-2022
https://dl.acm.org/doi/10.1145/3551357.3551370
Bolingbroke MPeyton Jones SWeirich S(2009)Types are calling conventionsProceedings of the 2nd ACM SIGPLAN symposium on Haskell10.1145/1596638.1596640(1-12)Online publication date: 3-Sep-2009
https://dl.acm.org/doi/10.1145/1596638.1596640
Show More Cited By

Index Terms

Bridging the gulf: a common intermediate language for ML and Haskell
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
        Polymorphism
      2. Language types
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Type structures

Recommendations

Bridging AOP to SMP: turning GCC into a metalanguage preprocessor
SAC '05: Proceedings of the 2005 ACM symposium on Applied computing

This article presents an strategy to combine important software engineering techniques, Static Metaprogramming (SMP) and generic Programming (GP) with Aspect Oriented Programming (AOP). These rely on specific language tools that, today, cannot be ...
Layout-sensitive language extensibility with SugarHaskell
Haskell '12: Proceedings of the 2012 Haskell Symposium

Programmers need convenient syntax to write elegant and concise programs. Consequently, the Haskell standard provides syntactic sugar for some scenarios (e.g., do notation for monadic code), authors of Haskell compilers provide syntactic sugar for more ...
Bridging the Gap Between Object-Oriented and Logic Programming

A description is given of an interface that was developed between Loops and Xerox Quintus Prolog. Loops is an extension to the Xerox AI environment to support object-oriented programming; Xerox Quintus Prolog is a version of Prolog that runs on Xerox ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '98: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 1998

403 pages

ISBN:0897919793

DOI:10.1145/268946

Chairmen:
David B. MacQueen
Bell Labs
,
Luca Cardelli
Digital Equipment Corp.

Copyright © 1998 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: 21 January 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL98

Sponsor:

POPL98: Symposium on Principles of Programming Languages

January 19 - 21, 1998

California, San Diego, USA

Acceptance Rates

POPL '98 Paper Acceptance Rate 32 of 175 submissions, 18%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
117
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)7

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Prott KTeegen FChristiansen J(2023)Embedding Functional Logic Programming in Haskell via a Compiler PluginPractical Aspects of Declarative Languages10.1007/978-3-031-24841-2_3(37-55)Online publication date: 8-Jan-2023
https://doi.org/10.1007/978-3-031-24841-2_3
Hanus MPrott KTeegen F(2022)A Monadic Implementation of Functional Logic ProgramsProceedings of the 24th International Symposium on Principles and Practice of Declarative Programming10.1145/3551357.3551370(1-15)Online publication date: 20-Sep-2022
https://dl.acm.org/doi/10.1145/3551357.3551370
Bolingbroke MPeyton Jones SWeirich S(2009)Types are calling conventionsProceedings of the 2nd ACM SIGPLAN symposium on Haskell10.1145/1596638.1596640(1-12)Online publication date: 3-Sep-2009
https://dl.acm.org/doi/10.1145/1596638.1596640
Lippmeier B(2009)Witnessing Purity, Constancy and MutabilityProceedings of the 7th Asian Symposium on Programming Languages and Systems10.1007/978-3-642-10672-9_9(95-110)Online publication date: 3-Dec-2009
https://dl.acm.org/doi/10.1007/978-3-642-10672-9_9
Meijer E(2007)Confessions of a used programming language salesmanACM SIGPLAN Notices10.1145/1297105.129707842:10(677-694)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1145/1297105.1297078
Meijer EGabriel RBacon DLopes CSteele G(2007)Confessions of a used programming language salesmanProceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applications10.1145/1297027.1297078(677-694)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1145/1297027.1297078
Voigtländer JJohann P(2007)Selective strictness and parametricity in structural operational semantics, inequationallyTheoretical Computer Science10.1016/j.tcs.2007.09.014388:1-3(290-318)Online publication date: 1-Dec-2007
https://dl.acm.org/doi/10.1016/j.tcs.2007.09.014
Johann PVoigtländer J(2006)The Impact of seq on Free Theorems-Based Program TransformationsFundamenta Informaticae10.5555/2367480.236748869:1-2(63-102)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.5555/2367480.2367488
Shao ZTrifonov V(2006)Type-directed continuation allocationTypes in Compilation10.1007/BFb0055515(116-135)Online publication date: 28-May-2006
https://doi.org/10.1007/BFb0055515
Tolmach A(2006)Optimizing ML using a hierarchy of monadic typesTypes in Compilation10.1007/BFb0055514(97-115)Online publication date: 28-May-2006
https://doi.org/10.1007/BFb0055514
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents