Почему нельзя сделать вывод, что 0+n=n в этой зависимо типизированной программе?

Я начинаю использовать Coq, и я хотел бы определить некоторые типизированные программы. Учтите следующее:

Inductive natlist : nat -> Type :=
  | natnil : natlist 0
  | natcons : forall k, nat -> natlist k -> natlist (S k).

Fixpoint natappend (n:nat) (l1: natlist n) (m:nat) (l2: natlist m) : natlist (n+m) :=
  match l1 with
    | natnil => l2
    | natcons _ x rest => natcons (n+m) x (natappend rest l2)
  end.

Так natlist k будет список natс длины k, Проблема с определением конкатенации как natappend это следующая ошибка:

Ошибка:
В среде
natappend: для всех: nat,
            natlist n ->
            по всей массе:
            natlist m -> natlist (n + m)
n: nat
l1: natlist n
м: нат
l2: natlist m
Термин "l2" имеет тип "natlist m"
в то время как ожидается, что будет иметь тип
 msgstr "natlist (?n@{n1:=0} + m)".

Как вы можете видеть, у него есть проблема с предложением:

| natnil => l2

потому что он утверждает, что тип l2 является natlist m в то время как тип результата должен быть natlist (n+m) = natlist (0+m),

Я знаю, что Coq не может разрешать произвольные выражения на уровне типов, чтобы избежать бесконечных вычислений, но я нахожу странным, что даже этот простой случай не обрабатывается.

Я использую CoqIDE на Linux, версия:

The Coq Proof Assistant, version 8.5 (February 2016)
  compiled on Feb 22 2016 18:19:5 with OCaml 4.02.2

Я видел живые классы, использующие версию MacOSX с кодом, подобным приведенному выше, который скомпилирован в IDE без этой ошибки, поэтому я немного озадачен.

Есть ли какие-то настройки, которые я должен установить, чтобы включить больше вывода типов и разрешить код, как указано выше? В качестве альтернативы: как я могу написать зависимый типизированный код, который не зависит от вывода типа?

Источник

2 ответа

Решение

Проблема в том, что у вас была ошибка типа во второй ветке. Вот версия, которая работает:

Fixpoint natappend {n m:nat} (l1 : natlist n) (l2 : natlist m) : natlist (n + m) :=
  match l1 with
  | natnil => l2
  | natcons n' x rest => natcons (n' + m) x (natappend rest l2)
  end.

Принципиальным отличием этой версии от оригинальной является параметр, передаваемый natcons: вот n' + mтогда как раньше n + m,

Этот пример очень хорошо иллюстрирует общую проблему с нелокальностью сообщений об ошибках в Coq, особенно при написании зависимых программ. Хотя Coq жаловался на первую ветку, проблема была на самом деле во второй ветви. Добавление аннотаций в ваш match Заявление, как предлагает @jbapple, может быть полезно при попытке диагностировать, что происходит не так.

Источник

Тебе нужно match ... as ... in ... return ... делать более сложные типы аннотаций. См. Главу Адама Члипалы "Библиотека MoreDep" в его книге "Сертифицированное программирование с зависимыми типами" или "Глава 17: Расширенное сопоставление с образцом" в руководстве Coq. У обоих есть concat пример, над которым вы работаете.

Вы также можете просто задержать бит зависимого типа до конца:

Definition natlist n := { x : list nat & n = length x }.

Затем докажите, что тип не зависит concat сохраняет суммы длин.

Источник
Другие вопросы по тегам