2008/08/03

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. RS 是 regular expressions,則 R ∪ S 也是個 regular expression;
  5. RS 是 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 分割成兩段 yszs(使得 xs = ys ++ zs),而且 yszs 分別和 rs 成功匹配,但我們不知道該怎麼分割。幸好有個簡單的做法:試過每種可能的分割就行了。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 xsTruexs 在集合 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 rfinite 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 renumerate 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 renumerate 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。

Labels: ,

<< 回到主頁