Programming with Composable Recursive Patterns and Transformations

Data processing using traditional pattern matching syntax and direct recursive functions is straightforward to write but becomes awkward in ambiguous (i.e., nondeterministic) cases: when programmers wish to avoid backtracking, they often end up having to write complicated code that sacrifices clarity and modularity. However, when the tree language being matched is regular, better solutions are possible.

This paper presents composable recursive patterns and transformations (CRPTs), a new programming language feature designed to tackle this problem. CRPTs resemble and act like recursive type definitions in a structurally-typed language, which can be composed seamlessly to type check programs, but they also have a runtime component: they are compiled into backtracking-free code that recognizes and transforms their input in linear time. They serve both to validate existing data—for example, when checking structured JSON input against a CRPT that acts as a data schema—and to transform data in a type-safe and efficient manner. We formalize the dynamic semantics of CRPTs, a static type system for them, and a translation into efficient code that executes in time linear in the size of the input and polynomial in the size of the pattern. We also demonstrate the practicality of CRPTs with an implementation in the MLscript programming language, which we evaluate against comparable existing approaches on several examples.