¿Por qué Coq incluye expresiones let en su lenguaje principal?

9

Coq incluye expresiones let en su lenguaje principal. Podemos traducir expresiones let a aplicaciones como esta: let x : t = v in b ~> (\(x:t). b) v entiendo que esto no siempre funciona porque el valor vno estaría disponible cuando se verifica la escritura b. Sin embargo, esto se puede solucionar fácilmente mediante una carcasa especial para la verificación de tipos de aplicaciones del formulario (\(x:t). b) v. Esto nos permite eliminar expresiones let a costa de un caso especial mientras se realiza la verificación de tipos. ¿Por qué Coq include todavía incluye expresiones let? ¿Tienen otras ventajas (además de no necesitar el caso especial)?

Labbekak
fuente
44
Su sugerencia suena como agregar un truco para evitar la necesidad de letexpresiones, pero a) no hay razón para evitar letexpresiones y también son convenientes, yb) agregar trucos a su lenguaje principal no es una gran idea.
Derek Elkins salió del SE

Respuestas:

23

Es un error común pensar que podemos traducir let-expresiones a aplicaciones. La diferencia entre let x : t := b in vy (fun x : t => v) bes que en la letexpresión-, durante la verificación de tipo de vsabemos que xes igual a b, pero en la aplicación no lo hacemos (la subexpresión fun x : t => vtiene que tener sentido por sí misma).

Aquí hay un ejemplo:

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

Su sugerencia para hacer de la aplicación (fun x : t => v) bun caso especial realmente no funciona. Pensemos en ello con más cuidado.

Por ejemplo, ¿cómo lidiarías con esto, continuando con el ejemplo anterior?

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

Presumiblemente, esto no funcionará porque ano se puede escribir, pero si desarrollamos su definición, obtenemos una expresión bien escrita. ¿Crees que los usuarios nos amarán u odiarán por nuestra decisión de diseño?

e₁ e₂e₁λ

También rompería el teorema fundamental que dice que cada subexpresión de una expresión bien tipada está bien tipada. Eso es tan sensato como introducirse nullen Java.

Andrej Bauer
fuente