我怎样才能让 Coq 相信我的函数实际上是递归的？

Question

我正在尝试用 Coq 编写一个程序来解析相对简单的上下文无关语法（一种括号），我的通用算法是让解析器潜在地 return 字符串的其余部分.例如，解析 "++]>><<" 应该 return CBTerminated [Incr Incr] ">><<" 然后，假设正在解析“[++]>><<”的解析器将能够获取“>>” <" 并继续。

很明显，字符串变小了，但让 Coq 相信这是另一回事。它给我错误

Recursive definition of parseHelper is ill-formed. [...] Recursive call to parseHelper has principal argument equal to "rest'" instead of "rest".

我认为这意味着它不相信 rest' < input 就像它相信 rest < input 一样。（其中 < 表示 "is smaller than"）。

我曾想过 return计算要跳过的字符数，但这似乎相当不雅且不必要。

Require Import Coq.Strings.String.
Require Import Coq.Strings.Ascii.
Require Import Coq.Lists.List.
Require Import ZArith.

Open Scope char_scope.
Open Scope list_scope.

Notation " [ ] " := nil (format "[ ]") : list_scope.
Notation " [ x ] " := (cons x nil) : list_scope.
Notation " [ x ; y ; .. ; z ] " := (cons x (cons y .. (cons z nil) ..)) : list_scope.

Inductive BF :=
    | Incr : BF
    | Decr : BF
    | Left : BF
    | Right : BF
    | In : BF
    | Out : BF
    | Sequence : list BF -> BF
    | While : BF -> BF.

Inductive BF_Parse_Result :=
    | UnmatchedOpen
    | EOFTerminated (u : list BF)
    | CBTerminated (u : list BF) (rest : string).

Definition bind (val : BF) (onto : BF_Parse_Result) :=
    match onto with
        | UnmatchedOpen => UnmatchedOpen
        | EOFTerminated values => EOFTerminated (cons val values)
        | CBTerminated values rest => CBTerminated (cons val values) rest
    end.

Fixpoint parseHelper (input : string) : BF_Parse_Result :=
    match input with
        | EmptyString => EOFTerminated nil
        | String first rest =>
             match first with
                 | "+" => bind Incr (parseHelper rest)
                 | "-" => bind Decr (parseHelper rest)
                 | "<" => bind Left (parseHelper rest)
                 | ">" => bind Right (parseHelper rest)
                 | "," => bind In (parseHelper rest)
                 | "." => bind Out (parseHelper rest)
                 | "]" => CBTerminated nil rest
                 | "[" =>
                     match parseHelper rest with
                         | UnmatchedOpen => UnmatchedOpen
                         | EOFTerminated _ => UnmatchedOpen
                         | CBTerminated vals rest' =>
                             bind (While (Sequence vals)) (parseHelper rest')
                     end
                 | _ => parseHelper rest
             end
    end.

Answer 1

您是否考虑过使用 well-founded recursion? Coq's standard library has a series of useful combinators for defining functions over well-founded relations. Reference 1 展示了两种用于一般递归的技术（有根据的递归和 monad）。

其他在 Agda 上下文中也非常有用的技术，就是所谓的 Bove-Capretta method，它定义了一个模仿已定义函数调用图的归纳谓词。

Coq 还有 Function 命令可以用来定义更通用的递归函数。每当我需要定义非结构递归函数时，我都会使用有根据的递归。

希望对您有所帮助。

我怎样才能让 Coq 相信我的函数实际上是递归的？

How can I convince Coq that my function is in fact recursive?

recursion

termination

coq