Почему не были введены новые языки, основанные на языках SSReflect?

Есть два соглашения, которые я нашел в расширении Coq SSReflect, которые кажутся особенно полезными, но которые я не видел широко принятыми на более новых языках с зависимым от языка (Lean, Agda, Idris).

Во-первых, где возможные предикаты выражаются как функции логического возврата, а не индуктивно определенные типы данных. Это придает разрешимость по умолчанию, открывает больше возможностей для доказательства путем вычислений и улучшает проверку производительности, избегая необходимости в том, чтобы механизм проверки соответствия выполнял большие условия доказательства. Основным недостатком, который я вижу, является необходимость использования рефлексивных лемм для управления этими булевыми предикатами при доказательстве.

Во-вторых, типы данных с инвариантами определяются как зависимые записи, содержащие простой тип данных плюс доказательство инварианта. Например, последовательности фиксированной длины определены в SSR, например:

Structure tuple_of : Type := Tuple {tval :> seq T; _ : size tval == n}.

seq и доказательство того, что длина этой последовательности является определенным значением. Это противоречит тому, как, например, Idris определяет этот тип:

data Vect : (len : Nat) -> (elem : Type) -> Type

Зависимая типизированная структура данных, в которой инвариант является частью его типа. Одно из преимуществ подхода SSReflect заключается в том, что он позволяет повторно использовать, так что, например, многие функции, определенные для seq и доказательства о них, все еще могут использоваться с tuple (работая в базовом seq), тогда как с помощью функций подхода Idris, таких как reverse, append и т.п. необходимо переписать для Vect. Lean на самом деле имеет эквивалент стиля SSReflect в своей стандартной библиотеке, vector, но также имеет array стиля Idris, который, похоже, имеет оптимизированную реализацию во время выполнения.

Одна книга, ориентированная на SSRelect, даже утверждает, что подход Vect n A style является антипаттерном:

Общим анти-шаблоном в языках с зависимой типизацией и Coq, в частности, является кодирование таких алгебраических свойств в определения самих типов данных и самих функций (канонический пример такого подхода - индексы с индексированием по длине). Хотя этот подход выглядит привлекательным, поскольку он демонстрирует силу зависимых типов для захвата определенных свойств типов данных и функций на них, он по своей сути не масштабируется, так как всегда будет другое интересное свойство, которое не было предусмотрено дизайнером типа/функции, поэтому в любом случае он должен быть закодирован как внешний факт. Вот почему мы защищаем подход, в котором типы данных и функции определяются как близкие к тому, как они будут определены программистом, насколько это возможно, и все необходимые их свойства доказаны отдельно.

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

Ответ 1

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

Вам не нужно переносить большие термины, как описано в тесте Эдвина Брэди под названием "принудительная оптимизация". У Agda есть принуждение, которое влияет на проверку типа (особенно, как вычисляются вселенные), но я не уверен, что материал, используемый только во время проверки типа, действительно стирается до времени выполнения. Во всяком случае, у Агды есть два понятия неуместности:. .(eq: p ≡ q) - обычная нерелевантность (что означает, что eq имеет значения во время проверки типа, поэтому оно по определению равно любому другому члену такого типа) и ..(x: A) - несоответствие позвоночника (не уверен, что это правильный термин. Я думаю, что источники Агда называют такую вещь "нестрогой неуместностью"), что буквально для уничтожения вычислительно-нерелевантных, но не совершенно несущественных терминов. Таким образом, вы можете определить

data Vec {α} (A : Set α) : ..(n : ℕ) -> Set α where
  [] : Vec A 0
  _∷_ : ∀ ..{n} -> A -> Vec A n -> Vec A (suc n)

и n будет стерта до времени выполнения. Или, по крайней мере, это похоже на то, что это было трудно, потому что у Agda много плохо документированных функций.

И вы можете написать эти доказательства нулевой стоимости в Coq, только потому, что он тоже реализует неуместность для вещей, которые живут в Prop. Но неуместность встроена в теорию Кока очень глубоко, в то время как в Агда это отдельная особенность, поэтому совершенно понятно, почему люди находят использование несоответствия в Коке более легко, чем в Агда.

Одно из преимуществ подхода SSReflect заключается в том, что он позволяет повторно использовать, так что, например, многие функции, определенные для seq и доказательства о них, все еще могут использоваться с tuple (работая в базовом seq), тогда как с помощью функций подхода Idris, таких как reverse, append и т.п. необходимо переписать для Vect.

Это не настоящее повторное использование, если вам все равно нужно доказывать свойства, и эти доказательства имеют такую же сложность, как и функции, определенные по индексированным данным. Также неудобно выполнять работу механизма унификации и передавать конкретные доказательства и применять леммы для получения length xs ≡ n из suc (length xs) ≡ n (а также sym, trans, subst и всех других лемм, которые могут быть унифицированы избавить вас от многих случаев). Более того, вы теряете определенную ясность, злоупотребляя пропозициональным равенством: имея xs: List A; length xs ≡ n + m xs: List A; length xs ≡ n + m вместо xs: Vec A (n + m) не улучшает читаемость ваших контекстов, особенно если они огромны, что часто бывает. И есть еще одна проблема: иногда сложнее определить функцию с использованием подхода SSReflect: вы упомянули reverse для Vect, я призываю вас определить эту функцию с нуля (с reverse для List как "повторно используемая" часть под капотом), а затем сравните свое решение с определением в Data.Vec из стандартной библиотеки Agda. И если у вас нет нерелевантности для предложений по умолчанию (что имеет место для Agda), тогда вам также нужно будет доказать свойства доказательств, если вы хотите доказать, скажем, reverse (reverse xs) ≡ xs которое много нетривиального шаблона.

Поэтому подход SSReflect не идеален. Другой тоже. Есть ли что-то, что улучшает оба? Да, Орнаменты (см. Декоративные Алгебры, Алгебраические Украшения и Сущность орнаментов). Вы можете легко получить Vec из List, применив соответствующую декоративную алгебру, но я не могу сказать, сколько повторного использования кода вы получите от него, и будут ли типы вас заводить или нет. Я слышал, что люди на самом деле используют украшения где-то.

Не значит, что у нас есть идеальное решение SSRelect, а другие отказываются его принять. Есть только надежда на более подходящий способ получить реальное повторное использование кода.

ОБНОВИТЬ

Антон Трунов в своем комментарии заставил меня понять, что я немного слишком Agda нрава и люди в Coq есть тактика, которая может упростить доказательствам много, так что доказать в Coq, как правило, легче (если у вас есть оружие, как crush от CPDT книги), чем определяющих функции над данными. Ну, тогда, я думаю, доказательство неуместности по умолчанию и тяжелая техника тактики делает подход SSReflect эффективным в Coq.

Ответ 2

Я могу представить некоторые мысли по первому вопросу (определение предикатов в виде функций, возвращающих логические значения). Моя самая большая проблема с этим подходом заключается в следующем: тогда по определению невозможно, чтобы функция имела ошибки, даже если выясняется, что она вычисляет не то, что вы намеревались ее вычислить. Во многих случаях это также заслоняет то, что вы на самом деле подразумеваете под предикатом, если вам нужно включить детали реализации процедуры решения для предиката в ее определении.

В математических приложениях также будут проблемы, если вы хотите определить предикат, который является специализацией чего-то, что не разрешимо вообще, даже если оно может быть разрешимым в вашем конкретном случае. Одним из примеров того, о чем я говорю здесь, будет определение группы с данной презентацией: в Coq общий способ определить это будет тотедоид с базовым множеством, являющимся формальными выражениями в генераторах, и равенством, заданным словом эквивалентность". В общем, это отношение не разрешимо, хотя во многих конкретных случаях оно есть. Однако, если вы ограничены определением групп с презентациями, где проблема слова разрешима, вы теряете способность определять объединяющую концепцию, которая объединяет все разные примеры вместе и доказывает общее представление о конечных представлениях или о конечно определенных группах. С другой стороны, определение отношения эквивалентности слов как абстрактного Prop или эквивалента является простым (если возможно, немного длинным).

Лично я предпочитаю сначала дать наиболее прозрачное возможное определение предиката, а затем, когда это возможно, предоставить процедуры принятия (функции, возвращающие значения типа {P} + {~P} являются моими предпочтениями здесь, хотя функции логического возврата будут работать тоже хорошо). Механизм класса Coq может обеспечить удобный способ регистрации таких процедур принятия решений; например:

Class Decision (P : Prop) : Set :=
decide : {P} + {~P}.
Arguments decide P [Decision].

Instance True_dec : Decision True := left _ I.
Instance and_dec (P Q : Prop) '{Decision P} '{Decision Q} :
  Decision (P /\ Q) := ...

(* Recap standard library definition of Forall *)
Inductive Forall {A : Type} (P : A->Prop) : list A -> Prop :=
| Forall_nil : Forall P nil
| Forall_cons : forall h t, P h -> Forall P t -> Forall P (cons h t).
(* Or, if you prefer:
Fixpoint Forall {A : Type} (P : A->Prop) (l : list A) : Prop :=
match l with
| nil => True
| cons h t => P h /\ Forall P t
end. *)

Program Fixpoint Forall_dec {A : Type} (P : A->Prop)
  '{forall x:A, Decision (P x)} (l : list A) :
  Decision (Forall P l) :=
  match l with
  | nil => left _ _
  | cons h t => if decide (P h) then
                  if Forall_dec P t then
                    left _ _
                  else
                    right _ _
                else
                  right _ _
  end.
(* resolve obligations here *)
Existing Instance Forall_dec.