The most widely used generic-programming system in the Haskell community, Scrap Your Boilerplate (SYB), also happens to be one of the slowest. Generic traversals in SYB are often an order of magnitude slower than equivalent handwritten, non-generic traversals. Thus while SYB allows the concise expression of many traversals, its use incurs a significant runtime cost. Existing techniques for optimizing other generic-programming systems are not able to eliminate this overhead.
This paper presents an optimization that eliminates this cost. Essentially, it is a partial evaluation that takes advantage of domain-specific knowledge about the structure of SYB. It optimizes SYB traversals to be as fast as handwritten, non-generic code, and benchmarks show that this optimization improves the speed of SYB traversals by an order of magnitude or more.
Optimization; Partial evaluation; Datatype-generic programming; Haskell; Scrap Your Boilerplate (SYB)
, , and . Optimizing SYB traversals is easy! Science of Computer Programming, 112, Part 2:170–193, November 2015. ISSN 0167-6423. doi: 10.1016/j.scico.2015.09.003.
@article{adams2015syb,
author = {Adams, Michael D. and Farmer, Andrew and Magalh{\~a}es, Jos{\'e} Pedro},
title = {Optimizing {SYB} traversals is easy!},
journal = {Science of Computer Programming},
pages = {170--193},
year = {2015},
volume = {112, Part 2},
series = {Selected and extended papers from Partial Evaluation and Program Manipulation 2014},
month = nov,
issn = {0167-6423},
doi = {10.1016/j.scico.2015.09.003},
}