Posts Tagged ‘EPITA’
[reClojure2025] Recognizing Regular Patterns in Mixed Type Sequences
Lecturer
Jim Newton is an Assistant Research Professor at EPITA, a prestigious engineering school in Paris, France. A veteran Lisp programmer since 1988, Jim has worked extensively with various dialects, including Common Lisp, SKILL++, and Clojure. His research focuses on the theoretical foundations of type systems in dynamically typed languages. At EPITA, he teaches courses on functional programming using Clojure and Scala. He is the author of several research papers and a PhD thesis titled “Representing and Computing with Types in Dynamically Typed Languages,” which forms the basis for the Regular Type Expression (RTE) library.
Abstract
While string-based regular expressions are a staple of modern programming, their application to sequences of heterogeneous types remains a relatively unexplored domain. This article details the development of Regular Type Expressions (RTEs), a framework for recognizing regular patterns within sequences of mixed-type elements in Clojure. We examine the transition from classical character-based Finite Automata to Symbolic Finite Automata, where transitions are governed by type predicates rather than literal characters. The discussion covers the theoretical challenges of implementing such a system, including the embedding of a Simple Type System (SETS) into the Clojure runtime, the construction of Deterministic Finite Automata (DFAs), and the complexities of subtype determination in a dynamic environment.
Beyond Strings: The Concept of Regular Type Expressions
Clojure programs frequently manipulate sequences—lists, vectors, or streams—that contain a variety of data types (e.g., a mixture of integers, strings, and keywords). While developers often need to validate the structure of these sequences, standard regular expressions are limited to character data. RTEs generalize the concept of regular languages to the level of types. Just as a standard regex might match the pattern a(a|b)*b, an RTE can be defined to match a sequence that “starts with an integer, contains zero or more strings or doubles, and ends with a keyword.”
Jim Newton’s work bridges the gap between the flexibility of dynamic typing and the rigor of formal language theory. By treating types as the alphabet of a regular language, RTEs allow developers to specify complex structural constraints on data. This is particularly useful in Clojure for validating macro arguments, processing heterogeneous data streams, or implementing sophisticated pattern-matching algorithms that go beyond simple structure-based destructuring.
Theoretical Challenges and Implementation
The implementation of RTEs in Clojure required solving several deep theoretical problems. Unlike character-based regex engines, where the alphabet is finite and each character is distinct, the “alphabet” of types is potentially infinite and overlapping. For example, a value might simultaneously satisfy the types Number, Integer, and Positive-Integer.
1. The Simple Type System (SETS)
To support RTEs, a fundamental type system (SETS) had to be embedded into the Clojure runtime. This system supports boolean algebraic operations on types: union, intersection, and complement. This allows for the definition of complex types such as “an element that is a String but not ‘admin'” or “an element that is either an Integer or a Keyword.”
2. Symbolic Finite Automata
The core of the RTE engine is a Symbolic Finite Automaton. In a standard DFA, a transition from one state to another is triggered by a specific character. In a Symbolic DFA, a transition is triggered if the next element in the sequence satisfies a given type predicate. A significant challenge here is ensuring the DFA remains deterministic. If an element matches multiple outgoing transitions (due to overlapping types), the automaton would become non-deterministic. To solve this, the system must be able to partition the type space into disjoint sets.
3. Subtype Determination
A critical requirement for DFA construction is the ability to determine if one type is a subtype of another. In a dynamic language like Clojure, which allows arbitrary predicates as types, this is not always decidable. Jim’s research introduces a “clever procedure” for DFA construction that maintains determinism even when the subtype relation cannot be fully determined, ensuring that the library remains robust across a wide range of use cases.
Code Sample: Using RTEs in Clojure
(require '[clojure-rte.core :refer [rte-match]])
;; Define an RTE: an Integer, followed by one or more Strings,
;; and ending with a Keyword.
(def my-pattern '(:cat Long (:* String) Keyword))
(rte-match my-pattern [1 "hello" "world" :done]) ; => true
(rte-match my-pattern [1 :done]) ; => true
(rte-match my-pattern ["wrong" :done]) ; => false
Practical Implications and Conclusion
The development of the clojure-rte library provides Clojure developers with a powerful tool for data validation and pattern recognition. It allows for the detection of unreachable code (by identifying patterns that can never be matched) and enables highly expressive type-based dispatch. Because the system is built on a solid theoretical foundation, it handles edge cases—such as empty sets or overlapping type definitions—with mathematical precision.
This project is part of a larger, multi-language research effort, with implementations also available in Scala, Python, and Common Lisp. By bringing the rigor of Symbolic Finite Automata to Clojure, Jim Newton has provided a compelling example of how theoretical computer science can enhance the practical tools of modern software engineering, particularly in the realm of dynamic, data-driven applications.