Почему Coq включает выражения let в основной язык

9

Coq включает в себя выражения let на своем основном языке. Мы можем переводить выражения let в приложения, подобные этому: let x : t = v in b ~> (\(x:t). b) v я понимаю, что это не всегда работает, потому что значение vне будет доступно при проверке типов b. Однако это можно легко исправить с помощью специального корпуса проверки типов приложений формы (\(x:t). b) v. Это позволяет нам удалять выражения let за счет особого случая при проверке типов. Почему Coq include все еще включает выражения let? Есть ли у них другие преимущества (кроме необходимости в особом случае)?

Labbekak
источник
4
Ваше предложение звучит как добавление хака, чтобы избежать необходимости в letвыражениях, но а) нет причин избегать letвыражений, и они также удобны, и б) добавление хаков в ваш основной язык не очень хорошая идея.
Дерек Элкинс покинул SE

Ответы:

23

Это распространенное заблуждение, что мы можем переводить letвыражения-приложения. Разница между let x : t := b in vи (fun x : t => v) bзаключается в том let, что в выражении -ex во время проверки типа vмы знаем, что xоно равно b, но в приложении мы этого не делаем (подвыражение fun x : t => vдолжно иметь смысл само по себе).

Вот пример:

(* Dependent type of vectors. *)
Inductive Vector {A : Type} : nat -> Type :=
  | nil : Vector 0
  | cons : forall n, A -> Vector n -> Vector (S n).

(* This works. *)
Check (let n := 0 in cons n 42 nil).

(* This fails. *)
Check ((fun (n : nat) => cons n 42 nil) 0).

Ваше предложение сделать заявку (fun x : t => v) bспециальным случаем не работает. Давайте подумаем об этом более тщательно.

Например, как бы вы справились с этим, продолжая приведенный выше пример?

Definition a := (fun (n : nat) => cons n 42 nil).
Check a 0.

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

Вы должны тщательно продумать, что значит иметь «особый случай». Если у меня есть приложение e₁ e₂, нужно ли нормализовать его, e₁прежде чем я решу, является ли это -abstraction? Если да, это означает, что я буду нормализовать плохо напечатанные выражения, и они могут циклически повторяться. Если нет, удобство использования вашего предложения кажется сомнительным.λ

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

Андрей Бауэр
источник