The expression lemma

Status

Short paper published in Proceedings of MPC 2008.
Full report to be submitted for journal publication.

History

• 16 April 2008 -- MPC 2008 final version (short paper) published online
• 4 March 2008 -- ExpLemmaLib; semi-complete release published online
• 6 February 2008 -- ExpLemmaLib; first cut published online
• 6 February 2008 -- Full report (draft) published online
• 28 January 2008 -- Short paper (draft) published online

Authors

Ralf Lämmel and Ondrej Rypacek

Abstract

Algebraic data types and catamorphisms (folds) play a central role in functional programming as they allow programmers to define recursive data structures and operations on them uniformly by structural recursion. Likewise, in object-oriented (OO) programming, recursive hierarchies of object types with virtual methods play a central role for the same reason. There is a semantical correspondence between these two situations which we reveal and formalize categorically. To this end, we assume a coalgebraic model of OO programming with functional objects. The development may be helpful in deriving refactorings that turn sufficiently disciplined functional programs into OO programs of a designated shape and vice versa.

Keywords

expression lemma, expression problem, functional object, catamorphism, fold, the composite design pattern, program calculation, distributive law, free monad, cofree comonad

Bibtex entry

@inproceedings{ExpressionLemma,
 author = "Ralf L{\"a}mmel and Ondrej Rypacek",
 title = "{The expression lemma}",
 booktitle = "{Proceedings of Mathematics of Program Construction (MPC) 2008}",
 publisher = "Springer",
 series = "LNCS",
 year = 2008,
 month = jul,
 note = {To appear}
}

Downloads

• Full report (draft): [.pdf]
• Short paper: [.pdf]
• Source distribution: [.html]