ABSTRACT
Generic programming allows the concise expression of algorithms that would otherwise require large amounts of handwritten code. A number of such systems have been developed over the years, but a common drawback of these systems is poor runtime performance relative to handwritten, non-generic code. Generic-programming systems vary significantly in this regard, but few consistently match the performance of handwritten code. This poses a dilemma for developers. Generic-programming systems offer concision but cost performance. Handwritten code offers performance but costs concision.
This paper explores the use of Template Haskell to achieve the best of both worlds. It presents a generic-programming system for Haskell that provides both the concision of other generic-programming systems and the efficiency of handwritten code. Our system gives the programmer a high-level, generic-programming interface, but uses Template Haskell to generate efficient, non-generic code that outperforms existing generic-programming systems for Haskell.
This paper presents the results of benchmarking our system against both handwritten code and several other generic-programming systems. In these benchmarks, our system matches the performance of handwritten code while other systems average anywhere from two to twenty times slower.
- Lennart Augustsson. Geniplate version 0.6.0.0, November 2011. URL http://hackage.haskell.org/package/geniplate/.Google Scholar
- Alan Bawden. Quasiquotation in Lisp. In ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, volume NS-99-1 of BRICS Notes Series, pages 4--12, Aarhus, Denmark, January 1999. BRICS.Google Scholar
- Neil C. C. Brown and Adam T. Sampson. Alloy: fast generic transformations for Haskell. In Proceedings of the 2nd ACM SIGPLAN symposium on Haskell, Haskell '09, pages 105--116, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-508-6. 10.1145/1596638.1596652. Google ScholarDigital Library
- Manuel M. T. Chakravarty, Gabriel C. Ditu, and Roman Leshchinskiy. Instant generics: Fast and easy, 2009.Google Scholar
- HASP Project. The habit programming language: The revised preliminary report, November 2010. URL http://hasp.cs.pdx.edu/habit-report-Nov2010.pdf.Google Scholar
- Ralf Hinze, Johan Jeuring, and Andres Löh. Type-indexed data types. In Eerke Boiten and Bernhard Möller, editors, Mathematics of Program Construction, volume 2386 of Lecture Notes in Computer Science, pages 77--91. Springer Berlin / Heidelberg, 2002. ISBN 978-3-540-43857-1. 10.1007/3-540-45442-X_10. Google ScholarDigital Library
- Ralf Hinze, Johan Jeuring, and Andres Löh. Comparing approaches to generic programming in Haskell. In Roland Backhouse, Jeremy Gibbons, Ralf Hinze, and Johan Jeuring, editors, Datatype-Generic Programming, volume 4719 of Lecture Notes in Computer Science, pages 72--149. Springer Berlin / Heidelberg, 2007. ISBN 978-3-540-76785-5. 10.1007/978-3-540-76786-2_2. Google ScholarDigital Library
- Patrik Jansson and Johan Jeuring. Polyp - a polytypic programming language extension. In Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL '97, pages 470--482, New York, NY, USA, 1997. ACM. ISBN 0-89791-853-3. 10.1145/263699.263763. Google ScholarDigital Library
- Oleg Kiselyov. Smash your boiler-plate without class and typeable, August 2006. URL http://article.gmane.org/gmane.comp.lang.haskell.general/14086.Google Scholar
- Ralf Lämmel and Simon Peyton Jones. Scrap your boilerplate: a practical design pattern for generic programming. In Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementation, TLDI '03, pages 26--37, New York, NY, USA, 2003. ACM. ISBN 1-58113-649-8. 10.1145/604174.604179. Google ScholarDigital Library
- José Pedro Magalhães, Stefan Holdermans, Johan Jeuring, and Andres Löh. Optimizing generics is easy! In Proceedings of the 2010 ACM SIGPLAN workshop on Partial evaluation and program manipulation, PEPM '10, pages 33--42, New York, NY, USA, 2010. ACM. ISBN 978-1-60558-727-1. 10.1145/1706356.1706366. Google ScholarDigital Library
- Neil Mitchell and Colin Runciman. Uniform boilerplate and list processing. In Proceedings of the ACM SIGPLAN workshop on Haskell workshop, Haskell '07, pages 49--60, New York, NY, USA, 2007. ACM. ISBN 978-1-59593-674-5. 10.1145/1291201.1291208. Google ScholarDigital Library
- Ulf Norell and Patrik Jansson. Prototyping generic programming in template haskell. In Dexter Kozen, editor, Mathematics of Program Construction, volume 3125 of Lecture Notes in Computer Science, pages 314--333. Springer Berlin / Heidelberg, 2004. ISBN 978-3-540-22380-1. 10.1007/978-3-540-27764-4_17.Google Scholar
- emgmBruno C. d. S. Oliveira, Ralf Hinze, and Andres Löh. Extensible and modular generics for the masses. In Trends in Functional Programming, volume 7 of Trends in Functional Programming, pages 199--216. Intellect, 2006. ISBN 978--1--84150--188--8.Google Scholar
- Bryan O'Sullivan. Criterion version 0.6.0.1, January 2012. URL http://hackage.haskell.org/package/criterion/.Google Scholar
- Alexey Rodriguez, Johan Jeuring, Patrik Jansson, Alex Gerdes, Oleg Kiselyov, and Bruno C. d. S. Oliveira. Comparing libraries for generic programming in Haskell. In Proceedings of the first ACM SIGPLAN symposium on Haskell, Haskell '08, pages 111--122, New York, NY, USA, 2008. ACM. ISBN 978-1-60558-064-7. 10.1145/1411286.1411301. Google ScholarDigital Library
- Dipanwita Sarkar, Oscar Waddell, and R. Kent Dybvig. A nanopass infrastructure for compiler education. In Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, ICFP '04, pages 201--212, New York, NY, USA, 2004. ACM. ISBN 1-58113-905-5. 10.1145/1016850.1016878. Google ScholarDigital Library
- Tim Sheard and Simon Peyton Jones. Template meta-programming for Haskell. In Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, Haskell '02, pages 1--16, New York, NY, USA, 2002. ACM. ISBN 1-58113-605-6. 10.1145/581690.581691. Google ScholarDigital Library
- Thomas van Noort, Alexey Rodriguez, Stefan Holdermans, Johan Jeuring, and Bastiaan Heeren. A lightweight approach to datatype-generic rewriting. In Proceedings of the ACM SIGPLAN workshop on Generic programming, WGP '08, pages 13--24, New York, NY, USA, 2008. ACM. ISBN 978-1-60558-060-9. 10.1145/1411318.1411321. Google ScholarDigital Library
Index Terms
- Template your boilerplate: using template haskell for efficient generic programming
Recommendations
Template your boilerplate: using template haskell for efficient generic programming
Haskell '12Generic programming allows the concise expression of algorithms that would otherwise require large amounts of handwritten code. A number of such systems have been developed over the years, but a common drawback of these systems is poor runtime ...
Scrap your boilerplate: prologically!
PPDP '09: Proceedings of the 11th ACM SIGPLAN conference on Principles and practice of declarative programming"Scrap Your Boilerplate" (SYB) is an established style of generic functional programming. The present paper reconstructs SYB within the Prolog language with the help of the univ operator and higher-order logic programming techniques. We pay attention to ...
Using Template Haskell for Abstract Interpretation
Metaprogramming consists of writing programs that generate or manipulate other programs. Template Haskell is a recent extension of Haskell, currently implemented in the Glasgow Haskell Compiler, giving support to metaprogramming at compile time. Our aim ...
Comments