Kleene Meets Church: Regular Expressions as Types

Abstract

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.

@misc{GRH15,
  author = {Niels Bj{\o}rn Bugge Grathwohl, Ulrik Terp Rasmussen, and Fritz Henglein},
  title = {{K}leene {M}eets {C}hurch: Regular Expressions as Types},
  series = {POPL 2015},
  note = {Poster presented at POPL 2015},
  location = {Mumbai, India},
  year = {2015},
  abstract = {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.  },
}