Programming with Composable Recursive Patterns and Transformations
Abstract
Data processing using traditional pattern matching syntax and direct recursive functions is straightforward to write but inherently restricted: in the presence of ambiguity (nondeterminism), programmers who wish to avoid backtracking often end up with complicated code that sacrifices clarity and modularity. However, when the tree language being matched is regular, more efficient solutions are possible. This paper presents pattern definitions, a new programming language feature that addresses this gap. They serve both to validate existing data – e.g., structured JSON input against a pattern acting like a data schema – and to transform data in a type-safe and efficient manner. Our approach supports recursive patterns and provides a concise formalization that captures the essence of structural refinement types. Most importantly, we present an implementation that generates backtracking-free code running in asymptotically linear time.
