Regular Expressions and Basic Computability Theory in Haskell

這篇 blogpost 討論的 regular expressions 是用 formal language theory 裡面常見的定義。

定義 令 Σ 是給定的 alphabet，則 regular expressions 是以下列規則建造：

1. x ∈ Σ 是個 regular expression；
2. ε 是個 regular expression；
3. ∅ 是個 regular expression；
4. 若 R 和 S 是 regular expressions，則 R ∪ S 也是個 regular expression；
5. 若 R 和 S 是 regular expressions，則 RS 也是個 regular expression；
6. 若 R 是個 regular expression，則 R* 也是個 regular expression。

為了方便，以下簡稱 regular expressions 為 regexes。在 Haskell 裡面我們定義一個新的 datatype RegExp a，其中 a 是 regex 的 alphabet type。

data RegExp a = Literal a
              | Epsilon
              | Empty
              | Union (RegExp a) (RegExp a)
              | Append (RegExp a) (RegExp a)
              | Kleene (RegExp a)
              deriving (Show, Read)

基本上就只是把數學定義照抄一遍而已。

Regular Expression Matching

讓我們照一般對 regex 的直覺寫一個 match function，拿一個 RegExp a 和 [a]，傳回一個 Bool 表示那個 [a] 是否匹配那個 RegExp a。這可以輕鬆地透過 Haskell 的 pattern matching 機制完成：對於每種可能的 regex，指定對應的判斷方式。

Literal x 這樣的 regex 只能匹配「恰有一個元素 x 的 list」。其他的 lists 都不對。

match (Literal x) [y] | y == x = True
match (Literal x) _ = False

一個 list xs 成功匹配 Epsilon 的充要條件是「xs 是 empty list」。

match Epsilon xs = null xs

不可能有任何 list 和 Empty 匹配。

match Empty _ = False

想匹配 r ∪ s，只要和其中一個成功匹配就行了。

match (r `Union` s) xs = match r xs || match s xs

先跳到 Kleene star。我們知道 R* = ε ∪ RR*，所以匹配左側 regex 就等於匹配右側 regex。因為 Haskell 的 laziness，這樣等同於測試是否匹配 ε 然後 R 然後 RR 然後 RRR 然後一直下去，發現匹配結果成功或失敗就停止。

match (Kleene r) xs = match (Epsilon `Union` (r `Append` Kleene r)) xs

最後是 r `Append` s 的情況。我們知道一個 list xs 要想匹配這個 regex，必須把 xs 分割成兩段 ys 和 zs（使得 xs = ys ++ zs），而且 ys、zs 分別和 r、s 成功匹配，但我們不知道該怎麼分割。幸好有個簡單的做法：試過每種可能的分割就行了。Haskell Prelude 有個函式 splitAt，給定一個長度 n，把一個 list 分割成長度 n 的 prefix 和剩下的部份，形成一個 pair。例如

splitAt 4 [1..10] = ([1,2,3,4],[5,6,7,8,9,10])

對於一個 list xs，所有可能的分割就是

[splitAt 0 xs, splitAt 1 xs, ..., splitAt (length xs) xs]

用 flip 改寫一下

[flip splitAt xs 0, flip splitAt xs 1, ..., flip splitAt xs (length xs)]

現在變成把 flip splitAt xs 套用到 [0..length xs] 的每個元素，而這就是 map 做的事情：

map (flip splitAt xs) [0..length xs]

到這裡我們就得到一個 list of pairs，是 xs 所有可能的分割方式。接下來對於每個 pair，我們要試著匹配 sublists 和對應的 regex。這再用一次 map 就能達成：

map (\(xs, ys) -> match r xs && match s ys)

或者用 Control.Arrow.*** 可以寫成

map (uncurry (&&) . (match r *** match s))

至此我們會得到一個 [Bool]，每一個 Bool 都是一個可能分割的匹配結果。只要有一個匹配成功就行了，所以最後用 or 取這些 Bools 的 disjunction。至此就完成 r `Append` s 情況的定義。

match (r `Append` s) xs =
  or $ map (\(xs, ys) -> match r xs && match s ys) $
  map (flip splitAt xs) [0..length xs]

A Semantic Function

讓 GHCi 告訴我們 match 的型別：

match :: (Eq a) => RegExp a -> [a] -> Bool

它說 alphabet a 的元素必須可以比較相等與否，然後 match 接收一個 RegExp a 和一個 [a]，傳回一個 Bool。對這種 function type 表示法稍微熟一點的人就知道這樣的描述是簡化過的。-> 是 right-associative，所以 match 的型別其實是

match :: (Eq a) => RegExp a -> ([a] -> Bool)

也就是說，match 是接收一個 RegExp a 的函式，結果是 [a] -> Bool 型別的函式。而 [a] -> Bool 其實是 set of [a]'s 的一種表述方式，即一個集合的 characteristic (indicator) function。令 p :: [a] -> Bool，若我們採納「p xs 為 True ⇔ xs 在集合 S 裡面」的詮釋，那麼 p 就唯一決定了 S（cf. axiom of specification，即對於任意集合 S，{ x | x ∈ S and P(x) } 是個 well-defined set）。因此 match 其實是 RegExp a 的一個 semantic function，把任何的 regex 映射到它的語意，即一個 set of [a]'s。這也正是數學上我們對於 regex 語意的定義：一個 regex 的語意是 Σ* 的子集合。

Another Semantic Function

既然如此，我們何不另外寫一個更直接的 semantic function，用 list 表示集合，直接把 RegExp a 映射到 [[a]] 呢？

enumerate :: RegExp a -> [[a]]

一個 regex 對應的集合可能是無窮集，但 Haskell 的 infinite lists 很好操作，所以不構成（大）問題。接著我們就再次對 regex 每個可能的結構定義對應的語意。前三種情形很簡單：

enumerate (Literal x) = [[x]]
enumerate Epsilon = [[]]
enumerate Empty = []

Kleene star 也用和 match 相同的伎倆。

enumerate (Kleene r) = enumerate (Epsilon `Union` (r `Append` Kleene r))

到了 Union，如果允許集合元素重複出現在 list 裡面的話，我們可能會定義

enumerate (r `Union` s) = enumerate r ++ enumerate s

把表示 set 的兩個 lists 接在一起，就是兩個集合的聯集，看起來很自然。不過這在計算上有個嚴重瑕疵，考慮

enumerate (Kleene (Literal '0') `Union` Literal '1')

這個結果其實等同於

enumerate (Kleene (Literal '0'))

因為 "1"（計算上）永遠不會出現在 list 裡面！用 computability theory 的術語，我們希望 enumerate r 對應的集合是 recursively enumerable，亦即每個元素都會在有窮時間內被列出來。但照剛才的定義，regex 0* ∪ 1 對應的 list 前段是 0* 對應的 infinite list，enumeration 於是就會永遠困在這個 infinite list 裡面走不到盡頭，也就不可能在有窮時間內列出 "1" 了。

一種解決方式是把 finite list 擺在前面，但一般而言我們不知道一個 list 是不是 finite。然而這裡我們需要的只是特例：判斷 enumerate r 是不是 finite，而這可以從 r 的結構得知。

finite (Literal _) = True
finite Epsilon = True
finite Empty = True
finite (Union r s) = finite r && finite s
finite (Append r s) = finite r && finite s
finite (Kleene _) = False

當 finite r 或 finite s 有一個成立時，就把有窮的那一個 list 放在前面；如果兩個 lists 都是 infinite，我們就交替走訪這兩個 lists。如此便可達成 enumerability，讓每一個元素在有窮時間內出現。

enumerate (r `Union` s)
  | finite r  = enumerate r ++ enumerate s
  | finite s  = enumerate s ++ enumerate r
  | otherwise = alternate (enumerate r) (enumerate s)
  where alternate (x : xs) (y : ys) = x : y : alternate xs ys

或者其實可以直接交替走訪，如果有一個 list 耗盡了就接另一個 list 的剩餘部份。亦即

enumerate (r `Union` s) = alternate (enumerate r) (enumerate s)
  where alternate (x : xs) (y : ys) = x : y : alternate xs ys
        alternate xs [] = xs
        alternate [] ys = ys

最後一個情況是 r `Append` s。初步嘗試是直接算 enumerate r 和 enumerate s 的 "Cartesian product"

enumerate (r `Append` s) = [xs ++ ys | xs <- enumerate r, ys <- enumerate s]

然而這一樣會使得原本是 recursively enumerable 的集合無法成功列舉。List comprehension 會先從 enumerate r 拿第一個元素出來、稱之為 xs，然後對於 enumerate s 的每個元素 ys 計算 xs ++ ys。如果 enumerate s 是無窮的，我們就永遠無法前進到 enumerate r 的第二個元素（如果有的話）。

把 enumerate r 和 enumerate s 視為兩個座標軸，我們的目標是讓平面上的任一點在有窮時間內出現。這正是有理數的列舉方式，即「有理數集可數」證明的核心。然而這樣的 traversal 在 Haskell 該怎麼寫呢？

觀察下面這張示意圖

走訪順序是紅、橙、黃、綠，一路往外。這些路線對於座標軸的投影就是我們觀察一個 list 的順序。因此觀察 [1..] 這個 list 的順序是

[1,1,2,1,2,3,1,2,3,4,...]

觀察 ['A'..] 這個 list 的順序則是

['A','B','A','C','B','A','D','C','B','A',...]

用 zip 把這兩個 lists 拉在一起就是我們要的 enumeration。如果兩個 lists 都是 infinite lists，這兩個觀察順序就很單純。對於一個 list xs，第一種觀察順序可以寫成

concat $ map (flip take xs) [1..]

第二種則可以寫成

concat $ map (reverse . flip take xs) [1..]

或是用 unfoldr 寫得（似乎）更有效率一點

concat $ unfoldr f (xs, [])
  where f (y : ys, zs) = Just (y : zs, (ys, y : zs))

對於 finite lists，這兩個觀察順序就比較麻煩，特別是當兩個 lists 都有窮的時候。但只要有一個 finite list，我們就可以把它放在內層迴圈而輕鬆達成 enumerability。所以整個 r `Append` s 的情況就寫成

enumerate (r `Append` s)
  | finite s  = [xs ++ ys | xs <- enumerate r, ys <- enumerate s]
  | finite r  = [xs ++ ys | ys <- enumerate s, xs <- enumerate r]
  | otherwise = zigzag (enumerate r) (enumerate s)
  where zigzag xs ys = zipWith (++) (concat $ map (flip take xs) [1..])
                                    (concat $ unfoldr f (ys, []))
        f (y : ys, zs) = Just (y : zs, (ys, y : zs))

至此便完成 enumerate 的定義。

Matching via Enumeration

有了 enumerate，我們可以定義另一個 match' function：

match' r xs = xs `elem` enumerate r

因為我們剛剛確保 enumerate r 確實列出 r 對應的集合，所以當 xs 匹配 r 時，match' r xs 一定會停。然而當 xs 不匹配 r 而且 enumerate r 是 infinite 時，match' r xs 就不會停了。因此 match' 只證明了 regular expression matching problem 是 semidecidable（只有答案是「對」的時候才保證會停），要證明 decidability 必須靠原本的 match。

--
好長的一篇通識文（花了四小時多）XD。

---

習題 上面說 match 證明了 regex matching problem 是 decidable，其實是錯的。請給一個反例使 match 不會終止。如何加以修改使 match 遇到每種輸入都終止呢？enumerate 有類似的問題嗎？

--
沒有人抓包，只好自己動手 XD。