Banana Algebra: Compositional Syntactic Language Extension

Jacob Andersen, Claus Brabrand, David Raymond Christiansen

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review


We propose an algebra of languages and transformations as a means of compositional syntactic language extension. The algebra provides a layer of high-level abstractions built on top of languages (captured by context-free grammars) and transformations (captured by constructive catamorphisms).
The algebra is self-contained in that any term of the algebra specifying a transformation can be reduced to a constant catamorphism, before the transfor- mation is run. Thus, the algebra comes “for free” without sacrificing the strong safety and efficiency properties of constructive catamorphisms.
The entire algebra as presented in the paper is implemented as the Banana Algebra Tool which may be used to syntactically extend languages in an incremental and modular fashion via algebraic composition of previously defined languages and transformations. We demonstrate and evaluate the tool via several kinds of extensions.
Original languageEnglish
JournalScience of Computer Programming
Issue number10
Pages (from-to) 1845–1870
Publication statusPublished - 2013


  • Languages; transformation; syntactic extension; macros; context-free grammars; catamorphisms; bananas; algebra.


Dive into the research topics of 'Banana Algebra: Compositional Syntactic Language Extension'. Together they form a unique fingerprint.

Cite this