Practical generic programming in OCaml

ABSTRACT

We describe deriving, a system of extensible generic functions for OCaml implemented as a preprocessor and supporting library. We argue that generating code from type-definitions has significant advantages over a combinator approach, taking serialisation as an example application: our generate-your-boilerplate design results in a system that is easy to use, has comprehensive coverage of types and handles cyclic values without imposing a burden on the user. Users can extend generic functions with specialised implementations at particular types; we show how this can lead to dramatically improved performance in the serialisation task without the user writing a single line of serialisation code.

REFERENCES

• 1: John Billings , Peter Sewell , Mark Shinwell , Rok Strniša, Type-safe distributed programming for OCaml, Proceedings of the 2006 workshop on ML, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159876.1159881]
• 2: Jacques Carette, Lydia E. van Dijk and Oleg Kiselyov. Syntactic extension for Monads in Ocaml. http://www.cas.mcmaster.ca/~carette/pa_monad/.
• 3: James Cheney , Ralf Hinze, A lightweight implementation of generics and dynamics, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.90-104, October 03, 2002, Pittsburgh, Pennsylvania [doi>10.1145/581690.581698]
• 4: Albert Cohen and C. Herrmann. Towards a High-Productivity and High-Performance Marshaling Library for Compound Data. 2nd MetaOCaml Workshop, 2005.
• 5: Ezra Cooper, Sam Lindley, Philip Wadler, and Jeremy Yallop. Links: Web Programming Without Tiers. FMCO, 2006.
• 6: Derek Dreyer , Robert Harper , Manuel M. T. Chakravarty , Gabriele Keller, Modular type classes, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 7: Martin Elsman. Type-Specialized Serialization with Sharing. Trends in Functional Programming, 2005.
• 8: Andrzej Filinski. Controlling Effects. PhD Thesis, School of Computer Science, Carnegie Mellon University, May 1996.
• 9: Jacques Garrigue. Programming with Polymorphic Variants. ML Workshop, 1998.
• 10: Jeremy Gibbons, Design patterns as higher-order datatype-generic programs, Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159861.1159863]
• 11: Ralf Hinze, Johan Jeuring, and Andres Löh. Comparing approaches to generic programming in Haskell. Spring School on Datatype-Generic Programming, 2006.
• 12: Ralf Hinze, Generics for the masses, Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, September 19-21, 2004, Snow Bird, UT, USA
• 13: Ralf Hinze, Andres Löh, and Bruno C. d. S. Oliveira. "Scrap Your Boilerplate" Reloaded FLOPS, 2006.
• 14: J. Hughes, Why functional programming matters, The Computer Journal, v.32 n.2, p.98-107, April 1989 [doi>10.1093/comjnl/32.2.98]
• 15: Martin Jambon. json-static. http://martin.jambon.free.fr/json-static.html.
• 16: Martin Jambon. pa tryfinally. http://martin.jambon.free.fr/pa_tryfinally.ml.
• 17: Patrik Jansson , Johan Jeuring, PolyP—a polytypic programming language extension, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.470-482, January 15-17, 1997, Paris, France [doi>10.1145/263699.263763]
• 18: Vesa A.J. Karvonen, Generics for the working ML'er, Proceedings of the 2007 workshop on Workshop on ML, October 05-05, 2007, Freiburg, Germany [doi>10.1145/1292535.1292547]
• 19: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams Iv , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand, Revised Report on the Algorithmic Language Scheme, Higher-Order and Symbolic Computation, v.11 n.1, p.7-105, August 1998 [doi>10.1023/A:1010051815785]
• 20: Andrew J. Kennedy, FUNCTIONAL PEARL Pickler combinators, Journal of Functional Programming, v.14 n.6, p.727-739, November 2004 [doi>10.1017/S0956796804005209]
• 21: Oleg Kiselyov. Post to Haskell list, August 2004. http://haskell.org/pipermail/haskell/2004-August/014463.html
• 22: Ralf Lämmel and Simon Peyton-Jones. Scrap your boilerplate: a practical design pattern for generic programming. TLDI, 2003.
• 23: Chuck Liang , Gopalan Nadathur, Tradeoffs in the Intensional Representation of Lambda Terms, Proceedings of the 13th International Conference on Rewriting Techniques and Applications, p.192-206, July 22-24, 2002
• 24: Neil Mitchell and Stefan O'Rear. Derive. http://www-users.cs.york.ac.uk/~ndm/derive/.
• 25: Simon Peyton Jones and John Hughes (editors). Haskell 98: A Non-strict, Purely Functional Language. February, 1999.
• 26: Daniel de Rauglaudre. IoXML. http://cristal.inria.fr/~ddr/IoXML/.
• 27: Martin Sandin. Tywith. http://tools.assembla.com/tywith/wiki.
• 28: Guido Tack, Leif Kornstaedt and Gert Smolka. Generic Pickling and Minimization. ML Workshop, 2005.
• 29: Philip Wadler, The essence of functional programming, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143169]
• 30: Stefan Wehr. ML Modules and Haskell Type Classes: A Constructive Comparison. Master's thesis, Albert-Ludwigs-Universität, Freiburg, Germany, November 2005.
• 31: Stephanie Weirich, RepLib: a library for derivable type classes, Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, September 17-17, 2006, Portland, Oregon, USA [doi>10.1145/1159842.1159844]
• 32: Noel Winstanley. DrIFT. http://repetae.net/~john/computer/haskell/DrIFT/.
• 33: Programming languages - C. ISO/IEC 9899:1999.
• 34: American National Standard for Programming Language Common LISP. ANSI X3.226:1994. J13/SC22/WG16 Common LISP

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Polymorphism

General Terms:
Design, Languages

Keywords:
OCaml, deriving, generic programming