Scrap your boilerplate: a practical design pattern for generic programming

Authors

Ralf Lämmel and Simon Peyton-Jones

Note

See the Scrap your boilerplate approach website.

Abstract

We describe a design pattern for writing programs that traverse data structures built from rich mutually-recursive data types. Such programs often have a great deal of "boilerplate" code that simply walks the structure, hiding a small amount of "real" code that constitutes the reason for the traversal. Our technique allows most of this boilerplate to be written once and for all, or even generated mechanically, leaving the programmer free to concentrate on the important part of the algorithm. These generic programs are much more adaptive when faced with data structure evolution because they contain many fewer lines of type-specific code. Our approach is simple to understand, reasonably efficient, and it handles all the data types found in conventional functional programming languages. It makes essential use of rank-2 polymorphism, an extension found in some implementations of Haskell. Further it relies on a simple type-safe cast operator.

Bibtex entries

@Article{LPJ03,
  author    = "Ralf L{\"a}mmel and Simon {Peyton Jones}",
  title     = "Scrap your boilerplate:
               a practical design pattern for generic programming",
  journal   = "ACM SIG{\-}PLAN Notices",
  publisher = "ACM Press",
  volume    = "38",
  number    = "3",
  pages     = "26--37",
  month     = mar,
  year      = "2003",
  note      = "Proceedings of the ACM SIGPLAN Workshop
               on Types in Language Design and Implementation (TLDI~2003)"
}

Downloads

• TLDI 2003 paper: [.pdf]; [.ps]
• Ralf slides at TLDI 2003 and elsewhere: [.pdf]; [.ps]
• Simon's slides used in some places: [.ppt]