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

research-article

Modular reifiable matching: a list-of-functors approach to two-level types

Authors:

Bruno C. d. S. Oliveira,

Shu-Hung YouAuthors Info & Claims

Haskell '15: Proceedings of the 2015 ACM SIGPLAN Symposium on Haskell

Pages 82 - 93

https://doi.org/10.1145/2804302.2804315

Published: 30 August 2015 Publication History

Abstract

This paper presents Modular Reifiable Matching (MRM): a new approach to two level types using a fixpoint of list-of-functors representation. MRM allows the modular definition of datatypes and functions by pattern matching, using a style similar to the widely popular Datatypes a la Carte (DTC) approach. However, unlike DTC, MRM uses a fixpoint of list-of-functors approach to two-level types. This approach has advantages that help with various aspects of extensibility, modularity and reuse. Firstly, modular pattern matching definitions are collected using a list of matches that is fully reifiable. This allows for extensible pattern matching definitions to be easily reused/inherited, and particular matches to be overridden. Such flexibility is used, among other things, to implement extensible generic traversals. Secondly, the subtyping relation between lists of functors is quite simple, does not require backtracking, and is easy to model in languages like Haskell. MRM is implemented as a Haskell library, and its use and applicability are illustrated through various examples in the paper.

References

[1]

K. Y. Ahn and T. Sheard. Shared subtypes: subtyping recursive parametrized algebraic data types. In Symposium on Haskell, pages 75–86, 2008.

Digital Library

[2]

E. Axelsson. A generic abstract syntax model for embedded languages. In ICFP ’12, pages 323–334. ACM, 2012.

Digital Library

[3]

P. Bahr. Composing and decomposing data types: a closed type families implementation of data types à la carte. In WGP ’14, pages 71–82. ACM, 2014.

Digital Library

[4]

P. Bahr and T. Hvitved. Compositional data types. In Workshop on Generic Programming, WGP ’11, pages 83–94, 2011.

Digital Library

[5]

E. Brady. Programming and reasoning with algebraic effects and dependent types. In ICFP ’13, pages 133–144. ACM, 2013.

Digital Library

[6]

B. Bringert and A. Ranta. A pattern for almost compositional functions. In ICFP ’06, pages 216–226. ACM, 2006.

Digital Library

[7]

J. Cheney. Scrap your nameplate. In ICFP ’05, 2005.

Digital Library

[8]

B. C. d. S. Oliveira. Modular visitor components: A practical solution to the expression families problem. In ECOOP ’09, July 2009.

Digital Library

[9]

B. Delaware, B. C. d. S. Oliveira, and T. Schrijvers. Meta-theory à la carte. In POPL ’13, 2013.

Digital Library

[10]

R. A. Eisenberg, D. Vytiniotis, S. Peyton Jones, and S. Weirich. Closed type families with overlapping equations. In POPL ’14, 2014.

Digital Library

[11]

M. Erwig and D. Ren. Monadification of functional programs. Science of Computer Programming, 52(1-3):101–129, 2004.

Digital Library

[12]

J. Garrigue. Programming with polymorphic variants. ACM SIGPLAN Workshop on ML, 1998.

[13]

M. Hyland, G. Plotkin, and J. Power. Combining effects: sum and tensor. Theoretical Computer Science, 357(1-3):70–99, 2006.

Digital Library

[14]

O. Kiselyov, A. Sabry, and C. Swords. Extensible effects: an alternative to monad transformers. In Symposium on Haskell, pages 59–70. ACM, 2013.

Digital Library

[15]

R. Lämmel and S. Peyton Jones. Scrap your boilerplate: a practical approach to generic programming. In TLDI ’03, pages 26–37. ACM, 2003.

Digital Library

[16]

R. Lämmel and S. Peyton Jones. Scrap your boilerplate: A practical design pattern for generic programming. In TLDI’03, 2003.

Digital Library

[17]

R. Lämmel and S. Peyton Jones. Scrap more boilerplate: Reflection, zips, and generalised casts. In ICFP ’04, 2004.

Digital Library

[18]

R. Lämmel and S. Peyton Jones. Scrap your boilerplate with class: Extensible generic functions. In ICFP ’05, pages 204–215. ACM, 2005.

Digital Library

[19]

R. Lämmel, J. Visser, and J. Kort. Dealing with large bananas. In WGP ’00, pages 46–59, 2000. Technical Report, Universiteit Utrecht.

[20]

G. Malcolm. Algebraic Data Types and Program Transformation. PhD thesis, Groningen University, The Netherlands, 1990.

[21]

L. Meertens. Paramorphisms. Formal Aspects of Computing, 4:413– 424, 1992.

Digital Library

[22]

T. Millstein, C. Bleckner, and C. Chambers. Modular typechecking for hierarchically extensible datatypes and functions. ACM Trans. Program. Lang. Syst., 26(5), Sept. 2004.

Digital Library

[23]

J. G. Morris and M. P. Jones. Instance chains: Type class programming without overlapping instances. In ICFP ’10, 2010.

Digital Library

[24]

G. Plotkin and M. Pretnar. Handlers of algebraic effects. In ESOP ’09, pages 80–94. Springer-Verlag, 2009.

Digital Library

[25]

M. Rhiger. Type-safe pattern combinators. Journal of Functional Programming, 19:145–156, 2009.

Digital Library

[26]

T. Sheard and E. Pasalic. Two-level types and parameterized modules. Journal of Functional Programming, 14(5):547–587, September 2004.

Digital Library

[27]

W. Swierstra. Data types à la carte. Journal of Functional Programming, 18(4):423–436, July 2008.

Digital Library

[28]

P. Wadler and S. Blott. How to make ad-hoc polymorphism less ad hoc. In POPL ’89, pages 60–76. ACM, 1989.

Digital Library

[29]

S. Weirich, B. A. Yorgey, and T. Sheard. Binders unbound. In ICFP ’11, 2011.

Digital Library

[30]

N. Wu, T. Schrijvers, and R. Hinze. Effect handlers in scope. In Symposium on Haskell, pages 1–12. ACM, 2014.

Digital Library

[31]

B. A. Yorgey, S. Weirich, J. Cretin, S. Peyton Jones, D. Vytiniotis, and J. P. Magalh˜aes. Giving haskell a promotion. In Workshop on Types in Language Design and Implementation, TLDI ’12, 2012.

Digital Library

Cited By

Hubers AMorris J(2023)Generic Programming with Extensible Data Types: Or, Making Ad Hoc Extensible Data Types Less Ad HocProceedings of the ACM on Programming Languages10.1145/36078437:ICFP(356-384)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607843
van der Rest CPoulsen C(2023)Towards a Language for Defining Reusable Programming Language ComponentsTrends in Functional Programming10.1007/978-3-031-21314-4_2(18-38)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-21314-4_2
Zhang WOliveira B(2020)Pattern matching in an open worldACM SIGPLAN Notices10.1145/3393934.327812453:9(134-146)Online publication date: 7-Apr-2020
https://dl.acm.org/doi/10.1145/3393934.3278124
Show More Cited By

Index Terms

Modular reifiable matching: a list-of-functors approach to two-level types
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features

Recommendations

Modular reifiable matching: a list-of-functors approach to two-level types
Haskell '15

This paper presents Modular Reifiable Matching (MRM): a new approach to two level types using a fixpoint of list-of-functors representation. MRM allows the modular definition of datatypes and functions by pattern matching, using a style similar to the ...
A flow-based approach for variant parametric types
Proceedings of the 2006 OOPSLA Conference

A promising approach for type-safe generic codes in the object-oriented paradigm is variant parametric type, which allows covariant and contravariant subtyping on fields where appropriate. Previous approaches formalise variant type as a special case of ...
Variant parametric types: A flexible subtyping scheme for generics

We develop the mechanism of variant parametric types as a means to enhance synergy between parametric and inclusion polymorphism in object-oriented programming languages. Variant parametric types are used to control both the subtyping between different ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Haskell '15: Proceedings of the 2015 ACM SIGPLAN Symposium on Haskell

August 2015

212 pages

ISBN:9781450338080

DOI:10.1145/2804302

Program Chair:
Ben Lippmeier

ACM SIGPLAN Notices Volume 50, Issue 12
Haskell '15
December 2015
212 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2887747
Editor:
Matthew Fluet
Rochester Institute of Technology
Issue’s Table of Contents

Copyright © 2015 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 the author(s) 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: 30 August 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP'15

Sponsor:

SIGPLAN

ICFP'15: 20th ACM SIGPLAN International Conference on Functional Programming

September 3 - 4, 2015

BC, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 35 of 86 submissions, 41%

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

10
Total Citations
View Citations
172
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hubers AMorris J(2023)Generic Programming with Extensible Data Types: Or, Making Ad Hoc Extensible Data Types Less Ad HocProceedings of the ACM on Programming Languages10.1145/36078437:ICFP(356-384)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607843
van der Rest CPoulsen C(2023)Towards a Language for Defining Reusable Programming Language ComponentsTrends in Functional Programming10.1007/978-3-031-21314-4_2(18-38)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-21314-4_2
Zhang WOliveira B(2020)Pattern matching in an open worldACM SIGPLAN Notices10.1145/3393934.327812453:9(134-146)Online publication date: 7-Apr-2020
https://dl.acm.org/doi/10.1145/3393934.3278124
Morris JMcKinna J(2019)Abstracting extensible data types: or, rows by any other nameProceedings of the ACM on Programming Languages10.1145/32903253:POPL(1-28)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1145/3290325
Zhang WOliveira BVan Wyk ERompf T(2018)Pattern matching in an open worldProceedings of the 17th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3278122.3278124(134-146)Online publication date: 5-Nov-2018
https://dl.acm.org/doi/10.1145/3278122.3278124
Koppel JPremtoon VSolar-Lezama A(2018)One tool, many languages: language-parametric transformation with incremental parametric syntaxProceedings of the ACM on Programming Languages10.1145/32764922:OOPSLA(1-28)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276492
Zhang HLi HOliveira BCombemale BMernik MRumpe B(2017)Type-safe modular parsingProceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3136014.3136016(2-13)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3136014.3136016
Muranushi TNishizawa STomita HNitadori KIwasawa MMaruyama YYashiro HNakamura YHotta HMakino JHosono NInoue HDuke DKameyama Y(2016)Automatic generation of efficient codes from mathematical descriptions of stencil computationProceedings of the 5th International Workshop on Functional High-Performance Computing10.1145/2975991.2975994(17-22)Online publication date: 8-Sep-2016
https://dl.acm.org/doi/10.1145/2975991.2975994
Hubers AMorris J(2023)Generic Programming with Extensible Data Types: Or, Making Ad Hoc Extensible Data Types Less Ad HocProceedings of the ACM on Programming Languages10.1145/36078437:ICFP(356-384)Online publication date: 31-Aug-2023
https://doi.org/10.1145/3607843
Haeri SKeir P(2019)Solving the Expression Problem in C++, á la LMSTheoretical Aspects of Computing – ICTAC 201910.1007/978-3-030-32505-3_20(353-371)Online publication date: 22-Oct-2019
https://doi.org/10.1007/978-3-030-32505-3_20

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