article

Type-safe pattern combinators

Author:

Morten RhigerAuthors Info & Claims

Journal of Functional Programming, Volume 19, Issue 2

Pages 145 - 156

https://doi.org/10.1017/S0956796808007089

Published: 01 March 2009 Publication History

Abstract

Macros still haven't made their way into typed higher-order programming languages such as Haskell and Standard ML. Therefore, to extend the expressiveness of Haskell or Standard ML, one must express new linguistic features in terms of functions that fit within the static type systems of these languages. This is particularly challenging when introducing features that span across multiple types and that bind variables. We address this challenge by developing, in a step by step manner, mechanisms for encoding patterns and pattern matching in Haskell in a type-safe way.

References

[1]

Danvy, O. (1998) Functional unparsing. J. Funct. Prog. 8(6), 621-625.

Digital Library

Google Scholar

[2]

Fähndrich, M. & Boyland, J. (1997) Statically checkable pattern abstractions. Pages 75-84 of: Tofte, Mads (ed), Proceedings of the 1997 ACM SIGPLAN international conference on functional programming (ICFP 1997). Amsterdam, The Netherlands: ACM Press.

Crossref

Google Scholar

[3]

Filinski, A. (1999) A semantic account of type-directed partial evaluation. In: International conference on principles and practice of declarative programming (PPDP 1999), Nadathur, G. (ed). Lecture Notes in Computer Science, vol. 1702. Paris, France: Springer-Verlag, pp. 378-395.

Crossref

Google Scholar

[4]

Fridlender, D. & Indrika, M. (2000) Do we need dependent types? J. Funct. Prog. 10(4), 409-415.

Digital Library

Google Scholar

[5]

Rhiger, M. (1999) Deriving a statically typed type-directed partial evaluator. In: Proceedings of the ACM SIGPLAN workshop on partial evaluation and semantics-based program manipulation (PEPM 1999), Danvy, O. (ed). BRICS Note Series, no. NS-99-1, Department of Computer Science, University of Aarhus, Denmark, pp. 25-29.

Google Scholar

[6]

Steele, Jr., G. L. (1999) Growing a language. Higher-Order Symb. Comput. 12(3), 221-236.

Digital Library

Google Scholar

[7]

Wadler, P. (1987) Views: A way for pattern matching to cohabit with data abstraction. In: Proceedings of the fourteenth annual ACM symposium on principles of programming languages (POPL 1987), O'Donnell, M. J. (ed). Munich, West Germany: ACM Press, pp. 307-313.

Crossref

Google Scholar

[8]

Yang, Z. (2004) Encoding types in ML-like languages. Theoret. Comput. Sci. 315(1), 151-190.

Digital Library

Google Scholar

Cited By

View all

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
Oliveira BMu SYou S(2015)Modular reifiable matching: a list-of-functors approach to two-level typesACM SIGPLAN Notices10.1145/2887747.280431550:12(82-93)Online publication date: 30-Aug-2015
https://dl.acm.org/doi/10.1145/2887747.2804315
Oliveira BMu SYou SLippmeier B(2015)Modular reifiable matching: a list-of-functors approach to two-level typesProceedings of the 2015 ACM SIGPLAN Symposium on Haskell10.1145/2804302.2804315(82-93)Online publication date: 30-Aug-2015
https://dl.acm.org/doi/10.1145/2804302.2804315
Show More Cited By

Recommendations

Squid: type-safe, hygienic, and reusable quasiquotes
SCALA 2017: Proceedings of the 8th ACM SIGPLAN International Symposium on Scala

Quasiquotes have been shown to greatly simplify the task of metaprogramming. This is in part because they hide the data structures of the intermediate representation (IR), instead allowing metaprogrammers to use the concrete syntax of the language they ...
Combinators and type-driven transformers in Objective Caml

We describe an implementation of LDTA 2011 Tool Challenge tasks in Objective Caml language. Instead of using some dedicated domain-specific tools we utilize typical functional programming machinery such as polymorphic functions, monads and combinators; ...
Expressive and strongly type-safe code generation
PPDP '17: Proceedings of the 19th International Symposium on Principles and Practice of Declarative Programming

Meta-programs are programs that generate other programs, but in weakly type-safe systems, type-checking a meta-program only establishes its own type safety, and generated programs need additional type-checking after generation. Strong type safety of a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Functional Programming

Journal of Functional Programming Volume 19, Issue 2

March 2009

124 pages

ISSN:0956-7968

Issue’s Table of Contents

Publisher

Cambridge University Press

United States

Publication History

Published: 01 March 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
1
Total Downloads

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

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Oliveira BMu SYou S(2015)Modular reifiable matching: a list-of-functors approach to two-level typesACM SIGPLAN Notices10.1145/2887747.280431550:12(82-93)Online publication date: 30-Aug-2015
https://dl.acm.org/doi/10.1145/2887747.2804315
Oliveira BMu SYou SLippmeier B(2015)Modular reifiable matching: a list-of-functors approach to two-level typesProceedings of the 2015 ACM SIGPLAN Symposium on Haskell10.1145/2804302.2804315(82-93)Online publication date: 30-Aug-2015
https://dl.acm.org/doi/10.1145/2804302.2804315
Solodkyy YDos Reis GStroustrup B(2013)Open pattern matching for C++ACM SIGPLAN Notices10.1145/2637365.251722249:3(33-42)Online publication date: 27-Oct-2013
https://dl.acm.org/doi/10.1145/2637365.2517222
Solodkyy YDos Reis GStroustrup BJärvi JKästner C(2013)Open pattern matching for C++Proceedings of the 12th international conference on Generative programming: concepts & experiences10.1145/2517208.2517222(33-42)Online publication date: 27-Oct-2013
https://dl.acm.org/doi/10.1145/2517208.2517222
Clements JFisler K(2010)“little language” project modulesJournal of Functional Programming10.1017/S095679680999028120:1(3-18)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1017/S0956796809990281

View Options

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.

Abstract

References

Cited By

Recommendations

Squid: type-safe, hygienic, and reusable quasiquotes

Combinators and type-driven transformers in Objective Caml

Expressive and strongly type-safe code generation

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations