Kleene Meets Church: Regular Expressions as Types

Niels Bjørn Bugge Grathwohl, Ulrik Terp Rasmussen, and Fritz Henglein
Poster presented at POPL 2015


Regular expressions are amongst the most widely used DSLs along with Excel and SQL. Despite this, they are ill-behaved from a programmer’s perspective. The language interpretation of regular expressions as regular languages makes it difficult to use REs as a data extraction tool, even though this is what they are often used for.