School of Computing

Alloy: Fast generic transformations for Haskell

Neil C.C. Brown and Adam T. Sampson

In Haskell '09: Proceedings of the 2009 ACM SIGPLAN Haskell Symposium, pages 182-196, September 2009.


Data-type generic programming can be used to traverse and manipulate specific parts of large heterogeneously-typed tree structures, without the need for tedious boilerplate. Generic programming is often approached from a theoretical perspective, where the emphasis lies on the power of the representation rather than on efficiency. We describe use cases for a generic system derived from our work on a nanopass compiler, where efficiency is a real concern, and detail a new generics approach (Alloy) that we have developed in Haskell to allow our compiler passes to traverse the abstract syntax tree quickly. We benchmark our approach against several other Haskell generics approaches and statistically analyse the results, finding that Alloy is fastest on heterogeneously-typed trees.

Download publication 458 kbytes (PDF)

Bibtex Record

author = {Neil C.C. Brown and Adam T. Sampson},
title = {{A}lloy: Fast Generic Transformations for {H}askell},
month = {September},
year = {2009},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {},
    publication_type = {inproceedings},
    submission_id = {5676_1254754046},
    ISBN = {978-1-60558-508-6},
    booktitle = {Haskell '09: Proceedings of the 2009 ACM SIGPLAN Haskell Symposium},
    refereed = {yes},

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014