Kleene Meets Church: Regular Expressions and Types

Together with Excel spreadsheet formulas and SQL queries, regular expressions, as implemented in present-day programming languages such as Ruby, Python, PHP, Perl, Java, C#, C, etc., are probably the most widely used domain-specific sublanguage in programming practice. Yet they are astonishingly badly behaved, complicated to use and badly performing. Our work will contribute to the effective use of regular expressions having, simultaneously, predictable, tool-independent semantics, guaranteed safety properties and high computational performance, without requiring users — scientists, application domain experts, or programmers without a computer science background — to understand the mechanics of the underlying computer science theory.