PLClub Discussion Group


Regular Expressions: History and Lambda Calculus

Oct 23 2019
Lawrence Dunn

Regular expressions have a reputation as “almost good parsers.” Actually, regular expressions are a beautiful part of the theory of finite computation, which was quickly noticed after Kleene introduced them as characterizations of finite recognition problems. Furthermore, while generally well-behaved, these objects have a dark side in the form of a complex equational theory and an apparent lack of canonical form. It has been shown that this equational theory has constructive content à la Curry-Howard, and we will present a sound and complete lambda calculus for the equational theory and explain why PL theorists and database theorists alike should take interest in these fascinating syntactic devices.