Pourquoi Coq inclut des let-expressions dans son langage principal

9

Coq inclut des let-expressions dans son langage principal. Nous pouvons traduire des expressions let dans des applications comme celle-ci: let x : t = v in b ~> (\(x:t). b) v je comprends que cela ne fonctionne pas toujours car la valeur vne serait pas disponible lors de la vérification de frappe b. Cependant, cela peut être facilement résolu par un boîtier spécial pour la vérification typographique des applications du formulaire (\(x:t). b) v. Cela nous permet de supprimer les expressions let au prix d'un cas spécial lors de la vérification de la typographie. Pourquoi Coq comprend-il toujours des let-expressions? Ont-ils d'autres avantages (en plus de ne pas avoir besoin du cas spécial)?

Labbekak
la source
4
Votre suggestion ressemble à l'ajout d'un hack pour éviter d'avoir besoin d' letexpressions, mais il n'y a pas de raison d'éviter les letexpressions et elles sont également pratiques, et b) l'ajout de hacks à votre langage de base n'est pas une bonne idée.
Derek Elkins a quitté le SE

Réponses:

23

C'est une idée fausse commune que nous pouvons traduire let-expresions en applications. La différence entre let x : t := b in vet (fun x : t => v) best que dans l' letexpression-, pendant la vérification de type de vnous savons que xest égal à b, mais dans l'application nous ne le faisons pas (la sous-expression fun x : t => vdoit avoir un sens par elle-même).

Voici un exemple:

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

Votre suggestion de faire de l'application (fun x : t => v) bun cas spécial ne fonctionne pas vraiment. Réfléchissons-y plus attentivement.

Par exemple, comment traiteriez-vous cela, en continuant l'exemple ci-dessus?

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

Vraisemblablement, cela ne fonctionnera pas car ane peut pas être tapé, mais si nous déplions sa définition, nous obtenons une expression bien typée. Pensez-vous que les utilisateurs vont nous aimer ou nous détester pour notre décision de conception?

Vous devez réfléchir soigneusement à ce que signifie avoir le "cas spécial". Si j'ai une application e₁ e₂, dois-je normaliser e₁avant de décider s'il s'agit d'une -abstraction? Si oui, cela signifie que je normaliserai les expressions mal typées, et celles-ci pourraient tourner. Si non, l'utilisabilité de votre proposition semble discutable.λ

Vous briseriez également le théorème fondamental qui dit que chaque sous-expression d'une expression bien typée est bien typée. C'est aussi sensé que d'introduire nulldans Java.

Andrej Bauer
la source