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

Abstract

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 rewrite 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.

Categories: Rewriting, Domain-specific Languages, Type Systems, Functional Programming