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

research-article

Open access

Generic deriving of generic traversals

Authors:

Matthew Pickering,

Nicolas WuAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 2, Issue ICFP

Article No.: 85, Pages 1 - 30

https://doi.org/10.1145/3236780

Published: 30 July 2018 Publication History

Abstract

Functional programmers have an established tradition of using traversals as a design pattern to work with recursive data structures. The technique is so prolific that a whole host of libraries have been designed to help in the task of automatically providing traversals by analysing the generic structure of data types. More recently, lenses have entered the functional scene and have proved themselves to be a simple and versatile mechanism for working with product types. They make it easy to focus on the salient parts of a data structure in a composable and reusable manner.

This paper uses the combination of lenses and traversals to give rise to a library with unprecedented expressivity and flexibility for querying and modifying complex data structures. Furthermore, since lenses and traversals are based on the generic shape of data, this information is used to generate code that is as efficient as hand-optimised versions. The technique leverages the structure of data to produce generic abstractions that are then eliminated by the standard workhorses of modern functional compilers: inlining and specialisation.

Supplementary Material

WEBM File (a85-kiss.webm)

Download
87.08 MB

References

[1]

Michael D Adams and Thomas M DuBuisson. 2012. Template your boilerplate: Using Template Haskell for efficient generic programming. In ACM SIGPLAN Notices, Vol. 47. ACM, 13–24.

Digital Library

[2]

Michael D. Adams, Andrew Farmer, and José Pedro Magalhães. 2014. Optimizing SYB is Easy!. In Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation (PEPM ’14). ACM, New York, NY, USA, 71–82.

Digital Library

[3]

Michael D. Adams, Andrew Farmer, and José Pedro Magalhães. 2015. Optimizing SYB Traversals is Easy! Sci. Comput. Program. 112, P2 (Nov. 2015), 170–193.

Digital Library

[4]

Lennart Augustsson. 2018. geniplate-mirror-0.7.6 library. http://hackage.haskell.org/package/geniplate-mirror-0.7.6

[5]

Richard Bird, Jeremy Gibbons, Stefan Mehner, Janis Voigtlaender, and Tom Schrijvers. 2013. Understanding Idiomatic Traversals Backwards and Forwards. In Haskell Symposium. http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/ uitbaf.pdf

Digital Library

[6]

Maximilian C. Bolingbroke. 2011. Constraint Kinds for GHC. http://blog.omega-prime.co.uk/2011/09/10/ constraint-kinds-for-ghc/

[7]

Joachim Breitner. 2018. Beyond correct and fast: Inspection Testing. CoRR abs/1803.07130 (2018). arXiv: 1803.07130 http://arxiv.org/abs/1803.07130

[8]

Joachim Breitner, Richard A. Eisenberg, Simon Peyton Jones, and Stephanie Weirich. 2014. Safe Zero-cost Coercions for Haskell. SIGPLAN Not. 49, 9 (Aug. 2014), 189–202.

Digital Library

[9]

Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, and Simon Marlow. 2005. Associated types with class. In POPL ’05: Proceedings of the 32nd ACM SIGPLAN-SIGACT sysposium on Principles of programming languages. ACM Press, 1–13.

Digital Library

[10]

Edsko de Vries and Andres Löh. 2014. True sums of products. In Proceedings of the 10th ACM SIGPLAN workshop on Generic programming. ACM, 83–94.

Digital Library

[11]

Richard A. Eisenberg, Dimitrios Vytiniotis, Simon Peyton Jones, and Stephanie Weirich. 2014. Closed Type Families with Overlapping Equations. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’14). ACM, New York, NY, USA, 671–683.

Digital Library

[12]

Richard A. Eisenberg, Stephanie Weirich, and Hamidhasan G. Ahmed. 2016. Visible Type Application. In Proceedings of the 25th European Symposium on Programming Languages and Systems - Volume 9632. Springer-Verlag New York, Inc., New York, NY, USA, 229–254.

[13]

Andrew Farmer. 2015. HERMIT: Mechanized Reasoning during Compilation in the Glasgow Haskell Compiler. Ph.D. Dissertation. University of Kansas, USA. http://hdl.handle.net/1808/19416

[14]

Ralf Hinze. 2000. A New Approach to Generic Functional Programming. In Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’00). ACM, New York, NY, USA, 119–132.

Digital Library

[15]

Mauro Jaskelioff and Russell O’Connor. 2015. A Representation Theorem for Second-Order Functionals. Journal of Functional Programming 25, e13 (2015).

[16]

Edward Kmett. 2018. lens-4.16 library. https://hackage.haskell.org/package/lens-4.16

[17]

Ralf Lämmel and Simon Peyton Jones. 2003. Scrap Your Boilerplate: A Practical Design Pattern for Generic Programming. In Types in Languages Design and Implementation. ACM Press, New York, NY, USA, 26–37.

Digital Library

[18]

Ralf Lämmel and Simon Peyton Jones. 2004. Scrap More Boilerplate: Reflection, Zips, and Generalised Casts. In Proceedings of the Ninth ACM SIGPLAN International Conference on Functional Programming (ICFP ’04). ACM, New York, NY, USA, 244–255.

Digital Library

[19]

José Pedro Magalhães, Atze Dijkstra, Johan Jeuring, and Andres Löh. 2010. A Generic Deriving Mechanism for Haskell. In Proceedings of the Third ACM Haskell Symposium on Haskell (Haskell ’10). ACM, New York, NY, USA, 37–48.

Digital Library

[20]

José Pedro Magalhães. 2012. Optimisation of generic programs through inlining. In Symposium on Implementation and Application of Functional Languages. Springer, 104–121.

[21]

José Pedro Magalhães. 2014. Generic Programming with Multiple Parameters. In Functional and Logic Programming, Michael Codish and Eijiro Sumii (Eds.). Springer International Publishing, Cham, 136–151.

[22]

Conor McBride and Ross Paterson. 2008. Applicative programming with effects. Journal of functional programming 18, 1 (2008), 1–13.

Digital Library

[23]

Neil Mitchell and Colin Runciman. 2007. Uniform boilerplate and list processing. In Proceedings of the ACM SIGPLAN workshop on Haskell workshop. ACM, 49–60.

Digital Library

[24]

Russell O’Connor. 2011. Functor is to Lens as Applicative is to Biplate: Introducing Multiplate. CoRR abs/1103.2841 (2011).

[25]

Simon Peyton Jones and Simon Marlow. 2002. Secrets of the glasgow haskell compiler inliner. Journal of Functional Programming 12, 4-5 (2002), 393–434.

Digital Library

[26]

Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, and Mark Shields. 2007. Practical Type Inference for Arbitraryrank Types. J. Funct. Program. 17, 1 (Jan. 2007), 1–82.

Digital Library

[27]

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.

[28]

Simon L Peyton Jones and AndréL M Santos. 1998. A transformation-based optimiser for Haskell. Science of computer programming 32, 1-3 (1998), 3–47.

Digital Library

[29]

Matthew Pickering, Jeremy Gibbons, and Nicolas Wu. 2017. Profunctor Optics: Modular Data Accessors. Programming Journal 1, 2 (2017), 7.

[30]

Martin Sulzmann, Gregory J. Duck, Simon Peyton Jones, and Peter J. Stuckey. 2007. Understanding Functional Dependencies via Constraint Handling Rules. J. Funct. Program. 17, 1 (Jan. 2007), 83–129.

Digital Library

[31]

Twan van Laarhoven. 2009. CPS-Based Functional References. (July 2009). http://www.twanvl.nl/blog/haskell/ cps-functional-references

[32]

Sjoerd Visscher and Li-yao Xia. 2018. one-liner-1.0 library. http://hackage.haskell.org/package/one-liner-1.0

[33]

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

[34]

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

[35]

Stephanie Weirich, Dimitrios Vytiniotis, Simon Peyton Jones, and Steve Zdancewic. 2011. Generative Type Abstraction and Type-level Computation. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’11). ACM, New York, NY, USA, 227–240.

Digital Library

[36]

Jeremy Yallop. 2017. Staged Generic Programming. Proc. ACM Program. Lang. 1, ICFP, Article 29 (Aug. 2017), 29 pages.

Digital Library

[37]

Brent A. Yorgey, Stephanie Weirich, Julien Cretin, Simon Peyton Jones, Dimitrios Vytiniotis, and José Pedro Magalhães. 2012. Giving Haskell a Promotion. In Proceedings of the 8th ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI ’12). ACM, New York, NY, USA, 53–66.

Digital Library

Cited By

Willis JWu NPickering M(2020)Staged selective parser combinatorsProceedings of the ACM on Programming Languages10.1145/34090024:ICFP(1-30)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3409002
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
Serrano ACorpa FSchrijvers T(2020)Describing microservices using modern Haskell (experience report)Proceedings of the 13th ACM SIGPLAN International Symposium on Haskell10.1145/3406088.3409018(1-8)Online publication date: 27-Aug-2020
https://dl.acm.org/doi/10.1145/3406088.3409018
Show More Cited By

Index Terms

Generic deriving of generic traversals
1. Software and its engineering
  1. Software creation and management
    1. Software development techniques
      1. Reusability
  2. Software notations and tools
    1. General programming languages
      1. Language features
        Data types and structures
      2. Language types
        Functional languages

Recommendations

Dependency-style generic haskell

Generic Haskell is an extension of Haskell that supports the construction of generic programs. During the development of several applications, such as an XML editor and compressor, we encountered a number of limitations with the existing (Classic) ...
Dependency-style generic haskell
ICFP '03: Proceedings of the eighth ACM SIGPLAN international conference on Functional programming

Generic Haskell is an extension of Haskell that supports the construction of generic programs. During the development of several applications, such as an XML editor and compressor, we encountered a number of limitations with the existing (Classic) ...
A comparative study of language support for generic programming
OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications

Many modern programming languages support basic generic programming, sufficient to implement type-safe polymorphic containers. Some languages have moved beyond this basic support to a broader, more powerful interpretation of generic programming, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 2, Issue ICFP

September 2018

1133 pages

EISSN:2475-1421

DOI:10.1145/3243631

Issue’s Table of Contents

Copyright © 2018 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 July 2018

Published in PACMPL Volume 2, Issue ICFP

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
1,009
Total Downloads

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

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Willis JWu NPickering M(2020)Staged selective parser combinatorsProceedings of the ACM on Programming Languages10.1145/34090024:ICFP(1-30)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3409002
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
Serrano ACorpa FSchrijvers T(2020)Describing microservices using modern Haskell (experience report)Proceedings of the 13th ACM SIGPLAN International Symposium on Haskell10.1145/3406088.3409018(1-8)Online publication date: 27-Aug-2020
https://dl.acm.org/doi/10.1145/3406088.3409018
Kiss CField TEisenbach SPeyton Jones S(2019)Higher-order type-level programming in HaskellProceedings of the ACM on Programming Languages10.1145/33417063:ICFP(1-26)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341706
Breitner J(2018)A promise checked is a promise kept: inspection testingACM SIGPLAN Notices10.1145/3299711.324274853:7(14-25)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3299711.3242748
Breitner JWu N(2018)A promise checked is a promise kept: inspection testingProceedings of the 11th ACM SIGPLAN International Symposium on Haskell10.1145/3242744.3242748(14-25)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3242744.3242748

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents