"Banana Algebra: Syntactic Language Extension via an Algebra of Languages and Transformations" and "Typed and Unambiguous Pattern Matching on Strings using Regular Expressions"

You are invited to attend one or both guest lectures by Claus Brabrand, IT University of Copenhagen, at the M.S./Ph.D. course "Topics in Programming Languages: Theory and Practice of Regular Expressions"

1) "Banana Algebra: Syntactic Language Extension via an Algebra of Languages and Transformations" 

Time:  14:15-15:00


We propose an algebra of languages and transformations as a means for extending languages syntactically. 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 catamorphism, before the transformation 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. This is joint work with Jacob Andersen (Aarhus Uni).

2) "Typed and Unambiguous Pattern Matching on Strings using Regular Expressions"

Time:  15:15-16:00


We show how to achieve typed and unambiguous declarative pattern matching on strings using regular expressions extended with a simple recording operator.

We give a characterization of ambiguity of regular expressions that leads to a sound and complete static analysis. The analysis is capable of pinpointing all ambiguities in terms of the structure of the regular expression and report shortest ambiguous strings. We also show how pattern matching can be integrated into statically typed programming languages for deconstructing strings and reproducing typed and structured values.

We validate our approach by giving a full implementation of the approach presented in this paper. The resulting tool, reg-exp-rec, adds typed and unambiguous pattern matching to Java in a stand-alone and non-intrusive manner. We evaluate the approach using several realistic examples.

This is joint work with Jakob G. Thomsen (Aarhus Uni).


Claus Brabrand received his Ph.D. from the BRICS Int'l Research Center at Aarhus University, Denmark (Jan. 2003). He is now Associate Professor of Programming, Logic, and Semantics at the IT University of Copenhagen.

Claus has previously worked at Aarhus University; the IBM T. J. Watson Research Center in New York, USA; and the nation-wide French research center, INRIA. His research is generally centered on turning programming language theory into tools. They include the design, analysis, and implementation of programming languages, domain specific languages, web technology, syntax and transformation, and educational research.

He is also the script-writer, director, and co-producer of the award-winning short-film "Teaching Teaching & Understanding Understanding" which is used around the world for educational development and for teaching teachers to teach for learning.´

See http://www.COPLAS.org for more information.