DReX: A Declarative Language for Efficiently Evaluating Regular String Transformations

Rajeev Alur, Loris D'Antoni, Mukund Raghothaman
University of Pennsylvania

What is DReX?

DReX is a domain specific language for string transformations. Think of examples like, “Replace every occurrence of the variable foo with the variable bar,” or “Transform telephone numbers formatted as (123) 456-7890 to 123-456-7890.”

  1. DReX is declarative. Transformations are modular, and small easy-to-understand transformers can be combined into more complicated ones.
  2. DReX is fast. There is a streaming one-pass algorithm to evaluate well-typed DReX programs.
  3. DReX is based on strong theoretical foundations. The class of functions expressible using DReX coincides with the class of regular string transformations. There are several equivalent characterizations, such as two-way finite state transducers, streaming string transducers, and graph transformations in monadic second-order logic. Regular string transformations are a robust class: they are closed with respect to composition, regular look-ahead, input reversal, etc.
  4. DReX permits algorithmic analysis. It is possible to mechanically answer audit questions like, “Does this transformer ever emit an unescaped backslash character?” Equivalence and precondition computation are decidable, we are working on practical programmer assistance tools for DReX.

It can be used either as a standalone application or as a Java library.

Try DReX Live!

Running drex-front version:

Publications

  1. Rajeev Alur, Adam Freilich, and Mukund Raghothaman. Regular combinators for string transformations. In Proceedings of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS ’14, pages 9:1--9:10. ACM, 2014. [Paper], [Full version], [Slides].
  2. Rajeev Alur, Loris D’Antoni, Mukund Raghothaman. DReX: A Declarative Language for Efficiently Computable Regular String Transformations. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’15, pages 125--137. ACM, 2015. [Paper], [Full paper], [PRECISE Industry Day, 2014, 2-minute pitch slides], [POPL 2015 Slides], [DReX Webpage].

Get DReX

  1. DReX.zip: This is the latest published version of the DReX tool.