使用补码操作形式化正则表达式

Question

我正在玩 Idris 中经过认证的正则表达式匹配器的形式化（我相信同样的问题存在于任何基于类型理论的证明助手中，例如 Agda 和 Coq）并且我一直在研究如何定义补码操作的语义。我有以下数据类型来表示正则表达式的语义：

data InRegExp : List Char -> RegExp -> Type where
 InEps : InRegExp [] Eps
 InChr : InRegExp [ a ] (Chr a)
 InCat : InRegExp xs l ->
         InRegExp ys r ->
         zs = xs ++ ys ->
         InRegExp zs (Cat l r)
 InAltL : InRegExp xs l ->
          InRegExp xs (Alt l r)
 InAltR : InRegExp xs r ->
          InRegExp xs (Alt l r)
 InStar : InRegExp xs (Alt Eps (Cat e (Star e))) ->
          InRegExp xs (Star e)
 InComp : Not (InRegExp xs e) -> InRegExp xs (Comp e)

我的问题是表示 InComp 构造函数的类型，因为由于 Not 的使用，它出现了 InRegExp 的非严格正数。由于此类数据类型可用于定义非终止函数，因此它们会被终止检查器拒绝。我想以 Idris 终止检查器接受的方式定义这种语义。

有没有什么方法可以表示补运算的语义而不出现负数 InRegExp？

Answer 1

你们可以相互定义 NotInRegExp 这将解释正则表达式无法识别的含义（我还没有检查这是否是有效语法）。

data NotInRegExp : List Char -> RegExp -> Type where
 NotInEps : Not (xs = []) -> NotInRegExp xs Eps
 NotInChr : Not (xs = [ a ]) -> NotInRegExp xs (Chr a)
 NotInCat : (forall xs ys, zs = xs ++ ys ->
             NotInRegExp xs l
            + InRegExp xs l * NotInRegExp ys r) ->
            NotInRegExp zs (Cat l r)
etc...

然后您应该能够定义一个很好的决策程序：

check : (xs : List Char) (e : RegExp) -> Either (InRegexp xs e) (NotInRegexp xs e)

Answer 2

您还可以通过对 RegExp 的递归加上一些用于 Star 语义的归纳数据类型来定义此类型。

我想它不会与内置模式匹配很好地交互，但它具有相同的归纳原理。

Answer 3

您可以通过对 Regex 的递归来定义 InRegex。在那种情况下，严格的积极性是没有问题的，但我们必须在结构上递归：

import Data.List.Quantifiers

data Regex : Type where
  Chr  : Char -> Regex
  Eps  : Regex
  Cat  : Regex -> Regex -> Regex
  Alt  : Regex -> Regex -> Regex
  Star : Regex -> Regex
  Comp : Regex -> Regex

InRegex : List Char -> Regex -> Type
InRegex xs (Chr x)     = xs = x :: []
InRegex xs Eps         = xs = []
InRegex xs (Cat r1 r2) = (ys ** (zs ** (xs = ys ++ zs, InRegex ys r1, InRegex zs r2)))
InRegex xs (Alt r1 r2) = Either (InRegex xs r1) (InRegex xs r2)
InRegex xs (Star r)    = (yss ** (All (\ys => InRegex ys r) yss, xs = concat yss))
InRegex xs (Comp r)    = Not (InRegex xs r)

如果我们想使用我们的旧定义，我们将需要一个用于 Star 情况的归纳类型。以下显然不起作用：

InRegex xs (Star r) = InRegex (Alt Eps (Cat r (Star r)))

然而，我们可以简单地改变定义并使有限性显式化：

InRegex xs (Star r) = (yss ** (All (\ys => InRegex ys r) yss, xs = concat yss))

这具有预期的含义，我看不出有任何缺点。

使用补码操作形式化正则表达式

Formalising regular expressions with a complement operation

regex

coq

agda

idris