Modular Implementation of Programming Languages and a Partial-Order Approach to Infinitary Rewriting

PhD defence by Patrick Bahr


In this dissertation we investigate two independent areas of research.

In the first part, we develop techniques for implementing programming languages in a modular fashion. Within this problem domain, we focus on operations on typed abstract syntax trees with the goal of developing a framework that facilitates the definition, manipulation and composition of such operations. The result of our work is a comprehensive combinator library that provides these facilities. What sets our approach apart is the use of recursion schemes derived from tree automata in order to implement operations on abstract syntax trees.

The second part is concerned with infinitary rewriting; a field that studies transfinite rewrites sequences.

We extend the established theory of infinitary rewriting in two ways:

(1) a novel approach to convergence in infinitary rewriting that replaces convergence in a metric space with the limit inferior in a partially ordered set;

(2) extending infinitary term rewriting to infinitary term graph rewriting.

Assessment committee:

Chairman: Associate professor Jakob Grue Simonsen, Department of Computer Science, University of Copenhagen, Denmark

Professor Jan Willem Klop, Department of Theoretical Computer Science, VU University Amsterdam, the Netherlands

Professor Graham Hutton, School of Computer Science, University of Nottingham, United Kingdom

Academic supervisor:

Professor Fritz Henglein, Department of Computer Science, University of Copenhagen, Denmark

For an electronic copy of the thesis, please contact Jette Giovanni Møller,