This presentation introduces Regular Type Expressions (RTEs), a system for recognizing and manipulating complex patterns within mixed-type sequences, particularly relevant for dynamic languages like Closure. Jim Newton, a Lisp programmer, highlights the limitations of standard Closure function dispatch (which focuses on arity, not type or shape) and proposes dstructuring-defn, a macro built upon RTEs. The core of RTEs involves representing regular expressions and types as S-expressions with boolean operators, which are then compiled into deterministic symbolic finite automata. This approach enables efficient, linear-time pattern matching (single traversal) and advanced static analysis, such as detecting unreachable code and computationally checking the equivalence or subtyping of complex type patterns—capabilities often impossible with standard language features due to the "semi-boolean" nature of subtyping in dynamic contexts.
Regular Type Expressions: Advanced Pattern Matching for Mixed-Type Sequences
0:00:17 Introduction to Regular Type Expressions (RTEs): Jim Newton, an assistant research professor and long-time Lisp programmer, introduces RTEs as a system to recognize regular patterns in mixed-type sequences, specifically in dynamic languages like Closure.
0:02:00 Project History & Availability: The project originated in 2016, formed part of his 2018 PhD thesis, and has implementations in Common Lisp, Scala, Python, and Closure, all available on GitHub.
0:03:12 Closure defn Limitations: Standard Closure function definition (defn) dispatches only on argument count (arity), not on the shape or types of arguments, confusing new programmers. Type hints are semantically ignored, and standard predicates (like int?) cannot be directly used as type names in defn.
0:05:22 Introducing dstructuring-defn: A custom macro that enables function dispatch based on both arity and the precise types of arguments. It supports advanced features like compile-time detection of unreachable code due to type overlaps (e.g., double being a subtype of number).
0:07:50 Extended Type System: The system extends Closure's type system to allow predicates (like int?) and boolean operators (and, or, not) to define complex types, enabling more expressive pattern matching.
0:09:32 Motivation for Finite Automata: The need to analyze sequences of mixed-type objects based on their shape and types naturally leads to using regular patterns and finite automata for efficient dispatch.
0:10:06 Defining Regular Type Expressions (RTEs): RTEs define patterns unambiguously using an S-expression based syntax with prefix operators (e.g., star, concatenate, or) that form an Abstract Syntax Tree.
0:11:01 Theoretical Challenges - Representation: A key challenge is representing regular expressions of types as S-expressions rather than traditional strings, aligning with Lisp's symbolic processing.
0:12:20 Theoretical Challenges - Pattern Recognition & Determinism: To recognize sequences efficiently, RTEs are compiled into symbolic finite automata (FA). The goal is to create deterministic FAs to allow linear-time matching (single traversal of the sequence) and avoid exponential backtracking.
0:14:54 Type Partitioning: Determinism is achieved by partitioning overlapping types into disjoint sets, ensuring each transition in the FA is unambiguous.
0:18:09 "Semi-Boolean" Subtype Question: A significant theoretical hurdle is that the question "is X a subtype of Y?" is not always definitively answerable (e.g., for predicates), but the system can still work by handling "don't know" answers and decomposing types.
0:22:43 Demo & Applications: The demo showcases re-match? for checking sequence conformance to RTEs, including complex intersections of patterns (e.g., "is it all numbers AND does it contain a ratio?"), which can be done in a single pass.
0:25:52 Static Analysis & Equivalence: The system can computationally determine if two RTEs are equivalent or if one is a subtype of another, or if an RTE represents an "empty" (unmatchable) set of sequences—a capability difficult to achieve with standard Closure code.
0:28:38 Key Takeaways: RTEs extend classical FA theory to dynamic type systems, offering type-based pattern matching, unreachable code detection, and efficient, advanced static analysis by compiling complex type patterns into deterministic finite automata.