8. Conclusion

We have shown how to apply existing and novel multi-stage programming techniques to transform a popular generic programming library into an optimising code generator. Our staging of SYB combines the following attributes:

Efficient : while generic programming libraries often suffer from poor performance, the output of the staged library is comparable to hand-written code.

Incremental: the staging is decomposed into a series of local changes with virtuous interactions, maintaining the original structure of the library. 

Type-safe: MetaOCaml’s type safety properties ensure that the staged library never generates ill-typed code. 

Reusable: the staging techniques presented here deal with the core elements of functional programming: algebraic data, higher-order functions, recursion, etc. We anticipate that these techniques will apply to a wide class of programs.