More Web Proxy on the site http://driver.im/

research-article

Multi-stage programs in context

Authors:

Matthew Pickering,

Csongor KissAuthors Info & Claims

Haskell 2019: Proceedings of the 12th ACM SIGPLAN International Symposium on Haskell

Pages 71 - 84

https://doi.org/10.1145/3331545.3342597

Published: 08 August 2019 Publication History

Abstract

Cross-stage persistence is an essential aspect of multi-stage programming that allows a value defined in one stage to be available in another. However, difficulty arises when implicit information held in types, type classes and implicit parameters needs to be persisted. Without a careful treatment of such implicit information---which are pervasive in Haskell---subtle yet avoidable bugs lurk beneath the surface.

This paper demonstrates that in multi-stage programming care must be taken when representing quoted terms so that important implicit information is kept in context and not discarded. The approach is formalised with a type-system, and an implementation in GHC is presented that fixes problems of the previous incarnation.

References

[1]

Cristiano Calcagno, Walid Taha, Liwen Huang, and Xavier Leroy. 2003. Implementing multi-stage languages using ASTs, Gensym, and reflection. In Proceedings of the 2nd international conference on Generative programming and component engineering (GPCE03). Association for Computing Machinery, 57–76.

Digital Library

[2]

Luis Damas and Robin Milner. 1982. Principal type-schemes for functional programs. In Symposium on Principles of Programming Languages (POPL ’82). ACM.

Digital Library

[3]

Richard A Eisenberg, Stephanie Weirich, and Hamidhasan G Ahmed. 2016. Visible type application. In European Symposium on Programming. Springer, 229–254.

Digital Library

[4]

Jeff Epstein, Andrew P. Black, and Simon Peyton Jones. 2011. Towards Haskell in the Cloud. In Proceedings of the 4th ACM Symposium on Haskell (Haskell ’11). ACM, New York, NY, USA, 118–129.

Digital Library

[5]

Oleg Kiselyov. 2014. The Design and Implementation of BER MetaO-Caml. In Functional and Logic Programming, Michael Codish and Eijiro Sumii (Eds.). Springer International Publishing, Cham, 86–102.

[6]

Oleg Kiselyov. 2018. Reconciling Abstraction with High Performance: A MetaOCaml approach. Foundations and Trends in Programming Languages 5, 1 (2018), 1–101.

Digital Library

[7]

Jeffrey R. Lewis, John Launchbury, Erik Meijer, and Mark B. Shields. 2000. Implicit Parameters: Dynamic Scoping with Static Types. In Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’00). ACM, New York, NY, USA, 108– 118.

Digital Library

[8]

Simon Marlow and Simon Peyton Jones. 2012. The Glasgow Haskell Compiler. In The Architecture of Open Source Applications, Amy Brown and Greg Wilson (Eds.). Chapter 5. https://www.aosabook.org/en/ghc. html

[9]

Martin Odersky, Eugene Burmako, and Dmytro Petrashko. 2016. A TASTY Alternative. (2016). http://infoscience.epfl.ch/record/226194

[10]

Simon Peyton Jones, Mark Jones, and Erik Meijer. 1997. Type classes: an exploration of the design space. In Haskell Workshop.

[11]

Simon Peyton Jones, Stephanie Weirich, Richard A Eisenberg, and Dimitrios Vytiniotis. 2016. A reflection on types. In A List of Successes That Can Change the World. Springer, 292–317.

[12]

Matthew Pickering, Nicolas Wu, and Boldizsár Németh. 2019. Working with Source Plugins. In Proceedings of the 2019 ACM SIGPLAN Symposium on Haskell (Haskell ’19). ACM, New York, NY, USA.

Digital Library

[13]

Evgeny Roubinchtein. 2015. IR-MetaOCaml: (re)implementing MetaO-Caml. Master’s thesis. University of British Columbia.

[14]

Alejandro Serrano, Jurriaan Hage, Dimitrios Vytiniotis, and Simon Peyton Jones. 2018. Guarded Impredicative Polymorphism. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2018). ACM, New York, NY, USA, 783–796.

Digital Library

[15]

Tim Sheard and Simon Peyton Jones. 2002. Template Metaprogramming for Haskell. In Proceedings of the 2002 ACM SIGPLAN Workshop on Haskell (Haskell ’02). ACM, New York, NY, USA, 1–16.

Digital Library

[16]

Nicolas Stucki, Aggelos Biboudis, and Martin Odersky. 2018. A Practical Unification of Multi-stage Programming and Macros. In Proceedings of the 17th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (GPCE 2018). ACM, New York, NY, USA, 14–27.

Digital Library

[17]

Walid Taha. 2004. A Gentle Introduction to Multi-stage Programming. Springer Berlin Heidelberg, Berlin, Heidelberg, 30–50.

[18]

Walid Taha and Tim Sheard. 2000. MetaML and multi-stage programming with explicit annotations. Theor. Comput. Sci. 248, 1-2 (2000), 211–242.

Digital Library

[19]

Alec Theriault. 2019. Levity polymorphic lift. GHC proposal. https: //github.com/ghc-proposals/ghc-proposals/pull/209

[20]

Dimitrios Vytiniotis, Simon Peyton Jones, Tom Schrijvers, and Martin Sulzmann. 2011. OutsideIn(X) Modular Type Inference with Local Assumptions. J. Funct. Program. 21, 4-5 (Sept. 2011), 333–412.

Digital Library

[21]

Phillip Wadler and Stephen Blott. 1989. How to Make Ad-hoc Polymorphism Less Ad Hoc. In Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’89). ACM, New York, NY, USA, 60–76.

Digital Library

[22]

Thomas Winant, Jesper Cockx, and Dominique Devriese. 2017. Expressive and Strongly Type-safe Code Generation. In Proceedings of the 19th International Symposium on Principles and Practice of Declarative Programming (PPDP ’17). ACM, New York, NY, USA, 199–210.

Digital Library

Cited By

Lubbers MKoopman PPlasmeijer R(2022)First-Class Data Types in Shallow Embedded Domain-Specific Languages using MetaprogrammingProceedings of the 34th Symposium on Implementation and Application of Functional Languages10.1145/3587216.3587219(1-12)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3587216.3587219
Xie NPickering MLöh AWu NYallop JWang M(2022)Staging with class: a specification for typed template HaskellProceedings of the ACM on Programming Languages10.1145/34987236:POPL(1-30)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498723
Frolich Dvan Binsbergen L(2021)A Generic Back-End for Exploratory ProgrammingTrends in Functional Programming10.1007/978-3-030-83978-9_2(24-43)Online publication date: 23-Aug-2021
https://doi.org/10.1007/978-3-030-83978-9_2
Show More Cited By

Index Terms

Multi-stage programs in context
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Preprocessors
      2. Source code generation
    2. General programming languages
      1. Language types
        Functional languages

Recommendations

Almost first-class language embedding: taming staged embedded DSLs
GPCE 2015: Proceedings of the 2015 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences

Embedded domain-specific languages (EDSLs), inheriting a general-purpose language's features as well as look-and-feel, have traditionally been second-class or rather non-citizens in terms of host-language design. This makes sense when one regards them ...
Asynchronous sessions with implicit functions and messages
Abstract
Session types are a well-established approach to ensuring protocol conformance and the absence of communication errors such as deadlocks in message passing systems. Haskell introduced implicit parameters, Scala popularised this feature ...
Highlights
- We introduce a new feature for concurrent programming languages: Implicit Messages.
Staging with control: type-safe multi-stage programming with control operators
GPCE 2017: Proceedings of the 16th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences

Staging allows a programmer to write domain-specific, custom code generators. Ideally, a programming language for staging provides all necessary features for staging, and at the same time, gives static guarantee for the safety properties of generated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Haskell 2019: Proceedings of the 12th ACM SIGPLAN International Symposium on Haskell

August 2019

175 pages

ISBN:9781450368131

DOI:10.1145/3331545

Program Chair:
Richard A. Eisenberg

Copyright © 2019 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: 08 August 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP '19

Sponsor:

SIGPLAN

ICFP '19: ACM SIGPLAN International Conference on Functional Programming

August 22 - 23, 2019

Berlin, Germany

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

5
Total Citations
View Citations
146
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)2

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lubbers MKoopman PPlasmeijer R(2022)First-Class Data Types in Shallow Embedded Domain-Specific Languages using MetaprogrammingProceedings of the 34th Symposium on Implementation and Application of Functional Languages10.1145/3587216.3587219(1-12)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3587216.3587219
Xie NPickering MLöh AWu NYallop JWang M(2022)Staging with class: a specification for typed template HaskellProceedings of the ACM on Programming Languages10.1145/34987236:POPL(1-30)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498723
Frolich Dvan Binsbergen L(2021)A Generic Back-End for Exploratory ProgrammingTrends in Functional Programming10.1007/978-3-030-83978-9_2(24-43)Online publication date: 23-Aug-2021
https://doi.org/10.1007/978-3-030-83978-9_2
van Binsbergen LVerano Merino MJeanjean Pvan der Storm TCombemale BBarais OKell SVerna D(2020)A principled approach to REPL interpretersProceedings of the 2020 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3426428.3426917(84-100)Online publication date: 18-Nov-2020
https://dl.acm.org/doi/10.1145/3426428.3426917
Pickering MLöh AWu NSchrijvers T(2020)Staged sums of productsProceedings of the 13th ACM SIGPLAN International Symposium on Haskell10.1145/3406088.3409021(122-135)Online publication date: 27-Aug-2020
https://dl.acm.org/doi/10.1145/3406088.3409021

View Options

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