Regex, set, and match

We are trying to answer these questions about regexes ¹ without using regexes to process regexes. We’ve been successful so far in analyzing Strings to verify they have the syntactic structure a regex must follow, and producing a tree-like recursive data type RE representing their essential structure.

That is, we’ve gone from the very general

StringLookingLikeAREGEX -> BehavesLikeAREGEX

to a slightly better

[Char] -> RE -> BehavesLikeAREGEX

after working out a

[Char] -> RE

implementation for the analysis part of the problem. Note the implementation is pure in the sense it does not need to interleave IO actions to work. This is not the usual case when working with actual interpreters, but it’s enough for this problem.

Let’s refine the problem once more looking to specifically address how to answer the questions, and deferring IO behaviors as much as possible. We know better than trying to use Haskell as if it were one of those languages where the imperative is to be impure.

Regex are actually shorthand for sets

The theoretical part of CI3725 teaches how languages are sets of words, and how languages have different complexities. Being able to succintly denote languages as sets is a very important skill, and is also thoroughly covered.

After showing ad hoc ways to denote languages as sets, and seeing how thay can be… chaotic and unwieldly, we step back and define the Regular Sets as a simpler approach. Out of any alphabet, a finite set of atomic symbols allowed in Sets, we provide shorthand notation for run-of-the-mill set operations.

Say our alfabet is Σ = {a, b}, then

Operations on the right hand side are the regular set union you learned in high school, as well as word concatenation, and Kleene star, the latter being defined in terms of itself.

Revisiting the questions we want to answer for any given regular expression already parsed as a RE:

1. What words will the regular expression match? This is equivalent to translating our RE into a set of words, following the rules described above.

2. Will the regular expression match this particular word w? This is equivalent to, given a solution to step (1), see if w is contained in the set. ²

This suggests we can refine our problem

RE -> BehavesLikeAREGEX

to be

RE -> [String] -> BehavesLikeAREGEX

focusing on

RE -> [String]

to address the first question. We could use regular Haskell lists as sets, then generate the list of all possible words that are part of the Regular Set associated to the regex given.

The astute reader probably noted that even though our alphabet is finite, if our regex uses the Kleene star the set is going to have an infinite number of finite length words.

Recursive set building

Another piece of knowledge students get out of the theoretical and practical topics covered during CI3725 is that regular languages and context-free languages are the only ones having automatic processing tools. That is, once you get to the AST (and symbol tables whenever required by local law), it is on you the student programmer, to figure out a way to synthesize whatever you need out of them. Whether it is machine code, an interpreter, or a different textual representation, you have to come up with a (recursive!) strategy to accomplish it.

In this case, we have to recursively process our RE to build and combine sets of words. A lazily generated [String] will suffice.

Reworking the table above in the context of our input (a RE) and our desired output (a [String]), we can figure out what to fo in (almost) every case:

The base cases should be self-explanatory: they are the leaves of the RE tree-like structure, directly translating into lists used as sets ³. No biggie.

In what follows, we’ll work under the assumed invariant that lists used as sets must have their elements in order from smaller to larger. That way, given that String can be compared (Ord), every set passed as argument, and every set returned as result, should maintain said invariant.

Set union

The union of two sets is a new set that combines all elements from both, without duplicates. Our sets are [String], and our invariant implies they are ordered with «smaller» elemens coming before «larger» elements. Writing union is a matter of going over both lists while keeping elements as we go. We can write the polymorphic

union :: Ord a => [a] -> [a] -> [a]
union []        ys        = ys
union xs        []        = xs
union xs@(x:xt) ys@(y:yt) = case compare x y of
                              LT -> x : xt `union` ys
                              EQ -> x : xt `union` yt
                              GT -> y : xs `union` yt

Not much to explain here: both lists (xs and ys) are ordered, so just merge their elements while keeping order. If there’s an element in both sets (the EQ case) we keep one and proceed with the rest of both lists.

Can’t catenate easily

Appending strings is a familiar operation:

ghci> "foo" ++ "bar"
"foobar"

In the context of set of words, concatenating sets A and B

{w_aw_b|w_a ∈ A, w_b ∈ B}

means that for every word w_a in set A, you build new words by picking every word from set B, and append them as sufixes of w_a. If |A| = m, |B| = n, then the concatenation will have m × n elements in total. If we write the above word for word (pun intended) using list comprehensions

ghci> let setA = ["foo","bar"]
ghci> let setB = ["x","xy","xyz"]
ghci> [ wA ++ wB | wA <- setA, wB <- setB ]
["foox","fooxy","fooxyz","barx","barxy","barxyz"]

Firstly, it break the ordering invariant. Secondly, we could have something like

ghci> let setA = ["","x","foo"]
ghci> let setB = ["","x","xyz","foo"]
ghci> [ wA ++ wB | wA <- setA, wB <- setB ]
["","x","xyz","foo","x","xx","xxyz","xfoo","foo","foox","fooxyz","foofoo"]

which breaks the no repeat and ordering invariant. And yes, the sets could be infinite…

A way to preserve the no repeat invariant could be reusing union: for each word in setA, build a set out of its concatenatin with every word of setB; if we do the same for every word in setA, we can then union all those sets together and repeats will go away… But union works under the ordered invariant, and we can’t guarantee that it will hold if we do it like this. Or can we?

The order we need

Standard semantics for (<) over Strings follow dictionary order, i.e. "alpha" < "beta". When I said the naïve implementation for concatenation breaks the order invariant, it was apparent that "x" appeared before "foo". Obviously wrong. Or is it?

Our goal is to generate a list containing all the words members of the regular set corresponding to a regular expression. Consider the regular expression

a*b*

Words, b, ab, aaaab, and aaabbbbb are part of the regular set so they should all appear in the list. But, under dictionary ordering, word b would have to appear after all the words that begin with a, wouldn’t it? All the words. An infinite number of words that begin with some sequence of a. That’s not good: the infinite set of words starting with b are never going to appear, because we’d have to generate the infinite set of words starting with a first!

We must generate and sort the words in a way that guarantees every word part of the regular set appears eventually. That is, we must find a way to generate the words like this

λ, a, b, ab, aa, ba, bb, aaa, aab, aba, abb, ...

and preserve that ordering when merging sets.

Instead of simple dictionary ordering we should generate words sorted by length first, and using dictionary order only between words having the same length. This ensures all words of length k appear before all words of length k+1. There migh be an infinite number of words, but they will all appear eventually given enough time.

Haskell’s newtype creates a new zero-cost type based on any existing type, such that it is incompatible with the original one, and simultaneously allowing custom typeclass interfaces. Using polymorphic lists as a base, let’s create a Length-Ordered List type

newtype LOL a = LOL [a] 
              deriving (Show,Eq)

where the zero-cost LOL constructor on the right, allows us to turn any polymorphic list [a] into a new incompatible type that can already be compared. The compiler automatically generates Show and Eq instance using the base type [a].

ghci> let lola = LOL "hello"
ghci> let lolb = LOL "world!"
ghci> lola == lolb
False
ghci> lola == LOL "hello"
True

Now, for any type a that has a form of ordering, let’s make LOL a be sorted using our desired custom ordering

instance Ord a => Ord (LOL a) where
  LOL x <= LOL y = (length x, x) <= (length y, y)

That is, the order between LOL x and LOL y is first given by their length, and then given by their implicit ordering. ⁴. For String, that would be dictionary order.

ghci> let lola = LOL "b"
ghci> let lolb = LOL "ab"
ghci> let lolc = LOL "ba"
ghci> lola < lolb          -- Order by length
True
ghci> lolb < lolc          -- Same length, dictionary order then
True

Now, if all our lists [LOL Char] ⁵ instead of plain [String], the order invariant actually becomes sort words first by length, then using dictionary order. Remember how we wrote union polimorphically?

union :: Ord a => [a] -> [a] -> [a]

Well, it still works because when a ~ LOL Char, the union of two [LOL Char] will use our custom sorting: argument sets ordered by length and dictionary, will result in the union set being ordered by length and dictionary.

Generic programming is a hell of a drug.

Cartesians can catenate

We can revisit our approach to catenation using this new custom ordering. Written in an extremely polymorphic and high-order way

orderedCross :: (Ord a, Ord b, Ord c)
              => (a -> b -> c) -> [a] -> [b] -> [c]
orderedCross _ []     _         = []
orderedCross _ _      []        = []
orderedCross f (x:xt) ys@(y:yt) = f x y 
                                 : orderedCross f [x] yt
                                   `union`
                                   orderedCross f xt ys

Given two sets of sortable elements [a] and [b], and a binary operation f able to combine one a and one b to produce a c, we’ll produce a sorted set [c]. Note the sort order is whatever is provided by the instanced types, so things will work for LOL Char.

The two bases cases arise from the fact that we are not interested in a full Cartesian product, because ordering is relevant in catenation: every word in A appended with every word in B, but not the other way around. Consider this (very) simplified example

The first base case signals we’ve considered every word in [a], so there’s no words to build, hence an empty set. In the table above, it means we’ve processed all rows.

The second base case signals that regardless of where we are in processing [a], we ran out of words to take from [b], so there’s no words to build, hence an empty set. In the table above, it means we’ve processed all the columns for a row.

The recursive case is used for every position in the table. Let’s consider what happens when processing the highligthed position. Bindings would be

x  ~ a_1
xt ~ [a_2]
y  ~ b_1 
yt ~ [b_2, b_3]
ys ~ [b_1, b_2, b_3]

We definitely need the current element. Moreover we can be absolutely sure it’s the smallest element in the new set because it’s built using the smallest element from each set. That’s why we can use the binary operation ⁶ to combine them and keep it in front of the resulting set.

The ordering invariant guarantees a₁ ≤ a₂. That means catenating a₁ with all remaining words in the same row would produce words that are at least the same length that if we used a₂. Here’s the kicker: this is also true even if there were infinite b_i !

Given that union merges sets from left to right, comparing elements two at a time

orderedCross f [x] yt
  { current substitution }
orderedCross f [a_1] [b_2,b_3]

would merge with

orderedCross f xt ys
  { current substitution }
orderedCross f [a_2] [b_1,b_2,b_3]

in a way that guarantees that, even if both lists were infinite, words will be produce from shorter lengths to larger lengths. This technique is known as dovetailing.

So, processing the highlighted cell immediately produces a word, so the consumer function will have something to work with. The recursive calls would be suspended until needed, and each one would need to produce exactly one element each, in order for union to merge and produce the next element. At every stage in the computation, there will always be an element available for the consumer function, and a progressively larger thunk cascade of pending orderedCross calls to union. Each one needs to produce exactly one element for union to carry on.

Laziness wins again.

In our scenario, [a], [b], and [c] would all be [LOL Char]. But we cannot use (++). LOL Char is actually a wrapper around [Char] making them incompatible with regular [Char], i.e. [Char] ++ [Char] works, but LOL Char ++ LOL Char is not going to work unless we make it work. But (++) is an operator defined explicitly in terms of lists ⁷ so it’s not generic enough.

Haskell’s lists are also Semigroup instances, having <> defined as ++. We can make LOL a a Semigroup

instance Semigroup (LOL a) where
  LOL x <> LOL y = LOL $ x <> y

so that Semigroup-combining two LOL a results in a new LOL a which uses a’s Semigroup nature to combine their inner values; the left hand side <> is the one we’re defining for LOL a, the right hand side <> is the one defined for [a]’s.

ghci> let lola = LOL "foo"
ghci> let lolb = LOL "bar"
ghci> lola <> lolb
LOL "foobar"

We can finally write

catenate  :: [LOL Char] -> [LOL Char] -> [LOL Char]
catenate = orderedCross (<>)

to compute catenation over lists of LOL Char. The resulting list is built in a way that guarantees words will be unique, and appear sorted, first by length, then dictionary sorted, and both argument lists could be infinite.

Generic lazy programming is a hell of a lazy drug.

Closure, finally

Our last task is to implement a function to compute R*, Kleene’s star or reflexive transitive closure. The original definition

{λ} ∪ {wz|w ∈ R ∧ z ∈ R*}

is evidently recursive, as it uses R* on the right hand side. There is a non-recursive alternative definition, but is uses an infinite union and that does not make things any easier. Looking at the right hand side, it’s apparent that every element in R is used as a prefix applied to every element in R*. We can write closure using a fixed point ⁸ technique:

closure :: Ord a => (a -> a -> a) -> a -> [a] -> [a]
closure f z []        = [z]
closure f z xs@(x:xt) = if x == z then closure f z xt
                                  else z : orderedCross f xs
                                                          (closure f z xs)

kleene :: [LOL Char] -> [LOL Char]
kleene r = closure (<>) (LOL "") r

The base case is trivial: if R = ∅, then R* = { λ } by definition of R* above. That’s it

The inductive case, because it will never reach the base case, as it feeds on itself like the Ouroboros.

Since R has elements, they are already ordered. R* must start with the empty word (the z-eroth word). The conditional makes sure that z is always the first word in R*. When taking the else branch, we can be sure that only the (possibly infinite) non-empty words remain in xs. Computing orderedCross of these non-empty words in xs with the closure generated by these same non-empty words will lazily produce all the words.

Let’s enumerate

The bases cases will turn the basic RE elements into minimal [LOL Char] sets, namely the empty set, the set containing the empty word, and singleton sets for every symbol found in the original regular expression

enumerate :: RE -> [String]
enumerate re = [x | (LOL x) <- go re]
  where
    go                     :: RE -> [LOL Char]
    go Empty               = []
    go Epsilon             = [LOL ""]
    go (Symbol a)          = [LOL [a]]

For every recursive case, we process each branch individually, and let the helper functions written before preserve the sorting invariant as they build larger and larger sets

    go (Alternate re0 re1) = go re0 `union` go re1
    go (Catenate re0 re1)  = go re0 `catenate` go re1
    go (Kleene re)         = kleene $ go re

Thanks to Haskell’s laziness and the dovetailing and fixed point design employed to write the helper functions, if a regex corresponds to an infinite set, enumeration will work as much as it needs to produce the next word in the language.

ghci> let regex = "a(a+bc*)d"
ghci> let Right re = parseRegex regex
ghci> take 10 $ enumerate re
["aad","abd","abcd","abccd","abcccd","abccccd","abcccccd","abccccccd","abcccccccd","abccccccccd"]

Notice all the LOL Char mechanics are fully hidden by the helper functions. The user of enumerate receives a plain lazy [String] that can be processed with standard Haskell list functions to look at particular ranges of interest:

• Start enumerating from the p-th word

enumerateFrom :: RE -> Int -> [String]
enumerateFrom re p = drop p (enumerate re)

ghci> take 3 $ enumerateFrom re 42
["abcccccccccccccccccccccccccccccccccccccccccd","abccccccccccccccccccccccccccccccccccccccccccd","abcccccccccccccccccccccccccccccccccccccccccccd"]

• Enumerate from the p-th to the q-th word, both included

enumerateFromTo :: RE -> Int -> Int -> [String]
enumerateFromTo re p q = take (q-p+1) $ drop p (enumerate re)

• What is the n-th word in the language?

enumerate re !! n

ghci> enumerate re !! 69
"abccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccd"

We can answer the student’s second question with a trivial brute force approach: in order to know if our regex re will be able to match a particular word s, we simply enumerate all words ignoring those shorter than s; if we find s among the words having the same length, we have a match; no match otherwise.

matches :: RE -> String -> Bool
matches re s = elem s
             $ takeWhile (\w -> length w == n)
             $ dropWhile (\w -> length w <  n)
             $ enumerate re
  where
    n = length s


ghci> take 5 $ enumerate re
["aad","abd","abcd","abccd","abcccd"]
ghci> matches re "aad"
True
ghci> matches re "aab"
False

Effectiveness vs efficiency

We’ve implemented an effective method in the sense that it will always terminate stating whether there’s a match or not. Granted, it is not very efficient, but that’s not the point of this post: sometimes you can compute things, but they turn out to be quite impractical. Finding the most efficient way to compute is the actual challenge.

A real regex matching algorithm would not enumerate a set to find a word, but instead would try to process the word to see at what point the regex can’t continue. Very efficient algorithms based on finite-state machine theory are used by programming languages providing native regex support, as well as lexer generators. These algorithms are taught as part of the course; students don’t need to implement them, but they must know how to run them, understand what’s going on, and how their behavior influences the design of a lexer.

However, dovetailing, fixed-point, and enumerate-and-find techniques are essential for the study of Computability Theory, a topic that is introducted by the end of CI3725 so students understand the limits of computation.

Our final task is to wrapp our enumerate and matches function family, as some IO behavior, so that students can interact with the tool. Clearly eparating pure computation from IO behavior will prove helpful in making the user interface independent and replaceable.