Por que a Coq inclui expressões let em sua linguagem principal

9

Coq inclui let-expression em sua linguagem principal. Podemos traduzir expressões let para aplicativos como este: let x : t = v in b ~> (\(x:t). b) v Entendo que isso nem sempre funciona porque o valor vnão estaria disponível ao digitar b. No entanto, isso pode ser facilmente corrigido através de um revestimento especial na verificação de tipos de aplicativos do formulário (\(x:t). b) v. Isso nos permite remover expressões let ao custo de um caso especial durante a digitação. Por que Coq include ainda inclui let-expression? Eles têm outras vantagens (além de não precisar do caso especial)?

Labbekak
fonte
4
Sua sugestão parece adicionar um hack para evitar a necessidade de letexpressões, mas não há motivo para evitar letexpressões e elas também são convenientes eb) adicionar hacks à sua linguagem principal não é uma boa idéia.
Derek Elkins saiu de SE

Respostas:

23

É um equívoco comum que possamos converter letexpressões -ex em aplicativos. A diferença entre let x : t := b in ve (fun x : t => v) bé que na letexpressão-, durante a verificação de tipo v, sabemos que xé igual a b, mas na aplicação, não (a subexpressão fun x : t => vdeve fazer sentido por si só).

Aqui está um exemplo:

(* 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).

Sua sugestão para tornar a aplicação (fun x : t => v) bum caso especial não funciona realmente. Vamos pensar sobre isso com mais cuidado.

Por exemplo, como você lidaria com isso, continuando o exemplo acima?

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

Presumivelmente, isso não funcionará porque anão pode ser digitado, mas se desdobrarmos sua definição, obteremos uma expressão bem digitada. Você acha que os usuários vão nos amar ou nos odiar por nossa decisão de design?

e₁ e₂e₁λ

Você também quebraria o teorema fundamental que diz que toda sub-expressão de uma expressão bem digitada é bem digitada. Isso é tão sensato quanto a introdução nullao Java.

Andrej Bauer
fonte